Week 3

Key Logical Equivalences

A way to prove equivalency besides using truth tables

∧ and ∨ are negators of each other

Identity Laws:

$p\wedge T\equiv p$ and $p\vee F\equiv p$

Domination Laws:

$p\vee T\equiv T$ and $p\wedge F\equiv F$

demonstration:

True is dominant in or statements (you just need one True for the whole thing to return True)

Idempotent Laws:

$p\vee p\equiv p$ and $p\wedge p\equiv p$

Double Negation Laws:

$\neg (\neg p)\equiv p$

demonstration:

negating a negation of a proposition gives back the proposition

Negation Laws

$p\vee \neg p\equiv T$ and $p\wedge \neg p\equiv F$

demonstration:

something or the lack of it will always return True
something and the lack of it will always return False

Commutative Laws:

$p\vee q\equiv q\vee p$ and $p\wedge q\equiv q\wedge p$

demonstration:

order doesn’t matter

Associative Laws:

Distributive Laws:

$(p\vee q(q\wedge r))\equiv (p\vee q)\wedge (q\vee r)$
$(p\wedge q(q\vee r))\equiv (p\wedge q)\vee (q\wedge r)$

Absorption Laws:

Predicate Logic vs Propositional

Predicate logic can have multiple truth values
Ex: Let x + y = z. be denoted by R(x,y,z) where U for all three is integers
4 + 3 = 7 -> T
1 + -2 = 5 -> F

Quantifier Symbols:

∀ = for all
∃ = there is at least one
If ∀ is True, ∃ is definitely `True