1.3 Logical equivalence
We say that two statements are logically equivalent, and denote this by \(P\equiv Q\), if they have identical truth values. In other words \(P\) is true exactly when \(Q\) is true. So from our last example, \[ (P\lor Q) \land (\lnot P \lor \lnot Q)\equiv (P\lor Q) \land \lnot( P \land Q) \equiv (P\land \lnot Q) \lor (\lnot P \land Q). \]
An expression which is always true independent of the truth of its components is called a tautology. For example \[P\lor\lnot P\] is a tautology.
An expression which is always false independent of the truth of its components is called a contradiction. For example \[P\land\lnot P\] is a contradiction.
The following theorem provides the algebraic rules for manipulating compound statements.
Let \(P,Q\) and \(R\) be statements. Let \(T\) and \(F\) denote true and false.
- Complement rules. \[P\lor\lnot P\equiv T\]\[P\land\lnot P\equiv F\]
- Identity rules.\[P\land T\equiv T\land P \equiv P\]\[P\lor F\equiv F\lor P \equiv P\]
- Idempotent rules. \[P\land P\equiv P\]\[P\lor P\equiv P\]
- Commutative rules. \[P\land Q\equiv Q\land P\]\[P\lor Q\equiv Q\lor P\]
- Associative rules. \[(P\land Q)\land R\equiv P\land (Q\land R)\]\[(P\lor Q)\lor R\equiv P\lor (Q\lor R)\]
- Distributive rules. \[(P\lor Q)\land R\equiv (P\land R)\lor(Q\land R)\]\[(P\land Q)\lor R\equiv (P\lor R)\land(Q\lor R)\]
- Double negation rule. \[P\equiv \lnot\lnot P\]
- De Morgan’s rules. \[\lnot(P\land Q)\equiv(\lnot P)\lor(\lnot Q)\]\[\lnot(P\lor Q) \equiv (\lnot P)\land(\lnot Q)\]
The associative rules allow us to be a bit lazier with bracketing: we can write \[P\land Q\land R\] without brackets since it doesn’t matter whether we interpret this as meaning \((P\land Q)\land R\) or \(P\land (Q\land R)\), and likewise for disjunction.
As an exercise, construct the truth tables to justify each of these rules.
As an example of how these rules can be used to deduce other rules we consider the Absorption rules: \[P\lor(P\land Q)\equiv P\] \[P\land(P\lor Q)\equiv P\] Thinking about the first of these, the disjunction says that \(P\) is true or \(P\land Q\) is true (or as always both). If \(P\) is true then, well, \(P\) is true, while if \(P\land Q\) is true then again \(P\) must be true. So if the disjunction holds then \(P\) must be true. But of course if \(P\) is true then the disjunction is also true, which explains the equivalence.
We can alternatively show this using the logical rules from the theorem. As a first step let us deduce another equivalence (the relevance of which will become apparent in a moment). We will show the rule: \[Q\lor T\equiv T\lor Q \equiv T\] This is obvious from the truth-tables, but let us see how to deduce it via the logical equivalence rules. What do the rules tell us about \(T\)? The complement rule allows us to write \[T\equiv Q\lor \lnot Q\] and therefore\[Q\lor T \equiv Q\lor (Q\lor \lnot Q)\equiv (Q\lor Q)\lor \lnot Q\]by the associative rule. The idempotent rule allows us to replace \(Q\lor Q\) with \(Q\) so we have \[Q\lor T\equiv Q\lor \lnot Q\equiv T\]by again applying the complement rule. The same holds for \(T\lor Q\) by commutativity.
With this new rule in our toolkit let us show the first absorption rule: \[\begin{align*} P\lor(P\land Q)&\equiv (P\land T)\lor(P\land Q) &\text{by the identity rule}\\ &\equiv P\land (T\lor Q) &\text{by the distributive rule}\\ &\equiv P\land T &\text{as }T\lor Q \equiv T\\ &\equiv P&\text{by the identity rule} \end{align*}\] We leave the second absorption rule as an exercise. As a hint, first consider the \(F\land Q\).
Here’s an example of a word problem.
There are three boxes on a table. One contains gold, the other two are empty. Each box has imprinted on it a clue to its contents. The clues are:
Box A: ”The gold is not here”;
Box B: ”The gold is not here”;
Box C: ”The gold is in Box B”.
Only one of these clues is a true statement and the other two are false. By writing this information in symbolic form, determine which box has the gold?
Let us write \(A,B,C\) for the statements “The gold is in box A” etc. The clues then translate as:
1st clue: \(\lnot A\)
2nd clue: \(\lnot B\)
3rd clue: \(B\)
How do we express the statement that one of the clues is true and the other two are false? This is a form of 3-way exclusive or: 1st is true and 2nd is false and 3rd is false, or the 1st is false and 2nd true and 3rd false, or 1st and 2nd false and 3rd true.
Putting our clues into this the statement that exactly one clue is correct becomes: \[(\lnot A \land \lnot \lnot B \land \lnot B)\lor(\lnot\lnot A \land \lnot B \land \lnot B)\lor(\lnot\lnot A \land \lnot\lnot B \land B)\] Similarly the statement that there is gold in exactly one box is: \[(A \land \lnot B \land \lnot C)\lor(\lnot A \land B \land \lnot C)\lor(\lnot A \land \lnot B \land C)\] Taking the first statement we can begin simplifying using the double negation rule to get: \[(\lnot A \land B \land \lnot B)\lor( A \land \lnot B \land \lnot B)\lor(A \land B \land B)\] Applying the complement rule to the first bracket and the idempotent rules to the other two we simplify to: \[(\lnot A \land F)\lor( A \land \lnot B)\lor(A \land B)\] The first term is always false so we have\[F\lor ( A \land \lnot B)\lor(A \land B) \equiv ( A \land \lnot B)\lor(A \land B)\]by the identity rule. Now by the distributive rule we have \(A \land (\lnot B\lor B)\), and finally we can apply the complement and identity rules to get \[A \land (\lnot B\lor B)\equiv A \land T \equiv A.\] The fact that only one clue is correct tells us that \(A\) is true, that is the gold is in box A.
Why did we also need the second statement: \[(A \land \lnot B \land \lnot C)\lor(\lnot A \land B \land \lnot C)\lor(\lnot A \land \lnot B \land C) \text{?}\] Remember this tells us that there is gold in only one box. Since we know that the gold is in box A, it thus follows that there is no gold in boxes B and C. We don’t really need the formula above to see this, but for completeness let’s go ahead and use it.
Since \(A\) is true and therefore \(\lnot A\) is false the statement becomes \[(T \land \lnot B \land \lnot C)\lor(F \land B \land \lnot C)\lor(F \land \lnot B \land C)\] The first term reduces to \(\lnot B \land \lnot C\) by the identity rule, while the second and third reduce to \(F\) giving us \[(\lnot B \land \lnot C)\lor F \lor F \equiv \lnot B \land \lnot C\] Hence (as expected) we conclude that \(B,C\) are false i.e. the boxes B,C have no gold.