We can use logical equivalences to reduce complex formulas into simpler ones.
Two new symbols
- T: Tautology (always 1)
- F: Contradiction (always 0)
Identity Law
p\;\wedge\;T\;\iff\;p\\p\;\vee\;F\;\iff\;p
P and True will be true when both P and Tautology are true.
P or False will be true when either is true, but False will never be true.
Domination Law
p\;\vee\;T\;\iff\;T\\p\wedge F\iff F
In domination law, P or True, P doesn’t really matter as T will always be true.
Example:
(p\;\vee\;F)\;\wedge\;(q\;\vee T)\\(p\;\vee\;F)\;\iff p\;=Identity Law\\(q\;\vee\;T)\iff T\;=DominationLaw\\p\;\wedge\;T\iff p\;=\;IdentityLaw\\Therefore:\\p
Therefore, we can replace the formula as they are logically equivalent with each other:
(p\;\vee\;F)\;\wedge\;(q\;\vee T)\;\iff p
Double Negation Law (DN)
\neg\neg p\;\iff p
If you reverse a value twice, it’s like not reversing at all.
DeMorgan’s Law (DEM)
\neg(p\;\wedge q)\iff \neg p\;\vee\;\neg q\\\neg(p\;\vee q)\iff\neg p\;\wedge\;\neg q
One thing to remember, distribute the negation and flip the connective.
Example:
\neg(\neg p\;\wedge\;\neg q)\\\neg\neg p\;\vee\;\neg\neg q\;=DeMorgan's\\p\;\vee\;q\;=\;Double Negation
Distributive Law
p\;\wedge\;(q\;\vee\;r)\;\iff (p\,\wedge\,q)\,\vee\,(p\,\wedge\,r)\\p\;\vee\;(q\;\wedge\;r)\iff\,(p\,\vee\,q)\,\wedge\,(p\,\vee\,r)
Review:=
3x(1+2)\;=(3x1)\,+\,(3x2)
Absorption Law
p\;\wedge\;(p\;\vee\;q)\;\iff p\\p\;\vee\;(p\;\wedge\;q)\;\iff p
Example:
\neg\neg p\,\vee ((p\,\vee\,F)\,\wedge\,\neg\neg q)\\p\,\vee\,((p\,\vee\,F)\,\wedge\,q)\;=DN*2\\p\,\vee\,(p\,\wedge\,q)\;=ID\\p\;=\;AbsorptionLaw
Commutativity Law
Flip the order.
p\,\wedge q\iff q\,\wedge\,p\\p\,\vee\,q\iff q\,\vee p
Associativity Law
Moving the order, just make sure they share the same connectives, otherwise we would be doing Distributive Law.
p\,\wedge\,(q\,\wedge\,r)\;\iff (p\,\wedge q)\,\wedge r\\p\,\vee\,(q\,\vee\,r)\;\iff (p\,\vee q)\,\vee r
Inverse Law
p\,\wedge \neg p \iff F\\p\,\vee\,\neg p\iff T
Conditional Law
p \rightarrow\,q\iff \neg p\,\vee q
Example:
Show:
(\neg (p\,\wedge q)\wedge q)\iff (\neg p\,\wedge q)
Whenever we see a ¬ outside of brackets, we can do DeMorgan’s first.
(\neg p\,\vee \neg q)\,\wedge q
Whenever we see opposite ∧ and ∨ inside and outside brackets, we can use Distributivity.
(q\,\wedge \neg p)\,\vee\,(q\,\wedge \neg q)
Next, we see:
q\,\wedge\,\neg q
This is Contradiction or always false, so we can do Inverse Law:
(q\,\wedge \neg p)\,\vee\,F
Now, anything with “or False” is Identity Law
(q\,\wedge \neg p)\,\vee\,F\;\iff q\,\wedge \neg p
Then using Commutativity Law, we can flip the order:
\neg p \wedge q
Therefore, the answer is TRUE:
(\neg (p\,\wedge q)\wedge q)\iff (\neg p\,\wedge q)
| Identity Law | ||
| Domination Law | ||
| Double Negation | ||
| DeMorgan’s Law | ||
| Distributive Law | ||
| Absorption Law | ||
| Commutativity Law | ||
| Associativity Law | ||
| Inverse Law | ||
| Conditional Law |
