Truly Understanding Logical Implication

Why "false implies anything"

Implication can be written in various ways (→, ⊃, ⇒) and it is the trickiest propositional-logic connective to understand properly. For this tutorial, which I have prepared for the Summer of Math Exposition, I plan to explain implication.

In particular, I will reveal what is behind the claim false implies anything and also what exactly is the link between implication and the if-then-else construction in typical programming languages.

Propositional Logic

But first, we have to discuss a little bit about propositional logic. Propositional logic is the logic of propositions, with propositions being statements that are either true or false.

Let us see a few examples:

• Snow is white.

• 2 + 2 = 4.

• It is raining.

• 2 x 2 = 7.

The first two are true, the last two are false (because it is currently not raining).

Here are a few examples of phrases that are not propositions:

• Is it snowing?

• Take a break!

• Red and black

• This sentence is false.

Questions (is it snowing?) are not propositions. Imperative statements (take a break!) are also not propositions. Nouns and noun phrases (red and black) of various shapes and forms are also not considered to be propositions.

More interestingly, various self-referential statements like this statement is false are also not considered to be propositions. This is because if we accepted the statement to be true, we would need to believe what is states, and it states that it is false. So the sentence would need to be both true and false. Similar story if we accepted the statement to be false. To keep things simple, logicians just stay clear of such statements and do not consider them to be propositions.

Molecular Propositions

All of our example propositions happen to be particularly simple; they are atomic, because they cannot be split into smaller propositions. But propositional logic also features more interesting propositions, which are called molecular.

These are constructed by joining together smaller propositions. Here are a few examples:

• Snow is white and 2 + 2 = 4.

• Snow is not white or 2 + 2 = 4 and it is raining.

The words (and, not, or, …) used in propositional logic to connect small propositions in order to build larger propositions are called propositional connectives or logical connectives or sometimes just simply connectives.

There are many connectives in propositional logic. The most common ones are:

• negation, which is expressed by words such as not or it is not true that;

• conjunction, which is expressed by words such as and, and also, but;

• disjunction, which is typically expressed by the word or; and

• implication, which is typically read if-then.

There are also some other connectives (double implication, exclusive or, …) in propositional logic, but they are not as widely used and they can all be expressed in terms of the connectives discussed above, so we will not delve into them.

Truth Values

The most important concept to discuss next is that of truth value. By definition, any proposition, be it atomic or molecular, has a truth value. The truth value of a proposition is denoted by VALUE and is either true, or false.

Let us take a molecular proposition as an example:

• Snow is white and 2 + 2 = 4.

How do we find its truth value?

An important trait of propositional logic, which helps answer this question, is that the truth value of a molecular proposition is considered to depend only on the truth values of the components:

• VALUE(Snow is white and 2 + 2 = 4) = F(VALUE(Snow is white), VALUE(2 + 2 = 4)).

The truth value of a proposition does not, in general, depend on the components themselves:

• VALUE(Snow is white and 2 + 2 = 4) = F(Snow is white, 2 + 2 = 4).

This makes propositional logic a truth-functional logic, because the truth value of a molecular proposition is a function of the truth values of its constituents.

In our example conjunction, both conjuncts are true (VALUE(Snow is white) = true and also VALUE(2 + 2 = 4) = true), and therefore the entire conjunction is also true.

This property, of being truth-functional, means that propositional logic is only a rough approximation of English, or of whatever language you speak natively. For example, an English statement such as

• It is raining but I have an umbrella.

would be considered a conjunction in propositional logic. The contrast between having an umbrella and rain, suggested by the use of the word but, is lost in translation. In propositional logic, there would be no difference between the proposition above and It is raining and I have an umbrella.

This fact, that propositional logic is a truth-functional approximation of English, turns out to be one key insight needed to truly understand implication.

Implication

Implication is a propositional connective, and therefore the truth value of an implication φ → ψ depends on the truth value of the antecedent, φ, and of the consequent, ψ. Depending on the truth values of the antecedent and the consequent, there are four cases to consider, which we organize into a truth table:

The second line of this table is sometimes controversial. This controversy is generated by a misunderstanding of propositional implication.

Propositions such as

• If it is raining, then I use an umbrella

are considered to be implications in propositional logic, the antecedent being it is raining and the consequent being I use an umbrella.

Remember that propositional logic is an imperfect approximation of English and that the truth value of an implication in its entirety is considered to depend only on the truth values of the constituent parts. This is a bit unfortunate, because English statements such as the one in our example typically convey to the reader some more information. In our example, the fact that it is raining causes me to use an umbrella. But in propositional logic, this cause-effect relation is lost. In propositional logic, the meaning of the sentence is weaker. It simply means that if the antecedent is true, then the consequent must be true as well, without necessarily implying a causality relation between them.

