Skip to main content

Boolean Equivalences

Reasoning in propositional logic often involves showing that two different formulas express the same proposition (i.e., that two formulas are tautologically equivalent). For instance, ¬(P∨Q)\neg (P\vee Q) and (¬P∧¬Q)(\neg P\wedge\neg Q) are different formulas (they have different syntax trees), but they are tautologically equivalent. The following truth table shows that that these formulas are tautologically equivalent:

PPQQ¬(P∨Q)\neg (P\vee Q)(¬P∧¬Q)(\neg P\wedge \neg Q)
T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}
T\mathsf{T}F\mathsf{F}F\mathsf{F}F\mathsf{F}
F\mathsf{F}T\mathsf{T}F\mathsf{F}F\mathsf{F}
F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}

Note that ¬(P∨Q)\neg (P\vee Q) and (¬P∧¬Q)(\neg P\wedge\neg Q) are both assigned F\mathsf{F} is rows 1, 2, and 3 and are both assigned T\mathsf{T} in row 4.

The above fact is a special case of the more general observation that any formula of the form ¬(X∨Y)\neg(X\vee Y) is tautologically equivalent to any formula of the form (¬X∧¬Y)(\neg X\wedge\neg Y). Other instances of this general observation include:

  1. ¬(¬P∨Q)\neg (\neg P\vee Q) is tautologically equivalent to (¬¬P∧¬Q)(\neg\neg P \wedge \neg Q).
  2. ¬(¬P∨P)\neg (\neg P\vee P) is tautologically equivalent to (¬¬P∧¬P)(\neg\neg P \wedge \neg P).
  3. ¬((P→Q)∨(R∨P))\neg ((P\rightarrow Q)\vee (R\vee P)) is tautologically equivalent to (¬(P→Q)∧¬(R∨P))(\neg(P\rightarrow Q) \wedge \neg (R\vee P)).

For all formulas XX and YY, we write X≈YX\approx Y when XX and YY are tautologically equivalent. For instance,

  1. ¬(¬P∨Q)≈(¬¬P∧¬Q)\neg (\neg P\vee Q)\approx (\neg\neg P \wedge \neg Q);
  2. ¬(¬P∨P)≈(¬¬P∧¬P)\neg (\neg P\vee P)\approx(\neg\neg P \wedge \neg P); and
  3. ¬((P→Q)∨(R∨P))≈(¬(P→Q)∧¬(R∨P))\neg ((P\rightarrow Q)\vee (R\vee P))\approx(\neg(P\rightarrow Q) \wedge \neg (R\vee P))

