Implication and equivalence

Propositional Logic: Introduction

Implication and equivalence

The transcription of natural language into a logical formula really becomes difficult with a conditional statement such as the implication. In natural language, we can make an "if...then..." construction in many ways, with different nuances. Below are a number of language expressions where $p$ and $q$ are meaningful statements about a fact (think, for example, "The sun is shining" and "I am biking"). Here we write "when/if" in case either of these two words can be used.

"If $p$ , then $q$ ."	" $q$ whenever $p$
"When/If $p$ , $q$ ."	" $q$ only as $p$ ."
" $p$ is sufficient for $q$ ."	"A sufficient condition for $q$ is $p$ ."
" $q$ when/if $p$ ."	" $q$ is necessary for $p$ ."
"A necessary condition for $p$ is $q$ ."	" $q$ follows from $p$ ."
" $q$ provided $p$ ."	" $q$ given that $p$ ."
" $q$ unless $\neg\,p$ ."	" $q$ provided $q$ ."

As an example, let's take a closer look at the sentence structure " $q$ only as $p$ ." having in mind the sample sentence "If you are good, you will get a piece of candy." spoken by a father to his son. If he is not good, the son should not expect any candy, although the father can give it anyway. This corresponds to the fact that the implication $g\rightarrow c$ and the formula $\neg\,g \lor c$ have the same truth table and are therefore logically equivalent.

Only if the son is good, but the father does not keep his promise, will the son be disappointed. This scenario corresponds in propositional logic to the situation where $g$ is true and $c$ is false in the proposition $g\rightarrow c$ . The formula $g\land \neg\,c$ in this scenario returns the truth value true and is the opposite of $\neg\,g \lor c$ . If the father says to his son "You get a candy, only if you are good" then it is clear in common language that the son will not get a candy if he is not good. This corresponds to $\neg\,g \oplus c$ , where $\oplus$ symbolises exclusive disjunction. The reason why we have put " $q$ only if $p$ ." in the above list of statements that are sentence constructions of implication is that we usually ignore such nuances in natural language in the process of transcription.

Implication

The implication $\varphi \rightarrow \psi$ of two propositions $\varphi$ and $\psi$ is a proposition which is false if $\varphi$ is true and $\psi$ is false, and true in all other cases.

So we consider $\varphi \rightarrow \psi$ and $\neg \,\varphi \lor \psi$ as logically equivalent formulas.

The symbol for the infix implication operator is $\rightarrow$

Example

The implication "If Marthe is ill, she stays at home." is true if the statements "Marthe is ill." and "She stays at home" are true.

But this implication is also true if the statement "Marthe is ill." is false.

The implication is only false if Marthe is ill, but does not stay at home. It cannot be that the statement "Marthe is ill." is true, but the statement "She stays at home" is false.
$\phantom{x}$

An Implication is an utterance of causality. The truth of the left-hand side of the proposition $\varphi\rightarrow \psi$ also means that the right-hand side is true. In a causal relationship, the right-hand side can still be true or false if the left-hand side is false. This is why thruth valuse of $\varphi\rightarrow \psi$ is defined as true in case $\varphi$ is false.

We have already noted a few times that in natural language the proposition "If $p$ , then $q$ " is often interpreted as a causal relationship that makes $q$ true because $p$ is true. But in classical logic this need not be the case. We can only draw the following two conclusions:

(Modus ponens) $q$ follows from $p$ and $p\rightarrow q$ .
(Mode tollens) $\neg p$ follows from $\neg\,q$ and $p\rightarrow q$ .

Computer language The if-then construction in most programming languages differs from the if-then construction in propositional logic. In most programming languages, the code "if condition then statement" means "if the condition is met, then execute the code, otherwise don't". As soon as the condition is not met, the code in the then part is no longer executed.

If you want to keep the propositional notation as close as possible to natural language, then a reverse arrow notation is obvious. The sentence "Marthe stays home when she is sick." is then transcribed to $q\leftarrow p$ with $p=\text{"She is ill."}$ and $p=\text{"Marthe stays at home"}$

