All the binary connectives we have learned so far – conjunction, disjunction and exclusive disjunction, were commutative – the order of the propositions connected by them did not matter. Now, we will learn an important binary connective which is not commutative – the *implication*.

**Definition**: Implication

Let \(L\) be a set of propositions with the interpretation $I$ and the corresponding valuation function $[[]]_I$. An **implication** “\(\Rightarrow\)” is a Boolean function

\[\Rightarrow :=\begin{cases}L \times L & \mapsto L \\

(x,y) &\mapsto x \Rightarrow y.

\end{cases}\]

defined by the following truth table:

$[[x]]_I$ | $[[y]]_I$ | $[[x \Rightarrow y]]_I$ |
---|---|---|

\(1\) | \(1\) | \(1\) |

\(0\) | \(1\) | \(1\) |

\(1\) | \(0\) | \(0\) |

\(0\) | \(0\) | \(1\) |

We read the implication $x\Rightarrow y$

“*if* $x$ *then* $y$”.

### Notes

- It is apparent from the truth table that the implication is not commutative – the order of the propositions connected by it counts. Therefore, both propositions have specific names – the first one is called the
**antecedent**, the second one the**consequent.** - The implication of two propositions is only false if a true antecedent implies a false consequent. This is called a
**contradiction**. Note that a false antecedent can imply both a true and a false consequent, without creating a contradiction. - But if a true antecedent implies a true consequent, we say it is a
**valid argument**. - There are more different readings of the implication $x\Rightarrow y$:
- If $x$, then $y$.
- $y$ follows from $x$.
- $x$ is
**sufficient**for $y$. - $y$ is
**necessary**for $x$. - $y$, if $x$.
- $x$, only if $y$.

- It is helpful to think about the implication as a
*cause*and*effect*chain.

| | | | | Contributors: *bookofproofs* | References: [7838]

## 1.**Lemma**: Implication as a Disjunction

## 2.**Lemma**: Negation of an Implication

## 3.**Definition**: Contrapositive

[7838] **Kohar, Richard**: “Basic Discrete Mathematics, Logic, Set Theory & Probability”, World Scientific, 2016

© 2018 Powered by BooOfProofs, All rights reserved.