Queste flashcard non sono ancora salvate — spariranno se lasci la pagina. Crea un account gratuito per conservarle e sbloccare tutto quello qui sotto.
What is the raw material of computation and communication?
Information
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are sets used for in programming?
To define types of objects
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a set?
A collection of objects without order or repetition
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the objects in a set called?
Elements or members
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can a set be specified?
By a comma-separated list between curly braces
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the symbol for the empty set?
Ø
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Give an example of a set with characters.
{Harry, Ginny, Hermione, Ron, Hagrid}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Give an example of a set with numbers.
{42, -273.15, 1729, 10100}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the significance of sets in programming languages?
They underlie any notion of type
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the symbol ∈ represent in set theory?
It indicates that an object is an element of a set. For example, CSIRAC ∈ {Manchester Baby, EDSAC, CSIRAC}.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the symbol ∉ represent in set theory?
It indicates that an object does not belong to a set. For example, SILLIAC ∉ {Manchester Baby, EDSAC, CSIRAC}.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can we specify a set succinctly when it has many elements?
By giving a condition that the elements must satisfy. For example, {x:x is even} represents all even numbers.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the notation {x:x is even} mean?
It represents the set of all x such that x is even.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Can the order of elements in a set affect its identity?
No, different orders do not affect the identity of the set. For example, {CSIRAC, Manchester Baby, EDSAC} = {Manchester Baby, EDSAC, CSIRAC}.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the importance of the colon : in set notation?
It separates the variable from the condition that must be satisfied for membership in the set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an example of a set that is defined by a condition?
{n:n is even} is a set defined by the condition that n is even.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the general form of set definitions?
{name : condition}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can the set of even integers be expressed?
{x ∈ Z : x is even}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the notation {x ∈ Z : x is even} mean?
The set of x in Z such that x is even.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an alternative way to specify a set?
By giving a rule for constructing each member.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can the set of even integers be expressed using a rule?
{2n : n ∈ Z}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does {2n : n ∈ Z} represent?
The set of 2n such that n is an integer.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is necessary for the condition in a set definition?
It must be precise and clear.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the cardinality of a set?
The cardinality of a set is the number of elements it contains, denoted by |A| or #A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How is the cardinality of a set determined?
By counting the number of elements listed in the set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the cardinality of the set {Harry, Ginny, Hermione, Ron, Hagrid}?
5
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the cardinality of the set {42, -273.15, 1729, 10100}?
4
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the cardinality of the set {CSIRAC, Manchester Baby, EDSAC}?
3
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the cardinality of the empty set {}?
0
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why is determining the cardinality important in computer science?
It helps determine the efficiency of algorithms and storage requirements.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a common practice when describing large sets informally?
Listing a few elements and using '...' to imply continuation.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a potential risk of defining sets using English text?
Imprecision in the definition of the set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the symbol Ø represent?
The empty set
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the set of positive integers denoted by?
N
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does Z represent in sets of numbers?
The set of all integers
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the set of rational numbers denoted by?
Q
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the set of real numbers denoted by?
R
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does Z+ denote?
The set of positive integers (N)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the notation for a closed interval?
[a,b]
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does [a,b) represent?
A half-open half-closed interval
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does (a,b) represent?
An open interval
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do you denote integers within an interval [a,b]?
[a,b]z
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a set of allowed characters called?
Alphabet
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an example of a finite alphabet?
The 26-letter English alphabet {a, b, c, ..., y, z}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a string over an alphabet?
A finite sequence of characters from that alphabet.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the length of the string 'babbage'?
7
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What symbol represents the empty string?
e (epsilon)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A^k denote?
All the strings of exactly k characters from alphabet A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the set A°?
The set containing just the empty string: A° = {ε}.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many strings of length k over an alphabet A are there?
|A|^k
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is |A¹| equal to?
|A| (the number of letters in the alphabet)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
If A = {0,1}, what is A³?
{000, 001, 010, 011, 100, 101, 110, 111}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the number of strings of length k over an alphabet A?
\(|A^k| = |A|^k\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A* represent in set theory?
The set of all finite strings over the alphabet A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an example of A* for A = {0,1}?
A* = {ε, 0, 1, 00, 01, 10, 11, ...}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A ⊆ B mean?
Every element of A is also an element of B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A ¢ B signify?
A is not a subset of B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How is the subset relation illustrated in a Venn diagram?
Set A is drawn entirely within set B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What logical implication does A ⊆ B represent?
If x ∈ A then x ∈ B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the notation for membership in a set?
x ∈ A means x is a member of set A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a proper subset?
A is a proper subset of B if A ⊆ B and A ≠ B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between the empty set and any set B?
The empty set Ø is a subset of every set B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A ⊂ B imply if A and B are finite?
A ⊂ B implies |A| ≤ |B|.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A ⊇ B mean?
A is a superset of B, meaning B is a subset of A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the implication of A ⊇ B?
Membership of B is implied by membership of A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the notation for a proper superset?
A is a proper superset of B is written as A ⊃ B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the definition of a subset?
A set A is a subset of B if every element of A is also an element of B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does it mean if two sets A and B are equal?
If A = B, then A ⊆ B and A ⊃ B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can you prove that two sets A and B are equal?
Prove that each is a subset of the other: A ⊆ B and B ⊆ A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the symbol ⇔ represent?
It represents that membership of A is equivalent to membership of B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does 'x ∈ A if and only if x ∈ B' imply?
Both conditions either hold or do not hold; they are equivalent.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a maximum clique?
A clique of maximum size; there is no larger clique.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a maximal clique?
A clique that is not a proper subset of any other clique.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A ⊆ B indicate?
Membership of A implies membership of B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A ⊃ B indicate?
Membership of B implies membership of A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do maximal and maximum cliques differ?
A maximal clique may be smaller than a maximum clique; all maximum cliques are maximal, but not vice versa.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a maximum subset?
A subset with the largest size among all subsets with a specific property.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a maximal subset?
A subset that cannot be enlarged without losing the property; it is not a proper subset of another subset with the same property.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the difference between minimum and minimal subsets?
A minimum subset has the smallest size; a minimal subset cannot be a proper superset of another subset with the property.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
In what context are maximum and maximal often treated as synonyms?
In the context of real numbers, the distinction is often unnecessary, and both terms can mean the same thing.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the total number of subsets of a finite set B with n elements?
\(|P(B)| = 2^n\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the power set of a set B?
The power set P(B) is the set of all subsets of B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How does the number of subsets grow as the size of the set increases?
It grows exponentially as the size of the set increases.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does it mean for two sets A and B to be incomparable?
A and B are incomparable if neither A ⊆ B nor B ⊆ A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the distinction between maximal and maximum?
Maximal refers to a property; maximum refers to the largest value with that property.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for calculating the number of choices for subsets of a set with n elements?
\(2^{|B|}\), where |B| is the number of elements in the set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens when making choices for elements of a set regarding subsets?
Choices are independent; one choice does not restrict others.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does n choose k represent?
The binomial coefficient \(\binom{n}{k}\) represents the number of ways to choose k elements from a set of n elements.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many subsets of size 0 can be formed from a set of size n?
There is exactly 1 way to choose 0 elements from a set of size n, which is to choose nothing.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the total number of subsets of a set of size n?
The total number of subsets is given by \(2^n\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a clique in social network analysis?
A clique is the largest set of people in a network where every person knows every other person.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a mutual stranger set?
A mutual stranger set is the largest set of people in a network where no one knows any other member of the set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between subsets and binomial coefficients?
The binomial coefficients count every subset of a set B exactly once, summing to \(2^n\) for all sizes k.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the significance of the power set in algorithm design?
The power set is used to analyze all possible subsets to find optimal solutions in problems like social network analysis.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the number of ways to choose all elements from a set of size n?
Only 1 way: choose all elements.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many options do we have when choosing 1 element from n elements?
We have n options.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the number of ways to choose n-1 elements from n elements?
We have n options (choosing one to exclude).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the symmetry observed in choosing subsets?
Choosing k elements to include is the same as choosing n-k elements to exclude.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the number of ways to choose k elements from n?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do we count the ways to choose k elements in order from n elements?
Use the formula: \(\(n(n-1)(n-2) imes...(n-k+1)\)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the factorial of n?
Defined as: \(\(n! = n(n-1)(n-2)...3 imes 2 imes 1\)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the number of ways to choose k elements in order?
\(\frac{n!}{(n-k)!}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many orderings are there for k elements chosen from a set?
\(k!\) ways to order the k elements
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between ordered and unordered choices of k elements?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the number of subsets of size k from n elements?
\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Which expression is more efficient for computation: \(\frac{n!}{(n-k)!}\) or \(\frac{n(n-1)(n-2)...(n-k+1)}{k!}\)?
\(\frac{n(n-1)(n-2)...(n-k+1)}{k!}\) is more efficient
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why is the order of operations important in computations?
It affects the accuracy of the result due to number size limitations
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a potential issue when computing large or small intermediate numbers?
It can affect the accuracy of the result
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the binomial coefficient for choosing 2 elements from n?
\(?inom{n}{2} = \frac{n(n-1)}{2}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can we count subsets of a given size recursively?
Divide subsets into those that include an element and those that don't.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
In the example with set B = {1,2,3,4,5}, how many 3-element subsets include element 1?
Count 2-element subsets from {2,3,4,5}: \(?inom{4}{2}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
In the example with set B = {1,2,3,4,5}, how many 3-element subsets do not include element 1?
Count 3-element subsets from {2,3,4,5}: \(?inom{4}{3}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the total number of 3-element subsets of a set of size 5?
It's given by \(?inom{5}{3}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do we express the total number of 3-element subsets?
Total = # subsets including 1 + # subsets not including 1
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the total number of 3-element subsets of set B?
It is calculated as the number of 3-element subsets that include 1 plus those that do not include 1.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do you calculate k-element subsets including a specific element b?
Choose k-1 elements from n-1 elements (those not including b). This can be done in \(?inom{n-1}{k-1}\) ways.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do you calculate k-element subsets not including a specific element b?
Choose k elements from n-1 elements (those not including b). This can be done in \(?inom{n-1}{k}\) ways.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the total number of k-element subsets?
The total is given by \(?inom{n}{k} = ?inom{n-1}{k-1} + ?inom{n-1}{k}\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the base cases for computing binomial coefficients?
The base cases are \(?inom{n}{0} = 1\) and \(?inom{n}{n} = 1\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How does the recursive method work for computing binomial coefficients?
It reduces the problem to simpler cases until reaching the base cases, ensuring the process stops.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does Pascal's triangle represent?
It represents binomial coefficients where each coefficient is the sum of the two coefficients directly above it.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the value of C(2, 1)?
The value is 2, calculated as \(?inom{2}{1} = 2\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the value of C(3, 1)?
The value is 3, calculated as \(?inom{3}{1} = 3\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the value of C(4, 2)?
The value is 6, calculated as \(?inom{4}{2} = 6\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the complement of a set A?
The complement of A, denoted by A', is the set of all elements of the universal set U that are not in A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does U/A represent?
U/A represents everything in the universal set U that is not in set A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
In the context of integers, what is the universal set?
The universal set can be the set Z of all integers.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the equation shown in Figure 1.2?
The equation is 10 = 4 + 6, where (2) = 10, (1) = 4, and (2) = 6 in Pascal's triangle.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are some examples of subsets of a universal set of integers?
Examples include even integers, odd integers, negative integers, and prime integers.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the universe of discourse?
The universe of discourse is the universal set that contains all elements under consideration.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the notation for the complement of A?
The complement of A can be denoted by A' or U/A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does A CU signify?
A CU signifies that A is a subset of the universal set U.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the size of set A when A and U are finite sets?
\(|A| = |U| - |A|\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the complement of A equal?
\(A^c = A\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the definition of the set difference B / A?
\(B \setminus A = \{ x \in B : x \notin A \}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
If A is a subset of B, what is the formula for the size of the set difference?
\(|B \setminus A| = |B| - |A|\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the union of two sets A and B?
\(A \cup B = \{x : x \in A \text{ or } x \in B\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the intersection of two sets A and B?
\(A \cap B = \{x : x \in A \text{ and } x \in B\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the notation A ⊆ B mean?
A is a subset of B
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the notation A ⊇ B mean?
A is a superset of B
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the condition for the size of the set difference |B \ A|?
It does not satisfy (1.9) unless A ⊆ B
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between subsets and supersets?
A ⊆ B ⇔ A ⊇ B
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the size of the union of two sets A and B?
\(|A| + |B| = |A \cup B| + |A \cap B|\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does it mean if two sets A and B are disjoint?
\(A \cap B = \emptyset\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the size of the disjoint union of two sets A and B?
\(|A \cup B| = |A| + |B|\) if \(A \cap B = \emptyset\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between the complement of the union of two sets and their complements?
\(\overline{A \cup B} = \overline{A} \cap \overline{B}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the result of counting elements in sets A and B?
Elements in both sets are counted twice.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the notation for the disjoint union of sets A and B?
\(A \sqcup B\) or \(A \oplus B\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the disjoint union of sets A and B?
Defined only when sets A and B are disjoint.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does Theorem 1 state about union and intersection?
\(A ?igcup B = A ?igcap B\) when x is in A or B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the complement of the intersection of two sets?
It is the union of their complements: \(A ?igcap B' = A' ?igcup B'\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are De Morgan's Laws for Sets?
They describe duality between union and intersection: \(A ?igcup B' = A' ?igcap B'\) and \(A ?igcap B' = A' ?igcup B'\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can we express Corollary 2 using Theorem 1?
\(A ?igcap B = A ?igcup B\) by using Theorem 1.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the result of A ∩ (B ∪ C)?
(A ∩ B) ∪ (A ∩ C)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the result of A ∪ (B ∩ C)?
(A ∪ B) ∩ (A ∪ C)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do union and intersection interact?
Union followed by intersection: A ∩ (B ∪ C). Intersection followed by union: A ∪ (B ∩ C).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is shown in Figure 1.8?
The relationship between A ∩ (B ∪ C) and (A ∩ B) ∪ (A ∩ C).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the symmetric difference of sets A and B?
\(A \Delta B = \{x : x \in A \text{ or } x \in B \text{ but not both}\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the first Distributive Law state about intersection and union?
Intersection distributes over union: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the second Distributive Law state about union and intersection?
Union distributes over intersection: \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for multiplication distributing over addition in numbers?
\(a \times (b + c) = (a \times b) + (a \times c)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Does addition distribute over multiplication?
No, generally \(a + (b \times c) \neq (a + b) \times (a + c)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the exclusive 'or' in the context of symmetric difference?
It means belonging to exactly one of the sets, excluding both.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the symmetric difference of sets A and B?
\(A \Delta B = (A/B) \cup (B/A)\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the result of the symmetric difference of a set with itself?
\(A \Delta A = \emptyset\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
When are two sets identical?
Two sets A and B are identical if and only if \(A \Delta B = \emptyset\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between the symmetric difference and complements?
\(A \Delta B = A^c \Delta B^c\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a Cartesian product?
An ordered pair (a, b) consists of two objects a and b together, in that order.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the Cartesian product of two sets A and B?
\(A \times B = \{(a,b): a \in A, b \in B\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
If A = {King, Queen, Jack} and B = {♣, ♡}, what is A × B?
\(A \times B = \{(King, \clubsuit), (King, \heartsuit), (Queen, \clubsuit), (Queen, \heartsuit), (Jack, \clubsuit), (Jack, \heartsuit)\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does R × R represent?
The set of all coordinates of points in the plane.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the size of the Cartesian product of two finite sets A and B?
\(|A \times B| = |A| \cdot |B|\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the Cartesian product of three sets A, B, and C?
\(A \times B \times C = \{(a,b,c): a \in A, b \in B, c \in C\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the general form of the Cartesian product for n sets A1, A2, ..., An?
\(A_1 \times A_2 \times \ldots \times A_n = \{(a_1,a_2,\ldots,a_n): a_i \in A_i\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the size of the Cartesian product of finite sets?
\(|A_1 \times A_2 \times \ldots \times A_n| = |A_1| \cdot |A_2| \cdots |A_n|\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can we express the Cartesian product of identical sets?
\(A^n\) indicates the Cartesian product of \(n\) identical sets.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the example of {0,1}³?
\(\{(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do we represent n-tuples as strings?
For binary alphabet {0,1}, \(\{0,1\}^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are R² and R³ in terms of Cartesian products?
\(R^2 = R \times R\) and \(R^3 = R \times R \times R\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the definition of a partition of a set A?
A partition is a set of disjoint nonempty subsets of A whose union is A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the two smallest exponents for any set A?
\(A^0 = \emptyset\), \(A^1 = A\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the size of A^n if A is finite?
The size of \(A^n\) is just \(|A|^n\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a partition of a set?
A partition of a set A is a collection of nonempty subsets such that every member of A belongs to exactly one subset.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is one possible partition of the set A = {a, b, c}?
{{a, c}, {b}}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many parts does the partition {{a, b}, {c}} have?
2
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What fails in the collection {{a, b}, {b, c}}?
Members are not disjoint; b belongs to two members.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a real-world application of partitions?
Classifying plant specimens by species.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many partitions are there for a set of size 3?
5
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the number of partitions for a set of size 4?
15
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the number of partitions for a set of size 10?
115975
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What fails in the collection {{a}, {b}} for A = {a, b, c}?
The union is not the entire set A; c is missing.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an example of a partition of infinite sets?
{ {even numbers}, {odd numbers} } is a partition of the set of nonnegative integers.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the coarsest partition of a set A?
The coarsest partition of A is {A}, which has just one part: the entire set A itself.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the finest partition of a set A?
The finest partition of A is {{a}: a ∈ A}, with one part for each element of A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens if A has one element regarding partitions?
If A has one element, the coarsest and finest partitions are the same.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many parts does the finest partition have if A is finite?
If A is finite, the finest partition has |A| parts.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many parts does the finest partition have if A is infinite?
If A is infinite, the finest partition has infinitely many parts.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship between coarsest and finest partitions when A has two elements?
If A has two elements, the coarsest and finest partitions are the only partitions of A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the statement 'int monthNumber;' declare in C?
It declares that the variable monthNumber has type int and allocates memory for it.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the statement 'char monthName[10];' declare in C?
It declares monthName as a string of at most 9 characters and allocates memory for it.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the set of possible values for a variable of type int in C?
Let Int be the set of possible values for a variable of type int.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the set of possible values for a variable declared as a string in C?
Let String be the set of possible values for a variable that is a string of at most 9 letters.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What type does the statement 'struct aNewType' create in C?
It creates a new type called aNewType for objects consisting of an int followed by a string.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the memory allocation for 'aNewType'?
It allocates memory so that the int is followed by the string in memory.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What type does 'union anotherNewType' represent?
It represents objects that can be either an int or a string.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the memory allocation for 'anotherNewType'?
It allocates a piece of memory large enough to contain either an int or a string.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
If A is a subset of B (A ⊆ B), what is A ∪ B?
A ∪ B = B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
If A is not a subset of B (A ⊈ B), what can you say about A ∪ B?
A ∪ B contains elements from both A and B, but is not equal to B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Complete: A ⊆ B if and only if Ā ∪ B = ___
B.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an equivalent condition for A ⊂ B using intersection?
A ∩ B = A.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an equivalent condition for A ⊆ B using set difference?
A - B = Ø (empty set).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the diagram on the left show?
It shows the set {a} and its sole subset, Ø (empty set).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the diagram on the right show?
It shows the set {a,b} and all its subsets.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the requirements for representing sets in the diagram?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How to draw a diagram for subsets of {a, b, c}?
Draw all subsets: - Ø - {a} - {b} - {c} - {a, b} - {a, c} - {b, c} - {a, b, c}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What should be labeled on the arrows in the diagram?
Label arrows by the sole member of Y \ X for pairs X, Y where X ⊆ Y and |Y| = |X| + 1.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can you draw the diagram in three dimensions?
Use layers or spheres to represent sets, with subsets inside larger sets, creating a 3D structure.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
For a set of n elements, how many sets are there?
There are \(2^n\) sets in total.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many arrows does the diagram have for n elements?
There are \(n \cdot 2^{n-1}\) arrows.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many arrows are labeled by each element of the n-element set?
Each element labels \(2^{n-1}\) arrows.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many directed paths are there from set X to set Y?
The number of directed paths from X to Y is given by the expression \(2^{|Y| - |X| - 1}\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the definition of internally disjoint paths?
Two paths are internally disjoint if no internal set on either path appears on the other path.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does it mean for paths to be mutually internally disjoint?
Paths are mutually internally disjoint if every pair of paths in the collection are internally disjoint.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the characteristic string of a subset A of U?
It is a string of n bits where the i-th bit indicates if element e_i belongs to A: 1 if yes, 0 if no.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many subsets does a set of three elements have?
A set of three elements has 8 subsets.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the significance of characteristic strings differing by one bit?
It allows efficient searching through subsets, requiring fewer changes when moving from one string to the next.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many regions does a single set divide the plane into?
A single set divides the plane into two regions: its interior and exterior.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many basic regions do two intersecting sets divide the plane into?
Two intersecting sets divide the plane into four basic regions.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the basic regions for two sets A and B?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How many regions do three sets divide the plane into?
Three sets can divide the plane into eight regions.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the complement of a set in a Venn diagram?
The complement of a set includes all elements not in the set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the total number of basic regions in a general Venn diagram for n sets?
\(2^n\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a characteristic of a general Venn diagram?
Every possible intersection corresponds to a basic region.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the maximum number of sets for which a general Venn diagram can be drawn with circles of the same size?
At most 7 sets.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the floor function [n/2]?
The greatest integer less than or equal to \(n/2\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the ceiling function [n/2]?
The least integer greater than or equal to \(n/2\).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens to the sequence of binomial coefficients as r goes from 0 to [n/2]?
They increase.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens to the sequence of binomial coefficients as r goes from [n/2] to n?
They decrease.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the significance of drawing Venn diagrams in information visualization?
They illustrate relationships among collections of sets.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are some criteria for drawing Venn diagrams?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can a three-dimensional general Venn diagram be represented?
By using spheres to represent each set.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens to (n) when n is even as r goes from 0 to n/2?
(n) increases
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens to (n) when n is even as r goes from n/2 to n?
(n) decreases
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens to (n) when n is odd as r goes from 0 to (n-1)/2?
(n) increases
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens to (n) when n is odd as r goes from (n+1)/2 to n?
(n) decreases
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the important property for every positive integer r in the range 1 ≤ r ≤ n - 1?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Who has more options when choosing subsets of size r? You or your friend?
It depends on n and r.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does |A ∪ B| express in terms of |A|, |B|, and |A ∩ B|?
|A ∪ B| = |A| + |B| - |A ∩ B|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does |A ∩ B| express in terms of |A|, |B|, and |A ∪ B|?
|A ∩ B| = |A| + |B| - |A ∪ B|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does |A ∪ B ∪ C| express in terms of |A|, |B|, |C|, and their intersections?
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does |A ∩ B ∩ C| express in terms of |A|, |B|, |C|, and their unions?
|A ∩ B ∩ C| = |A| + |B| + |C| - |A ∪ B| - |A ∪ C| - |B ∪ C| + |A ∪ B ∪ C|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does i_k represent in the context of sets A1, A2, ..., An?
i_k is the sum of all sizes of intersections of k of the sets.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the expression for |A ∪ B| when n = 2?
|A| + |B| - |A ∩ B|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the expression for |A ∪ B ∪ C| when n = 3?
|A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the general expression for |A₁ ∪ A₂ ∪ ... ∪ Aₘ|?
Sum of sizes of individual sets - Sum of sizes of pairwise intersections + Sum of sizes of triple intersections - ... + (-1)^{m-1} |A₁ ∩ A₂ ∩ ... ∩ Aₘ|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is U₁ when n = 3?
U₁ = |A₁| + |A₂| + |A₃|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is U₂ when n = 3?
U₂ = |A₁ ∪ A₂| + |A₁ ∪ A₃| + |A₂ ∪ A₃|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the expression for |A ∩ B| in terms of U₁ and U₂?
|A ∩ B| = U₁ + U₂ - |A ∪ B|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the expression for |A ∩ B ∩ C| in terms of U₁, U₂?
|A ∩ B ∩ C| = U₁ + U₂ - |A ∪ B ∪ C|
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can |A B| be expressed in three different ways?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the shaded region in a Venn diagram for sets A, B, C represent?
The region(s) that form A ∩ B ∩ C
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the relationship shown by (A ∪ B) △ (A ∩ B)?
(A ∪ B) △ (A ∩ B) = A △ B
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What condition do members of A₁ △ A₂ △ ... △ Aₙ satisfy?
They belong to an odd number of the sets A₁, A₂, ..., Aₙ.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Does A × B equal A × B?
No, it does not hold in general. For example, if A = {1} and B = {2}, then A × B = {(1,2)} and A × B = {(2,1)}. They are not equal when the order of elements matters in the Cartesian product.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
List all partitions of {1,2,3,4} into three parts.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the parts of U defined by sets A, B, C in a Venn diagram?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Can R have a partition with all parts as open intervals?
Yes, R can be partitioned into open intervals, such as (−∞, 0) and (0, ∞).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Can R have a partition with all parts as half-open half-closed intervals?
Yes, R can be partitioned into half-open half-closed intervals, such as [0, 1) and [1, 2).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Can R have a partition with all parts as closed intervals?
Yes, R can be partitioned into closed intervals, such as [0, 1] and [1, 2].
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Who was the first president of the United States?
George Washington
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the capital of France?
Paris
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the largest planet in our solar system?
Jupiter
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for the area of a circle?
\(A = \pi r^2\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for standard deviation?
\(\sigma = \sqrt{\frac{\sum_{i=1}^{N}(x_i - \mu)^2}{N}}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the parts of a neuron?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the first 5 presidents of the United States?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a function?
A function consists of: - A set called the domain - A set called the codomain - A specification for each element x of the domain, defining a unique member f(x) of the codomain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What three things must be specified for a task?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of a function?
The domain is the set of all possible input values for the function.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the codomain of a function?
The codomain is the set of all possible output values for the function.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does f(x) represent in a function?
f(x) represents the unique value in the codomain corresponding to the input x from the domain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How do you sort a list of names?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an example of a function task in sports?
Determining the maximum number of goals kicked by any team in a season based on game records.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the argument in a function?
The argument is also called the parameter or the input.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the value of a function denoted as?
The value is denoted as f(x) and is also called the output.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What happens if an argument does not belong to the domain?
If an argument does not belong to the domain, the function is considered undefined.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the function SumOfFourIntCubes?
The domain is the set of all quadruples of integers (Z×Z×Z×Z).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for SumOfFourIntCubes?
The formula is SumOfFourIntCubes(w,x,y,z) = w³ + x³ + y³ + z³.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the function SumOfFourRealCubes?
The domain is the set of all quadruples of real numbers.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the formula for SumOfFourRealCubes?
The formula is SumOfFourRealCubes(w,x,y,z) = w³ + x³ + y³ + z³.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the function SumOfFourIntCubes?
\(dom(SumOfFourIntCubes) = extbf{Z} \times extbf{Z} \times extbf{Z} \times extbf{Z}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the function SumOfFourRealCubes?
\(dom(SumOfFourRealCubes) = extbf{R} \times extbf{R} \times extbf{R} \times extbf{R}\)
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why are functions with the same rule considered different if their domains are different?
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the image of a function?
The exact set of possible values of a function, a subset of the codomain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the domain of a function signify?
It is a promise that the function will work for every member of the domain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why might a function have a more modest domain?
A modest domain can simplify the function's promises, making them easier to keep.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why do we allow 'looseness' in the codomain of functions?
It is often harder to know the image than to specify a natural codomain. Sometimes it's impossible to know exactly which values are feasible.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the codomain in the Maximum Goals example?
The codomain is the set \(\mathbb{N} \{0\}\) (nonnegative integers).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why is the Pompous Python function difficult to compute?
It is impossible to compute perfectly due to the vast number of programs involved and results on uncomputability.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the codomain represent in a function?
It represents a promise that all values returned by the function will be in that set, but not all members must be actual function values.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is currently unknown about the SumOfFourIntCubes function?
It is not known whether every integer can be written as the sum of four cubes.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the codomain specified for SumOfFourIntCubes?
The codomain is specified as \(\mathbb{Z}\) (the set of all integers).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the practical reason for specifying a codomain?
It allows for a simple, easily-described set that includes all possible function values, even if it has other values too.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a function's codomain?
The codomain is a set that includes all possible outputs of a function, which may or may not match the actual outputs (image).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a function that maps its domain onto its codomain called?
It is called a surjection or said to be onto.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the rule of a function specify?
The rule specifies the relationship between each member of its domain and the corresponding value of the function.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Does the rule of a function specify how to compute the function?
No, it specifies what must be done, but not how to do it.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is an example of a sorting algorithm?
Examples include Bucket Sort, Merge Sort, Insertion Sort, and Quick Sort.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the Fibonacci sequence?
The Fibonacci sequence is generated by starting with two 1s and repeatedly adding the two most recent numbers together.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Why is the term range avoided in function definitions?
The term 'range' is confusing as it can refer to either the image or the codomain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the rule for the function that squares integers?
The rule is that any integer argument is squared, with domain and codomain as Z.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a function's rule?
A function's rule associates each argument in its domain with a unique value in its codomain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the function Employer?
{Annie Jump Cannon, Henrietta Swan Leavitt, Muriel Heagney, Winsome Bellamy}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the codomain of the function Employer?
The set of all astronomical observatories over the last two centuries.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What are the ordered pairs for the function Employer?
{(Annie Jump Cannon, Harvard College Observatory), (Henrietta Swan Leavitt, Harvard College Observatory), (Muriel Heagney, Melbourne Observatory), (Winsome Bellamy, Sydney Observatory)}
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Is the function Employer a surjection?
No, its image is a proper subset of the codomain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the graph of a function?
The set of all ordered pairs (x, f(x)) of a function f.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
How can the squaring function be represented?
As {(x, x²): x ∈ Z}.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the horizontal axis represent in a function's graph?
The domain of the function.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the vertical axis represent in a function's graph?
The codomain of the function.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Who is associated with the Harvard College Observatory?
Annie Jump Cannon
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the Employer function?
A set of four people
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the codomain of the Employer function?
Not specified in the text
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is one way to depict functions visually?
Using a Venn diagram
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does each point in the domain of a function have?
Exactly one arrow going out of it
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain of the Sorting function?
The set of all possible lists of names
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Which observatory is associated with Muriel Heagney?
Melbourne Observatory
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the purpose of plots in functions?
To display information about the function
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does increasing dimensions in plots not always help with?
Understanding domains and codomains
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Who is associated with the Sydney Observatory?
Winsome Bellamy
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the first task in software development?
To work out what must be done, known as analysis.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the analysis process involve?
Extensive communication with the owner of a problem (e.g., a client).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a possible outcome of the analysis process?
A function specification.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the difference between 'what' and 'how' in software development?
'What' is the task to be done; 'how' is the method to do it.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What do we design after specifying a function?
An algorithm for the function.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What programming language is mentioned for implementation?
Python.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
Is the software development process purely linear?
No, it often involves going back and re-doing parts of previous stages.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What may highlight problems in the design process?
The design process itself may highlight problems or gaps.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a function in the mathematical sense?
A specification of what rather than how.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What additional aspect does the term 'function' have in programming languages?
It often includes code or an algorithm for computation.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is emphasized when using the term 'mathematical function'?
It indicates that no code or algorithm is given.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a function definition format?
name: domain name(x) codomain, precise description of the function value, in terms of x.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the function f: R → R represent?
It gives squares of real numbers: f(x) = x².
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the domain in the function f: R → R?
The domain is R (real numbers).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the codomain of the function f: R → R?
The codomain is also R (real numbers).
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is a common way to state a function definition?
The function f : R → R is defined by f(x) = x².
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What does the mapping arrow (→) in a function rule indicate?
It differs from the ordinary arrow → that goes from domain to codomain.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the alternative form for specifying the rule of a function?
X → precise description of the function value, in terms of x.
Sfoglia le tue carte qui, oppure sign up to study with spaced repetition.
What is the raw material of computation and communication?
Information
What are sets used for in programming?
To define types of objects
What is a set?
A collection of objects without order or repetition
What are the objects in a set called?
Elements or members
How can a set be specified?
By a comma-separated list between curly braces
What is the symbol for the empty set?
Ø
Give an example of a set with characters.
{Harry, Ginny, Hermione, Ron, Hagrid}
Give an example of a set with numbers.
{42, -273.15, 1729, 10100}
What is the significance of sets in programming languages?
They underlie any notion of type
What does the symbol ∈ represent in set theory?
It indicates that an object is an element of a set. For example, CSIRAC ∈ {Manchester Baby, EDSAC, CSIRAC}.
What does the symbol ∉ represent in set theory?
It indicates that an object does not belong to a set. For example, SILLIAC ∉ {Manchester Baby, EDSAC, CSIRAC}.
How can we specify a set succinctly when it has many elements?
By giving a condition that the elements must satisfy. For example, {x:x is even} represents all even numbers.
What does the notation {x:x is even} mean?
It represents the set of all x such that x is even.
Can the order of elements in a set affect its identity?
No, different orders do not affect the identity of the set. For example, {CSIRAC, Manchester Baby, EDSAC} = {Manchester Baby, EDSAC, CSIRAC}.
What is the importance of the colon : in set notation?
It separates the variable from the condition that must be satisfied for membership in the set.
What is an example of a set that is defined by a condition?
{n:n is even} is a set defined by the condition that n is even.
What is the general form of set definitions?
{name : condition}
How can the set of even integers be expressed?
{x ∈ Z : x is even}
What does the notation {x ∈ Z : x is even} mean?
The set of x in Z such that x is even.
What is an alternative way to specify a set?
By giving a rule for constructing each member.
How can the set of even integers be expressed using a rule?
{2n : n ∈ Z}
What does {2n : n ∈ Z} represent?
The set of 2n such that n is an integer.
What is necessary for the condition in a set definition?
It must be precise and clear.
What is the cardinality of a set?
The cardinality of a set is the number of elements it contains, denoted by |A| or #A.
How is the cardinality of a set determined?
By counting the number of elements listed in the set.
What is the cardinality of the set {Harry, Ginny, Hermione, Ron, Hagrid}?
5
What is the cardinality of the set {42, -273.15, 1729, 10100}?
4
What is the cardinality of the set {CSIRAC, Manchester Baby, EDSAC}?
3
What is the cardinality of the empty set {}?
0
Why is determining the cardinality important in computer science?
It helps determine the efficiency of algorithms and storage requirements.
What is a common practice when describing large sets informally?
Listing a few elements and using '...' to imply continuation.
What is a potential risk of defining sets using English text?
Imprecision in the definition of the set.
What does the symbol Ø represent?
The empty set
What is the set of positive integers denoted by?
N
What does Z represent in sets of numbers?
The set of all integers
What is the set of rational numbers denoted by?
Q
What is the set of real numbers denoted by?
R
What does Z+ denote?
The set of positive integers (N)
What is the notation for a closed interval?
[a,b]
What does [a,b) represent?
A half-open half-closed interval
What does (a,b) represent?
An open interval
How do you denote integers within an interval [a,b]?
[a,b]z
What is a set of allowed characters called?
Alphabet
What is an example of a finite alphabet?
The 26-letter English alphabet {a, b, c, ..., y, z}
What is a string over an alphabet?
A finite sequence of characters from that alphabet.
What is the length of the string 'babbage'?
7
What symbol represents the empty string?
e (epsilon)
What does A^k denote?
All the strings of exactly k characters from alphabet A.
What is the set A°?
The set containing just the empty string: A° = {ε}.
How many strings of length k over an alphabet A are there?
|A|^k
What is |A¹| equal to?
|A| (the number of letters in the alphabet)
If A = {0,1}, what is A³?
{000, 001, 010, 011, 100, 101, 110, 111}
What is the formula for the number of strings of length k over an alphabet A?
\(|A^k| = |A|^k\)
What does A* represent in set theory?
The set of all finite strings over the alphabet A.
What is an example of A* for A = {0,1}?
A* = {ε, 0, 1, 00, 01, 10, 11, ...}
What does A ⊆ B mean?
Every element of A is also an element of B.
What does A ¢ B signify?
A is not a subset of B.
How is the subset relation illustrated in a Venn diagram?
Set A is drawn entirely within set B.
What logical implication does A ⊆ B represent?
If x ∈ A then x ∈ B.
What is the notation for membership in a set?
x ∈ A means x is a member of set A.
What is a proper subset?
A is a proper subset of B if A ⊆ B and A ≠ B.
What is the relationship between the empty set and any set B?
The empty set Ø is a subset of every set B.
What does A ⊂ B imply if A and B are finite?
A ⊂ B implies |A| ≤ |B|.
What does A ⊇ B mean?
A is a superset of B, meaning B is a subset of A.
What is the implication of A ⊇ B?
Membership of B is implied by membership of A.
What is the notation for a proper superset?
A is a proper superset of B is written as A ⊃ B.
What is the definition of a subset?
A set A is a subset of B if every element of A is also an element of B.
What does it mean if two sets A and B are equal?
If A = B, then A ⊆ B and A ⊃ B.
How can you prove that two sets A and B are equal?
Prove that each is a subset of the other: A ⊆ B and B ⊆ A.
What does the symbol ⇔ represent?
It represents that membership of A is equivalent to membership of B.
What does 'x ∈ A if and only if x ∈ B' imply?
Both conditions either hold or do not hold; they are equivalent.
What is a maximum clique?
A clique of maximum size; there is no larger clique.
What is a maximal clique?
A clique that is not a proper subset of any other clique.
What does A ⊆ B indicate?
Membership of A implies membership of B.
What does A ⊃ B indicate?
Membership of B implies membership of A.
How do maximal and maximum cliques differ?
A maximal clique may be smaller than a maximum clique; all maximum cliques are maximal, but not vice versa.
What is a maximum subset?
A subset with the largest size among all subsets with a specific property.
What is a maximal subset?
A subset that cannot be enlarged without losing the property; it is not a proper subset of another subset with the same property.
What is the difference between minimum and minimal subsets?
A minimum subset has the smallest size; a minimal subset cannot be a proper superset of another subset with the property.
In what context are maximum and maximal often treated as synonyms?
In the context of real numbers, the distinction is often unnecessary, and both terms can mean the same thing.
What is the total number of subsets of a finite set B with n elements?
\(|P(B)| = 2^n\)
What is the power set of a set B?
The power set P(B) is the set of all subsets of B.
How does the number of subsets grow as the size of the set increases?
It grows exponentially as the size of the set increases.
What does it mean for two sets A and B to be incomparable?
A and B are incomparable if neither A ⊆ B nor B ⊆ A.
What is the distinction between maximal and maximum?
Maximal refers to a property; maximum refers to the largest value with that property.
What is the formula for calculating the number of choices for subsets of a set with n elements?
\(2^{|B|}\), where |B| is the number of elements in the set.
What happens when making choices for elements of a set regarding subsets?
Choices are independent; one choice does not restrict others.
What does n choose k represent?
The binomial coefficient \(\binom{n}{k}\) represents the number of ways to choose k elements from a set of n elements.
How many subsets of size 0 can be formed from a set of size n?
There is exactly 1 way to choose 0 elements from a set of size n, which is to choose nothing.
What is the formula for the total number of subsets of a set of size n?
The total number of subsets is given by \(2^n\).
What is a clique in social network analysis?
A clique is the largest set of people in a network where every person knows every other person.
What is a mutual stranger set?
A mutual stranger set is the largest set of people in a network where no one knows any other member of the set.
What is the relationship between subsets and binomial coefficients?
The binomial coefficients count every subset of a set B exactly once, summing to \(2^n\) for all sizes k.
What is the significance of the power set in algorithm design?
The power set is used to analyze all possible subsets to find optimal solutions in problems like social network analysis.
What is the number of ways to choose all elements from a set of size n?
Only 1 way: choose all elements.
How many options do we have when choosing 1 element from n elements?
We have n options.
What is the number of ways to choose n-1 elements from n elements?
We have n options (choosing one to exclude).
What is the symmetry observed in choosing subsets?
Choosing k elements to include is the same as choosing n-k elements to exclude.
What is the formula for the number of ways to choose k elements from n?
How do we count the ways to choose k elements in order from n elements?
Use the formula: \(\(n(n-1)(n-2) imes...(n-k+1)\)\)
What is the factorial of n?
Defined as: \(\(n! = n(n-1)(n-2)...3 imes 2 imes 1\)\)
What is the formula for the number of ways to choose k elements in order?
\(\frac{n!}{(n-k)!}\)
How many orderings are there for k elements chosen from a set?
\(k!\) ways to order the k elements
What is the relationship between ordered and unordered choices of k elements?
What is the formula for the number of subsets of size k from n elements?
\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)
Which expression is more efficient for computation: \(\frac{n!}{(n-k)!}\) or \(\frac{n(n-1)(n-2)...(n-k+1)}{k!}\)?
\(\frac{n(n-1)(n-2)...(n-k+1)}{k!}\) is more efficient
Why is the order of operations important in computations?
It affects the accuracy of the result due to number size limitations
What is a potential issue when computing large or small intermediate numbers?
It can affect the accuracy of the result
What is the binomial coefficient for choosing 2 elements from n?
\(?inom{n}{2} = \frac{n(n-1)}{2}\)
How can we count subsets of a given size recursively?
Divide subsets into those that include an element and those that don't.
In the example with set B = {1,2,3,4,5}, how many 3-element subsets include element 1?
Count 2-element subsets from {2,3,4,5}: \(?inom{4}{2}\)
In the example with set B = {1,2,3,4,5}, how many 3-element subsets do not include element 1?
Count 3-element subsets from {2,3,4,5}: \(?inom{4}{3}\)
What is the total number of 3-element subsets of a set of size 5?
It's given by \(?inom{5}{3}\)
How do we express the total number of 3-element subsets?
Total = # subsets including 1 + # subsets not including 1
What is the total number of 3-element subsets of set B?
It is calculated as the number of 3-element subsets that include 1 plus those that do not include 1.
How do you calculate k-element subsets including a specific element b?
Choose k-1 elements from n-1 elements (those not including b). This can be done in \(?inom{n-1}{k-1}\) ways.
How do you calculate k-element subsets not including a specific element b?
Choose k elements from n-1 elements (those not including b). This can be done in \(?inom{n-1}{k}\) ways.
What is the formula for the total number of k-element subsets?
The total is given by \(?inom{n}{k} = ?inom{n-1}{k-1} + ?inom{n-1}{k}\).
What are the base cases for computing binomial coefficients?
The base cases are \(?inom{n}{0} = 1\) and \(?inom{n}{n} = 1\).
How does the recursive method work for computing binomial coefficients?
It reduces the problem to simpler cases until reaching the base cases, ensuring the process stops.
What does Pascal's triangle represent?
It represents binomial coefficients where each coefficient is the sum of the two coefficients directly above it.
What is the value of C(2, 1)?
The value is 2, calculated as \(?inom{2}{1} = 2\).
What is the value of C(3, 1)?
The value is 3, calculated as \(?inom{3}{1} = 3\).
What is the value of C(4, 2)?
The value is 6, calculated as \(?inom{4}{2} = 6\).
What is the complement of a set A?
The complement of A, denoted by A', is the set of all elements of the universal set U that are not in A.
What does U/A represent?
U/A represents everything in the universal set U that is not in set A.
In the context of integers, what is the universal set?
The universal set can be the set Z of all integers.
What is the equation shown in Figure 1.2?
The equation is 10 = 4 + 6, where (2) = 10, (1) = 4, and (2) = 6 in Pascal's triangle.
What are some examples of subsets of a universal set of integers?
Examples include even integers, odd integers, negative integers, and prime integers.
What is the universe of discourse?
The universe of discourse is the universal set that contains all elements under consideration.
What is the notation for the complement of A?
The complement of A can be denoted by A' or U/A.
What does A CU signify?
A CU signifies that A is a subset of the universal set U.
What is the formula for the size of set A when A and U are finite sets?
\(|A| = |U| - |A|\)
What does the complement of A equal?
\(A^c = A\)
What is the definition of the set difference B / A?
\(B \setminus A = \{ x \in B : x \notin A \}\)
If A is a subset of B, what is the formula for the size of the set difference?
\(|B \setminus A| = |B| - |A|\)
What is the union of two sets A and B?
\(A \cup B = \{x : x \in A \text{ or } x \in B\}\)
What is the intersection of two sets A and B?
\(A \cap B = \{x : x \in A \text{ and } x \in B\}\)
What does the notation A ⊆ B mean?
A is a subset of B
What does the notation A ⊇ B mean?
A is a superset of B
What is the condition for the size of the set difference |B \ A|?
It does not satisfy (1.9) unless A ⊆ B
What is the relationship between subsets and supersets?
A ⊆ B ⇔ A ⊇ B
What is the formula for the size of the union of two sets A and B?
\(|A| + |B| = |A \cup B| + |A \cap B|\)
What does it mean if two sets A and B are disjoint?
\(A \cap B = \emptyset\)
What is the formula for the size of the disjoint union of two sets A and B?
\(|A \cup B| = |A| + |B|\) if \(A \cap B = \emptyset\)
What is the relationship between the complement of the union of two sets and their complements?
\(\overline{A \cup B} = \overline{A} \cap \overline{B}\)
What is the result of counting elements in sets A and B?
Elements in both sets are counted twice.
What is the notation for the disjoint union of sets A and B?
\(A \sqcup B\) or \(A \oplus B\)
What is the disjoint union of sets A and B?
Defined only when sets A and B are disjoint.
What does Theorem 1 state about union and intersection?
\(A ?igcup B = A ?igcap B\) when x is in A or B.
What is the complement of the intersection of two sets?
It is the union of their complements: \(A ?igcap B' = A' ?igcup B'\).
What are De Morgan's Laws for Sets?
They describe duality between union and intersection: \(A ?igcup B' = A' ?igcap B'\) and \(A ?igcap B' = A' ?igcup B'\).
How can we express Corollary 2 using Theorem 1?
\(A ?igcap B = A ?igcup B\) by using Theorem 1.
What is the result of A ∩ (B ∪ C)?
(A ∩ B) ∪ (A ∩ C)
What is the result of A ∪ (B ∩ C)?
(A ∪ B) ∩ (A ∪ C)
How do union and intersection interact?
Union followed by intersection: A ∩ (B ∪ C). Intersection followed by union: A ∪ (B ∩ C).
What is shown in Figure 1.8?
The relationship between A ∩ (B ∪ C) and (A ∩ B) ∪ (A ∩ C).
What is the symmetric difference of sets A and B?
\(A \Delta B = \{x : x \in A \text{ or } x \in B \text{ but not both}\}\)
What does the first Distributive Law state about intersection and union?
Intersection distributes over union: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
What does the second Distributive Law state about union and intersection?
Union distributes over intersection: \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
What is the formula for multiplication distributing over addition in numbers?
\(a \times (b + c) = (a \times b) + (a \times c)\)
Does addition distribute over multiplication?
No, generally \(a + (b \times c) \neq (a + b) \times (a + c)\)
What is the exclusive 'or' in the context of symmetric difference?
It means belonging to exactly one of the sets, excluding both.
What is the formula for the symmetric difference of sets A and B?
\(A \Delta B = (A/B) \cup (B/A)\)
What is the result of the symmetric difference of a set with itself?
\(A \Delta A = \emptyset\)
When are two sets identical?
Two sets A and B are identical if and only if \(A \Delta B = \emptyset\)
What is the relationship between the symmetric difference and complements?
\(A \Delta B = A^c \Delta B^c\)
What is a Cartesian product?
An ordered pair (a, b) consists of two objects a and b together, in that order.
What is the Cartesian product of two sets A and B?
\(A \times B = \{(a,b): a \in A, b \in B\}\)
If A = {King, Queen, Jack} and B = {♣, ♡}, what is A × B?
\(A \times B = \{(King, \clubsuit), (King, \heartsuit), (Queen, \clubsuit), (Queen, \heartsuit), (Jack, \clubsuit), (Jack, \heartsuit)\}\)
What does R × R represent?
The set of all coordinates of points in the plane.
What is the formula for the size of the Cartesian product of two finite sets A and B?
\(|A \times B| = |A| \cdot |B|\)
What is the Cartesian product of three sets A, B, and C?
\(A \times B \times C = \{(a,b,c): a \in A, b \in B, c \in C\}\)
What is the general form of the Cartesian product for n sets A1, A2, ..., An?
\(A_1 \times A_2 \times \ldots \times A_n = \{(a_1,a_2,\ldots,a_n): a_i \in A_i\}\)
What is the size of the Cartesian product of finite sets?
\(|A_1 \times A_2 \times \ldots \times A_n| = |A_1| \cdot |A_2| \cdots |A_n|\)
How can we express the Cartesian product of identical sets?
\(A^n\) indicates the Cartesian product of \(n\) identical sets.
What is the example of {0,1}³?
\(\{(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)\}\)
How do we represent n-tuples as strings?
For binary alphabet {0,1}, \(\{0,1\}^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}\)
What are R² and R³ in terms of Cartesian products?
\(R^2 = R \times R\) and \(R^3 = R \times R \times R\)
What is the definition of a partition of a set A?
A partition is a set of disjoint nonempty subsets of A whose union is A.
What are the two smallest exponents for any set A?
\(A^0 = \emptyset\), \(A^1 = A\).
What is the size of A^n if A is finite?
The size of \(A^n\) is just \(|A|^n\).
What is a partition of a set?
A partition of a set A is a collection of nonempty subsets such that every member of A belongs to exactly one subset.
What is one possible partition of the set A = {a, b, c}?
{{a, c}, {b}}
How many parts does the partition {{a, b}, {c}} have?
2
What fails in the collection {{a, b}, {b, c}}?
Members are not disjoint; b belongs to two members.
What is a real-world application of partitions?
Classifying plant specimens by species.
How many partitions are there for a set of size 3?
5
What is the number of partitions for a set of size 4?
15
What is the number of partitions for a set of size 10?
115975
What fails in the collection {{a}, {b}} for A = {a, b, c}?
The union is not the entire set A; c is missing.
What is an example of a partition of infinite sets?
{ {even numbers}, {odd numbers} } is a partition of the set of nonnegative integers.
What is the coarsest partition of a set A?
The coarsest partition of A is {A}, which has just one part: the entire set A itself.
What is the finest partition of a set A?
The finest partition of A is {{a}: a ∈ A}, with one part for each element of A.
What happens if A has one element regarding partitions?
If A has one element, the coarsest and finest partitions are the same.
How many parts does the finest partition have if A is finite?
If A is finite, the finest partition has |A| parts.
How many parts does the finest partition have if A is infinite?
If A is infinite, the finest partition has infinitely many parts.
What is the relationship between coarsest and finest partitions when A has two elements?
If A has two elements, the coarsest and finest partitions are the only partitions of A.
What does the statement 'int monthNumber;' declare in C?
It declares that the variable monthNumber has type int and allocates memory for it.
What does the statement 'char monthName[10];' declare in C?
It declares monthName as a string of at most 9 characters and allocates memory for it.
What is the set of possible values for a variable of type int in C?
Let Int be the set of possible values for a variable of type int.
What is the set of possible values for a variable declared as a string in C?
Let String be the set of possible values for a variable that is a string of at most 9 letters.
What type does the statement 'struct aNewType' create in C?
It creates a new type called aNewType for objects consisting of an int followed by a string.
What is the memory allocation for 'aNewType'?
It allocates memory so that the int is followed by the string in memory.
What type does 'union anotherNewType' represent?
It represents objects that can be either an int or a string.
What is the memory allocation for 'anotherNewType'?
It allocates a piece of memory large enough to contain either an int or a string.
If A is a subset of B (A ⊆ B), what is A ∪ B?
A ∪ B = B.
If A is not a subset of B (A ⊈ B), what can you say about A ∪ B?
A ∪ B contains elements from both A and B, but is not equal to B.
Complete: A ⊆ B if and only if Ā ∪ B = ___
B.
What is an equivalent condition for A ⊂ B using intersection?
A ∩ B = A.
What is an equivalent condition for A ⊆ B using set difference?
A - B = Ø (empty set).
What does the diagram on the left show?
It shows the set {a} and its sole subset, Ø (empty set).
What does the diagram on the right show?
It shows the set {a,b} and all its subsets.
What are the requirements for representing sets in the diagram?
How to draw a diagram for subsets of {a, b, c}?
Draw all subsets: - Ø - {a} - {b} - {c} - {a, b} - {a, c} - {b, c} - {a, b, c}
What should be labeled on the arrows in the diagram?
Label arrows by the sole member of Y \ X for pairs X, Y where X ⊆ Y and |Y| = |X| + 1.
How can you draw the diagram in three dimensions?
Use layers or spheres to represent sets, with subsets inside larger sets, creating a 3D structure.
For a set of n elements, how many sets are there?
There are \(2^n\) sets in total.
How many arrows does the diagram have for n elements?
There are \(n \cdot 2^{n-1}\) arrows.
How many arrows are labeled by each element of the n-element set?
Each element labels \(2^{n-1}\) arrows.
How many directed paths are there from set X to set Y?
The number of directed paths from X to Y is given by the expression \(2^{|Y| - |X| - 1}\).
What is the definition of internally disjoint paths?
Two paths are internally disjoint if no internal set on either path appears on the other path.
What does it mean for paths to be mutually internally disjoint?
Paths are mutually internally disjoint if every pair of paths in the collection are internally disjoint.
What is the characteristic string of a subset A of U?
It is a string of n bits where the i-th bit indicates if element e_i belongs to A: 1 if yes, 0 if no.
How many subsets does a set of three elements have?
A set of three elements has 8 subsets.
What is the significance of characteristic strings differing by one bit?
It allows efficient searching through subsets, requiring fewer changes when moving from one string to the next.
How many regions does a single set divide the plane into?
A single set divides the plane into two regions: its interior and exterior.
How many basic regions do two intersecting sets divide the plane into?
Two intersecting sets divide the plane into four basic regions.
What are the basic regions for two sets A and B?
How many regions do three sets divide the plane into?
Three sets can divide the plane into eight regions.
What is the complement of a set in a Venn diagram?
The complement of a set includes all elements not in the set.
What is the total number of basic regions in a general Venn diagram for n sets?
\(2^n\)
What is a characteristic of a general Venn diagram?
Every possible intersection corresponds to a basic region.
What is the maximum number of sets for which a general Venn diagram can be drawn with circles of the same size?
At most 7 sets.
What is the floor function [n/2]?
The greatest integer less than or equal to \(n/2\).
What is the ceiling function [n/2]?
The least integer greater than or equal to \(n/2\).
What happens to the sequence of binomial coefficients as r goes from 0 to [n/2]?
They increase.
What happens to the sequence of binomial coefficients as r goes from [n/2] to n?
They decrease.
What is the significance of drawing Venn diagrams in information visualization?
They illustrate relationships among collections of sets.
What are some criteria for drawing Venn diagrams?
How can a three-dimensional general Venn diagram be represented?
By using spheres to represent each set.
What happens to (n) when n is even as r goes from 0 to n/2?
(n) increases
What happens to (n) when n is even as r goes from n/2 to n?
(n) decreases
What happens to (n) when n is odd as r goes from 0 to (n-1)/2?
(n) increases
What happens to (n) when n is odd as r goes from (n+1)/2 to n?
(n) decreases
What is the important property for every positive integer r in the range 1 ≤ r ≤ n - 1?
Who has more options when choosing subsets of size r? You or your friend?
It depends on n and r.
What does |A ∪ B| express in terms of |A|, |B|, and |A ∩ B|?
|A ∪ B| = |A| + |B| - |A ∩ B|
What does |A ∩ B| express in terms of |A|, |B|, and |A ∪ B|?
|A ∩ B| = |A| + |B| - |A ∪ B|
What does |A ∪ B ∪ C| express in terms of |A|, |B|, |C|, and their intersections?
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
What does |A ∩ B ∩ C| express in terms of |A|, |B|, |C|, and their unions?
|A ∩ B ∩ C| = |A| + |B| + |C| - |A ∪ B| - |A ∪ C| - |B ∪ C| + |A ∪ B ∪ C|
What does i_k represent in the context of sets A1, A2, ..., An?
i_k is the sum of all sizes of intersections of k of the sets.
What is the expression for |A ∪ B| when n = 2?
|A| + |B| - |A ∩ B|
What is the expression for |A ∪ B ∪ C| when n = 3?
|A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
What is the general expression for |A₁ ∪ A₂ ∪ ... ∪ Aₘ|?
Sum of sizes of individual sets - Sum of sizes of pairwise intersections + Sum of sizes of triple intersections - ... + (-1)^{m-1} |A₁ ∩ A₂ ∩ ... ∩ Aₘ|
What is U₁ when n = 3?
U₁ = |A₁| + |A₂| + |A₃|
What is U₂ when n = 3?
U₂ = |A₁ ∪ A₂| + |A₁ ∪ A₃| + |A₂ ∪ A₃|
What is the expression for |A ∩ B| in terms of U₁ and U₂?
|A ∩ B| = U₁ + U₂ - |A ∪ B|
What is the expression for |A ∩ B ∩ C| in terms of U₁, U₂?
|A ∩ B ∩ C| = U₁ + U₂ - |A ∪ B ∪ C|
How can |A B| be expressed in three different ways?
What does the shaded region in a Venn diagram for sets A, B, C represent?
The region(s) that form A ∩ B ∩ C
What is the relationship shown by (A ∪ B) △ (A ∩ B)?
(A ∪ B) △ (A ∩ B) = A △ B
What condition do members of A₁ △ A₂ △ ... △ Aₙ satisfy?
They belong to an odd number of the sets A₁, A₂, ..., Aₙ.
Does A × B equal A × B?
No, it does not hold in general. For example, if A = {1} and B = {2}, then A × B = {(1,2)} and A × B = {(2,1)}. They are not equal when the order of elements matters in the Cartesian product.
List all partitions of {1,2,3,4} into three parts.
What are the parts of U defined by sets A, B, C in a Venn diagram?
Can R have a partition with all parts as open intervals?
Yes, R can be partitioned into open intervals, such as (−∞, 0) and (0, ∞).
Can R have a partition with all parts as half-open half-closed intervals?
Yes, R can be partitioned into half-open half-closed intervals, such as [0, 1) and [1, 2).
Can R have a partition with all parts as closed intervals?
Yes, R can be partitioned into closed intervals, such as [0, 1] and [1, 2].
Who was the first president of the United States?
George Washington
What is the capital of France?
Paris
What is the largest planet in our solar system?
Jupiter
What is the formula for the area of a circle?
\(A = \pi r^2\)
What is the formula for standard deviation?
\(\sigma = \sqrt{\frac{\sum_{i=1}^{N}(x_i - \mu)^2}{N}}\)
What are the parts of a neuron?
What are the first 5 presidents of the United States?
What is a function?
A function consists of: - A set called the domain - A set called the codomain - A specification for each element x of the domain, defining a unique member f(x) of the codomain.
What three things must be specified for a task?
What is the domain of a function?
The domain is the set of all possible input values for the function.
What is the codomain of a function?
The codomain is the set of all possible output values for the function.
What does f(x) represent in a function?
f(x) represents the unique value in the codomain corresponding to the input x from the domain.
How do you sort a list of names?
What is an example of a function task in sports?
Determining the maximum number of goals kicked by any team in a season based on game records.
What is the argument in a function?
The argument is also called the parameter or the input.
What is the value of a function denoted as?
The value is denoted as f(x) and is also called the output.
What happens if an argument does not belong to the domain?
If an argument does not belong to the domain, the function is considered undefined.
What is the domain of the function SumOfFourIntCubes?
The domain is the set of all quadruples of integers (Z×Z×Z×Z).
What is the formula for SumOfFourIntCubes?
The formula is SumOfFourIntCubes(w,x,y,z) = w³ + x³ + y³ + z³.
What is the domain of the function SumOfFourRealCubes?
The domain is the set of all quadruples of real numbers.
What is the formula for SumOfFourRealCubes?
The formula is SumOfFourRealCubes(w,x,y,z) = w³ + x³ + y³ + z³.
What is the domain of the function SumOfFourIntCubes?
\(dom(SumOfFourIntCubes) = extbf{Z} \times extbf{Z} \times extbf{Z} \times extbf{Z}\)
What is the domain of the function SumOfFourRealCubes?
\(dom(SumOfFourRealCubes) = extbf{R} \times extbf{R} \times extbf{R} \times extbf{R}\)
Why are functions with the same rule considered different if their domains are different?
What is the image of a function?
The exact set of possible values of a function, a subset of the codomain.
What does the domain of a function signify?
It is a promise that the function will work for every member of the domain.
Why might a function have a more modest domain?
A modest domain can simplify the function's promises, making them easier to keep.
Why do we allow 'looseness' in the codomain of functions?
It is often harder to know the image than to specify a natural codomain. Sometimes it's impossible to know exactly which values are feasible.
What is the codomain in the Maximum Goals example?
The codomain is the set \(\mathbb{N} \{0\}\) (nonnegative integers).
Why is the Pompous Python function difficult to compute?
It is impossible to compute perfectly due to the vast number of programs involved and results on uncomputability.
What does the codomain represent in a function?
It represents a promise that all values returned by the function will be in that set, but not all members must be actual function values.
What is currently unknown about the SumOfFourIntCubes function?
It is not known whether every integer can be written as the sum of four cubes.
What is the codomain specified for SumOfFourIntCubes?
The codomain is specified as \(\mathbb{Z}\) (the set of all integers).
What is the practical reason for specifying a codomain?
It allows for a simple, easily-described set that includes all possible function values, even if it has other values too.
What is a function's codomain?
The codomain is a set that includes all possible outputs of a function, which may or may not match the actual outputs (image).
What is a function that maps its domain onto its codomain called?
It is called a surjection or said to be onto.
What does the rule of a function specify?
The rule specifies the relationship between each member of its domain and the corresponding value of the function.
Does the rule of a function specify how to compute the function?
No, it specifies what must be done, but not how to do it.
What is an example of a sorting algorithm?
Examples include Bucket Sort, Merge Sort, Insertion Sort, and Quick Sort.
What is the Fibonacci sequence?
The Fibonacci sequence is generated by starting with two 1s and repeatedly adding the two most recent numbers together.
Why is the term range avoided in function definitions?
The term 'range' is confusing as it can refer to either the image or the codomain.
What is the rule for the function that squares integers?
The rule is that any integer argument is squared, with domain and codomain as Z.
What is a function's rule?
A function's rule associates each argument in its domain with a unique value in its codomain.
What is the domain of the function Employer?
{Annie Jump Cannon, Henrietta Swan Leavitt, Muriel Heagney, Winsome Bellamy}
What is the codomain of the function Employer?
The set of all astronomical observatories over the last two centuries.
What are the ordered pairs for the function Employer?
{(Annie Jump Cannon, Harvard College Observatory), (Henrietta Swan Leavitt, Harvard College Observatory), (Muriel Heagney, Melbourne Observatory), (Winsome Bellamy, Sydney Observatory)}
Is the function Employer a surjection?
No, its image is a proper subset of the codomain.
What is the graph of a function?
The set of all ordered pairs (x, f(x)) of a function f.
How can the squaring function be represented?
As {(x, x²): x ∈ Z}.
What does the horizontal axis represent in a function's graph?
The domain of the function.
What does the vertical axis represent in a function's graph?
The codomain of the function.
Who is associated with the Harvard College Observatory?
Annie Jump Cannon
What is the domain of the Employer function?
A set of four people
What is the codomain of the Employer function?
Not specified in the text
What is one way to depict functions visually?
Using a Venn diagram
What does each point in the domain of a function have?
Exactly one arrow going out of it
What is the domain of the Sorting function?
The set of all possible lists of names
Which observatory is associated with Muriel Heagney?
Melbourne Observatory
What is the purpose of plots in functions?
To display information about the function
What does increasing dimensions in plots not always help with?
Understanding domains and codomains
Who is associated with the Sydney Observatory?
Winsome Bellamy
What is the first task in software development?
To work out what must be done, known as analysis.
What does the analysis process involve?
Extensive communication with the owner of a problem (e.g., a client).
What is a possible outcome of the analysis process?
A function specification.
What is the difference between 'what' and 'how' in software development?
'What' is the task to be done; 'how' is the method to do it.
What do we design after specifying a function?
An algorithm for the function.
What programming language is mentioned for implementation?
Python.
Is the software development process purely linear?
No, it often involves going back and re-doing parts of previous stages.
What may highlight problems in the design process?
The design process itself may highlight problems or gaps.
What is a function in the mathematical sense?
A specification of what rather than how.
What additional aspect does the term 'function' have in programming languages?
It often includes code or an algorithm for computation.
What is emphasized when using the term 'mathematical function'?
It indicates that no code or algorithm is given.
What is a function definition format?
name: domain name(x) codomain, precise description of the function value, in terms of x.
What does the function f: R → R represent?
It gives squares of real numbers: f(x) = x².
What is the domain in the function f: R → R?
The domain is R (real numbers).
What is the codomain of the function f: R → R?
The codomain is also R (real numbers).
What is a common way to state a function definition?
The function f : R → R is defined by f(x) = x².
What does the mapping arrow (→) in a function rule indicate?
It differs from the ordinary arrow → that goes from domain to codomain.
What is the alternative form for specifying the rule of a function?
X → precise description of the function value, in terms of x.
Sei sicuro di voler eliminare 0 flashcard? Questa azione non può essere annullata.
Seleziona i tag da rimuovere da 0 flashcard selezionata(e):
Caricamento tag...