|
Table 1 Logical Equivalencies For the operation that corresponds to conjunction (Ù) of propositions we will use the raised dot (×). Sometimes we will use juxtaposition of the variables. Thus xy will have the same meaning as x×y which is the same as x Ù y. This operator is referred to as the meet of "x and y".For the operation that corresponds to disjunction (Ú) of propositions we will use the + symbol. x + y is referred to as the join of "x and y". Given any statement variables x, y, and z, a tautology 1 and a contradiction 0, (Ù = ×, Ú = +) the following logical equivalencies hold: |
||
|
1. Commutative laws: |
x × y = y × x |
x + y = y + x |
|
2. Associative laws: |
(x × y) × z = x × (y × z) |
(x + y) + z = x + (y + z) |
|
3. Distributive laws: |
x × (y + z)= (x × y)+ (x × z) |
x + (y × z)= (x + y) × (x + z) |
|
4. Identity laws: |
x × 1 = x |
x + 0 = x |
|
5. Negation laws: |
x + x' = 1 |
x × x' = 0 |
|
6. Double negative law: |
(x')' = x |
|
|
7. Idempotent laws: |
x × x = x |
x + x = x |
|
8. De Morgan's laws: |
(x × y)' = x' + y' |
(x + y)' = x' × y' |
|
9. Universal bound laws: |
x + 1 = 1 |
x × 0 = 0 |
|
10. Absorption laws: |
x + (x × y) = x |
x × (x + y) = x |
|
10.b |
(x × y) + (x × y') = x |
(x + y) × (x + y') = x |
|
11. Negations of 1 and 0: |
1' = 0 |
0' = 1 |
Example 1: Use the other laws in Table 1 to establish the absorption law (10):
x × (x + y) = x.
Do not use truth tables. A starting point is
|
x × (x + y) |
= |
(x × x)+ (x × y) |
by distribution, law 3 |
|
|
= |
x + (x × y) |
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
|
x × (x + y) |
= |
(x + 0) × (x + y) |
by identity, law 4 |
|
|
= |
x + (0 × y) |
by distribution, law 3 |
|
|
= |
x + 0 |
by boundness, law 9 |
|
|
= |
x |
by identity, law 4. |