Module 04: Propositional Logic Proofs
Argument
A logical argument consists of premises, which are statements assumed to be true and used as evidence, and a conclusion, which is the statement that follows logically from the premises. An argument typically looks like this:
premise 1
premise 2
premise 3
∴ conclusion
The symbol ∴ means "therefore" and introduces the conclusion. Note that an argument can have multiple premises (or even none) but only one conclusion.
Validity
An argument is valid if whenever all the premises are true, the conclusion is also true. This is tested using a truth table by checking if the conclusion is true in every critical row. A critical row is a row in which all premises are true. Note that the value of the conclusion for non-critical rows does not matter to validity.
The following argument is valid, since the conclusion is true in every critical row.
c
(a → (b ⋀ c))
(a ⋁ ~c)
∴ b
| inputs | premises | conclusion | |||||
| a | b | c | c | (a → (b ⋀ c)) | (a ⋁ ~c) | b | |
| F | F | F | F | T | T | ||
| F | F | T | T | T | F | ||
| F | T | F | F | T | T | ||
| F | T | T | T | T | F | ||
| T | F | F | F | F | T | ||
| T | F | T | T | F | T | ||
| T | T | F | F | T | T | ||
| T | T | T | T | T | T | T | critical row: true conclusion |
An argument is invalid only when there is at least one critical row with a false conclusion.
The following argument is invalid, since there is at least one critical row with a false conclusion. The following example has 2 such critical rows.
(a → b)
(a → (b ⋀ c))
∴ c
| inputs | premises | conclusion | ||||
| a | b | c | (a → b) | (a → (b ⋀ c)) | c | |
| F | F | F | T | T | F | critical row: false conclusion |
| F | F | T | T | T | T | critical row: true conclusion |
| F | T | F | T | T | F | critical row: false conclusion |
| F | T | T | T | T | T | critical row: true conclusion |
| T | F | F | F | F | ||
| T | F | T | F | F | ||
| T | T | F | T | F | ||
| T | T | T | T | T | T | critical row: true conclusion |
Notice that a valid logical argument is a promise. The promise guarantees the conclusion is true whenever the premises are true, but it guarantees nothing when the premises are not all true.
Contradictory Premises
When no row in a truth table has all premises true at the same time, the premises are contradictory. Such an argument is logically valid because it is impossible for all premises to be true and the conclusion false. However, contradictory premises make the argument useless in practice.
The following argument does not have critical rows; therefore, it has contradictory premises, and it is valid.
c
(a ⟶ (b ⋀ c))
(a ⋁ ~c)
(~a ⋁ ~b)
∴ b
| inputs | premises | conclusion | no critical rows | |||||
| a | b | c | c | (a → (b ⋀ c)) | (a ⋁ ~c) | (~a ⋁ ~b) | b | |
| F | F | F | F | T | T | T | F | |
| F | F | T | T | T | F | T | F | |
| F | T | F | F | T | T | T | T | |
| F | T | T | T | T | F | T | T | |
| T | F | F | F | F | T | T | F | |
| T | F | T | T | F | T | T | F | |
| T | T | F | F | F | T | F | T | |
| T | T | T | T | T | T | F | T | |
Rules of Inference
One straightforward method to verify if an argument is valid is to construct a truth table with columns for each premise and check the conclusion values for each critical row. However, as for the logically equivalent proofs, this approach can become impractical as the number of input variables increases.
A more efficient and elegant method is to infer new premises using a series of rules of inference. It is also valid to transform premises into equivalent statements using equivalence laws.
For this course, the following list of rules of inference should be used as the basis:
|
Modus Ponens (M.PON) (p → q) p ∴ q |
Modus Tollens (M.TOL) (p → q) ~q ∴ ~p |
|
Generalization (GEN) p ∴ (p ⋁ q) |
Specialization (SPEC) (p ⋀ q) ∴ p |
|
Conjunction (CONJ) p q ∴ (p ⋀ q) |
Elimination (ELIM) (p ⋁ q) ~q ∴ p |
|
Transitivity (TRANS) (p → q) (q → r) ∴ (p → r) |
Proof by Cases (CASE) (p → r) (q → r) ∴ ((p ⋁ q) → r) |
|
Resolution (RES) (p ⋁ q) (~p ⋁ r) ∴ (q ⋁ r) |
Contradiction (CONTD) (p → F) ∴ ~p |
You don't need to memorize this list; a formula sheet will be provided to you at all assessments during the course.
Similar to equivalence laws, having agreed on rules to use, we should justify that these rules always work. Each of our rules of inference is itself a valid argument, which keeps it from producing an invalid result. You can check their validity with truth tables.
Let's use these laws to prove that the following argument is valid:
c
(a → (b ⋀ c))
(a ⋁ ~c)
∴ b
Proof:
| 01. c | |
| 02. (a → (b ⋀ c)) | |
| 03. (a ⋁ ~c) | |
| 04. a | Elimination from steps 1 and 3 |
| 05. (b ⋀ c) | Modus Ponens from steps 2 and 4 |
| 06. b | Specialization from step 5 |
Note that rules of inference cannot be used on parts of statements, so it is not possible to conclude (a → c) from ((a ⋀ b) → c) using SPEC, for example. You can check that ((a ⋀ b) → c) can be true while (a → c) is false in the case when a is true, b is false, and c is false, which proves that this argument is invalid.
When it is possible to derive the negation of a given conclusion from the premises, doing so does not necessarily show the original argument to be invalid. It is still possible that the premises are contradictory, in which case the original argument and the version that negates the conclusion are both valid.
As a result, rules of inference cannot be used to prove that an argument is invalid. Instead, the simplest and most effective approach is to find a single critical row, a case where all premises are true and the conclusion is false. The existence of just one such row is sufficient to establish that the argument is invalid, making it unnecessary to construct the entire truth table.
(a → b)
(a → (b ⋀ c))
∴ c
Proof that this argument is invalid:
| a ≡ F b ≡ T c ≡ F |
| Premise 1 is true: (a → b) ≡ (F → T) ≡ T |
| Premise 2 is true: (a → (b ⋀ c)) ≡ (F → (T ⋀ F)) ≡ (F → F) ≡ T |
| Conclusion is false: c ≡ F |
Finally, an argument with contradictory premises, that is, premises that are never all true at the same time, does not have any critical rows and is logically valid. In such cases, any conclusion can be derived from the premises, including both the conclusion and its negation. This is because from a contradiction, one can infer anything, a principle known as the principle of explosion. As a result, it is always possible to conclude false from contradictory premises.
c
(a → (b ⋀ c))
(a ⋁ ~c)
(~a ⋁ ~b)
∴ b
Proof:
| 01. c | |
| 02. (a → (b ⋀ c)) | |
| 03. (a ⋁ ~c) | |
| 04. (~a \vee ~b) | |
| 05. a | Elimination from steps 1 and 3 |
| 06. ~b | Elimination from steps 4 and 5 |
| 07. (b ⋀ c) | Modus Ponens from steps 2 and 5 |
| 08. b | Specialization from steps 7 |
| 09. (b ⋀ ~b) | Conjunction from steps 6 and 8 |
| 10. F | Negation from steps 9 |
From here, we can prove anything. Let's say we want to prove x, a variable that doesn't even appear in the premises. We derive (F ⋁ x in step 11 by Generalization from step 10 and then x in step 12 by Identity from step 11.
Remember, an argument with contradictory premises is always valid!
Read More
Epp, Susanna. Discrete Mathematics with Applications.
5th edition: 2.3
4th edition: 2.3
3rd edition: 1.3