2.5. Deduction

Logic can be applied to draw conclusions from a set of premises. A premise is just a proposition that is known to be true or that has been accepted to be true for the sake of argument, and a conclusion is a proposition that can be deduced logically from the premises. The idea is that if you believe that the premises are true, then logic forces you to accept that the conclusion is true. An argument is a claim that a certain conclusion follows from a given set of premises. Here is an argument laid out in a traditional format:

If today is Tuesday, then this is Belgium
Today is Tuesday
\(\therefore\) This is Belgium

The premises of the argument are shown above the line, and the conclusion below. The symbol \(\therefore\) is read ‘therefore’. The claim is that the conclusion, ‘’This is Belgium’’, can be deduced logically from the two premises, ‘’If today is Tuesday, then this is Belgium’’ and ‘’Today is Tuesday’’. In fact, this claim is true. Logic forces you to accept this argument. Why is that?

2.5.1. Arguments

Let \(p\) stand for the proposition ‘’Today is Tuesday’’, and let \(q\) stand for the proposition ‘’This is Belgium’’. Then the above argument has the form

\(p\rightarrow q\)
\(p\)
\(\therefore\) \(q\)

Now, for any propositions \(p\) and \(q\)—not just the ones in this particular argument—if \(p\rightarrow q\) is true and \(p\) is true, then \(q\) must also be true. This is easy to check in a truth table:

\(p\)	\(q\)	\(p\rightarrow q\)
0	0	1
0	1	1
1	0	0
1	1	1

The only case where both \(p\rightarrow q\) and \(p\) are true is on the last line of the table, and in this case, \(q\) is also true. If you believe \(p\rightarrow q\) and \(p\), you have no logical choice but to believe \(q\). This applies no matter what \(p\) and \(q\) represent. For example, if you believe ‘’If Jill is breathing, then Jill pays taxes’’, and you believe that ‘’Jill is breathing’’, logic forces you to believe that ‘’Jill pays taxes’’. Note that we can’t say for sure that the conclusion is true, only that if the premises are true, then the conclusion must be true.

This fact can be rephrased by saying that \(\big((p\rightarrow q)\wedge p\big)\rightarrow q\) is a tautology. More generally, for any compound propositions \(\mathscr{P}\) and \(\mathscr{Q}\), saying ‘’\(\mathscr{P}\rightarrow \mathscr{Q}\) is a tautology’’ is the same as saying that ‘’in all cases where \(\mathscr{P}\) is true, \(\mathscr{Q}\) is also true’’.^[1] We will use the notation \(\mathscr{P}\Longrightarrow\mathscr{Q}\) to mean that \(\mathscr{P}\rightarrow \mathscr{Q}\) is a tautology. Think of \(\mathscr{P}\) as being the premise of an argument or the conjunction of several premises. To say \(\mathscr{P}\Longrightarrow\mathscr{Q}\) is to say that \(\mathscr{Q}\) follows logically from \(\mathscr{P}\). We will use the same notation in both propositional logic and predicate logic. (Note that the relation of \(\Longrightarrow\) to \(\rightarrow\) is the same as the relation of \(\equiv\) to \(\leftrightarrow\).)

Definition 2.10

Let \(\mathscr{P}\) and \(\mathscr{Q}\) be any formulas in either propositional logic or predicate logic. The notation \(\mathscr{P}\Longrightarrow\mathscr{Q}\) is used to mean that \(\mathscr{P}\rightarrow\mathscr{Q}\) is a tautology. That is, in all cases where \(\mathscr{P}\) is true, \(\mathscr{Q}\) is also true. We then say that \(\mathscr{Q}\) can be logically deduced from \(\mathscr{P}\) or that \(\mathscr{P}\) logically implies \(\mathscr{Q}\).

An argument in which the conclusion follows logically from the premises is said to be a valid argument. To test whether an argument is valid, you have to replace the particular propositions or predicates that it contains with variables, and then test whether the conjunction of the premises logically implies the conclusion. We have seen that any argument of the form

\(p\rightarrow q\)
\(p\)
\(\therefore\) \(q\)

is valid, since \(\big((p\rightarrow q)\wedge p\big)\rightarrow q\) is a tautology. This rule of deduction is called modus ponens. It plays a central role in logic. Another, closely related rule is modus tollens, which applies to arguments of the form

\(p\rightarrow q\)
\(\lnot q\)
\(\therefore\) \(\lnot p\)

To verify that this is a valid argument, just check that \(\big((p\rightarrow q)\wedge \lnot q\big)\Longrightarrow \lnot p\), that is, that \(\big((p\rightarrow q)\wedge \lnot q\big)\rightarrow \lnot p\) is a tautology. As an example, the following argument has the form of modus tollens and is therefore a valid argument:

If Feyenoord is a great team, then I’m the king of the Netherlands
I am not the king of the Netherlands
\(\therefore\) Feyenoord is not a great team

You might remember this argument from this section. You should note carefully that the validity of this argument has nothing to do with whether or not Feyenoord can play football well. The argument forces you to accept the conclusion only if you accept the premises. You can logically believe that the conclusion is false, as long as you believe that at least one of the premises is false.^[2]

Another named rule of deduction is the Law of Syllogism, which has the form

\(p\rightarrow q\)
\(q\rightarrow r\)
\(\therefore\) \(p\rightarrow r\)

For example:

If you study hard, you do well in school
If you do well in school, you get a good job
\(\therefore\) If you study hard, you get a good job

There are many other rules. Here are a few that might prove useful. Some of them might look trivial, but don’t underestimate the power of a simple rule when it is combined with other rules.

\(p\vee q\)
\(\lnot p\)
\(\therefore\) \(q\)

\(p\)
\(q\)
\(\therefore\) \(p\wedge q\)

\(p\wedge q\)
\(\therefore\) \(p\)

\(p\)
\(\therefore\) \(p\vee q\)

Logical deduction is related to logical equivalence. We defined \(\mathscr{P}\) and \(\mathscr{Q}\) to be logically equivalent if \(\mathscr{P}\leftrightarrow\mathscr{Q}\) is a tautology. Since \(\mathscr{P}\leftrightarrow\mathscr{Q}\) is equivalent to \((\mathscr{P}\rightarrow\mathscr{Q})\wedge(\mathscr{Q}\rightarrow\mathscr{P})\), we see that \(\mathscr{P}\equiv \mathscr{Q}\) if and only if both \(\mathscr{Q}\Longrightarrow\mathscr{P}\) and \(\mathscr{P}\Longrightarrow\mathscr{Q}\). Thus, we can show that two statements are logically equivalent if we can show that each of them can be logically deduced from the other. Also, we get a lot of rules about logical deduction for free—two rules of deduction for each logical equivalence we know. For example, since \(\lnot(p\wedge q)\equiv (\lnot p\vee \lnot q)\), we get that \(\lnot(p\wedge q)\Longrightarrow (\lnot p\vee \lnot q)\). For example, if we know ‘’It is not both sunny and warm’’, then we can logically deduce ‘’Either it’s not sunny or it’s not warm.’’ (And vice versa.)

2.5.2. Valid arguments and proofs

In general, arguments are more complicated than those we’ve considered so far. Here, for example, is an argument that has five premises:

\((p\wedge r)\rightarrow s\)
\(q\rightarrow p\)
\(t\rightarrow r\)
\(q\)
\(t\)
\(\therefore\) \(s\)

Is this argument valid? Of course, you could use a truth table to check whether the conjunction of the premises logically implies the conclusion. But with five propositional variables, the table would have 32 lines, and the size of the table grows quickly when more propositional variables are used. So, in general, truth tables are not practical when we have a large number of variables.

Video

For a relatively small number of variables (say three or fewer) a truth table can be a rather efficient method to test validity of an argument. In one of the pencasts of this course I show how you can use truth tables to test for validity as well as how you can use them to find counterexamples for invalid arguments: youtu.be/lSZS3qbA88o

Fortunately, there is another way to proceed, based on the fact that it is possible to chain several logical deductions together. That is, if \(\mathscr{P}\Longrightarrow\mathscr{Q}\) and \(\mathscr{Q}\Longrightarrow\mathscr{R}\), it follows that \(\mathscr{P}\Longrightarrow\mathscr{R}\). This means we can demonstrate the validity of an argument by deducing the conclusion from the premises in a sequence of steps. These steps can be presented in the form of a proof:

Definition 2.11

A formal proof that an argument is valid consists of a sequence of propositions such that the last proposition in the sequence is the conclusion of the argument, and every proposition in the sequence is either a premise of the argument or follows by logical deduction from propositions that precede it in the list.

The existence of such a proof shows that the conclusion follows logically from the premises, and therefore that the argument is valid. Here is a formal proof that the argument given above is valid. The propositions in the proof are numbered, and each proposition has a justification.

Proof. .

1.	\(q\rightarrow p\)	premise
2.	\(q\)	premise
3.	\(p\)	from 1 and 2 (modus ponens)
4.	\(t\rightarrow r\)	premise
5.	\(t\)	premise
6.	\(r\)	from 4 and 5 (modus ponens)
7.	\(p\wedge r\)	from 3 and 6
8.	\((p\wedge r)\rightarrow s\)	premise
9.	\(s\)	from 7 and 8 (modus ponens)

□

Tip