These are all instances of the following general principle (called DeMorgan's Law):

¬(X∨Y)≈(¬X∧¬Y)\neg(X\vee Y)\approx(\neg X\wedge\neg Y)

In the following table, some key equivalences are displayed (these are known as axioms of Boolean algebra).

NameEquivalence
Double Negation¬¬X≈X\neg\neg X\approx X
DeMorgan's Rules¬(X∨Y)≈(¬X∧¬Y)\neg( X\vee Y)\approx (\neg X\wedge \neg Y)
¬(X∧Y)≈(¬X∨¬Y)\neg( X\wedge Y)\approx (\neg X\vee \neg Y)
Distribution(X∧(Y∨Z))≈((X∧Y)∨(X∧Z))(X\wedge( Y\vee Z))\approx ((X\wedge Y)\vee ( X\wedge Z))
(X∨(Y∧Z))≈((X∨Y)∧(X∨Z))(X\vee(Y\wedge Z))\approx ((X\vee Y)\wedge (X\vee Z))
Absorption(X∨(X∧Y)≈X(X\vee(X\wedge Y)\approx X
(X∧(X∨Y)≈X(X\wedge( X\vee Y)\approx X
Commutativity(X∧Y)≈(Y∧X)(X\wedge Y)\approx(Y\wedge X)
(X∨Y)≈(Y∨X)(X\vee Y)\approx(Y\vee X)
Conditional Definition(X→Y)≈(¬X∨Y)(X\rightarrow Y)\approx(\neg X\vee Y)

In addition to the above principles, the following general facts about tautological equivalence can be used to explain why two formulas are tautologically equivalent.

NameRule
ReflexivityX≈XX\approx X
SymmetryIf X≈YX\approx Y, then Y≈XY\approx X
TransitivityIf X≈YX\approx Y and Y≈ZY\approx Z, then X≈ZX\approx Z
TautologyIf YY is a tautology, then X≈(X∧Y)X\approx (X\wedge Y)
ContradictionIf YY is a contradiction, then X≈(X∨Y)X\approx (X\vee Y)

We can think of the above facts about tautological equivalence as inference rules that can be used with the axioms of Boolean algebra to explain why equivalences hold.

Example

We can use the above principles and rules to explain why the following equivalence holds.

P≈(P∧Q)∨(P∧¬Q).P \approx (P\wedge Q)\vee (P\wedge \neg Q).

We do this by listing some equivalences with brief explanations that reference the axioms and rules given above.

1.P≈P∧(Q∨¬Q)P\approx P\wedge(Q\vee\neg Q)
Explanation: Since Q∨¬QQ\vee\neg Q is a tautology, this is an instance of the Tautology Rule.
2.P∧(Q∨¬Q)≈(P∧Q)∨(P∧¬Q)P\wedge(Q\vee\neg Q)\approx (P\wedge Q)\vee (P\wedge\neg Q)
Explanation: This is an instance of one of the Distribution axioms.
3.P≈(P∧Q)∨(P∧¬Q)P\approx (P\wedge Q)\vee (P\wedge\neg Q)
Explanation: This follows from the Transitivity Rule since we established in step 1 that P≈P∧(Q∨¬Q)P\approx P\wedge(Q\vee\neg Q) and in step 2 that P∧(Q∨¬Q)≈(P∧Q)∨(P∧¬Q)P\wedge(Q\vee\neg Q)\approx (P\wedge Q)\vee (P\wedge\neg Q).

More generally, we can adapt the above explanation to show the following: for any formulas XX and YY,

X≈(X∧Y)∨(X∧¬Y).X\approx ( X\wedge Y)\vee ( X\wedge\neg Y).
Example

We can use the above principles and rules to explain why the following equivalence holds.

P∨¬P≈Q∨¬Q.P\vee \neg P \approx Q\vee \neg Q.

We do this by listing some equivalences with brief explanations that reference the axioms and rules given above.

1.(P∨¬P)≈(P∨¬P)∧(Q∨¬Q)(P\vee \neg P)\approx (P\vee \neg P)\wedge(Q\vee\neg Q)
Explanation: Since Q∨¬QQ\vee\neg Q is a tautology, this is an instance of the Tautology Rule.
2.(Q∨¬Q)≈(Q∨¬Q)∧(P∨¬P)(Q\vee \neg Q)\approx (Q\vee \neg Q)\wedge(P\vee\neg P)
Explanation: Since P∨¬PP\vee\neg P is a tautology, this is an instance of the Tautology Rule.
3.(P∨¬P)∧(Q∨¬Q)≈(Q∨¬Q)∧(P∨¬P)(P\vee \neg P)\wedge(Q\vee\neg Q) \approx (Q\vee\neg Q)\wedge (P\vee \neg P)
Explanation: This is an instance of the commutative axiom for ∧\wedge statying that X∧Y≈Y∧XX\wedge Y \approx Y\wedge X, with XX is (P∨¬P)(P \vee \neg P) and YY is (Q∨¬Q)(Q \vee \neg Q).
4.(P∨¬P)≈(Q∨¬Q)∧(P∨¬P)(P\vee\neg P)\approx (Q\vee\neg Q)\wedge (P\vee \neg P)
Explanation: This follows from the Transitivity Rule since we established in step 1 that (P∨¬P)≈(P∨¬P)∧(Q∨¬Q)(P\vee \neg P)\approx (P\vee \neg P)\wedge(Q\vee\neg Q) and in step 3 that (P∨¬P)∧(Q∨¬Q)≈(Q∨¬Q)∧(P∨¬P)(P\vee \neg P)\wedge(Q\vee\neg Q) \approx (Q\vee\neg Q)\wedge (P\vee \neg P).
5.(Q∨¬Q)∧(P∨¬P)≈(Q∨¬Q)(Q\vee \neg Q)\wedge(P\vee\neg P) \approx (Q\vee \neg Q)
Explanation: This follows from the Symmetry Rule since we established (Q∨¬Q)≈(Q∨¬Q)∧(P∨¬P)(Q\vee \neg Q)\approx (Q\vee \neg Q)\wedge(P\vee\neg P) in step 2.
6.(P∨¬P)≈(Q∨¬Q)(P\vee\neg P) \approx (Q\vee \neg Q)
Explanation: This follows from the Transitivity Rule since we established in step 4 that (P∨¬P)≈(Q∨¬Q)∧(P∨¬P)(P\vee\neg P)\approx (Q\vee\neg Q)\wedge (P\vee \neg P) and in step 5 that (Q∨¬Q)∧(P∨¬P)≈(Q∨¬Q)(Q\vee \neg Q)\wedge(P\vee\neg P) \approx (Q\vee \neg Q).

More generally, we can adapt the above explanation to show the following: for any formulas XX and YY, if XX and YY are both tautologies, then X≈YX\approx Y.

There is an additional inference rule that plays a crucial role when showing two formulas are equivalent.

Replacement of Equivalents: If X≈YX\approx Y and α≈β\alpha\approx\beta, then Z≈Z′Z\approx Z' where Z′Z' is ZZ with some occurrences of XX replaced with YY.

For example, since ¬¬P≈P\neg \neg P\approx P and ¬(¬P∧Q)≈(¬¬P∨¬Q)\neg (\neg P \wedge Q)\approx (\neg\neg P\vee \neg Q), we can use the above rule to conclude that ¬(¬P∧Q)≈(P∨¬Q)\neg (\neg P \wedge Q)\approx (P\vee \neg Q). This is an application of the above rule since (P∧Q)(P\wedge Q) is (¬¬P∧Q)(\neg\neg P\wedge Q) with the single occurrence of ¬¬P\neg\neg P replaced with PP.

Example

We can use the above principles and rules (including Replacements of Equivalents) to explain why the following equivalence holds.

¬(P→Q)≈P∧¬Q.\neg(P\rightarrow Q) \approx P\wedge\neg Q.

We do this by listing some equivalences with brief explanations that reference the axioms and rules given above.

1.(P→Q)≈(¬P∨Q)(P\rightarrow Q)\approx (\neg P\vee Q)
Explanation: This is an instance of the Conditional Equivalence axiom.
2.¬(P→Q)≈¬(P→Q)\neg(P\rightarrow Q)\approx \neg(P\rightarrow Q)
Explanation: This is an instance of the Reflexivity Rule.
3.¬(P→Q)≈¬(¬P∨Q)\neg(P\rightarrow Q)\approx \neg(\neg P\vee Q)
Explanation: This is an instance of the Replacement of Equivalents rule given that we established in step 1 that (P→Q)≈(¬P∨Q)(P\rightarrow Q)\approx (\neg P\vee Q), we established in step 2 that ¬(P→Q)≈¬(P→Q)\neg(P\rightarrow Q)\approx \neg(P\rightarrow Q), and ¬(¬P∨Q)\neg (\neg P\vee Q) is ¬(P→Q)\neg (P\rightarrow Q) with the single occurrence of P→QP\rightarrow Q replaced with ¬P∨Q\neg P\vee Q.
4.¬(¬P∨Q)≈(¬¬P∧¬Q)\neg(\neg P\vee Q)\approx (\neg\neg P\wedge \neg Q)
Explanation: This is an instance of the DeMorgan's Rule.
5.¬¬P≈P\neg\neg P \approx P
Explanation: This is an instance of the Double Negation.
6.¬(¬P∨Q)≈(P∧¬Q)\neg(\neg P\vee Q)\approx (P\wedge \neg Q)
Explanation: This is an instance of the Replacement of Equivalents rule given that we established in step 4 that ¬(¬P∨Q)≈(¬¬P∧¬Q)\neg(\neg P\vee Q)\approx (\neg\neg P\wedge \neg Q), we established in step 5 that ¬¬P≈P\neg\neg P\approx P, and $ (P\wedge \neg Q)$ is (¬¬P∧¬Q)(\neg\neg P\wedge \neg Q) with the single occurrence of ¬¬P\neg\neg P replaced with PP.
6.¬(P→Q)≈(P∧¬Q)\neg (P\rightarrow Q) \approx (P\wedge \neg Q)
Explanation: This follows from the Transitivity Rule since we established in step 3 that ¬(P→Q)≈¬(¬P∨Q)\neg(P\rightarrow Q)\approx \neg(\neg P\vee Q) and we established in step 6 that ¬(¬P∨Q)≈(P∧¬Q)\neg(\neg P\vee Q)\approx (P\wedge \neg Q).

More generally, we can adapt the above explanation to show the following: for any formulas XX and YY,

¬(X→Y)≈(X∧¬Y).\neg(X\rightarrow Y)\approx(X\wedge\neg Y).

Practice Questions#

  1. True or False: For any formulas XX and YY if XX and YY are both tautologies, then X≈YX\approx Y.

  2. True or False: (A∧¬A)≈(B∧¬B)(A\wedge \neg A) \approx (B\wedge \neg B)

  3. Which formula can be substituted for XX to make the following true: (A→B)≈X(A \rightarrow B)\approx X?

  4. Which of the formulas is equivalent to ¬A→A\neg A\rightarrow A?

  5. Which of the formulas is equivalent to A→¬AA\rightarrow \neg A?

  6. Which of the following formulas is equivalent to ((A→B)∧A)∨((A→B)∧¬A)((A\rightarrow B)\wedge A)\vee ((A\rightarrow B) \wedge \neg A)?

  7. Which of the following formulas is equivalent to P→(Q→R)P\rightarrow (Q\rightarrow R)?

  8. True or False: For all formulas XX and YY, ¬(X↔Y)≈(¬X↔¬Y)\neg (X\leftrightarrow Y)\approx (\neg X \leftrightarrow \neg Y)

  9. True or False: For all formulas XX and YY, X≈YX\approx Y if and only if ¬X≈¬Y\neg X \approx \neg Y.

  10. Suppose that XX and YY are formulas and that X∧Y≈XX\wedge Y \approx X. Which of the following is true?

  11. Suppose that XX and YY are formulas and that X∨Y≈XX\vee Y \approx X. Which of the following is true?