Sets: N = natural numbers = {0,1 ,2, 3...}, Z = integers = {..., -3, -2, -1, 0, 1, 2, 3...} positive integers = {1,2, 3...} R = set of real numbers, R+ = set of
positive real numbers, C = set of complex numbers, Q = set of rational numbers, closed interval: [a, b], open interval: (a, b) , ∅ ≠ { ∅ } ,
cardinality=|A|, cardinality of the power set P(A) is 2ⁿ , A – B = A ∩`B , Inclusion-Exclusion:|A ∪ B| = |A| + | B| − |A ∩ B|
Proof de Morgan:
Functions: ƒ: A → B: A is called the domain, B is called the co-domain
Injective: if ƒ(x)=ƒ(y) and x, y ∈A with x ≠ y, then x=y
Not injective: elements x, y∈A such that x ≠ y and ƒ(x)=ƒ(y)
Surjective: an element y∈B and find element x∈A such that ƒ(x)=y
Not surjective: an element y∈B such that ƒ(x)≠y for all x∈A
floor ceiling
Propositional logic: p->q=if p, then q =
• p implies q • q whenever p
• if p, q • p is sufficient for q
• p only if q • q follows from p
• q unless ¬p • q is necessary for p
• q when p • a necessary condition for p is q
• q if p • a sufficient condition for q is p
converse: q →p contrapositive: ¬q → ¬ p Inverse: ¬ p → ¬ q, Precedence of Logical Operators: ¬ , Ù , Ú , ® , «
predicate logic: ¬"x J(x) and $x ¬J(x) are equivalent, ¬$ x J(x) and " x ¬J(x) are equivalent
Modus Ponens: Modus Tollens:
Hypothetical Syllogism: Disjunctive Syllogism:
Addition: Simplification: Conjunction: Resolution:
Universal Instantiation (UI): Universal Generalization (UG):
Existential Instantiation (EI): Existential Generalization(EG):
Boolean algebra: + is (OR), • is (AND)
and or
Sum-of-Products Expansion: add the expressions that have
the value 1
Proofs: The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an integer k, such that n = 2k + 1.
Proof by Contraposition: Assume ¬q and show ¬p is also true.
Proof by Contradiction: To prove p, assume ¬p and derive a contradiction.
induction:
1) Base Step: Show that P (1) is true,
2) inductive hypnosis: assume p(k) is true
3) Inductive Step: Show that P(k) → P (k + 1) is true for all positive integers k
Recursion: an=rn depending on the degree of the equation is the number of r solutions “an-k has k solutions”
Ex:an-1+2an-2 is a degree 2
1)substitute an with rn in the whole equation 2) let the equation = 0 3) divide by the most degree (smallest r power) 4) solve for r
the general equation is an = alfa1(r1)^n+ alfa2(r2)^n+… (depends on the degree)
if r1 = r2 then the general equation is an = alfa1(r)^n+ alfa2 n(r)^n
positive real numbers, C = set of complex numbers, Q = set of rational numbers, closed interval: [a, b], open interval: (a, b) , ∅ ≠ { ∅ } ,
cardinality=|A|, cardinality of the power set P(A) is 2ⁿ , A – B = A ∩`B , Inclusion-Exclusion:|A ∪ B| = |A| + | B| − |A ∩ B|
Proof de Morgan:
Functions: ƒ: A → B: A is called the domain, B is called the co-domain
Injective: if ƒ(x)=ƒ(y) and x, y ∈A with x ≠ y, then x=y
Not injective: elements x, y∈A such that x ≠ y and ƒ(x)=ƒ(y)
Surjective: an element y∈B and find element x∈A such that ƒ(x)=y
Not surjective: an element y∈B such that ƒ(x)≠y for all x∈A
floor ceiling
Propositional logic: p->q=if p, then q =
• p implies q • q whenever p
• if p, q • p is sufficient for q
• p only if q • q follows from p
• q unless ¬p • q is necessary for p
• q when p • a necessary condition for p is q
• q if p • a sufficient condition for q is p
converse: q →p contrapositive: ¬q → ¬ p Inverse: ¬ p → ¬ q, Precedence of Logical Operators: ¬ , Ù , Ú , ® , «
predicate logic: ¬"x J(x) and $x ¬J(x) are equivalent, ¬$ x J(x) and " x ¬J(x) are equivalent
Modus Ponens: Modus Tollens:
Hypothetical Syllogism: Disjunctive Syllogism:
Addition: Simplification: Conjunction: Resolution:
Universal Instantiation (UI): Universal Generalization (UG):
Existential Instantiation (EI): Existential Generalization(EG):
Boolean algebra: + is (OR), • is (AND)
and or
Sum-of-Products Expansion: add the expressions that have
the value 1
Proofs: The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an integer k, such that n = 2k + 1.
Proof by Contraposition: Assume ¬q and show ¬p is also true.
Proof by Contradiction: To prove p, assume ¬p and derive a contradiction.
induction:
1) Base Step: Show that P (1) is true,
2) inductive hypnosis: assume p(k) is true
3) Inductive Step: Show that P(k) → P (k + 1) is true for all positive integers k
Recursion: an=rn depending on the degree of the equation is the number of r solutions “an-k has k solutions”
Ex:an-1+2an-2 is a degree 2
1)substitute an with rn in the whole equation 2) let the equation = 0 3) divide by the most degree (smallest r power) 4) solve for r
the general equation is an = alfa1(r1)^n+ alfa2(r2)^n+… (depends on the degree)
if r1 = r2 then the general equation is an = alfa1(r)^n+ alfa2 n(r)^n
