www.vagupu.

com

Chapter 10 Logic

10 LOGIC
Objectives
After studying this chapter you should
• understand the nature of propositional logic;
• understand the connectives NOT, OR, AND;
• understand implication and equivalence;
• be able to use truth tables;
• be able to identify tautology and contradiction;
• be able to test the validity of an argument.

10.0 Introduction
It may seem unusual for philosophical ideas of logic based on
intuition to be represented mathematically, however, the
mathematics that has developed to describe logic has, in recent
years, been crucial in the design of computer circuits and in
automation.

Charles L Dodgson (1832 -1898) who under the pseudonym

Lewis Carroll wrote 'Alice in Wonderland', was an Oxford
mathematician who wrote about logic. One example of his logic
problems concerns Mrs Bond's ducks.

Activity 1 Do ducks wear collars?

The following lines are taken from Lewis Carroll's book
'Symbolic Logic' first published in 1897.

"All ducks in this village, that are branded 'B' belong to

Mrs Bond;

Ducks in this village never wear lace collars, unless they

are branded 'B';

Mrs Bond has no grey ducks in this village."

Is the conclusion 'no grey ducks in this village wear lace collars'
valid?

153
 www.vagupu.com

Chapter 10 Logic

10.1 The nature of logic

The Greek philosopher Aristotle (384-322 BC) is considered to
be the first to have studied logic in that he formed a way of
representing logical propositions leading to a conclusion.
Aristotle's theory of syllogisms provides a way of analysing
propositions given in the form of statements.

For example, here are some propositions.

All apples are fruits.

No toothache is pleasant.

Some children like chocolate.

Some cheese is not pasteurised.

In each of these statements a subject, S (e.g. apples) is linked to

a predicate, P (e.g. fruits). The quantity of each subject is
indicated by the word 'all', 'no' or 'some'.

Statements can also be described as universal ('all' or 'no') or

particular ('some') and affirmative or negative.

The four statements above can be described in this way:

all S is P universal affirmative

no S is P universal negative

some S is P particular affirmative

some S is not P particular negative .

Aristotle described an argument by linking together three

statements; two statements, called premises, lead to a third
statement which is the conclusion based on the premises. This
way of representing an argument is called a syllogism.

Example
If fruits are tasty

and apples are fruits

then apples are tasty.

In this example of a syllogism the conclusion of the argument

has apples as subject (S) and tasty as predicate (P). The first
premise includes P and the second premise includes S and both
the premises include 'fruit', which is known as the middle term
(M).

154
 www.vagupu.com

Chapter 10 Logic

The syllogism can therefore be described as:

If M is P

and S is M

then S is P.

Activity 2 Finding the figure

By removing all the words the last example can be described as

MP

SM

SP

On the assumption that

• the conclusion of the argument must be SP,
• the first premise must contain P,
• the second premise must contain S,
• both the first and the second premise must contain M,
find the three other arrangements.

Together these are known as the four figures of the syllogism.

Not all syllogisms are valid

Each of the four figures can be universal or particular, affirmative
or negative, but not all these arrangements give valid arguments.

Example
Is this valid?

No M is P

All S is M

Some S is P.

155
 www.vagupu.com

Chapter 10 Logic

Solution
An example of this syllogism might be:

No animal with 4 legs is a bird

All cats are animals with 4 legs

Some cats are birds.

Obviously this arrangement is an invalid argument!

Activity 3 Valid or invalid?

Decide if these syllogisms are valid.
(a) Some M is P (b) All P is M
All S is M No S is M
All S is P No S is P

(c) No M is P (d) Some P is M

All M is S All M is S
Some S is P Some S is P

10.2 Combining propositions

Modern logic is often called propositional logic; the word
'proposition' is defined as a statement that is either true or false.
So far, a variety of propositions have been considered, such as
premises and conclusions to an argument.

For example, consider the statement

'the water is deep'.

It is not possible to say if this is true or false unless the word

'deep' is defined and, without a precise definition, this cannot be
called a proposition.

Example
• p stands for the proposition 'January has 31 days',
which is true.
• q stands for the proposition ' 4 + 7 = 10 ', which is false.
• 'What a hot day' is not a proposition because it is not in
subject-predicate form; also the word 'hot' is not defined.

156
 www.vagupu.com

Chapter 10 Logic

