|
Theorem 1.1.1 Logical Equivalences Given any statement variables p, q, and r, a tautology t and a contradiction c, the following logical equivalences hold: |
||
|
1. Commutative laws: |
p Ù q Û q Ù p |
p Ú q Û q Ú p |
|
2. Associative laws: |
(p Ù q) Ù r Û p Ù (q Ù r) |
(p Ú q) Ú r Û p Ú (q Ú r) |
|
3. Distributive laws: |
p Ù (q Ú r)Û (p Ù q)Ú (p Ù r) |
p Ú (q Ù r)Û (p Ú q)Ù (p Ú r) |
|
4. Identity laws: |
p Ù t Û p |
p Ú c Û p |
|
5. Negation laws: |
p Ú Ø p Û t |
p Ù Ø p Û c |
|
6. Double negative law: |
Ø (Ø p) Û p |
|
|
7. Idempotent laws: |
p Ù p Û p |
p Ú p Û p |
|
8. De Morgan's laws: |
Ø (p Ù q) Û Ø p Ú Ø q |
Ø (p Ú q) Û Ø p Ù Ø q |
|
9. Universal bound laws: |
p Ú t Û t |
p Ù c Û c |
|
10. Absorption laws: |
p Ú (p Ù q) Û p |
p Ù (p Ú q) Û p |
|
11. Negations of t and c: |
Ø t Û c |
Ø c Û t |
Example 1: Use the other laws in Theorem 1.1.1 to establish the absorption law (10):
p Ù (p Ú q) Û p.
Do not use truth tables. A starting point is
|
p Ù (p Ú q) |
Û |
(p Ù p)Ú (p Ù q) |
by distribution, law 3 |
|
Û |
p Ú (p Ù q) |
by idempotence, law 7 |
which turns out to be another version of the absorption law (10). Obviously, reapplying the distributive law becomes cyclic, and thus we got nowhere. This is one of those cases where a "trick" is needed. Such a trick is found by using the identity law (4). So
|
p Ù (p Ú q) |
Û |
(p Ú c)Ù (p Ú q) |
by identity, law 4 |
|
Û |
p Ú (c Ù q) |
by distribution, law 3 |
|
|
Û |
p Ú c |
by boundness, law 9 |
|
|
Û |
p |
by identity law 4. |
|