Propositions
Different Ways of Expressing p → q |
q unless ¬p, q if p, q whenever p, q follows from p, p only if q, q when p, p is sufficient for q, q is necessary for p. |
Proposition |
True/False, with no variables. Ex) The sky is blue = Prop. n+1 is even Not prop bc n is unknown. |
Tautology |
a proposition which is always true. Ex) p ∨¬ p |
contradiction |
a proposition which is always false. Ex) p ∧¬ p |
contingency |
a proposition which is neither a tautology nor a contradiction, such as p |
satisfiable |
at least one truth table is true. |
p -> q |
Only false when p = T q = F. everthing else true. |
converse |
q -> p |
inverse |
-p -> -q |
contrapositive |
-q -> -p |
p <-> q |
if and only if. true if and only if p and q have the same truth value ex) p = t q = t or p = f q = f |
Logically equivalent |
p≡q. all truth values have to be the equal aka same results. |
Negate Quantifiers |
¬∀xP (x) ≡ ∃x ¬P (x). ¬∃xQ(x) ≡ ∀x ¬Q(x) |
Functions
function from A to B. f: A -> B |
an assignment of exactly one element of B to each element of A |
domain of f |
the set A, where f is a function from A to B. ans is A |
codomain of f |
the set B, where f is a function from A to B. ans is B |
b is the image of a under f |
b = f (a). "what does this map to" |
a is a pre-image of b under f |
f (a) = b. "what values map to this". |
range |
values of codomain that were mapped to by domain. |
Injective Function (one to one) |
a function f is one-to-one if and only if f (a) =/= f (b) whenever a =/= b. each value in the range is mapped to exactly one element of domain. (each range value is mapped once). ∀a∀b(f (a) = f (b) → a = b) or equivalently ∀a∀b(a =/= b → f (a) =/= f (b)) |
Surjective function (onto) |
every element in codomain maps to at least one element in domain. (each element in codomain is mapped). if and only if for every element b ∈ B there is an element a ∈ A with f (a) = b |
To show that f is injective |
f(x1)=f(x2) => x1=x2. x1=/=x2 => f(x1)=/=f(x2). ex) f(a) = f(b) => a=b. ex) f(x) = x+3. f(a) = 7, a+3=7, a=4. f(b)=7. b=4. f(a)=f(b) a=b, 1to1 |
To show that f is not injective |
Find particular elements x, y ∈ A such that x /= y and f (x) = f (y) |
To show that f is surjective |
solve in terms of x. pick 2 random ys, if x eqns comes back in domain, surjective. domain matters, Z, R, N has to map x and y in same. ex) f(x)=x+3. f(4)=7, f(5)=8. always mapped, onto. |
To show that f is not surjective |
Find a particular y ∈ B such that f (x) = y for all x ∈ A |
Bijective function |
all range is mapped to and mapped to once (injective and surjective) |
Inverse |
has to be bijective. f^-1(y) = x if and only if f(x) = y. because this is both 1to1 and onto, its a bijection, therefore invertible. |
composition of fns |
f(g(a)) or f o g(a) |
floor/ceiling |
bracketwithlow only/highonly. round down/up to nearest integer. ex) -2.2 floor = -3. 5.5 ceil = 6. |
properties |
x floor = n if and only if n ≤ x < n + 1. x ciel = n if and only if n − 1 < x ≤ n. x floor = n if and only if x − 1 < n ≤ x. x ciel = n if and only if x ≤ n < x + 1. x − 1 < floorx ≤ x ≤ cielx < x + 1. floorx = −cielx. cielx = -floorx. ciel(x + n) = cielx + n. opp of last floor |
ex) let f(x) = floor((x^2)/2). find f(S) if S={0,1,2,3} |
f(0) = 0, f(1) = 0. f(2) = 2, f(3) = 4 |
equal functions |
Two functions are equal when they have the same domain, the same codomain and map each element of the domain to the same element of the codomain |
|
|
Proofs
Direct Proof |
assume p is true, prove q. p => q. Always start with this then try contraposition. |
Proof by contraposition |
assume ~q is true, prove ~p. (~q => ~p) equals (p => q) |
Vacuous proof |
if we can show that p is false, then we have a proof, called a vacuous proof, of the conditional statement p → q |
Proof by contradiction |
Assume ~p is true, find contradiction, therefore ~p is true. prove that p is true if we can show that ¬p → (r ∧ ¬r) is true for some proposition r |
Counterexample |
to show that a statement of the form ∀xP (x) is false, we need only find a counterexample. |
Proof by exhuastion |
ex: Prove that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4. Prove by doing n = 1,2,3,4 |
Proof by cases |
ex: Prove that if n is an integer, then n2 ≥ n. Case (i): When n = 0. Case (ii): When n ≥ 1. Case (iii): In this case n ≤ −1 |
Constructive Existence Proof |
∃xP(x). To find if P(x) exists, show an example P(c) = True |
Nonconstructive Existence Proof |
Assume no values makes P(x) true. Then contradict. |
UNIQUENESS proof |
When asked for unique, prove exists, then unique. ex: x exists, x=/=y , so y doesnt have that property, therefore x is unique. |
without loss of generality |
an assumption in a proof that makes it possible to prove a theorem by reducing the number of cases to consider in the proof |
|
|
Sets
Element of set |
a ∈ A, a ∈/ A |
roster method |
V = {a, e, i, o, u}, O = {1, 3, 5, 7, 9}. |
set builder notation |
ex: the set O of all odd positive integers less than 10 can be written as: O = {x ∈ Z+ | x is odd and x < 10}. ex) A = {𝑥|𝑥 ≥ −1 ∧ 𝑥 < 1}. ex) {x | P(x)| |
Interval Notation |
[-2,8) |
Natural numbers N |
N = {0, 1, 2, 3, . . .} |
Integers Z |
Z = {. . . , −2, −1, 0, 1, 2, . . .} |
Positive Integers Z+ |
Z+ = {1, 2, 3, . . .} |
Rational Numbers Q |
Q = {p/q | p ∈ Z, q ∈ Z, and q =/= 0} |
Real Numbers R |
All previous sets (N, Z, Q) |
R+ |
positive real numbers |
Complex numbers C |
{a+bi, ...} |
Equal Sets |
Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets, then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B). We write A = B if A and B are equal sets. Dont matter if its {1,3,3,3,2,2,3,}, still {1,3,2}. Also dont matter order. |
Null/ Empty Set |
∅, nothing. {}. |
{∅} |
1 element |
Singleton set |
One element. |
Universal Set U |
Universe in context of statement. Example vowels in alphabet: U = {z,y,x,w, ...}, A = {a,e,i,o,u} A is a subset of U. |
Subset |
∀x(x ∈ A → x ∈ B). Ex) the set A is a subset of B if and only if every element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of the set B. Ex) A = {1,2,3}, B = {1,2,3,4}, A ⊆ B. |
Showing that A is a Subset of B |
To show that A ⊆ B, show that if x belongs to A then x also belongs to B. |
Showing that A is Not a Subset of B |
To show that A ⊆/ B, find a single x ∈ A such that x ∈/ B. |
Showing Two Sets are Equal |
To see if A = B, Show A ⊆ B and B ⊆ A |
proper subset |
∀x(x ∈ A → x ∈ B) ∧ ∃x(x ∈ B ∧ x ∈ A)A ⊆ B but A =/= B. B contains an element not in A. Ex) A = {1,2,3}, B= {1,2,3,4}. 4 makes it proper subset. |
Cardinality |
|A| Distinct elements of set. A = {1,2,3,3,4,4} |A| = 4 |
Power Set |
the power set of S is the set of all subsets of the set S. The power set of S is denoted by P(S). Ex) A = {1,2,3}. P(A) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}. Ex) P({∅}) = {∅, {∅}} |
Cardinality of Power Set |
2^n, n is elements. |
Tuple |
(a1,a2,a3, ..., an) Ordered. Ex) (5,2) =/= (2,5) |
Cartesian Product |
{(a, b) | a ∈ A ∧ b ∈ B}. The Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Ex) A = {0,1} B = {2,3,4}, A x B = {(0,2),(0,3),(0,4),(1,2),(1,3),(1,4)} |
Truth Set |
P(x): abs(x) = 3. Truth Set of P(x) = {3,-3} |
|
|
Set Operations
Union |
A ∪ B = {x | x ∈ A ∨ x ∈ B}. Ex) A = {1,4,7} B = {4,5,6}. A ∪ B = {1,4,5,6,7} |
Intersection |
A ∩ B = {x | x ∈ A ∧ x ∈ B}. Ex) A = {1,4,7} B = {4,5,6}. A ∩ B = {4}. |
disjoint |
If A ∩ B = nothing, A and B are disjoint. |
principle of inclusion–exclusion |A ∪ B| = |A| + |B| − |A ∩ B| |
ex) A = {1,2,3,4,5}, B ={4,5,6,7,8}. }A u B| = |A| + |B| -|A n B} = 5 + 5 - 2 = 8 |
A − B, difference of A and B |
A - B = A ∩ B. {x | x ∈ A ∧ x /∈ B} Elements in A that are not in B. Ex) {1, 3, 5} − {1, 2, 3} = {5}. This is different from the difference of {1, 2, 3} and {1, 3, 5}, which is the set {2}. |
Complement of A, A^c |
{x ∈ U | x /∈ A} Everything in the universe context thats not in A. Ex) U = {1,2,3,4}. A = {2} B = {3}. A^c = {1,3,4} |
U = ℝ A = {𝑥|𝑥 ≥ −1 ∧ 𝑥 < 1}, B ={𝑥|𝑥 < 0 ∨ 𝑥 ≥ 2} |
𝐴 ∪ 𝐵 = {𝑥|𝑥 < 1 ∨ 𝑥 ≥ 2}. 𝐴 ∩ 𝐵 = {𝑥|𝑥 < 0 ∧ 𝑥 ≥ −1}. 𝐴^c = {𝑥|𝑥 < −1 ∨ 𝑥 ≥ 1}. |
Identity, , , , , , , absorbtion, |
A ∩ U = A. A ∪ ∅ = A. |
domination |
A ∪ U = U. A ∩ ∅ = ∅ |
idempotent |
A ∪ A = A. A ∩ A = A |
complementation |
(Ac)c = A |
commutative |
A ∪ B = B ∪ A. A ∩ B = B ∩ A |
associative |
A ∪ (B ∪ C) = (A ∪ B) ∪ C. A ∩ (B ∩ C) = (A ∩ B) ∩ C |
distributive |
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
de morgans |
(A n b)c = Ac u Bc. (A U B)c = Ac n Bc |
absorption |
A ∪ (A ∩ B) = A. A ∩ (A ∪ B) = A. |
complement |
A ∪ Ac = U. A ∩ Ac = ∅. |
countable |
a set that either is finite or can be placed in one-to-one correspondence with the set of positive integers. To be countable, there must exist a 1-1 and onto (bijection) between the set and ℕ! (i.e. ℤ+) |
Ex) Show that the set of positive even integers E is countable set. |
Let f(x) = 2x. Then f is a bijection from N to E since f is both one-to-one and onto. To show that it is one-to-one, suppose that f( n) = f( m). Then 2 n = 2 m, and so n = m. To see that it is onto, suppose that t is an even positive integer. Then t = 2k for some positive integer k and f(k) = t |
|
