1.7: Logical Equivalence

In your previous mathematics classes (such as algebra and trigonometry), you encountered many examples where two different-looking formulas turned out to be equal. Analogously, in Logic, there can be two different assertions that happen to have the same truth value in all possible situations. (This means that, for every possible assignment of true or false to the variables, either both of the assertions are true, or both are false.) Such assertions are said to be logically equivalent.

Notation \(\PageIndex{1}\)

We will write \({A} \equiv {B}\) to denote that \({A}\) is logically equivalent to \({B}\).

It can take a lot of work to verify that two assertions are logically equivalent. On the other hand, to show that two assertions are not logically equivalent, you only need to find one example of an assignment to the variables, such that one of the assertions is true and the other is false.

Example \(\PageIndex{2}\)

If \(A\) is true and \(B\) is false, then \(A \lor B\) is true, but \(A \Rightarrow B\) is false. Therefore, the assertions \(A \lor B\) and \(A \Rightarrow B\) are not logically equivalent.

Exercise \(\PageIndex{3}\)

Show that each of the following pairs of sentences are not logically equivalent.

1. \(A \lor B \lor \lnot C\), \((A \lor B) \& (C \Rightarrow A)\)
2. \((P \Rightarrow Q) \lor (Q \Rightarrow P)\), \(P \lor Q\)
3. \((X \& Y) \Rightarrow Z\), \(X \lor (Y \Rightarrow Z)\)

Example \(\PageIndex{4}\)

Show that \(\lnot(A \lor B) \equiv \lnot A \& \lnot B\).

Solution

The variables \(A\) and \(B\) may each be either true or false, and we will evaluate both assertions for all possible combinations. To make it clear that none of the possibilities have been missed, we proceed systematically: for each value of \(A\), we consider the two possible values for \(B\).

1. Assume \(A\) is true.
   1. Assume \(B\) is true. We have \[\lnot(A \lor B) \quad=\quad \lnot(T \lor T) \quad=\quad \lnot T \quad=\quad F\] and \[\lnot A \& \lnot B \quad=\quad \lnot T \& \lnot T \quad=\quad F \& F \quad=\quad F .\] Both assertions are false.
   2. Assume \(B\) is false. We have \[\lnot(A \lor B) \quad=\quad \lnot(T \lor F) \quad=\quad \lnot T \quad=\quad F\] and \[\lnot A \& \lnot B \quad=\quad \lnot T \& \lnot F \quad=\quad T \& F \quad=\quad F .\] Both assertions are false.
2. Assume \(A\) is false.
   1. Assume \(B\) is true. We have \[\lnot(A \lor B) \quad=\quad \lnot(F \lor T) \quad=\quad \lnot T \quad=\quad F\] and \[\lnot A \& \lnot B \quad=\quad \lnot F \& \lnot T \quad=\quad T \& F \quad=\quad F .\] Both assertions are false.
   2. Assume \(B\) is false. We have \[\lnot(A \lor B) \quad=\quad \lnot(F \lor F) \quad=\quad \lnot F \quad=\quad T\] and \[\lnot A \& \lnot B \quad=\quad \lnot F \& \lnot F \quad=\quad T \& T \quad=\quad T .\] Both assertions are true.

In all cases, either both assertions are true, or both are false. Therefore, they are logically equivalent.

We can also solve the problem without doing so much work:

Easier solution

Note that the assertion \(\lnot(A \lor B)\) is true if and only if \(A \lor B\) is false, which means that neither \(A\) nor \(B\) is true. Therefore, \[\text{$\lnot(A \lor B)$ is true if and only if $A$ and~$B$ are both false.}\] Also, \(\lnot A \& \lnot B\) is true if and only if \(\lnot A\) and \(\lnot B\) are both true, which means that: \[\text{$\lnot A \& \lnot B$ is true if and only if $A$ and~$B$ are both false.}\]

