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 preimage 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 onetoone 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 
(A^{c)}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 = A}c u B^{c. (A U B)}c = A^{c n B}c 
absorption 
A ∪ (A ∩ B) = A. A ∩ (A ∪ B) = A. 
complement 
A ∪ A^{c = U. A ∩ A}c = ∅. 
countable 
a set that either is finite or can be placed in onetoone correspondence with the set of positive integers. To be countable, there must exist a 11 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 onetoone and onto. To show that it is onetoone, 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 
