Discrete Test 2 review

De Morgan’s Law

¬(P ∧ Q) ≡ ¬P ∨ ¬Q
not (P and Q), same as not P, or not Q

Distributive Law

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p and (q or r), same as (p and q) or (p and r)

Contrapositive

(p → q) ≡ (¬q → ¬p)

If p then q, same as if not q then not p

Converse

Converse of (p → q) is (q → p)
If p then q, converse is if q then p

Inverse

Inverse of (p → q) is (¬p → ¬q)
If p then q, inverse is if not p then not q

p only if q same as…

if p then q

Biconditional

p ↔ q ≡ (p → q) ∧ (q → p)
p if and only if q

if p then q, and if q then p

necessary condition

In p → q: “If it’s raining, then the ground is wet.”

“the ground is wet” in necessary

q is necessary for p

sufficient condition

In p → q: “If it’s raining, then the ground is wet.”

“it’s raining” is sufficient

p is sufficient for q

∀

for all

universal quantifier

∃

there exist

existential quantifier

a | b

“a divides b”, b is a multiple of a

example: 3 | 12 because 12 = 3 · 4

17 ≡ 5 (mod 12)

12 divides (17 − 5) = 12

23 ≡ 2 (mod 7)

7 divides (23 − 2) = 21

−1 ≡ 11 (mod 12)

12 divides (−1 − 11) = −12