To emphasise the fact that propositional implication does not convey any information on causality, some authors refer to implication as material implication, or truth-functional implication.

As an immediate consequence, material implication allows for seemingly non-sensical propositions such as If the Earth is flat, then 2 + 2 = 4.

Such propositions are syntactically allowed in propositional logic and their truth values are well defined, even if there is absolutely no causality relation between the Earth being flat, or not, and 2 + 2 being 4.

Knowing that implication is weaker in propositional logic than in English, it is somewhat easier to accept that the seemingly non-sensical statement If the Earth is flat, then 2 + 2 = 4 is true. This fact corresponds to the second line in the truth table for implication.

In our case, the antecedent is false, because the Earth is not flat, and the consequent is true, because 2 + 2 is 4, and therefore the implication in its entirety is true.

If you disagree with truth functionality, know that you are not alone: there are logicians studying non-truth-functional logics, such as relevance logic.

Truth Table

But, by definition, propositional logic is truth-functional and it turns out that truth-functionality is the right choice for doing math and computer science. Assuming you do agree with the principle of truth functionality, I will now convince you that the only reasonable truth table for implication is the one that we have just seen:

I will use a fact from elementary mathematics, which you will agree to, no doubt:

• Any natural number is an integer.

Let us rephrase this slightly:

• If x is a natural, then x is an integer.

You will agree that the statement holds for any value of x. In particular, the statement must be true for x = 42, x = -7 and x = π.

For x = 42, the antecedent is true, because 42 is a natural number. The consequent is also true, because 42 is an integer. This explains the last line in the truth table – if you agree that any natural is an integer, then you must also agree that an implication with a true antecedent and a true consequent is true.

For x = -7, the antecedent is false, because -7 is not a natural, and the consequent is true, because -7 is an integer. This corresponds to the second line of the truth table. As you have already agreed to our statement any natural is an integer, we need to have true in the result column in this second line. This is easily the most controversial line in the truth table, but we do not have much choice here.

Taking x to be π, we now have that both the antecedent and the consequent are false. This corresponds to line one in the truth table, where we must also have the value true in the result column.

The only line unaccounted for is line three, but the result in line three is hardly controversial, and matches everyone's intuition about implication. Moreover, if the result were true in the third line, then any implication whatsoever would be true, and the connective would be completely devoid of any sense, so it wouldn't be of much use.

Summing up, if you agree to the principle of truth functionality and to the statement any natural is an integer, then the only reasonable interpretation for implication is the standard one, whose truth table is given here.

False Implies Anything

The truth function associated to implication assigns the value true to any implication where the antecedent is false, independently of whether the consequent is true or false. This fact is often summarised under the slogan false implies anything, meaning that false implies both true and false.

This explains why the sentences If the Earth is flat, then 2 + 2 = 4 and If the Earth is flat then 2 + 2 ≠ 4 are both considered to be true in propositional logic.

As their antecedents are false, even if there is no causality relation between the Earth being flat, or not, and arithmetic, each of the two implications must be true, according to the first two lines in the truth table.

Conditional Statements

There is one more issue that I want to address, which is the link between implication and the conditional statement in programming languages.

You might stumble upon various sources of information that first teach you some logic and then proceed to claim that the if-then-else construction in typical programming languages is in some way an implication in disguise, with the condition of the statement acting as the antecedent of the implication and the then-branch acting as the consequent of the implication:

While there are indeed many important uses of logic in programming and computer science, there is absolutely no link whatsoever between propositional implication and the conditional statement and I want to dispel this myth.

It is rather easy to see that in an imperative language, the statement in the then-branch is an instruction for the computer:

But instructions are not propositions. This is because, by definition, a proposition is a statement that is either true or false. Instructions, which are imperative statements, do not count as propositions. Therefore, while the condition of the if-then statement could under certain assumptions be modelled as a proposition and act as the antecedent of some implication, the instruction in the then-block is not a proposition and therefore cannot be the consequent of any logical implication.

A similar line of reasoning carries over to functional languages such as Haskell, which have conditional expressions instead of conditional statements:

if x < n then    
    x + 1           ← noun phrase, not a proposition
else    
    x               ← what about the else branch?

In such languages, the then-branch is some expression to be evaluated when the condition is true, and the expression is a noun, not a proposition. Furthermore, the conditional expression in a functional language must have an else branch, which would not fit anywhere in the landscape of conditionals-as-implications myth.

Truly Understanding Algorithms

If you enjoy programming and want to learn more about algorithms, make sure you subscribe to the Truly Understanding Algorithms YouTube channel.