Final Exam Flashcards
What is the disjoint union ⊔?
Is the union of A and B when A ∩ B = ∅. i.e. A and B are disjoint.
What is the output of the Euclidean Algorithm?
the gcd
What is the gcd?
If m and n are non-zero integers, then the largest integer which is a common divisor of both m and n is called the greatest common divisor of m and n.
Define integer division.
The integer d is said to divide the integer a if
a = d . t for some integer t.
d is a divisor of a
a is a multiple of d
Define common divisor.
d is said to be the common divisor of integer m and n if d | m and d | n
Informal defenition of sets.
A set is a collection of objects. The objects of a set are called the elements of the set.
Define the extensionality principal.
Two sets are equal iff they have the same elements.
i.e. S = T iff x ∈ S implies x ∈ T and x ∈ T implies x ∈ S
Define subset.
A set T is a subset of a set S if every element of T is also an element of S.
Define proper subset. Give the symbol.
T is a proper subset of S if T is a subset of S and T is not equal to S.
⊊
What does it mean to say two sets A and B are disjoint?
A ∩ B = ∅
What is the notation for the set theoretic difference?
A \ B
What is a set?
A set is determined completely by its elements.
What is the null set?
A set with no elements
Give the 5 logical laws of sets.
x ∈ A ∪ B iff x ∈ A or x ∈ B.
x ∈ A ∩ B iff x ∈ A and x ∈ B.
x ∈ A \ B iff x ∈ A and x ∉ B.
A ⊂ B iff x ∈ A implies x ∈ B.
A = B iff x ∈ A implies x ∈ B and x ∈ B implies x ∈ A
What is the notation for restricted comprehension?
{x ∈ S | c(x)} ⊆ S
What is unrestricted comprehension, why is this a problem?
This is when we drop the requirement that x ∈ S. This leads to problems as Ω := {x | x is a set not containing itself} tells us that Ω ∈ Ω and Ω ∉ Ω which is a contradiction. The element Ω cannot be both in the set and out of it.
What rule prevents unrestricted comprehension?
Axiomatic Rules for Set Theory. A set cannot be an element of itself. x ∉ x always.
What is U?
The ambient set containing all possibilities. So for every A ⊂ U, we can define A^c = U \ A.
What is a proposition?
Is a declarative sentence that is either true or false.
What is the symbol for XOR?
⊕
Define logical equivalence.
Two compound propositions are logically equivalent if their equivalence is a tautology under all possible assignments of truth values to their prime propositions.
What are the two absorption laws?
(P ^ Q) v Q = Q
(P v Q) ^ Q = Q
What is the role for the part P and the part Q in P implies Q.
P is the hypothesis
Q is the conclusion
What is the equivalence law?
P <-> Q = (P -> Q) ^ (Q -> P)
What is the converse of P -> Q?
Q -> P
What is a Mersenne Prime?
A prime of the form (2^n) - 1
What is iff? Split it in two and give the names of each part.
If and only if is an equivalence relation.
Hence P <-> Q is the same as
P -> Q ^ Q->P
P -> Q is the ONLY IF part and means it is NECESSARY that Q is true for P to be true.
Q -> P is the IF part and means it is SUFFICIENT that Q is true for P.
Create a predicate to represent the fact that the square of any real number is non-negative.
∀x ∈ R : x^2 >= 0
Create a predicate to represent the fact that 16 is a square integer.
∃n ∈ Z : n^2 = 16
What is the truth set of P (on S)?
{x ∈ S | P(x) }
All the elements of S that satisfy the predicate P.
Translate the following predicates into truth sets.
P(x) ^ Q(x)
P(x) v Q(x)
¬P(x)
P(x) ^ ¬Q(x)
P(x) ⊕ Q(x) (Give another name for this one)
A ∩ B
A ∪ B
A^c = U \ A
A ∩ B^c = A \ B
(A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A) (Symmetric Sum)
where A = {x ∈ U | P(x)}
B = {x ∈ U | Q(x)}
Constant Rule for summation.
n sum k = m (c . ak) = c (n sum k = m (ak) )
Sum Rule for summation.
n sum k = m (ak + bk) is equivalent to
(n sum k = m (ak) ) +
(n sum k = m (bk) )
Sum of a constant rule.
n sum k = m (c) is equivalent to
(n - m + 1)c
Sum of numbers between 1 and n.
n (n + 1) / 2
Sum of numbers between 1^2 and n^2. (n sum k=1 (k^2) )
n(n + 1)(2n + 1) / 6
Rule for shifting delimiters.
Apply this rule to 30 sum k=15 (2k + 3)
l + s sum n = k + s (A(n-s))
is equivalent to
l sum n=k (An)
Also should add a new variable i = n + s
E.g. = 16 sum i=1 (2i + 31) where i is equal to k - 14.
Rule for geometric sum.
(n sum k=0 (a^k))
a^(n+1) - 1 / (a - 1)
Is a sum i=1 b sum j=1 (2i + 3j)
the same as b sum j=1 a sum i=1 (2i + 3j)?
Yes
Rule for nested sums with products.
n sum i=1 (Ai) * m sum j=1 (Bj)
n sum i=1 m sum j=1 (Ai)(Bj)
Explain the three principles of positivity.
Trichotomy: for every real x, exactly one of the following is true x > 0, x = 0, -x > 0.
Closedness: the sum and the product of positive numbers is positive.
Archimedean Axiom: For every real number x, there exists an integer n such that n - x is positive.
What is the strictly less than sign?
<
Define binary relation?
A binary relation on a set S is a predicate P(x, y) with x, y free variables ranging over S.
Define total order.
A total order <= on a set is a binary relation such that all the following holds.
Reflexivity: For all s elements of S, s <= s
Anti-Symmetry: For all s and t elements of S, [s <= t ^ t <= s ] -> s = t
Transitivity: For all s, t and u elements of S, [s <= t ^ t <= u] -> (s <= u)
Strong Connectedness: For all s and t elements of S, (s <= t) v (t <= s).
What bracket is used for (a) less than and equal to range and (b) less than range
[ is inclusive
( is exclusive
|2x + 3| <= 5. Expand the inequality.
-5 <= 2x + 3 <= 5
Should infinity be included for infinite intervals. How should the range of an infinite set be described?
No.
(-∞, ∞) := R
Define a function.
Let A and B be two sets, A function f from A to B assigns to every element a ∈ A a unique element f(a) ∈ B.
Define extensionality for functions.
Two functions f: A -> B and g: X -> Y are considered to be equal iff,
A = X (same domains)
B = Y (same codomains)
For all a ∈ A f(a) = g(a) (Same results)
Define the image of a function f: A -> B.
Is the set im(f) ;= {b ∈ B | ∃a ∈ A : f(a) = b} = {f(a) ∈ B | a ∈ A} ⊂ B
Condition for surjectivity.
im(g) = codom(g)
Define a real function.
A -> B is a real function if A ⊂ R and B ⊂ R
Define the natural domain.
The natural domain D(f) of an algebraic formula f(x) is the set of real numbers x for which f(x) evaluates to a unique real number.
What are the four essential laws for finding the solutions to inequalities?
ab = 0 <-> a = 0 v b = 0
a/b = 0 <-> a = 0 ^ b != 0
ab > 0 <-> (a > 0 ^ b > 0) v (a < 0 ^ b < 0) <-> a/b > 0
ab < 0 <-> (a > 0 ^ b < 0) v (a < 0 ^ b > 0) <-> a/b < 0
What does A subset B imply?
(x ∈ A) -> (x ∈ B)
What is |a| < b?
-b < a ^ a < b
What is |a| > b?
a > b v -a>b
Define injective. Give another name.
Explain it.
A function is said to be injective if for all a1 and a2 elements of the domain. f(a1) = f(a2) implies a1 = a2.
Also called ‘one to one’
Two different inputs yield different outputs.
Define surjective. Give another name. Explain it.
A function is said to be surjective if for all b elements of codomain, some a exists where f(a) = b.
Also called ‘onto’.
Im(f) = codom(f)
What is the co-restriction to an arbitrary function f:A -> B?
f~ : A –> im(f)
Makes the arbitrary function always surjective.
Define bijective. Explain it.
A function is bijective if it is both surjective and injective.
All inputs map to exactly one output. All outputs are mapped to by exactly one input. One to one correspondence.
Under what condition can two function f and g be made into composites?
codom(f) = dom(g)
Define composities.
For functions f and g where codom(f) = dom(g). g ∘ f is the composite or g(f(x))
Define the identity function.
For any set S, the identity function on S is just the function. ids : S –> S
Define inverse function.
f: A –> B and g: B –> A
For all a elements of A : g(f(a)) = a
For all b elements of B : f(g(b)) = b
Describe the graph of 2^x.
Describe the differences in the graphs of 3^x and (1/2)^x
Intercepts the y-axis at y=1, slopes downward to the left.
3^x has a steeper slope down to the left, is smaller at values below 0 and greater above.
(1/2)^x is the reflection of 2^x through the y-axis and slopes down to the right.
Describe the graph of log2(x). Describe the differences between the graph of log5(x).
log2(x) intercepts the x axis at x=1. It slopes from high values of y to low values of y without crossing the y-axis.
log5(x) intercepts the same but is steeper as it slopes from high y-values to low y-values.
Expand (a1 * a2)^x
a1^x * a2^x
State the change of bases rule in logarithms.
loga(y) = logb(y) / logb(a)
What is the floor of x?
The largest integer less or equal to x.
What is the ceiling of x?
The smallest integer greater or equal to x
How many decimal digits does a positive integer have?
floor(log10(n)) + 1
What is the highest power of p dividing N!?
floor(N/p) + floor(N/p^2)+ floor(N/p^3) + ….
How many multiples of m are there among 1 to N integers.
floor(N/m)
What does the lower limit need to be to sum a geometric sum a^k?
n=0