So the two assertions \(\lnot(A \lor B)\) and \(\lnot A \& \lnot B\) are true in exactly the same situation (namely, when \(A\) and \(B\) are both false); and they are both false in all other situations. Therefore, they are logically equivalent.

Exercise \(\PageIndex{5}\)

Verify each of the following important logical equivalences. For most of these, you should not need to evaluate the assertions for all possible values of the variables.

1. rules of negation: \[\begin{aligned} \lnot \lnot A \qquad &\equiv \qquad A \\ \lnot(A \& B) \qquad &\equiv \qquad \lnot A \lor \lnot B \\ \lnot(A \lor B) \qquad &\equiv \qquad \lnot A \& \lnot B \\ \lnot ( A \Rightarrow B) \qquad &\equiv \qquad A \& \lnot B \\ \lnot ( A \Leftrightarrow B) \qquad &\equiv \qquad A \Leftrightarrow \lnot B \end{aligned}\]
2. commutativity of \(\&\), \(\lor\), and \(\Leftrightarrow\): \[\begin{aligned} A \& B \qquad &\equiv \qquad B \& A \\ A \lor B \qquad &\equiv \qquad B \lor A \\ A \Leftrightarrow B \qquad &\equiv \qquad B \Leftrightarrow A \end{aligned}\]
3. associativity of \(\&\) and \(\lor\): \[\begin{aligned} (A \& B) \& C \qquad &\equiv \qquad A \& (B \& C) \\ (A \lor B) \lor C \qquad &\equiv \qquad A \lor (B \lor C) \end{aligned}\]

The rules of negation for \(\&\) and \(\lor\) are often called De Morgan’s Laws, in honour of the British mathematician Augustus De Morgan (1806–1871, http://en.Wikipedia.org/wiki/Augustus_De_Morgan).

The rules of negation can be used to simplify the negation of any assertion.

Example \(\PageIndex{6}\)

Simplify \(\lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr)\).

Solution

We have \[\begin{aligned} \lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr) &\equiv (A \lor B) \& \lnot (A \& \lnot C) \\& \equiv (A \lor B) \& (\lnot A \lor \lnot \lnot C) \\& \equiv (A \lor B) \& (\lnot A \lor C) . \end{aligned}\]

If \({A} \equiv {B}\), then \({A}, \ \therefore {B}\) is a valid deduction. For example, the above example shows that \[\lnot \bigl( (A \lor B) \Rightarrow (A \& \lnot C) \bigr), \ \therefore (A \lor B) \& (\lnot A \lor C)\] is a valid deduction.

Exercise \(\PageIndex{7}\)

Use the rules of negation to simplify each of the following assertions (until negation is not applied to anything but variables).

1. \(\lnot \bigl( (A \lor B) \Rightarrow (C \& D) \bigr)\)
2. \(\lnot \bigl( (A \Rightarrow B) \lor (C \& D) \bigr)\)
3. \(\lnot \Bigl( A \Rightarrow \bigl( B \Rightarrow( C \Rightarrow D) \bigr) \Bigr)\)
4. \(\lnot \Bigl( \bigl( (A \Rightarrow B) \Rightarrow C \bigr) \Rightarrow D \Bigr)\)
5. \(\lnot \bigl( (P \lor \lnot Q) \& R \bigr)\)
6. \(\lnot (P \& Q \& R \& S)\)
7. \(\lnot \Bigl( \bigl( P \Rightarrow ( Q \& \lnot R) \bigr) \lor (P \& \lnot Q) \Bigr)\)

Exercise \(\PageIndex{8}\)

Use the rules of negation to simplify the negation of each of these assertions. Express your answers in English.

1. If it is raining, then the bus will not be on time.
2. I am sick, and I am tired.
3. Either the Pope is here, or the Queen and the Registrar are both here.
4. If Tom forgot his backpack, then Sam will eat either a pickle or a potato, and either Bob will not have lunch, or Alice will drive to the store.