Once a formal proof has been constructed, it is convincing. Unfortunately, it’s not necessarily easy to come up with the proof. Usually, the best method is a combination of working forward (‘’Here’s what I know, what can I deduce from that?’’) and working backwards (‘’Here’s what I need to prove, what other things would imply that?’’). For this proof, I might have thought: I want to prove \(s\). I know that \(p\wedge r\) implies \(s\), so if I can prove \(p\wedge r\), I’m okay. But to prove \(p\wedge r\), it’ll be enough to prove \(p\) and \(r\) separately… .

Of course, not every argument is valid, so the question also arises, how can we show that an argument is invalid? Let’s assume that the argument has been put into general form, with all the specific propositions replaced by propositional variables. The argument is valid if in all cases where all the premises are true, the conclusion is also true. The argument is invalid if there is even one case where all the premises are true and the conclusion is false. We can prove that an argument is invalid by finding an assignment of truth values to the propositional variables which makes all the premises true but makes the conclusion false. We call such an assignment a counterexample . To disprove the validity of an argument you should always provide a counterexample. This holds in propositional logic, predicate logic, and any other type of argument you may be asked to disprove.

For example, consider an argument of the form:

\(p\rightarrow q\)
\(q\rightarrow (p\wedge r)\)
\(r\)
\(\therefore\) \(p\)

In the case where \(p\) is false, \(q\) is false, and \(r\) is true, the three premises of this argument are all true, but the conclusion is false. This counterexample shows that the argument is invalid.

To apply all this to arguments stated in English, we have to introduce propositional variables to represent all the propositions in the argument. For example, consider:

John will be at the party if Mary is there and Bill is not there. Mary will be at the party if it’s on Friday or Saturday. If Bill is at the party, Tom will be there. Tom won’t be at the party if it’s on Friday. The party is on Friday. Therefore, John will be at the party.

Let \(j\) stand for ‘’John will be at the party’’, \(m\) for ‘’Mary will be there’’, \(b\) for ‘’Bill will be there’’, \(t\) for ‘’Tom will be there’’, \(f\) for ‘’The party is on Friday’’, and \(s\) for ‘’The party is on Saturday’’. Then this argument has the form

\((m\wedge \lnot b)\rightarrow j\)
\((f\vee s)\rightarrow m\)
\(b\rightarrow t\)
\(f\rightarrow \lnot t\)
\(f\)
\(\therefore\) \(j\)

This is a valid argument, as the following proof shows:

Proof. .

1.	\(f\rightarrow\lnot t\)	premise
2.	\(f\)	premise
3.	\(\lnot t\)	from 1 and 2 (modus ponens)
4.	\(b\rightarrow t\)	premise
5.	\(\lnot b\)	from 4 and 3 (modus tollens)
6.	\(f\vee s\)	from 2
7.	\((f\vee s)\rightarrow m\)	premise
8.	\(m\)	from 6 and 7 (modus ponens)
9.	\(m\wedge\lnot b\)	from 8 and 5
10.	\((m\wedge\lnot b)\rightarrow j\)	premise
11.	\(j\)	from 10 and 9 (modus ponens)

□

Note

You may have noticed that we start our proofs with the word ‘proof’ and end it with a little square. This is done to illustrate clearly where our proof starts and ends. Historically different symbols and expressions have been used to indicate that a proof is done. You may have heard of the abbreviation Q.E.D. for instance for ‘Quod Erat Demonstrandum’, which translates to: ‘what was to be shown’. Even in ancient Greece a Greek version of Q.E.D. was used by Greek mathematicians like Euclid. You are free to choose between Q.E.D. and the open square, so long as you remember that no proof is complete if it does not have either one of them.

2.5.3. Proofs in predicate logic

So far in this section, we have been working mostly with propositional logic. But the definitions of valid argument and logical deduction apply to predicate logic as well.

One of the most basic rules of deduction in predicate logic says that \((\forall xP(x))\Longrightarrow P(a)\) for any entity \(a\) in the domain of discourse of the predicate \(P\). That is, if a predicate is true of all entities, then it is true of any given particular entity. This rule can be combined with rules of deduction for propositional logic to give the following valid arguments:

\(\forall x(P(x)\rightarrow Q(x))\)
\(P(a)\)
\(\therefore\) \(Q(a)\)

\(\forall x(P(x)\rightarrow Q(x))\)
\(\lnot Q(a)\)
\(\therefore\) \(\lnot P(a)\)

These valid arguments go by the names of modus ponens and modus tollens for predicate logic. Note that from the premise \(\forall x(P(x)\rightarrow Q(x))\) we can deduce \(P(a)\rightarrow Q(a)\). From this and from the premise that \(P(a)\), we can deduce \(Q(a)\) by modus ponens. So the first argument above is valid. The second argument is similar, using modus tollens.

