Discrete Math formula sheet

12 formulas · what each one means · a free lesson for each

steplyclass.com/formula-sheets/discrete-math/ · free, step-by-step lessons for every formula

Logic

Implication

p → q is false only when p is true and q is false

De Morgan's laws

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

Implication as or

p → q ≡ ¬p ∨ q

Contrapositive

p → q ≡ ¬q → ¬p

Negating quantifiers

¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)

Induction

true for n = 1, and true for k → true for k + 1

Congruence

a ≡ b (mod n) ⇔ n divides a − b

Same remainder when divided by n.Lesson: Remainders →

Mod of a product

ab mod n = (a mod n)(b mod n) mod n

Work with the remainders, keep the numbers small.Lesson: Powers mod n, last digits →

Euclid's algorithm

gcd(a, b) = gcd(b, a mod b)

First-order recurrence

a_n = r a_n−1 → a_n = a₀ rⁿ

Second-order recurrence

a_n = c₁ a_n−1 + c₂ a_n−2 → r² = c₁ r + c₂

Euler path

0 or 2 odd vertices

0 odd: an Euler circuit; 2 odd: start at one, end at the other.Lesson: Euler paths →