Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
The Book of
Foundational Mathematics
1 Propositional Logic
2 Arguments and Proof
- The Structure of Basic Arguments
- Rules of Inference
- Using the Rules of Inference
- Logically Equivalent Arguments
- Invalid Arguments
- Universal Specification
- Universal Generalization
- Axioms, Definitions, Theorems, and Proofs
- Proof Technique: Direct Proofs
- Proof Technique: Indirect Proofs
- Proof Technique: Contradiction
- Mistakes in Proofs
- Proof Technique: Equivalence
4 Relations and Functions
Appendix
Logically Equivalent Arguments
Fundamentally, an argument is nothing more than a logical implication. The basic structure of a logical implication is a hypothesis and a conclusion, where the hypothesis is a conjunction of multiple premises.
We’ve seen in Chapter 1 that it’s possible to construct logically equivalent propositions using logical laws. Since an argument is fundamentally a proposition based on an implication, it should be possible to construct a different argument that is logically equivalent to the original argument. In some cases, this new, equivalent argument may be easier to verify than the original argument, which is why we would invest time investigating how to construct logically equivalent arguments in the first place.
Proof by Contradiction
The general structure of an argument is given as follows:
| p1 | |
| p2 | |
| ⋮ | |
| pn | |
| ∴ | c |
This means we’re only considering cases where each of the premises p1 through pn have truth values of 1.
If we take a look at the propositional form of this argument with only one premise, we get
p1 → c.
Notice that we would need c = 1 in order for this implication to be true, but this is logically equivalent to ¬p1 ∨ c. We could extend this a little bit further:
| p1 → c | Reason | |
| ⟺ | ¬p1 ∨ c | (p → q) ⟺ (¬p ∨ q) |
| ⟺ | ¬(p1 ∧ ¬c) | DeMorgan’s Law |
So, if p1 → c is a valid argument, then ¬(p1 ∧ ¬c) would be a true proposition.
Thus, if p1 → c then it would be impossible to have both p1 = 1 and c = 0, or in other words for p1 = 1 and ¬c = 1. It would be a contradiction. In other words, we get the argument
[p1 ∧ ¬c] → F0.
This is where this proof strategy gets its name: for a valid argument, by assuming the negation of the desired conclusion, a contradiction is produced. Thus, the negation of the conclusion must be false, meaning the conclusion by itself must be true.
Let’s look at a truth table to get a better idea of what’s going on:
| p1 | c | ¬c | F0 | p1 ∧ ¬c | [p1 ∧ ¬c] → F0 | p1 → c | (p1 → c) ↔ [(p1 ∧ ¬c) → F0] |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
So the implications (p1 → c) and [(p1 ∧ ¬c) → F0] are logically equivalent. This means that the arguments are also equivalent (since arguments are just implications.) As such, if we establish that one of (p1 → c) or [(p1 ∧ ¬c) → F0] are valid, then the other argument must also be valid.
Example 2.4.1
Frank is a farmer who loves being outdoors and working on his gardens. He grows two kinds of plants: sunflowers and wheat. However, he can’t plant both in his garden as both kinds of plants may interfere with each others’ growth. Furthermore, if he grows wheat, then he’ll be able to make his own bread.
Consider the following propositions:
| s: | Frank plants sunflowers in his garden. |
| w: | Frank plants wheat in his garden. |
| b: | Frank bakes bread using the wheat he grew in his garden. |
We can express the above situation in the following argument:
| ¬s ↔ w | |
| w → b | |
| ¬b | |
| ∴ | s |
In order to establish the validity of the above argument, we could instead consider if the equivalent argument
| ¬s ↔ w | |
| w → b | |
| ¬b | |
| ¬s | |
| ∴ | F0 |
is valid. To do so, we use the rules of inference and the laws of logic:
| Step | Proposition | Reason |
|---|---|---|
| (1) | ¬s ↔ w | Premise |
| (2) | (¬s → w) ∧ (w → ¬s) | (a ↔ b) ⇔ [(a → b) ∧ (b → a)] |
| (3) | ¬s → w | Conjunctive Simplification on (2) |
| (4) | w → b | Premise |
| (5) | ¬s → b | Law of the Syllogism on (3) and (4) |
| (6) | ¬s | Premise |
| (7) | b | Modus Ponens on (5) and (6) |
| (8) | ¬b | Premise |
| (9) | b ∧ ¬b | Rule of Conjunction on (7) and (8) |
| (10) | ∴F0 | (b ∧ ¬b) ⇔ F0 |
So, using the rules of inference, we’ve determined that the argument
| ¬s ↔ w | |
| w → b | |
| ¬b | |
| ¬s | |
| ∴ | F0 |
is valid, meaning that the original argument
| ¬s ↔ w | |
| w → b | |
| ¬b | |
| ∴ | s |
is also valid.
Therefore, if we know that
Frank plant’s wheat if and only if he does not plant sunflowers.
If Frank plants wheat, then Frank will make bread using wheat he grew in his garden.
Frank does not make bread using wheat he grew in his garden.
are all true propositions, we then we know that Frank planted sunflowers in his garden.
Chains of Implications
Suppose we knew that the argument
| p | |
| ∴ | q → r |
was valid. Since p = 1, we know that q → r = 1. But now suppose we also knew that q = 1. Since q → r = 1 and q = 1, then we’d have that r = 1 as well. Notice that since p = 1 and q = 1, we have that p ∧ q = 1. Writing this argument out as a proposition, we get
p → (q → r).
Thus, we see that if we had both p and q, then we would necessarily have r. This actually becomes the argument
[p ∧ q] → r.
This line of reasoning seems to suggest that the argument p → (q → r) is logically equivalent to the argument [p ∧ q] → r. Let’s confirm this suspicion with a truth table.
| p | q | r | (q → r) | p → (q → r) | p ∧ q | [p ∧ q] → r | [p → (q → r)] ↔ [(p ∧ q) → r] |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Just as we expected, the biconditional is tautological, meaning we have a logical equivalency between the argument p → (q → r) and the argument [p ∧ q] → r.
Just like we said before, establishing the validity of one of these arguments automatically establishes the validity of the other argument.
Example 2.4.2
Frank has been thinking about using the wheat he grows in his garden to open a bakery where he bakes tasty bread for sale to customers. Of course he’ll need a building to serve as his store, and he’ll need to make sure his tractor is working so he can actually farm crops. Suppose we had the following propositions:
| t: | Frank fixes his tractor. |
| s: | Frank grows sunflowers in his garden. |
| w: | Frank grows wheat in his garden. |
| b: | Frank bakes bread using the wheat he grew in his garden. |
| m: | Frank saves enough money to buy a building for his bake shop. |
| ★: | Frank opens a bake shop where he sells his bread. |
Now consider the following argument:
| t → (s ∨ w) | |
| t | |
| (b ∧ m) → ★ | |
| m | |
| w → b | |
| ∴ | ¬s → ★ |
We can determine if the above argument is valid by determining the validity of the following equivalent argument:
| t → (s ∨ w) | |
| t | |
| (b ∧ m) → ★ | |
| m | |
| w → b | |
| ¬s | |
| ∴ | ★ |
So, let’s see if we can determine if the above argument is valid:
| Step | Proposition | Reason |
|---|---|---|
| (1) | t | Premise |
| (2) | t → (s ∨ w) | Premise |
| (3) | s ∨ w | Modus Ponens on (1) and (2) |
| (4) | ¬s | Premise |
| (5) | w | Rule of Disjunctive Syllogism on (3) and (4) |
| (6) | w → b | Premise |
| (7) | b | Modus Ponens on (5) and (6) |
| (8) | m | Premise |
| (9) | b ∧ m | Rule of Conjunction on (7) and (8) |
| (10) | (b ∧ m) → ★ | Premise |
| (11) | ∴★ | Modus Ponens on (9) and (10) |
So we reached the desired conclusion. This means that the above two arguments are valid.