Negation NOT ~
Each proposition has a corresponding negation and, if the Note
proposition is denoted by p, the negation of the proposition is In the printed form, a
denoted by ~p, read as 'not p'. proposition is shown by a
Example small letter printed bold, eg
a, b.
If p is the proposition 'the table is made of pine',
When writing by hand it is
not easy to make letters bold,
then ~p is the proposition 'the table is not made of pine'.
so each letter is written with
If q is the proposition 'the sack is empty', then ~ q is the a squiggle underneath it (as
statement 'the sack is not empty'. It is not correct to assume that with vectors), to indicate that
the negation is 'the sack is full', since the statement 'the sack is it is a proposition.
not empty' could mean 'the sack is only partly full'. For example, the
proposition printed as p
would be hand written as p .
~
Connectives
Simple propositions such as

'Elgar composed the Enigma Variations'

'Elgar lived in Malvern'

can be joined by the connective 'and' to form a compound

proposition such as

'Elgar composed the Enigma Variations and lived in

Malvern.'

A compound proposition can be described as a proposition

made up of two or more simple propositions joined by
connectives.

There is a variety of connectives which will now be defined.

Conjunction AND ∧
If two propositions are joined by the word AND to form a
compound statement, this is called a conjunction and is denoted
by the symbol ∧ .
Example
If p is the proposition 'the sun is shining'

and q is the proposition 'Jack is wearing sunglasses',

then p ∧ q represents the conjunction 'the sun is shining AND

Jack is wearing sunglasses'

157
 www.vagupu.com

Chapter 10 Logic

Disjunction OR ∨
If two statements are joined by the word OR to form a
compound proposition, this is called a disjunction and is
denoted by the symbol ∨ .

Example
If p is the proposition 'Ann is studying geography'

and q is the proposition 'Ann is studying French'

then the disjunction p ∨ q is the compound statement

'Ann is studying geography OR French.'

The word 'OR' in this context can have two possible meanings.

Can Ann study both subjects?

Think about the meaning of these two sentences.

'I can deliver your coal on Wednesday or Thursday.'

'My fire can burn logs or coal.'

The first sentence implies that there is only one delivery of coal
and illustrates the exclusive use of OR, meaning 'or' but not
'both'. The coal can be delivered on Wednesday or Thursday,
but would not be delivered on both days.

The second sentence illustrates the inclusive use of 'OR'

meaning that the fire can burn either logs or coal, or both logs
and coal.

The word 'OR' and the symbol ' ∨ ' are used for the inclusive
OR, which stands for 'and/or'.

The exclusive OR is represented by the symbol ⊕ .

Activity 4 Exclusive or inclusive?

Write down three English sentences which use the inclusive OR
and three which use the exclusive OR.

Now that a range of connectives is available propositions can be

combined into a variety of compound propositions.

158
 www.vagupu.com

Chapter 10 Logic

Example
Use p, q and r to represent affirmitive (or positive) statements and
express the following proposition symbolically.

'Portfolios may include paintings or photographs but not collages.'

Solution
So, let p be 'portfolios may include paintings'

let q be 'portfolios may include photographs'

and let r be 'portfolios may include collages'.

The proposition therefore becomes

(p ∨ q) ∧ ~ r.

Exercise 10A
1. For each of these compound propositions, use 2. Let p be 'the cooker is working', q 'the food
p, q and r to represent affirmative (or positive) supply is adequate' and r 'the visitors are
statements and then express the proposition hungry'. Write the following propositions in
symbolically. 'plain English':
(a) This mountain is high and I am out of breath. (a) p∧ ~ r
(b) It was neither wet nor warm yesterday. (b) q ∧ r∧ ~ p
(c) During this school year Ann will study two or (c) r∨ ~ q
three subjects.
(d) ~ r∨ ( p ∧ q)
(d) It is not true that 3 + 7 = 9 and 4 + 4 = 8.
(e) ~ q ∧ ( ~ p∨ ~ r)

10.3 Boolean expressions

The system of logic using expressions such as p ∨ q and ~ p ∧ r
was developed by the British mathematician George Boole
(1815 - 1864).

The laws of reasoning were already well known in his time and
Boole was concerned with expressing the laws in terms of a
special algebra which makes use of what are known as Boolean
expressions, such as ~ a∧ b.

159
 www.vagupu.com

Chapter 10 Logic

Activity 5 Using plain English

Define three propositions of your own, p, q and r, and write in plain
English the meaning of these Boolean expressions.

