DIscrete Math Review

Proposition

A statement that can be evaluated as true or false. Never both.

¬

negation, NOT, negates the proposition

∧

conjunction, AND, both must be true

∨

disjunction, OR, either one must be true

⊕

exclusive or, XOR, only 1 must be true (both can’t be true)

=>

implication, CONDITIONAL, if p is false, q is always true; if p is true, check q for its truth value.

<=>

biconditional, IFF, both truth values must match, TT or FF

¬q => ¬p

contrapositive

¬p => ¬q

inverse

q => p

converse

p ∧ ¬p

contradiction, always false

p ∨ ¬p

tautology, always true

p ∧ q, p ∨ q

contigency, depends on truth values

Commutative Law (Propositions)

p ∨ q ≡ q ∨ p

Associative Law (Propositions)

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributive Law (Propositions)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

De Morgan’s Law (Propositions)

¬(p ∨ q) ≡ ¬p ∧ ¬q

Propositional Function P(x)

Plug in any x, get true or false as result

∀

universal quantifier, “for all”, all must satisfy P(x)

∃

existential quantifier, “there exists”, some satisfy P(x)

∃!

uniqueness quantifier, “there exists only 1”, only 1 satisfies P(x)

Argument

Premises with a conclusion.

Premises

A list of propositions assumed to be true

Modus Ponens
p => q
p

q (modus)

Modus Tollens
p => q
¬q

¬p

Hypothetical Syllogism
p => q
q => r

p => r

Disjunctive Syllogism
p v q
¬p

q

Conjunction
p
q

p ∧ q

Addition
p

p ∨ q

Simplification
p ∧ q

p OR q

Resolution
¬p ∨ r
p ∨ q

r ∨ q

Universal Instantiation
∀xP(x)

P(c) for any c

Existential Instantiation
∃xP(x)

P(c) for some c

Universal Generalization

P(c) for any c

∀xP(x)

Existential Generalization

P(c) for some c

∃xP(x)

Proof

A valid argument establishing the truth of some statement.

Direct Proof

Prove p => q; assume p is true, show q is true

Proof by Contrapositive

Prove p => q; assume ¬q is true, show ¬p is true

Proof by Contradiction

Prove p is true, assume ¬p => q, where q is always false

a ∈ A

a is an element of set A

∅

empty set

ℕ

natural numbers (0, 1, 2, 3 4…)

ℤ

integers (…-2, -1…1, 2, 3)

ℤ⁺

positive integers (1, 2, 3…)

ℚ

rational numbers (decimals/fractions)

ℝ

all real numbers

ℝ⁺

all positive real numbers

| A |

cardinality; number of unique elements in set A

A = B

All ∈ in A are in B

A ⊆ B

Every ∈ A is also ∈ B (subset)

A ⊂ B

Some ∈ E is also ∈ B (proper subset)

P(A)

power set; all subsets of A

A ∪ B

union, everything in A and B

A ∩ B

intersection, shared elements in A and B

A ⊕ B

symmetric difference, elements unique in A and B

A - B

difference, elements unique in A

A‾

complement, elements not in A

A×B

cortesian product, set of all pairs using elements from A and B

|A×B| =

|A| * |B|

|A ∪ B| =

|A| + |B| - |A ∩ B|

Commutative Law (Sets)

A ∪ B = B ∪ A

Associative Law (Sets)

(A ∪ B) ∪ C = A ∪ (B ∪ C)

Complement Law

(A‾)‾ = A

Distribution Law (Sets)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

De Morgan’s Law (Sets)

(A ∪ B)‾ = A‾ ∩ B‾

f: A → B

Every element in A is mapped to an output element in B.

A

domain

B

codomain

Range

Set of all images of A

Injective

ONE-TO-ONE, no 2 outputs are shared

Surjective

ONTO, every element in B is mapped to

Bijective

Both injective and surjective; domain = codomain

f^-1 = B → A

inverse; exists only if function is bijective.
1) Change f(x) to y
2) Switch x and y
3) Solve for new y

⌈

ceiling, round up

⌋

floor, round down

Geometric Sequence

ar⁰ + ar¹ + ar² + …

Arithmetic Sequence

a + 0*d, a + 1*d, a + 2*d + …

Σc*a_i

c * Σa_i

Σa_i + b_i

Σa_i + Σb_i

Σrⁱ , r = 1

n + 1

Σrⁱ , r ≠ 1

(rⁿ⁺¹ - 1)/(r-1)

Σa_j - a_j-1

a_n - a₀

Σ(a + kd) 

a(n+1) + d*((n(n+1))/2)

O(g(x))

Upper bound

Θ(g(x))

Bounded above and below

Ω(g(x))

Lower bound

Linear Search O(n)

Move down the list until desired element is found

Binary Search O(log n)

Find midpoint, compare to desired element, and shrink the list until its found

Bubble Sort O(n²)

Look at first 2 elements, biggest # bubbles up to the top, continue…

Selection Sort O(n²)

Find the smallest element, swap with the element in the 1st position, continue…

Insertion Sort O(n²)

Look at the 2nd element, compare it to the 1st element. If smaller, switch them. Next, look at the 3rd element and compare it to the elements before it. Insert it in the correct position, then continue…

a | b

iff b = ac. (a is a factor of b)

if a | b and a | c

a | (b + c)

if a | b

a | cb

if a | b and b | c

a | c

Division Algorithm

a = qd + r

a

dividend

d

divisor

q

quotient, = a/d⌋