Last night, I came across a simple propositional logic problem concerned with the validity of the following statement:
((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C)
At first, I thought it is valid. But on drawing the truth table, I was surprised to see that it isn't valid.
| A | B | C | A ⇒ B | B ⇒ C | A ⇒ C | (A ⇒ B) ∧ (B ⇒ C) | ((A ⇒ B) ∧ (B ⇒ C)) ⇔ (A ⇒ C) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | T | F | F |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | T | F | F |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
My intuition had failed. The truth table shows that there are two cases in which the statement is false.
Case 1: (A ⇒ C) ∧ (B ⇒ C) ∧ ¬(A ⇒ B)
In this case, A implies C and B implies C, but A does not imply B. This corresponds to the third row in the truth table. It makes sense. Two things can imply a third thing but they need not imply each other. For example, rain may imply wet soil and snow may imply wet soil as well, but rain need not imply snow. Here is another example that demonstrates this.
The following two statements are true for any integer x.
4 | x ⇒ 2 | x
6 | x ⇒ 2 | x
But the following statement is false when x ≡ 4 (mod 12) or x ≡ 8 (mod 12).
4 | x ⇒ 6 | x
In other words, if an integer is a multiple of 4 or 6, then it is also a multiple of 2. But this is not equivalent to saying that if an integer is a multiple of 4, then it is also a multiple of 6. That's not even correct as we can confirm for x ∈ {4, 8, 16, 20, 28, 32, …}.
Case 2: (A ⇒ B) ∧ (A ⇒ C) ∧ ¬(B ⇒ C)
In this case, A implies B as well as C but B does not imply C. This corresponds to the sixth row in the truth table. It makes sense as well. One thing can imply two other things but those two things need not imply each other. For example, rain may imply wet soil and flooded rivers but wet soil need not imply flooded rivers. The soil could be wet due to irrigation sprinklers. Once again, here is a mathematical example to demonstrate this.
The following two statements are true for any integer x.
6 | x ⇒ 2 | x
6 | x ⇒ 3 | x
But the following statement is false when x is an odd multiple of 3.
2 | x ⇒ 3 | x
The truth table correctly tells us that saying, "If an integer is a mutliple of 6, then it is a multiple of 2 as well as 3," is not equivalent to saying, "If an integer is a multiple of 2, it is a multiple of 3 as well." That would be nonsense.
Encoding intuition correctly
My intuition incorrectly concluded that the (A ⇒ B) ∧ (B ⇒ C) ⇔ (A ⇒ C) is valid because I was not translating the given statement correctly in my mind. I was thinking that if A implies B and B implies C, of course A must also imply C. This is true but this is not what the given statement represents. The given statement means something more than this. In addition to what I thought, it also means that if A does not imply B or B does not imply C, then A does not imply C as well. This however doesn't happen. The truth table shows that even though A does not imply B or B does not imply C, it is possible that A implies C.
As far as my intuition is concerned, the following would be the right way to represent what I was thinking.
((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
Indeed, this statement is valid as can be seen from the truth table below.
| A | B | C | A ⇒ B | B ⇒ C | A ⇒ C | (A ⇒ B) ∧ (B ⇒ C) | ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | T | F | T |
| T | F | F | F | T | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | T | F | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | T | T | T | T |