1. q∧r 3. ~ p ∨ ( q ∧ r)
2. ~ p∧ r 4. r∧ ( ~ p ∨ q)

Using truth tables

In Section 10.2 a proposition was defined as a statement that is either
true or false. In the context of logic, the integers 0 and 1 are used to
represent these two states.

0 represents false

1 represents true.

Clearly, if a proposition p is true then ~p is false; also if p is false, then

~ p is true. This can be shown in a truth table, as below.

p ~p
0 1
1 0
Th
e first column shows the two possibilities that the proposition p can be true or false.

The connectives, ∨ and ∧ can also be defined by truth tables, as shown

below.

p q p∧ q
0 0 0
0 1 0
1 0 0
1 1 1

This truth table shows the truth values (0 or 1) of the conjunction p ∧ q .

Since p ∧ q means p AND q, then p ∧ q can only be true (ie 1) when p

is true AND q is true.

If a negation is used, it is best to add the negation column, eg ~p, to the

truth table.

160
 www.vagupu.com

Chapter 10 Logic

Example
Construct the truth table for p ∧ ~ q.

Solution
p q ~q p∧ ~ q
0 0 1 0
0 1 0 0
1 0 1 1
1 1 0 0

If p AND ~q are true (ie both are 1) then p∧ ~ q is true.

Exercise 10B
Construct truth tables for the following.
1. q ∨ r 3. p ∨ ~ r
2. ~ p ∧ r 4. ~ p∨ ~ q

10.4 Compound propositions

More complicated propositions can be represented by truth
tables, building up parts of the expression.

Example
Construct the truth table for the compound proposition
( a∨ b)∨ ~ c.
Solution

a b c (a∨ b) ~c (a∨ b)∨ ~ c

0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 1
1 0 0 1 1 1
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 0 1

161
 www.vagupu.com

Chapter 10 Logic

Exercise 10C
Construct truth tables for the following:
1. ( a∨ b) ∨ c 5. a∧ ( b ∨ c)

2. a∧ ( b ∧ c) 6. ( a∧ b) ∨ ( a∧ c)
3. a∨ ( b ∨ c) 7. a∨ ( b ∧ c)

4. ( a∧ b) ∧ c 8. ( a∨ b) ∧ ( a∨ c)

You should notice that some of your answers in this exercise

are the same. What are the implications of this? Can you
think of similar rules for numbers in ordinary algebra? What
names are given to these properties?

10.5 What are the implications?

'If I win this race, then I will be in the finals.'
'If the light is red, then you must stop.'
These two sentences show another connective, 'if ... then ...'
which is indicated by the symbol ⇒.

x ⇒ y is the compound proposition meaning that proposition x

implies proposition y.

Returning to the compound proposition

'If I win this race, then I will be in the finals',

this can be written as a ⇒ b where a is the proposition 'I win

the race' and b is the proposition 'I will be in the finals'. The
first proposition, a, 'I win this race', can be true or false.
Likewise, the second proposition 'I will be in the finals' can be
true or false.

If I win the race (a is true) and I am in the final (b is true) then

the compound proposition is true ( a ⇒ b is true).

Activity 6 The implication truth table

If I fail to win the race ( a is false) and I am not in the final (b is
false), is the compound proposition a ⇒ b true or false?

If I win the race but am not in the final (illness, injury), then is
the compound proposition a ⇒ b true or false?

By considering these two questions and two others, it is possible

to build up a truth table for the proposition a ⇒ b . Think about

162
 www.vagupu.com

Chapter 10 Logic

the other two questions and their answers, and hence complete the
following truth table.

a b a⇒ b
0 0
0 1
1 0
1 1

The values in this truth table often cause much argument, until it is
realised that the connective ⇒ is about implication and not about
cause and effect.

It is not correct to assume that a ⇒ b means a causes b or that b

results from a.

In fact, the implication connective, ⇒ , is defined by the values

shown in the truth table whatever the propositions that make up the
compound proposition.

Consider the implication a ⇒ b

'If it is hot, it is June.'

The only way of being sure that this implication a ⇒ b is false is

by finding a time when it is hot but it isn't June; i.e. when a is true
but b is false. Hence the truth table for a ⇒ b is as follows:

a b a⇒ b
0 0 1
0 1 1
1 0 0
1 1 1

In logic, the two propositions which make up a compound

proposition may not be related in the usual sense.

163
 www.vagupu.com

Chapter 10 Logic

