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, $\neg (P\vee Q)$ and $(\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:

$P$	$Q$	$\neg (P\vee Q)$	$(\neg P\wedge \neg Q)$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$

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

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

1. $\neg (\neg P\vee Q)$ is tautologically equivalent to $(\neg\neg P \wedge \neg Q)$.
2. $\neg (\neg P\vee P)$ is tautologically equivalent to $(\neg\neg P \wedge \neg P)$.
3. $\neg ((P\rightarrow Q)\vee (R\vee P))$ is tautologically equivalent to $(\neg(P\rightarrow Q) \wedge \neg (R\vee P))$.

For all formulas $X$ and $Y$, we write $X\approx Y$ when $X$ and $Y$ are tautologically equivalent. For instance,

1. $\neg (\neg P\vee Q)\approx (\neg\neg P \wedge \neg Q)$;
2. $\neg (\neg P\vee P)\approx(\neg\neg P \wedge \neg P)$; and
3. $\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):

$$\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).

Name	Equivalence
Double Negation	$\neg\neg X\approx X$
DeMorgan's Rules	$\neg( X\vee Y)\approx (\neg X\wedge \neg Y)$ $\neg( X\wedge Y)\approx (\neg X\vee \neg Y)$
Distribution	$(X\wedge( Y\vee Z))\approx ((X\wedge Y)\vee ( X\wedge Z))$ $(X\vee(Y\wedge Z))\approx ((X\vee Y)\wedge (X\vee Z))$
Absorption	$(X\vee(X\wedge Y)\approx X$ $(X\wedge( X\vee Y)\approx X$
Commutativity	$(X\wedge Y)\approx(Y\wedge X)$ $(X\vee Y)\approx(Y\vee X)$
Conditional Definition	$(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.

Name	Rule
Reflexivity	$X\approx X$
Symmetry	If $X\approx Y$, then $Y\approx X$
Transitivity	If $X\approx Y$ and $Y\approx Z$, then $X\approx Z$
Tautology	If $Y$ is a tautology, then $X\approx (X\wedge Y)$
Contradiction	If $Y$ is a contradiction, then $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 \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\approx P\wedge(Q\vee\neg Q)$

Explanation: Since $Q\vee\neg Q$ is a tautology, this is an instance of the Tautology Rule.

2.$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\approx (P\wedge Q)\vee (P\wedge\neg Q)$

Explanation: This follows from the Transitivity Rule since we established in step 1 that $P\approx P\wedge(Q\vee\neg Q)$ and in step 2 that $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 $X$ and $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\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\vee \neg P)\approx (P\vee \neg P)\wedge(Q\vee\neg Q)$

Explanation: Since $Q\vee\neg Q$ is a tautology, this is an instance of the Tautology Rule.

2.$(Q\vee \neg Q)\approx (Q\vee \neg Q)\wedge(P\vee\neg P)$

Explanation: Since $P\vee\neg P$ is a tautology, this is an instance of the Tautology Rule.

3.$(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\wedge Y \approx Y\wedge X$, with $X$ is $(P \vee \neg P)$ and $Y$ is $(Q \vee \neg Q)$.

4.$(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\vee \neg P)\approx (P\vee \neg P)\wedge(Q\vee\neg Q)$ and in step 3 that $(P\vee \neg P)\wedge(Q\vee\neg Q) \approx (Q\vee\neg Q)\wedge (P\vee \neg P)$.

5.$(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\vee \neg Q)\approx (Q\vee \neg Q)\wedge(P\vee\neg P)$ in step 2.

6.$(P\vee\neg P) \approx (Q\vee \neg Q)$

Explanation: This follows from the Transitivity Rule since we established in step 4 that $(P\vee\neg P)\approx (Q\vee\neg Q)\wedge (P\vee \neg P)$ and in step 5 that $(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 $X$ and $Y$, if $X$ and $Y$ are both tautologies, then $X\approx Y$.

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

Replacement of Equivalents: If $X\approx Y$ and $\alpha\approx\beta$, then $Z\approx Z'$ where $Z'$ is $Z$ with some occurrences of $X$ replaced with $Y$.

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

Example

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

$$\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\rightarrow Q)\approx (\neg P\vee Q)$

Explanation: This is an instance of the Conditional Equivalence axiom.

2.$\neg(P\rightarrow Q)\approx \neg(P\rightarrow Q)$

Explanation: This is an instance of the Reflexivity Rule.

3.$\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\rightarrow Q)\approx (\neg P\vee Q)$, we established in step 2 that $\neg(P\rightarrow Q)\approx \neg(P\rightarrow Q)$, and $\neg (\neg P\vee Q)$ is $\neg (P\rightarrow Q)$ with the single occurrence of $P\rightarrow Q$ replaced with $\neg P\vee Q$.

4.$\neg(\neg P\vee Q)\approx (\neg\neg P\wedge \neg Q)$

Explanation: This is an instance of the DeMorgan's Rule.

5.$\neg\neg P \approx P$

Explanation: This is an instance of the Double Negation.

6.$\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 $\neg(\neg P\vee Q)\approx (\neg\neg P\wedge \neg Q)$, we established in step 5 that $\neg\neg P\approx P$, and $ (P\wedge \neg Q)$ is $(\neg\neg P\wedge \neg Q)$ with the single occurrence of $\neg\neg P$ replaced with $P$.

6.$\neg (P\rightarrow Q) \approx (P\wedge \neg Q)$

Explanation: This follows from the Transitivity Rule since we established in step 3 that $\neg(P\rightarrow Q)\approx \neg(\neg P\vee Q)$ and we established in step 6 that $\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 $X$ and $Y$,

$$\neg(X\rightarrow Y)\approx(X\wedge\neg Y).$$

Practice Questions

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

   True False

   ​

2. True or False: $(A\wedge \neg A) \approx (B\wedge \neg B)$

   True False

   ​

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

   $B\rightarrow A$

   $A\wedge \neg B$

   $\neg A\vee B$

   ​

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

   $\neg A$

   $A$

   This is a contradiction, so it is equivalent to any contradiction.

   ​

5. Which of the formulas is equivalent to $A\rightarrow \neg A$?

   $\neg A$

   $A$

   This is a contradiction, so it is equivalent to any contradiction.

   ​

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

   $A\rightarrow B$

   $B$

   $A$

   $B\rightarrow A$

   ​

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

   $(P\rightarrow Q)\rightarrow R)$

   $(Q\rightarrow (P\rightarrow R))$

   $(Q\rightarrow R)\rightarrow P)$

   None of the above.

   ​

8. True or False: For all formulas $X$ and $Y$, $\neg (X\leftrightarrow Y)\approx (\neg X \leftrightarrow \neg Y)$

   True

   False

   ​

9. True or False: For all formulas $X$ and $Y$, $X\approx Y$ if and only if $\neg X \approx \neg Y$.

   True

   False

   ​

10. Suppose that $X$ and $Y$ are formulas and that $X\wedge Y \approx X$. Which of the following is true?

    $Y\rightarrow X$ is a tautology.

    $X\rightarrow Y$ is a tautology.

    ​

11. Suppose that $X$ and $Y$ are formulas and that $X\vee Y \approx X$. Which of the following is true?

    $Y\rightarrow X$ is a tautology.

    $X\rightarrow Y$ is a tautology.

    ​