Last night, I came across a simple propositional logic problem concerned with the validity of the statement:

\[ \bigl((A \implies B) \land (B \implies C)\bigr) \iff (A \implies 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 \implies B\)\(B \implies C\)\(A \implies C\) \((A \implies B) \land (B \implies C)\) \(\bigl((A \implies B) \land (B \implies C)\bigr)\) \(\iff\) \((A \implies C)\)
TTT TTT T T
TTF TFF F T
TFT FTT F F
TFF FTF F T
FTT TTT T T
FTF TFT F F
FFT TTT T T
FFF TTT T T

My intuition had failed. The truth table shows that there are two cases in which the statement is false.

Case 1: \((A \implies C) \land (B \implies C) \land \lnot(A \implies 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 \mid x \implies 2 \mid x. \\ 6 \mid x \implies 2 \mid x. \]

But the following statement is false when \(x \equiv 4 \pmod{12}\) or \(x \equiv 8 \pmod{12}\).

\[ 4 \mid x \implies 6 \mid x. \]

In other words, if an integer is a multiple of \(4\) as well as a multiple of \(6\), then it is also a multiple of \(2\). But this is not equivalent to claiming that if an integer is a multiple of \(4\), then it is also a multiple of \(6\). Such a claim is not correct as we can confirm for \(x \in \{4, 8, 16, 20, 28, 32, \dots\}\).

Case 2: \((A \implies B) \land (A \implies C) \land \lnot(B \implies 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 \mid x \implies 2 \mid x. \\ 6 \mid x \implies 3 \mid x. \]

But the following statement is false when \(x\) is an odd multiple of \(3\).

\[ 2 \mid x \implies 3 \mid x. \]

In other words, if an integer is a multiple of 6, then it is a multiple of 2 as well as 3. But this is not equivalent to claiming that if an integer is a multiple of 2, then it is also a multiple of 3. Such a claim is clearly false as we can confirm for \(x \in \{3, 9, 15, 21, \dots\}\).

Encoding intuition correctly

My intuition incorrectly concluded that the \(\bigl((A \implies B) \land (B \implies C)\bigr) \iff (A \implies 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.

\[ \bigl((A \implies B) \land (B \implies C)\bigr) \implies (A \implies C). \]

Indeed, this statement is valid as can be seen from the truth table below.

\(A\)\(B\)\(C\) \(A \implies B\)\(B \implies C\)\(A \implies C\) \((A \implies B) \land (B \implies C)\) \(\bigl((A \implies B) \land (B \implies C)\bigr)\) \(\implies\) \((A \implies C)\)
TTT TTT T T
TTF TFF F T
TFT FTT F T
TFF FTF F T
FTT TTT T T
FTF TFT F T
FFT TTT T T
FFF TTT T T

No comments

Post a comment

RSS