Example
'If Christmas is coming (C), today is Sunday (S).'

C S C ⇒S
0 0 1
0 1 1
1 0 0
1 1 1

However difficult it may seem to invent a meaning for this

implication, the truth table will be exactly the same as before.

Exercise 10D
1. Give the truth values (1 or 0) of these (b) I do not spread manure nor do I water the
propositions. plants and the crops do not grow.
(a) If all multiples of 9 are odd, then multiples of (c) If I spread manure the crops grow.
3 are even.
(d) The crops grow if I water the plants and do
(b) If dogs have four legs then cats have four not spread manure.
legs.
(e) If I do not water the plants, then I spread
(c) If the sea is blue, the sky is green. manure and the crops grow.
(d) Oxford is in Cornwall if Sheffield is in 3. Using a, b and c from Question 2, interpret the
Yorkshire. following propositions.
(e) Pentagons have six sides implies that (a) ( a∧ b) ∨ ( a∧ c)
quadrilaterals have four sides.
2. If a represents 'the crops grow', b is 'I water the (b) ( c∨ ~ b) ⇒~ a
plants' and c is 'I spread manure', express these
(c) a ⇒ b ∧ c
propositions in terms of a, b and c.
(a) If I water the plants the crops grow. (d) ~ a∨ c⇒ b

10.6 Recognising equivalence

There is a difference between the proposition

'If it is dry, I will paint the door.'

and the proposition

'If, and only if, it is dry, I will paint the door.'

If p is 'it is dry' and q is 'I will paint the door', then p ⇒ q

represents the first proposition.

164
 www.vagupu.com

Chapter 10 Logic

The second proposition uses the connective of equivalence

meaning 'if and only if ' and is represented by the symbol ⇔ ,
i.e. p ⇔ q represents the second proposition.

The truth table for p ⇔ q shown here is more obvious than the
truth table for implication.
p q p⇔ q
0 0 1
0 1 0
1 0 0
1 1 1
You will see that p ⇔ q simply means that the two propositions p
and q are true or false together: this accounts for the use of the
word 'equivalence'. Note that if you work out the truth table for
q ⇔ p you will get the same results as for p ⇔ q .

Exercise 10E
1. If a is a true statement and b is false, write 2. If a is 'the theme park has excellent rides', b is
down the truth value of: 'entrance charges are high' and c is 'attendances
(a) a ⇔~ b are large', write in plain English the meaning of:

(b) ~ b ⇔~ a. (a) c⇔ ( a∧ ~ b)

(b) ( ~ c ∨ ~ b) ⇒ a .

10.7 Tautologies and

contradictions
In the field of logic, a tautology is defined as a compound
proposition which is always true whatever the truth values of
the constituent statements.

p ~p p∨ ~ p

0 1 1
1 0 1

This simple truth table shows that

p∨ ~ p is a tautology.

The opposite of a tautology, called a contradiction, is defined

as a compound proposition which is always false whatever the
truth values of the constituent statements.

165
 www.vagupu.com

Chapter 10 Logic

p ~p p∧ ~ p
0 1 0
1 0 0

This simple truth table shows that

p∧ ~ p is a contradiction.

Example
Is [ a∧ ( b∨ ~ b)] ⇔ a a tautology or a contradiction?

Solution
The clearest way to find the solution is to draw up a truth table.
If the result is always true then the statement is a tautology; if
always false then it is a contradiction.

a b ~b (b∨ ~ b) a∧ (b∨ ~ b) [ a∧ (b∨ ~ b)] ⇔ a

0 0 1 1 0 1
0 1 0 1 0 1
1 0 1 1 1 1
1 1 0 1 1 1

The truth table shows that, since the compound statement is

always true, the example given is a tautology.

Exercise 10F
Decide whether each of the following is a tautology or a
contradiction.

1. ( a ⇒ b) ⇔ ( a∧ ~ b)
2. [ a∧ ( a ⇒ b)]∧ ~ b
3. ~ ( a ⇒ b) ⇒ [( b ∨ c) ⇒ ( a∨ c)]

166
 www.vagupu.com

Chapter 10 Logic

10.8 The validity of an argument

In Section 8.1 the idea of an argument was described as a set of
premises (such as p, q and r) which leads to a conclusion (c):

p
q
r
•
•
•
c

A valid argument is one in which, if the premises are true, the

