1 of 2

8.4 Three More Laws

Besides distribution, BOOL obeys other laws that have algebraic counterparts. For example, you know you can regroup addition, called associativity (Ass):

(2+3)+4 = 2+(3+4)

Associativity also holds for multiplication:

(2×3)×4 = 2×(3×4)

What matters is that the functions being regrouped are the same. The same does not hold for mixed functions:

(2×3)+4 ≠ 2×(3+4)

Associativity (Ass):
(P&Q)&R ⇔ P&(Q&R)
(PvQ)vR ⇔ Pv(QvR)

BOOL works the same way. Conjunction and disjunction both obey associativity laws.

(P&Q)&R ⇔ P&(Q&R)

(PvQ)vR ⇔ Pv(QvR)

What is key is that the connectives aren’t mixed: you already know that (P&Q)vR is not equivalent to P&(QvR).

Commutativity (Comm):
P&Q ⇔ Q&P
PvQ ⇔ QvP

Another law, commutativity (Comm), also holds in algebra and BOOL.

2+3 = 3+2

2×3 = 3×2

P&Q ⇔ Q&P

PvQ ⇔ QvP

Idempotence (Idemp):
P&P ⇔ P
PvP ⇔ P

Finally, BOOL obeys a law called idempotence (Idemp), which basically allows you to eliminate redundancies.

P&P ⇔ P

PvP ⇔ P

These three laws allow you to simplify sentences in ways that DeMorgan’s, Double Negation, and Distribution couldn’t.

For example, take the sentence (RvS)vS. Each step of the next problem makes a chain of equivalences using one of these three laws.

Here’s a harder one, in which we simplify the sentence ((P&Q)&P)&Q.

Congratulations: you have now learned all six of the key equivalences that hold in BOOL:

  1. DeMorgan’s (DeM)
  2. Double Negation (DN)
  3. Distribution (Dist)
  4. Associativity (Ass)
  5. Commutativity (Comm)
  6. Idempotence (Idemp)

When you cite these principles to justify lines in a chain of equivalences, you can just cite the abbreviated names. You should now take out a blank piece of paper and make sure you can write out each of those laws from memory. Do that once a day for a week and you will really know them.

Here’s a final problem to test your knowledge on.