In practice you will also encounter the implication arrow $\implies$ instead of $\rightarrow$ to make an "if ... then ..." statement in logic. Although they are often used interchangeably, there is a subtle difference. With $\varphi\rightarrow\psi$ the truth depends only on the truth values of $\varphi$ and $\psi$ ; the definition of the implication arrow $\rightarrow$ is defined via a truth table. The symbol $\implies$ is actually meant to be an implication symbol in the meta-language through which we talk about logic formulas. An example may make this subtle distinction clearer.

Suppose $\varphi$ is a formula that contains only the connectives $\neg$ , $\land$ , and $\lor$ . Then the dual formula $\varphi^{\mathrm{d}}$ is defined as the formula resulting from replacing every occurrence of $\land$ in $\varphi$ with $\lor$ and replacing every occurrence of $\lor$ in $\varphi$ with $\land$ . Now suppose that $\varphi$ and $\psi$ are equivalent formulas containing only the connectives $\neg$ , $\land$ , and $\lor$ . From this we may conclude that $\varphi^{\mathrm{d}}$ and $psi^{\mathrm{d}}$ are also logically equivalent. This is a statement about logical formulas that does not quite fall within the system of propositional logic. We therefore write this down with another symbol:

$\varphi\leftrightarrow \psi \implies \varphi^{\mathrm{d}}\leftrightarrow \psi^{\mathrm{d}}$

If $\varphi$ and $\psi$ are logical formulas, then the following truth table is applicable:

$\begin{array}{cc|c} \varphi & \psi & \varphi\rightarrow \psi \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$

With the implication it is easy to introduce logical equivalence of propositions.

Equivalence

Two propositions are logically equivalent (in short: equivalent) when the two propositions have the same truth value in all cases, i.e., either both true or both false; in all other cases the propositions are not equivalent.

Equivalence is symbolised by the infix operator $\leftrightarrow$ , which represents the connective "exactly if" in natural language. Other popular phrases in plain language include "...if...and not otherwise.", "...only if..." and "if...then..., and vice versa."

In mathematics and propositional logic, the implication $\leftrightarrow$ stands for "if and only if" and "is a necessary and sufficient condition for".

Example

"You can take flight KL1845 on July 25 with departure time 11:45 if and only if you have purchased a flight ticket for flight KL1845 on July 25 with departure time 11:45." In order to be able to take the planned flight, you must have purchased a valid flight ticket, and you can take this flight only if you have purchased a valid flight ticket.

Natural language In natural language, the distinction between implication and equivalence is often blurred. If a mother says to her child "If you finish your plate, you get dessert." she usually implicitly means that her child only gets a dessert if s/he finishes her/his plate. If the child gets dessert, then s/he has finished her/his plate, even though this is not explicitly stated in the mother's statement.

In practice you will also come across the double implication arrow $\iff$ instead of $\leftrightarrow$ to make an "if and only if" statement in logic. Although they are often used interchangeably, there is a subtle difference. With $\varphi\leftrightarrow\psi$ the truth depends only on the truth values of $\varphi$ and $\psi$ ; the definition of the equivalence arrow $\leftrightarrow$ is defined via a truth table. The symbol $\iff$ is actually meant to be an equivalence symbol in the meta-language where we talk about logic formulas. An example may make this subtle distinction clearer.

Suppose $\varphi$ is a formula that contains only the connectives $\neg$ , $\land$ , and $\lor$ . Then the dual formula $\varphi^{\mathrm{d}}$ is defined as the formula resulting from replacing every occurrence of $\land$ in $\varphi$ with $\lor$ and replacing every occurrence of $\lor$ in $\varphi$ with $\land$ . Now suppose that $\varphi$ and $\psi$ are equivalent formulas containing only the connectives $\neg$ , $\land$ , and $\lor$ . From this we may conclude that $\varphi^{\mathrm{d}}$ and $\psi^{\mathrm{d}}$ are also logically equivalent, and vice versa. This is a statement about logical formulas that does not quite fall within the system of propositional logic. We therefore write this with another symbol:

$\varphi\leftrightarrow \psi \iff \varphi^{\mathrm{d}}\leftrightarrow \psi^{\mathrm{d}}$

If $\varphi$ and $\psi$ are logical formulas, then the following truth table is applicable:

$\begin{array}{cc|c} \varphi & \psi & \varphi\leftrightarrow \psi \\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$