conclusion must be true. An invalid argument is one that is not
valid. The validity of an argument can, in fact, be independent
of the truth (or falsehood) of the premises. It is possible to have
a valid argument with a false conclusion or an invalid argument
with a true conclusion. An argument can be shown to be valid if
p ∧ q ∧ r∧....⇒ c is always true (i.e. a tautology).

Example
Represent the following argument symbolically and determine
whether the argument is valid.

If cats are green then I will eat my hat.

I will eat my hat.

Cats are green.

Solution
Write the argument as

a⇒ b
b
a

The argument is valid if ( a ⇒ b) ∧ b ⇒ a.

a b ( a ⇒ b) ( a ⇒ b) ∧ b ( a ⇒ b) ∧ b ⇒ a
0 0 1 0 1
0 1 1 1 0
1 0 0 0 1
1 1 1 1 1

167
 www.vagupu.com

Chapter 10 Logic

The truth table shows that the argument is not always true (i.e.
it is not a tautology) and is therefore invalid. The second line in
the truth table shows that the two premises a ⇒ b and b can
both be true with the conclusion a being false. In other words,
the compound proposition ( a ⇒ b) ∧ b ⇒ a is not always true
(i.e. it is not a tautology). Therefore the argument

a⇒ b
b
a
is invalid.

Exercise 10G
Determine whether these arguments are valid. 3. p⇒ q
1. a⇒ b r⇒~ q
a⇒ c p ⇒~ r
a ⇒ ( b ∧ c) 4. Form a symbolic representation
of the following argument and
2. ~ b ⇒~ a determine whether it is valid.
b If I eat well then I get fat.
a If I don't get rich then I
don't get fat.
I get rich.

10.9 Miscellaneous Exercises

1. Denote the positive (affirmative) statements in 2. Draw up a truth table for these propositions:
the following propositions by a, b, c, .... and
express each proposition symbolically. (a) ( p∨ ~ q) ⇒ q
(a) Either you have understood this chapter, or
you will not be able to do this question.
[ ]
(b) p ∨ ( ~ p ∨ q) ∨ ( ~ p∧ ~ q)

(c) ( ~ p∨ ~ q) ⇒ ( p∧ ~ q)
(b) 64 and169 are perfect squares.
(d) ~ p ⇔ q
(c) −4 > − 9 and 4 > − 9 .
(e) ( ~ p ∧ q) ∨ ( r∧ p)
(d) This is neither the right time nor the right
place for an argument. (f) ( p ⇔ q) ⇒ ( ~ p ∧ q)
(e) If the wind is blowing from the east, I will go
sailing tomorrow. 3. Decide whether each of the following is a
(f) The train standing at platform 5 will not tautology:
leave unless all the doors are shut. (a) ~ a ⇒ ( a ⇒ b)
(g) The telephone rang twice and there was no
(b) ~ ( a∨ b) ∧ a
reply.
(h) My friend will go to hospital if his back (c) [ a∧ ( a ⇒ b)] ⇒ a
doesn't get better.
(d) ( a ⇒ b) ⇔~ ( a∧ ~ b)

168
 www.vagupu.com

Chapter 10 Logic

4. Decide whether each of the following is a *6. Lewis Carroll gave many arguments in his book
contradiction: 'Symbolic Logic'. Decide whether the following
arguments are valid.
(a) ( a∧ b) ∨ ( ~ a∧ ~ b)
(a) No misers are unselfish.
(b) ( a ⇒ b) ⇔ ( a∧ ~ b) None but misers save egg-shells.
No unselfish people save egg-shells.
(c) ~ ( a∧ b) ∨ ( a∨ b)
(b) His songs never last an hour;
(d) ( a∨ b) ⇒~ ( b ∨ c) A song, that lasts an hour, is tedious.
5. Formulate these arguments symbolically using p, His songs are never tedious.
q and r, and decide whether each is valid.
(a) If I work hard, then I earn money (c) Babies are illogical;
I work hard Nobody is despised who can manage a
crocodile;
I earn money
Illogical persons are despised.
(b) If I work hard then I earn money Babies cannot manage crocodiles.
If I don't earn money then I am not (Hint a : persons who are able to
successful manage a crocodile.
I earn money b : persons who are babies
c : persons who are despised
(c) I work hard if and only if I am successful d : persons who are logical)
I am successful
I work hard.

(d) If I work hard or I earn money then I am

successful
I am successful
If I don't work hard then I earn money.

169
 www.vagupu.com

Chapter 10 Logic

170