The most famous logical deduction of them all is an application of modus ponens for predicate logic:

All humans are mortal
Socrates is human
\(\therefore\) Socrates is mortal

This has the form of modus ponens with \(P(x)\) standing for ‘’\(x\) is human’’, \(Q(x)\) standing for ‘’\(x\) is mortal’’, and \(a\) standing for the noted entity, Socrates.

To disprove validity of arguments in predicate logic, you again need to provide a counterexample. These are most easily given in the form of a mathematical structure. Consider for instance the following argument:

\(\exists x P(x)\)
\(\forall x(P(x) \to Q(x))\)
\(\therefore\) \(\forall xQ(x)\)

This argument is not valid and we can prove that using the following structure \(\mathcal{A}\).

• \(D = \{a,b\}\)

• \(P^\mathcal{A} = \{a\}\)

• \(Q^\mathcal{A} = \{a\}\)

As you can see, the first premise is true. There is an \(x\) such that \(P(x)\) holds, namely \(x=a\). The second premise is also true, as for all \(x\) for which \(P(x)\) holds (so only \(x=a\)), \(Q(x)\) also holds (and indeed \(Q(a)\)) holds. However the conclusion is false, as \(Q(b)\) does not hold, so the \(Q(x)\) does not hold for all \(x\).

There is a lot more to say about logical deduction and proof in predicate logic, and we’ll spend the whole of the next chapter on the subject.

2.5.4. Exercises

Exercise (1†)

Verify the validity of modus tollens and the Law of Syllogism.

Exercise (2†)

Each of the following is a valid rule of deduction. For each one, give an example of a valid argument in English that uses that rule.

\(p\vee q\)
\(\lnot p\)
\(\therefore\) \(q\)

\(p\)
\(q\)
\(\therefore\) \(p\wedge q\)

\(p\wedge q\)
\(\therefore\) \(p\)

\(p\)
\(\therefore\) \(p\vee q\)

Exercise (3†)

There are two notorious invalid arguments that look deceptively like modus ponens and modus tollens:

\(p\rightarrow q\)
\(q\)
\(\therefore\) \(p\)

\(p\rightarrow q\)
\(\lnot p\)
\(\therefore\) \(\lnot q\)

Show that each of these arguments is invalid. Give an English example that uses each of these arguments.

Exercise (4†)

Decide whether each of the following arguments is valid. If it is valid, give a formal proof. If it is invalid, show that it is invalid by finding an appropriate assignment of truth values to propositional variables.

1. \(p\rightarrow q\)
   \(q\rightarrow s\)
   \(s\)
   \(\therefore\) \(p\)

2. \(p\wedge q\)
   \(q\rightarrow (r\vee s)\)
   \(\lnot r\)
   \(\therefore\) \(s\)

3. \(p\vee q\)
   \(q\rightarrow (r\wedge s)\)
   \(\lnot p\)
   \(\therefore\) \(s\)

4. \((\lnot p)\rightarrow t\)
   \(q\rightarrow s\)
   \(r\rightarrow q\)
   \(\lnot(q\vee t)\)
   \(\therefore\) \(p\)

5. \(p\)
   \(s\rightarrow r\)
   \(q\vee r\)
   \(q\rightarrow\lnot p\)
   \(\therefore\) \(\lnot s\)

6. \(q\rightarrow t\)
   \(p\rightarrow(t\rightarrow s)\)
   \(p\)
   \(\therefore\) \(q\rightarrow s\)

Exercise (5†)

For each of the following English arguments, express the argument in terms of propositional logic and determine whether the argument is valid or invalid.

1. If it is Sunday, it rains or snows. Today, it is Sunday and it’s not raining. Therefore, it must be snowing.

2. If there is herring on the pizza, Jack won’t eat it. If Jack doesn’t eat pizza, he gets angry. Jack is angry. Therefore, there was herring on the pizza.

3. At 8:00, Jane studies in the library or works at home. It’s 8:00 and Jane is not studying in the library. So she must be working at home.

---

[1]

Here, ‘’in all cases’’ means for all combinations of truth values of the propositional variables in \(\mathscr{P}\) and \(\mathscr{Q}\), i.e., in every situation. Saying \(\mathscr{P}\rightarrow \mathscr{Q}\) is a tautology means it is true in all cases. But by definition of \(\rightarrow\), it is automatically true in cases where \(\mathscr{P}\) is false. In cases where \(\mathscr{P}\) is true, \(\mathscr{P}\rightarrow \mathscr{Q}\) will be true if and only if \(\mathscr{Q}\) is true.

[2]

Unless the conclusion is a tautology. If that’s the case, then even when a premise is false the conclusion will still be true. You do always know that if the conclusion is false then at least one of the premises is false.