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:
Truth Table of the Implication
| $[[x]]_I$ |
$[[y]]_I$ |
$[[x \Rightarrow y]]_I$ |
| \(1\) |
\(1\) |
\(1\) |
| \(0\) |
\(1\) |
\(1\) |
| \(1\) |
\(0\) |
\(0\) |
|
\(0\) |
\(0\) |
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.
Table of Contents
- Lemma: Implication as a Disjunction
- Lemma: Negation of an Implication
- Definition: Contrapositive
Mentioned in:
Branches: 1
Definitions: 2 3
Examples: 4
Explanations: 5
Lemmas: 6 7 8 9 10 11 12 13 14
Parts: 15
Proofs: 16 17 18 19 20 21 22 23 24 25 26
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Kohar, Richard: "Basic Discrete Mathematics, Logic, Set Theory & Probability", World Scientific, 2016
