Lesson 7

One of the most frequently used (and least intuitive!) connections is implication: \(x \Rightarrow y\). As we can see from its truth table, implication is false only in the case when \(x=1, y=0\). It can be read as: “truth implies truth only, whereas falsehood implies anything”. Despite the fact that such behavior of implication may raise questions (why do we believe that truth follows from falsehood?), we have already used the fact that it behaves this way. For example, we are confident that the statement \[\text{(\(x\) is divisible by \(4\))}\Rightarrow \text{(\(x\) is divisible by \(2\))}\] is true for all \(x\). By substituting \(x=4,x=5,x=6\), we get all cases when the implication is true: \(1 \Rightarrow 1\), \(0 \Rightarrow 0\), \(0 \Rightarrow 1\).

It is easy to see that \(x \Rightarrow y\) is not equivalent to \(y \Rightarrow x\) (they have different truth tables!). However, it is equivalent to \((\neg y) \Rightarrow (\neg x)\). This is called the principle of contraposition, and we have used it more than once: to prove that from \(x\) follows \(y\), we prove that from \(\neg y\) follows \(\neg x\). Formally, this is written as: \[(x \Rightarrow y) \equiv ((\neg y) \Rightarrow (\neg x)) \ .\]