# Tautologies

This example illustrates an alternative to using truth tables to establish the equivalence
of two propositions. An alternative proof is obtained by excluding all possible
ways in which the propositions may fail to be equivalent. Here is another example.
Example 2.3.2. Show ¬(p → q) is equivalent to p ∧ ¬q.
Solution 1. Build a truth table containing each of the statements.
p q ¬q p → q ¬(p → q) p ∧ ¬q
T T F T F F
T F T F T T
F T F T F F
F F T T F F
Since the truth values for ¬(p → q) and p∧¬q are exactly the same for all possible
combinations of truth values of p and q, the two propositions are equivalent.
Solution 2. We consider how the two propositions could fail to be equivalent. This
can happen only if the first is true and the second is false or vice versa.
Case 1. Suppose ¬(p → q) is true and p ∧ ¬q is false.
¬(p → q) would be true if p → q is false. Now this only occurs if p is true
and q is false. However, if p is true and q is false, then p ∧ ¬q will be true.
Hence this case is not possible.
Case 2. Suppose ¬(p → q) is false and p ∧ ¬q is true.
p ∧ ¬q is true only if p is true and q is false. But in this case, ¬(p → q) will
be true. So this case is not possible either.
Since it is not possible for the two propositions to have different truth values, they
must be equivalent.