Question

Use a truth table to prove that P → Q is logically equivalent to ¬P ∨ Q.

Answer 1

Here is a proof using a truth table to show that P → Q is logically equivalent to ¬P ∨ Q.

Understanding Logical Equivalence

Two logical expressions are considered logically equivalent if they have the exact same truth value for all possible combinations of truth values of their atomic components (in this case, P and Q).

To prove this, we will construct a truth table that evaluates both expressions and then compare their final columns.

Step-by-Step Truth Table Construction

1. Identify Atomic Propositions: The basic statements are P and Q.
2. List All Possible Truth Combinations: With two propositions, there are 2² = 4 possible combinations of truth values (True/False).
3. Evaluate the Left-Hand Side (P → Q): We'll add a column for the conditional statement P → Q. Remember the rule for a conditional: it is only false when the first part (P) is true and the second part (Q) is false.
4. Evaluate the Right-Hand Side (¬P ∨ Q): To do this, we first need an intermediate column for the negation of P, which is ¬P. Then, we can evaluate the disjunction (OR, ∨) between the ¬P column and the Q column. Remember the rule for disjunction: it is only false when both parts are false.
5. Compare the Final Columns: We will compare the column for P → Q with the column for ¬P ∨ Q. If they are identical, the expressions are logically equivalent.

---

The Truth Table

Here is the completed truth table:

| P | Q | P → Q | ¬P | ¬P ∨ Q |
| :---: | :---: | :---: | :---: | :---: |
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |

Analysis of the Columns

1. Column (P → Q):
   Row 1 (T → T): If P is true and Q is true, the implication is True.
   Row 2 (T → F): This is the only case where the implication is False. A true premise cannot lead to a false conclusion.
   Row 3 (F → T): If P is false, the implication is True (this is called vacuous truth).
   Row 4 (F → F): If P is false, the implication is also True (vacuous truth).

2. Column (¬P ∨ Q):
   Row 1 (F ∨ T): False OR True is True.
   Row 2 (F ∨ F): False OR False is False.
   Row 3 (T ∨ T): True OR True is True.
   Row 4 (T ∨ F): True OR False is True.

Conclusion

As you can see by comparing the third column (P → Q) and the fifth column (¬P ∨ Q), their truth values are identical for every possible combination of truth values for P and Q.

| P → Q | ¬P ∨ Q |
| :---: | :---: |
| T | T |
| F | F |
| T | T |
| T | T |

Since the final truth columns are identical, we have successfully proven that P → Q is logically equivalent to ¬P ∨ Q. This is a fundamental equivalence in logic, often called the Material Implication equivalence.