23

Chapter 23
Logic and algebra

Objectives
 To understand the Boolean operations ∨, ∧,  and the axioms of Boolean algebra.
 To understand and apply the concepts of proposition and truth value.
 To construct truth tables for compound statements and to recognise tautologies.
 To represent circuits using logic gates.
 To use Karnaugh maps to simplify Boolean expressions.

The words ‘or’, ‘and’, ‘not’, ‘true’ and ‘false’ are central to this chapter. You may have
already met these words in your studies of sets, probability and proofs. In this chapter, these
ideas are brought together in a formal way as Boolean algebra.
In Chapter 2, we looked at sets and operations on sets, including union ∪, intersection ∩ and
complementation  . This chapter begins by studying these operations on the set of all subsets
of a given set. We have seen in Chapter 5 that, if a finite set has n elements, then there are
2n subsets. Such structures are examples of Boolean algebras.
We will see that the ideas of Boolean algebra flow through into a formal study of logic.
Some of the concepts introduced in Chapter 6 will reappear in this chapter, including
negation, De Morgan’s laws, implication, converse and contrapositive.
Early work in logic was carried out by George Boole (1815–1864) in his book An
Investigation of the Laws of Thought, published in 1854. His aims in the book were to
. . . investigate the fundamental laws of those operations of the mind by which
reasoning is performed; to give expression to them in the symbolical language
of a Calculus, and upon this foundation to establish the science of Logic and
construct its method.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 616 Chapter 23: Logic and algebra

The ideas of Boolean algebra were first applied to electronic circuits in the 1930s, by Claude
Shannon (1916–2001). Today, Boolean algebra forms the foundation of computer science,
and is central to electronics and programming. You can use Boolean logic when you submit a
query to a search engine, such as Google or Yahoo.

23A Sets and circuits

 Basic set notation
A set is any collection of objects where order is not important. We first recall some of the
basic notation from Section 2A.
 The set of all the elements being considered in a given context is called the universal set
and is denoted by ξ.
 The set with no elements is called the empty set and is denoted by ∅.
 We say that a set B is a subset of a set A if each element of B is also in A. In this case,
we write B ⊆ A. Note that ∅ ⊆ A and A ⊆ A.
The following three operations on sets play an important role in this chapter.
The union of sets A and B is denoted by A ∪ B and consists
of all elements that belong to A or B:
A ∪ B = { x : x ∈ A or x ∈ B } A B

The intersection of sets A and B is denoted by A ∩ B and

consists of all elements that belong to both A and B:
A ∩ B = { x : x ∈ A and x ∈ B } A B

The complement of a set A is denoted by A and consists of

all elements of the universal set ξ that are not in A: A′
A = { x ∈ ξ : x  A } A

In this chapter, you will see how these ideas can be extended and applied in analogous
situations. We begin by looking at the ‘structure’ of the set of all subsets of a set.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23A Sets and circuits 617

 The set of all subsets of a set

We consider the operations ∪, ∩ and  on the set of all subsets of a set. We have proved in
Section 5G that a set with n elements has 2n subsets.
For example, consider the universal set ξ = {a, b, c, d}. There are 16 subsets:
 the empty set: ∅
 the subsets of size 1: {a}, {b}, {c}, {d}
 the subsets of size 2: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}
 the subsets of size 3: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}
 the universal set: ξ.
We can make the following observations for these sets and, more generally, for any such
collection of subsets. We will illustrate how to prove these laws in Example 1. You will see
similar laws reoccurring throughout this chapter.

Algebra of sets
For A, B, C ⊆ ξ, the following are true:
Primary  A∪A= A  A∩A= A
 A∪∅= A  A∩ξ= A
 A∪ξ=ξ  A∩∅=∅

Associativity  (A ∪ B) ∪ C = A ∪ (B ∪ C)  (A ∩ B) ∩ C = A ∩ (B ∩ C)

Commutativity  A ∪ B = B ∪ A  A∩B= B∩A

Distributivity  A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)  A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Absorption  A ∪ (A ∩ B) = A  A ∩ (A ∪ B) = A

Complements  A ∪ A = ξ  A ∩ A = ∅
 ∅ = ξ  ξ = ∅
 (A ∪ B) = A ∩ B  (A ∩ B) = A ∪ B
 (A ) = A

You may notice that some of these laws are similar to laws of arithmetic involving +, ×,
0 and 1. For example, the laws A ∪ ∅ = A and A ∩ ξ = A are analogous to the arithmetic
statements a + 0 = a and a × 1 = a.
You may also notice that all but one of these laws occurs as a member of a pair. The two laws
in each pair are called dual statements.

Dual statements
For a given statement about sets, the dual statement is obtained by interchanging:
∪ with ∩, ∅ with ξ, ⊆ with ⊇

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 618 Chapter 23: Logic and algebra

In the following example, we show a method for proving a result about sets. We also show
how to illustrate the result with a Venn diagram. But note that drawing a Venn diagram is not
a proof, just as in geometry drawing a diagram is not a proof.

Equality for sets

When proving that two sets are equal, we can use the following equivalence:
X ⊆ Y and Y ⊆ X ⇔ X = Y

Example 1
a Illustrate (A ∪ B) = A ∩ B with Venn diagrams.
b Prove that (A ∪ B) = A ∩ B .

Solution
a Note: Required regions are shaded.
We first draw the diagram for (A ∪ B) .

(A ∪ B)

A B

To help draw the diagram for A ∩ B , we draw diagrams for A and B .

A B A ∩ B

A B A B A B

The diagrams for (A ∪ B) and A ∩ B are the same.

b We must show that (A ∪ B) ⊆ A ∩ B and A ∩ B ⊆ (A ∪ B) .

Let x ∈ ξ.
i x ∈ (A ∪ B) ⇒ x  A ∪ B ii x ∈ A ∩ B ⇒ x ∈ A and x ∈ B
⇒ x  A and x  B ⇒ x  A and x  B
 
⇒ x ∈ A and x ∈ B ⇒ x A∪B
 
⇒ x∈A ∩B ⇒ x ∈ (A ∪ B)

Hence (A ∪ B) ⊆ A ∩ B . Hence A ∩ B ⊆ (A ∪ B) .

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23A Sets and circuits 619

Example 2
Write the dual of (A ∩ B ) ∩ B = ∅.

Solution
(A ∪ B ) ∪ B = ξ

 Light switches
Claude Shannon was first to realise that the ideas of logic could be applied to electronic
circuits. ‘On’ and ‘off’ can be used in a way analogous to ‘true’ and ‘false’. In this chapter,
we follow the opposite path. We first introduce switching circuits, and then see in the next
section how they can be interpreted using Boolean algebra.

Switches in parallel
The following diagram shows two switches x and y in parallel. If at least one of the switches
is closed, then current flows and the light is on. In this case, we say that the system is closed.
The four possible situations for two switches in parallel are summarised in the table.

x Switches x and y in parallel

x y State of system
open open open
open closed closed
closed open closed
y closed closed closed

Switches in series
The following diagram shows two switches x and y in series. If both switches are closed,
then current flows and the light is on. In this case, we say that the system is closed.
The four possible situations for two switches in series are summarised in the table.

Switches x and y in series

x y State of system
x y
open open open
open closed open
closed open open
closed closed closed

Complementary switches x x
The complement switch x is always in the opposite state to x. open closed
closed open

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 620 Chapter 23: Logic and algebra

New notation
We now introduce a new notation that will be used throughout this chapter in several different
contexts.
 Use 0 for open.
 Use 1 for closed.
 Use the notation x ∨ y, read as ‘x or y’, for two switches x and y connected in parallel.
 Use the notation x ∧ y, read as ‘x and y’, for two switches x and y connected in series.
 Use x for the complement of x.
We repeat the three tables above with the new notation.

Or (parallel) And (series) Complement

x y x∨y x y x∧y x x
0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1

We now have three operations ∨, ∧ and  acting on the set {0, 1}.
Note: The operations ∨ and ∧ are analogous to union ∪ and intersection ∩. For this reason,
the symbols ∨ and ∧ are also read as ‘join’ and ‘meet’.
This new notation allows us to represent more complicated switching circuits. You will see
the notation used again in the next section in a more general context.

Example 3
Consider the expression
(x ∧ y) ∨ (z ∧ x )
a Draw the switching circuit that is represented by this expression.
b Give the table with entries 0s and 1s describing the operation of this circuit.

Solution
a x y

z x′

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23A 23A Sets and circuits 621

b For three variables x, y and z, there are 23 = 8 possible combinations of 0s and 1s.
This gives the first three columns of the table. To find the value of (x ∧ y) ∨ (z ∧ x ) in
each case, we start by finding the values of the simpler expressions x ∧ y and z ∧ x .

x y z x x∧y z ∧ x (x ∧ y) ∨ (z ∧ x )
0 0 0 1 0 0 0
0 0 1 1 0 1 1
0 1 0 1 0 0 0
0 1 1 1 0 1 1
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 1 0 1
1 1 1 0 1 0 1

Exercise 23A

Example 1b 1 Prove each of the following results:

a (A ∩ B) = A ∪ B b (A ∪ B) ∩ (A ∪ B ) = A
c A = (A ∩ B) ∪ (A ∩ B ) d (P ∪ Q) ∪ (P ∩ Q) = (P ∪ Q) ∩ (Q ∪ P)

2 Set difference is defined as

A \ B = A ∩ B = { x : x ∈ A and x  B }
Prove the following results:
a P \ (Q \ R) = (P \ Q) ∪ (P ∩ R) b P ∩ (Q \ R) = (P ∩ Q) \ (P ∩ R)

Example 2 3 Write the dual of each of the following:

a (A ∪ ξ) ∩ (A ∩ ∅) = ∅ b If A ∩ B = ∅, then A ∪ B = A .
c A∩B⊆ A∪B

Example 3 4 For each of the following expressions:

i draw the switching circuit that is represented by the expression
ii give the table with entries 0s and 1s describing the operation of this circuit.
a (x ∧ y) ∨ z b (x ∨ y) ∧ (x ∧ y)
c x ∧ (y ∨ z) d (x ∨ y ) ∧ (y ∨ z)

5 Consider the expression (x ∧ y) ∨ ((z ∨ x) ∧ y ).

a Draw the switching circuit that is represented by this expression.
b Give the table with entries 0s and 1s describing the operation of this circuit.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 622 Chapter 23: Logic and algebra

23B Boolean algebra

We have now seen two different examples of a Boolean algebra:
 the set of all subsets of a set with the operations ∪, ∩ and 
 the set {0, 1} with the operations ∨, ∧ and  .
In general, a Boolean algebra is a set B with operations ∨, ∧,  and distinguished
elements 0, 1 such that the following axioms are satisfied, for all x, y, z ∈ B:

Axiom 1 x∨y=y∨x (∨ is commutative)

x∧y=y∧x (∧ is commutative)

Axiom 2 (x ∨ y) ∨ z = x ∨ (y ∨ z) (∨ is associative)
(x ∧ y) ∧ z = x ∧ (y ∧ z) (∧ is associative)

Axiom 3 x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) (∨ distributes over ∧)

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) (∧ distributes over ∨)

Axiom 4 x∨0= x (0 is the identity for ∨)

x∧1= x (1 is the identity for ∧)

Axiom 5 x ∨ x = 1 ( is complementation)
x ∧ x = 0

Given these rules, we can prove new results, as shown in the following example.

Example 4
Prove that, for each Boolean algebra B and all x, y, z ∈ B:
a x∨1=1
b x∧0=0
c If x ∨ z = 1 and x ∧ z = 0, then z = x .
d (x ∨ y) = x ∧ y

Solution
a x ∨ 1 = (x ∨ 1) ∧ 1 (axiom 4)

= (x ∨ 1) ∧ (x ∨ x ) (axiom 5)
= x ∨ (1 ∧ x ) (axiom 3)

= x ∨ (x ∧ 1) (axiom 1)

= x∨x (axiom 4)
=1 (axiom 5)

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23B Boolean algebra 623

b x ∧ 0 = (x ∧ 0) ∨ 0 (axiom 4)
= (x ∧ 0) ∨ (x ∧ x ) (axiom 5)

= x ∧ (0 ∨ x ) (axiom 3)

= x ∧ (x ∨ 0) (axiom 1)
= x ∧ x (axiom 4)
=0 (axiom 5)
Note: Part b is the dual of part a.

c Let x ∈ B. We know that x ∨ x = 1 and x ∧ x = 0, by axiom 5. Assume that there is

another element z which satisfies x ∨ z = 1 and x ∧ z = 0. Then
x = x ∧ 1 (axiom 4)

= x ∧ (x ∨ z) since x ∨ z = 1
 
= (x ∧ x) ∨ (x ∧ z) (axiom 3)
= (x ∧ x ) ∨ (x ∧ z) (axiom 1)

= 0 ∨ (x ∧ z) (axiom 5)

= (x ∧ z) ∨ (x ∧ z) since x ∧ z = 0
= (z ∧ x) ∨ (z ∧ x ) (axiom 1)

= z ∧ (x ∨ x ) (axiom 3)
=z∧1 (axiom 5)
=z (axiom 4)

d We will show that x ∧ y is the complement of x ∨ y using part c.

First consider (x ∨ y) ∨ (x ∧ y ):
   
(x ∨ y) ∨ (x ∧ y ) = (x ∨ y) ∨ x ∧ (x ∨ y) ∨ y (axiom 3)
   
= y ∨ (x ∨ x ) ∧ x ∨ (y ∨ y ) (axioms 1 and 2)
= (y ∨ 1) ∧ (x ∨ 1) (axiom 5)
=1∧1 by part a
=1 (axiom 4)
Now consider (x ∨ y) ∧ (x ∧ y ):
(x ∨ y) ∧ (x ∧ y ) = (x ∧ y ) ∧ (x ∨ y) (axiom 1)
   
= (x ∧ y ) ∧ x ∨ (x ∧ y ) ∧ y (axiom 3)
   
= y ∧ (x ∧ x ) ∨ x ∧ (y ∧ y ) (axioms 1 and 2)
= (y ∧ 0) ∨ (x ∧ 0) (axiom 5)
=0∨0 by part b
=0 (axiom 4)
Hence x ∧ y is the complement of x ∨ y by part c. That is, (x ∨ y) = x ∧ y .

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 624 Chapter 23: Logic and algebra

The set of all subsets of a set is a Boolean algebra with the operations ∪, ∩,  and the identity
elements ∅, ξ. All the laws for sets given in Section 23A have parallel results for Boolean
algebras in general. Some are axioms, and the others can be proved from the axioms (see
Example 4 and Exercise 23B).

Properties of Boolean algebras

Primary  x∨x= x  x∧x= x
 x ∨ 0 = x (A4)  x ∧ 1 = x (A4)
 x∨1=1  x∧0=0

Associativity (A2)  (x ∨ y) ∨ z = x ∨ (y ∨ z)  (x ∧ y) ∧ z = x ∧ (y ∧ z)

Commutativity (A1)  x∨y=y∨x  x∧y=y∧x

Distributivity (A3)  x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)  x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Absorption  x ∨ (x ∧ y) = x  x ∧ (x ∨ y) = x

Complements  x ∨ x = 1 (A5)  x ∧ x = 0 (A5)

 0 = 1  1 = 0
 (x ∨ y) = x ∧ y  (x ∧ y) = x ∨ y
 (x ) = x

Note: The properties (x ∨ y) = x ∧ y and (x ∧ y) = x ∨ y are called De Morgan’s laws.
You have seen them used in the context of logic in Section 6B.

 Boolean functions and expressions

You have met functions in other areas of mathematics and we can think about the expressions
that we have met above in this way. A simple example of a Boolean function is
f : {0, 1} → {0, 1}, f (x) = x ∨ 1
In this case, we have f (0) = 0 ∨ 1 = 1 and f (1) = 1 ∨ 1 = 1.
In general, a Boolean function has one or more arguments from {0, 1} and values in {0, 1}.

Example 5
Give the table of values for the Boolean function f (x, y) = (x ∧ y) ∨ y .

Solution

x y y x∧y f (x, y) = (x ∧ y) ∨ y
0 0 1 0 1
0 1 0 0 0
1 0 1 0 1
1 1 0 1 1

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23B Boolean algebra 625

The next example shows how to find a Boolean expression for a Boolean function given in
table form. We don’t give a formal proof, but you can easily verify the result by forming the
table of values. In Section 23D, we will see the importance of this process in electronics.

Example 6
Find a Boolean expression for the Boolean function given by the following table.

x y z f (x, y, z)
1 0 0 0 0
2 0 0 1 0
3 0 1 0 1
4 0 1 1 0
5 1 0 0 1
6 1 0 1 0
7 1 1 0 1
8 1 1 1 1

Solution
We look at the rows where a 1 occurs in the rightmost column: rows 3, 5, 7 and 8.
Each row corresponds to some combination using ∧ of either x or x , either y or y , and
either z or z .
For example, row 3 corresponds to x ∧ y ∧ z . We use x for a 1-entry in the x-column and
use x for a 0-entry. The same rule is followed for the y- and z-columns.
 Row 3 x ∧ y ∧ z
 Row 5 x ∧ y ∧ z
 Row 7 x ∧ y ∧ z
 Row 8 x ∧ y ∧ z
Now combine these terms using ∨. We obtain the Boolean expression
(x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z)
We can write the Boolean function as
f (x, y, z) = (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z)

Notes:
 We will see in Example 20 that this expression simplifies to (x ∧ y) ∨ (x ∧ z ) ∨ (y ∧ z ).
 It follows from the associativity of ∨ and ∧ that we can write expressions such as x ∧ y ∧ z
and a ∨ b ∨ c ∨ d unambiguously without using brackets.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 626 Chapter 23: Logic and algebra 23B

Equivalent Boolean expressions

Two Boolean expressions are equivalent if they represent the same Boolean function.

If two Boolean expressions represent the same Boolean function, then it is possible to derive
one expression from the other using the axioms of Boolean algebras.

Example 7
Consider the two Boolean expressions
 
(x ∨ y) ∧ (x ∨ y) ∨ x and x ∨ y
Show that these two expressions are equivalent by:
a showing that they represent the same Boolean function
b using the axioms and properties of Boolean algebras.

Solution
a x y x∨y x x ∨ y (x ∨ y) ∧ (x ∨ y) ((x ∨ y) ∧ (x ∨ y)) ∨ x
0 0 0 1 1 0 0
0 1 1 1 1 1 1
1 0 1 0 0 0 1
1 1 1 0 1 1 1

Columns 3 and 7 of the table are the same, and therefore the two expressions determine
the same Boolean function.
   
b (x ∨ y) ∧ (x ∨ y) ∨ x = (y ∨ x) ∧ (y ∨ x ) ∨ x (axiom 1)
  
= y ∨ (x ∧ x ) ∨ x (axiom 3)
= (y ∨ 0) ∨ x (axiom 5)
=y∨x (axiom 4)
= x∨y (axiom 1)

Exercise 23B

Example 4 1 Prove each of the following, where x and y are elements of a Boolean algebra B:
a x∧x= x b x∨x= x c (x ) = x
d x = (x ∧ y) ∨ (x ∧ y ) e x ∨ (x ∧ y) = x

2 Show that a ∨ [(b ∧ c ) ∧ (d ∧ b )] = a.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23B 23C Logical connectives and truth tables 627

Example 5 3 For each of the following Boolean functions, produce a table of values:
a f (x, y) = (x ∧ y ) ∧ (x ∧ y )
b f (x, y, z) = (x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x)

4 Draw a switching circuit for each of the following expressions. Try to simplify your
circuit by first simplifying the expression using the properties of Boolean algebras.
a (x ∧ y ) ∨ (x ∧ y )
b (x ∧ y) ∨ (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y )

Example 6 5 For each of the following, find a Boolean expression for the given Boolean function:
a x y f (x, y) b x y z f (x, y, z)
0 0 1 0 0 0 1
0 1 1 0 0 1 1
1 0 0 0 1 0 0
1 1 1 0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0

Example 7 6 Show that the expressions (x ∨ y) ∧ (x ∨ y ) and (x ∧ y) ∨ (x ∧ y ) are equivalent by:
a showing that they represent the same Boolean function
b using the axioms and properties of Boolean algebras.

23C Logical connectives and truth tables

A proposition or statement is a sentence which is either true or false. Examples of
statements are:
 The boy plays tennis.
 5 + 7 = 12
 5 + 7 = 10
Note that ‘5 + 7’ is not a statement.
A statement can be assigned a truth value: T if it is true, or F if it is false. For example,
the statement ‘5 + 7 = 12’ is true (T), and the statement ‘5 + 7 = 10’ is false (F).
A statement is often denoted by a capital letter A, B, C, . . . .

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 628 Chapter 23: Logic and algebra

 The logical connectives ‘or’, ‘and’, ‘not’

Logical connectives enable statements to be combined together to form new statements.
In English, two sentences may be combined by a grammatical connective to form a new
compound sentence. For example, consider the following sentences:
A Gary went to the cinema. B Gary did not go to the cinema.
C Kay went to the cinema. D Gary and Kay went to the cinema.
Statement B is the negation (not) of statement A. Statement D is the conjunction (and) of
statements A and C. The same can be done using logical connectives.
We will consider two statements about an integer n. G H
 Let G be the statement ‘n is odd’. 1 T T
 Let H be the statement ‘n > 10’. 2 T F
Given two statements, there are four possible combinations of 3 F T
truth values, as shown in the table on the right.
4 F F
Or
The symbol ∨ is used for ‘or’. Truth table for ‘or’
 The statement G ∨ H is ‘n is odd or n > 10’. G H G∨H
The statement G ∨ H is known as the disjunction of G and H. T T T
If either or both of the statements are true, then the compound T F T
statement is true. If both are false, then the compound statement F T T
is false. This is shown in the table on the right, which is called a
F F F
truth table.

And
Truth table for ‘and’
The symbol ∧ is used for ‘and’. G H G∧H
 The statement G ∧ H is ‘n is odd and n > 10’.
T T T
The statement G ∧ H is known as the conjunction of G and H. T F F
If both statements are true, then the compound statement is true.
F T F
If either or both are false, then the compound statement is false.
This can be shown conveniently in a truth table. F F F

Not
Truth table for ‘not’
The symbol ¬ is used for ‘not’.
A ¬A
 The statement ¬G is ‘n is even’.
T F
 The statement ¬H is ‘n ≤ 10’.
F T
In general, the statement ¬A is called the negation of A and
has the opposite truth value to A.
Note: The negation operation ¬ corresponds to complementation in Boolean algebra. But in
propositional logic, it is common to use the notation ¬A instead of A .

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23C Logical connectives and truth tables 629

 Truth tables for compound statements

More complicated compound statements can be built up using these three connectives. For
example, the statement ¬G ∧ ¬H is ‘n is even and n ≤ 10’.
We can use truth tables to find the truth values of compound statements.
To construct the truth table for ¬G ∧ ¬H, we first find the truth values for the simpler
statements ¬G and ¬H, and then use the truth table for ∧. Note that ¬G ∧ ¬H is true if and
only if both ¬G and ¬H are true.

G H ¬G ¬H ¬G ∧ ¬H
T T F F F
T F F T F
F T T F F
F F T T T

Example 8
Write the truth table for ¬(A ∨ B).

Solution
The truth values for the simpler statement A ∨ B are found first.

A B A∨B ¬(A ∨ B)
T T T F
T F T F
F T T F
F F F T

Example 9
Write the truth table for A ∧ B ∧ (¬A).

Solution

A B A∧B ¬A A ∧ B ∧ (¬A)
T T T F F
T F F F F
F T F T F
F F F T F

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 630 Chapter 23: Logic and algebra

Equivalent statements, tautologies and contradictions

Two statements that have the same truth values are logically equivalent.

Example 10
Show that ¬(A ∧ B) is logically equivalent to ¬A ∨ ¬B.

Solution

A B ¬A ¬B A∧B ¬(A ∧ B) ¬A ∨ ¬B
T T F F T F F
T F F T F T T
F T T F F T T
F F T T F T T

The truth values for ¬(A ∧ B) and ¬A ∨ ¬B are the same, so the statements are equivalent.

 A tautology is a statement which is true under all circumstances.

 A contradiction is a statement which is false under all circumstances.

Example 11
Show that (¬A) ∨ (A ∨ B) is a tautology.

Solution

A B ¬A A∨B (¬A) ∨ (A ∨ B)
T T F T T
T F F T T
F T T T T
F F T F T

Example 12
Show that (A ∨ B) ∧ (¬A ∧ ¬B) is a contradiction.

Solution

A B ¬A ¬B A∨B ¬A ∧ ¬B (A ∨ B) ∧ (¬A ∧ ¬B)

T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T F

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23C Logical connectives and truth tables 631

 Implication
We now consider another logical connective, called implication.
For statements A and B, we can form the compound statement Truth table for ‘implies’
A ⇒ B, which is read as ‘A implies B’ or as ‘If A, then B’.
A B A⇒B
The truth table for ⇒ is shown on the right. T T T
It is useful to consider whether this truth table is consistent with a T F F
‘common sense’ view of implication. F T T
 Let A be the statement ‘I am elected’. F F T
 Let B be the statement ‘I will make public transport free’.

Therefore A ⇒ B is the statement ‘If I am elected, then I will make public transport free’.
Now consider each row of the truth table:
Row 1 I am elected (A is true) and public transport is made free (B is true). I have kept
my election promise. The statement A ⇒ B is true.
Row 2 I am elected (A is true) but public transport is not made free (B is false). I have
broken my election promise. The statement A ⇒ B is false.
Rows 3 & 4 I am not elected (A is false). Whether or not public transport is made free, I have
not broken my promise, as I was not elected. The statement A ⇒ B is true.

Note that the only possible way that A ⇒ B could be false is if I am elected but do not make
public transport free. Otherwise, the statement is not false, and therefore must be true.

In general, the statement A ⇒ B is true, except when A is true and B is false.

The statement A ⇒ B is logically equivalent to ¬A ∨ B, as A B ¬A ¬A ∨ B

shown in the truth table on the right.
T T F T
T F F F
F T T T
F F T T

Example 13
Give the truth table for B ⇒ (A ∧ ¬B).

Solution

A B ¬B A ∧ ¬B B ⇒ (A ∧ ¬B)
T T F F F
T F T T T
F T F F F
F F T F T

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 632 Chapter 23: Logic and algebra

Example 14
Give the truth table for [(A ∨ B) ∧ ¬B] ⇒ A.

Solution

A B ¬B A∨B (A ∨ B) ∧ ¬B [(A ∨ B) ∧ ¬B] ⇒ A

T T F T F T
T F T T T T
F T F T F T
F F T F F T

Note: The statement [(A ∨ B) ∧ ¬B] ⇒ A is a tautology.

Equivalence
Truth table for equivalence
Another logical connective is equivalence, which is
A B A⇔B
represented by the symbol ⇔. It has the truth table shown.
T T T
You can check using truth tables that the statement A ⇔ B
T F F
is logically equivalent to (A ⇒ B) ∧ (B ⇒ A) and also to
(A ∧ B) ∨ (¬A ∧ ¬B). F T F
F F T

Example 15
Give the truth table for (¬A ∨ ¬B) ⇔ ¬(A ∧ B).

Solution

A B ¬A ¬B A∧B ¬(A ∧ B) ¬A ∨ ¬B (¬A ∨ ¬B) ⇔ ¬(A ∧ B)

T T F F T F F T
T F F T F T T T
F T T F F T T T
F F T T F T T T

Note: It can be seen that this is a tautology. The two statements ¬A ∨ ¬B and ¬(A ∧ B) are
logically equivalent.

Converse and contrapositive

Let A be the statement ‘You study Mathematics’ and let B be the statement ‘You study
Physics’. The following two statements form a pair of converse statements:
 ‘If you study Mathematics, then you study Physics.’ (A ⇒ B)
 ‘If you study Physics, then you study Mathematics.’ (B ⇒ A)

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23C Logical connectives and truth tables 633

The following two statements form a pair of contrapositive statements:

 ‘If you study Mathematics, then you study Physics.’ (A ⇒ B)
 ‘If you do not study Physics, then you do not study Mathematics.’ (¬B ⇒ ¬A)

In general, for a conditional statement A ⇒ B:

 the converse statement is B ⇒ A
 the contrapositive statement is ¬B ⇒ ¬A.

Note: Using truth tables, you can check that a statement A ⇒ B is equivalent to its
contrapositive ¬B ⇒ ¬A, but is not equivalent to its converse B ⇒ A.

Deductions
We can use truth tables to check the validity of logical deductions.

Example 16
Use truth tables to investigate the validity of each of the following deductions:
a All kangaroos jump. Jumping needs strength. So kangaroos need strength.
b In March, there are strong winds every day. The wind is not strong today. Therefore it
is not March.
c On Mondays I go swimming. Today is not Monday. Therefore I do not swim today.

Solution
a  Let A be the statement ‘It is a kangaroo’.
 Let B be the statement ‘It jumps’.
 Let C be the statement ‘It needs strength’.
The compound statement to be considered is
 
(A ⇒ B) ∧ (B ⇒ C) ⇒ (A ⇒ C)

A B C A ⇒ B B ⇒ C A ⇒ C (A ⇒ B) ∧ (B ⇒ C) [(A ⇒ B) ∧ (B ⇒ C)] ⇒ (A ⇒ C)
T T T T T T T T
T T F T F F F T
T F T F T T F T
T F F F T F F T
F T T T T T T T
F T F T F T F T
F F T T T T T T
F F F T T T T T

Therefore [(A ⇒ B) ∧ (B ⇒ C)] ⇒ (A ⇒ C) is a tautology, so the deduction is correct.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 634 Chapter 23: Logic and algebra 23C

b  Let M be the statement ‘It is March’.

 Let S be the statement ‘There are strong winds’.
The compound statement to consider is [(M ⇒ S ) ∧ (¬S )] ⇒ ¬M.

M S M⇒S ¬S (M ⇒ S ) ∧ (¬S ) ¬M [(M ⇒ S ) ∧ (¬S )] ⇒ ¬M

T T T F F F T
T F F T F F T
F T T F F T T
F F T T T T T

Since [(M ⇒ S ) ∧ (¬S )] ⇒ ¬M is a tautology, the deduction is correct.

c  Let M be the statement ‘It is Monday’.
 Let S be the statement ‘I swim today’.
The compound statement to consider is [(M ⇒ S ) ∧ (¬M)] ⇒ ¬S .

M S M⇒S ¬M (M ⇒ S ) ∧ (¬M) ¬S [(M ⇒ S ) ∧ (¬M)] ⇒ ¬S

T T T F F F T
T F F F F T T
F T T T T F F
F F T T T T T

The deduction is not valid. It fails to be true when M is false and S is true.

Here is a list of some useful tautologies that can be used to form valid deductions:
1 [(A ⇒ B) ∧ (B ⇒ C)] ⇒ (A ⇒ C)
2 [(A ⇒ B) ∧ A] ⇒ B
3 [(A ⇒ B) ∧ (¬B)] ⇒ ¬A
4 [(A ∨ B) ∧ (¬A)] ⇒ B
5 (A ⇒ B) ⇔ (¬B ⇒ ¬A) (contrapositive)
6 ¬(A ∨ B) ⇔ (¬A ∧ ¬B) (De Morgan’s law)
7 ¬(A ∧ B) ⇔ (¬A ∨ ¬B) (De Morgan’s law)
We have seen the first and third of these tautologies used in Example 16. Others will be
considered in Exercise 23C. Here is an example for the second tautology:
If it is Tuesday, then the flight arrives at 10 a.m. It is Tuesday. Therefore the
flight arrives at 10 a.m.

Exercise 23C
1 For each statement (P), write down its negation (¬P):
a Your eyes are blue. b The sky is grey. c This integer is odd.
d I live in Switzerland. e x>2 f This number is less than 100.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23C 23C Logical connectives and truth tables 635

2 Consider the following four statements.

 A: It is dark.  B: It is cold.  C: It is good.  D: It is soft.
Using the given table of opposites, write each of the following dark light
statements in English:
cold hot
a A∨B b A∧B c ¬A ∧ B
good bad
d ¬(A ∧ B) e C ∨ ¬A f ¬(A ∨ D)
soft hard
g A ∨ ¬D

3 Consider the following four statements.

 A: It is wet.  B: It is rough.  C: It is difficult.  D: It is expensive.
Write each of the following in symbols:
a It is rough and wet. b It is expensive or difficult.
c It is not difficult but is expensive. d It is not wet and not rough.
e It is not expensive and not difficult. f It is rough or wet.

4 Consider the following four statements.

 A: It is wet.  B: It is rough.  C: It is difficult.  D: It is expensive.
Using the given table of opposites, write each of the wet dry
following statements in English:
rough smooth
a A∨B b A∧B
difficult easy
c ¬A ∧ B d ¬(A ∧ B)
expensive inexpensive
e C ∨ ¬A f ¬(A ∨ D)
g A ∨ ¬D

5 Consider the following three statements for x a natural number.

 A: x is a prime number.
 B: x is an even number.
 C: x is divisible by 6.
Write each of the following in English as concisely as possible:
a A∨B b B∧C c A∧B d ¬A ∧ B
e ¬(A ∧ B) f C ∨ ¬A g ¬(A ∨ C) h A ∨ ¬C

Example 10 6 Show that each of the following pairs of statements are equivalent:
a ¬(A ∨ B) ¬A ∧ ¬B b ¬(¬A) A
c A∨A A d A∨B ¬(¬A ∧ ¬B)
e A∧B ¬(¬A ∨ ¬B) f A ∧ ¬B ¬(¬A ∨ B)
Example 12 7 Show that (A ∧ B) ∧ (¬B) is a contradiction.

8 Show that (¬A ∧ B) ∧ A is a contradiction.

Example 11 9 Show that (¬A ∧ ¬B) ∨ B ∨ A is a tautology.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 636 Chapter 23: Logic and algebra 23C

Example 13, 14 10 Give a truth table for each of the following statements:
a (A ∧ B) ⇒ A b (A ∨ B) ⇒ A c (¬B ∨ ¬A) ⇒ A
d (¬B ∧ A) ⇒ A e (B ∨ ¬A) ⇒ ¬A f (¬B ∨ ¬A) ⇒ (¬B ∧ A)
g (¬B ∨ A) ⇒ ¬(B ∧ A) h ¬B ∧ (¬B ⇒ A)

11 Show that each of the following pairs of statements are equivalent:

a A∧B ¬(A ⇒ ¬B) b A∨B ¬A ⇒ B
c A⇔B ¬[(A ⇒ B) ⇒ ¬(B ⇒ A)]

12 Show that each of the following is a tautology:

a (A ∧ B) ⇒ (A ∨ B) b [A ∧ (A ⇒ B)] ⇒ B c [(A ∨ B) ∧ (¬A)] ⇒ B

Example 15 13 Show that ¬(P ∨ Q) ⇔ (¬P ∧ ¬Q) is a tautology. Give the corresponding result for
sets A and B, and illustrate with a Venn diagram.

14 The logical connective nor is written symbolically as ↓. The statement A ↓ B is true if

and only if neither A nor B is true. Thus A ↓ B is equivalent to ¬(A ∨ B).
a Give the truth table for A ↓ B and B ↓ A.
b Show that A ↓ A is equivalent to ¬A.
c Show that [(A ↓ A) ↓ (B ↓ B)] ⇔ (A ∧ B) is a tautology.
d Show that ¬(A ↓ B) ⇔ (A ∨ B) is a tautology.

15 For each of the following statements:

i write the converse ii write the contrapositive.
a If x = 6, then x is an even integer.
b If I am elected, then public transport will improve.
c If I pass this exam, then I will be qualified as an actuary.

23D Logic circuits

In Section 23A, we introduced circuits composed of switches. In this section, we consider
designing circuits composed of logic gates.
We use the Boolean operations ∨, ∧ and ¬ on the set {0, 1}.

A B A∨B A B A∧B A ¬A
0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1

These correspond to the logical operations ‘or’, ‘and’ and ‘not’ if we interpret 0 as ‘false’ and
1 as ‘true’. In a circuit, we interpret 0 as ‘low voltage’ and 1 as ‘high voltage’.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23D Logic circuits 637

 Logic gates
We will create circuits using the following three logic gates, which carry out the operations
of ‘or’ (∨), ‘and’ (∧) and ‘not’ (¬).

‘or’ gate (∨) ‘and’ gate (∧) ‘not’ gate (¬)

Each gate is shown with the inputs on the left and the output on the right. For example, if an
‘or’ gate has inputs 0 and 1, then the output will be 1.
We can build a logic circuit to represent any Boolean expression.

Example 17
Give the gate representation of the Boolean expression (A ∧ B) ∨ C.

Solution

Note: The inputs to this circuit are labelled A, B and C. The output of the circuit will
reflect the state of these inputs according to the logic statement (A ∧ B) ∨ C.

Example 18
a Give the gate representation of the Boolean expression A ∨ (¬A ∧ B).
b Describe the operation of this circuit through a truth table.

Solution
a A
A
¬A ∧ B
A ¬A
B
B

b A B ¬A ¬A ∧ B A ∨ (¬A ∧ B)
0 0 1 0 0
0 1 1 1 1
1 0 0 0 1
1 1 0 0 1

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 638 Chapter 23: Logic and algebra 23D

In Example 6, we saw a technique for constructing a Boolean expression to match a given

truth table of 0s and 1s. Given any truth table, we can construct a matching Boolean
expression and therefore build a logic circuit that will operate according to the given table.
This is what makes Boolean algebra so central to electronics.

Given any truth table that specifies the required operation of a circuit, it is possible to
build an appropriate circuit using ‘or’, ‘and’ and ‘not’ gates.

Exercise 23D

Example 17, 18 1 Draw a circuit using logic gates for each of the following:
a A ∧ (¬B) b ¬(A ∨ B) c ¬(¬P ∧ Q) ∨ R
d A ∧ (¬B ∨ A) e (¬A ∨ B) ∧ (¬B ∨ A) f (¬A ∧ B) ∨ (B ∧ ¬C) ∨ A

2 For each of the following, give a Boolean expression that represents the circuit and give
a truth table describing the operation of the circuit:
a b
X A

Y B

c A

23E Karnaugh maps

We want to be able to simplify Boolean expressions so that the circuits we build from them
are simpler and therefore cheaper. In Section 23B, we showed how to simplify Boolean
expressions using the axioms. In this section, we introduce a more pictorial approach.

 Minimal representation
We start by formalising what it means for a Boolean expression to be ‘simplified’.
A minimal representation of a Boolean function f is a Boolean expression E which
represents f and satisfies the following:
 The expression E has the form E1 ∨ E2 ∨ · · · ∨ En , where each Ei is an expression such as
x ∧ y or x ∧ y ∧ z or y ∧ z .
 If F is any other expression of this form which also represents f , then the number of
terms Fi is greater than or equal to the number of terms Ei .
 If F and E have the same number of terms, then the number of variables in F is greater
than or equal to the number of variables in E.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23E Karnaugh maps 639

 Karnaugh maps involving two variables

We demonstrate how a different representation of a truth table can be used to find a minimal
expression. The truth table for f (x, y) = (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y) is shown below.

x y f (x, y)
0 0 1 x  ∧ y
0 1 1 x ∧ y
1 0 0 x ∧ y
1 1 1 x∧y

As in Example 6, each row of the truth table corresponds to some combination using ∧ of
either x or x , and either y or y . This is shown to the right of the truth table above. Using this
correspondence, we fill the values of f (x, y) into the following 2 × 2 table.

y y′

x 1 0

x′ 1 1

The next step is to shade the 1s which occur in pairs as 1 × 2 or 2 × 1 blocks.

y y′

x 1 0

x′ 1 1

The table above is called a Karnaugh map.

To find a minimal expression, we read off the label of each coloured block:
 Red The two 1s in the red block have labels x y and x y . The common label for the 1s in
the red block is x . So the red block has label x .
 Green The two 1s in the green block have labels xy and x y. The common label for the 1s
in the green block is y. So the green block has label y.
 Together Combine the block labels using ∨. This gives x ∨ y.
The minimal expression is f (x, y) = x ∨ y.
The following calculation illustrates why this process works:
red block green block
  
 
(x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y) = (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y) ∨ (x ∧ y)
   
= x ∧ (y ∨ y) ∨ (x ∨ x) ∧ y
   
= x ∧ 1 ∨ 1 ∧ y
= x ∨ y

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 640 Chapter 23: Logic and algebra

We could have used the original expression (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y) to fill in the Karnaugh
map directly, by putting a 1 for each of the terms x ∧ y , x ∧ y and x ∧ y in the expression. A
Boolean expression must be of a form like this to enter directly into a Karnaugh map.

Example 19
Simplify (x ∧ y) ∨ (x ∧ y ) ∨ (x ∧ y).

Solution Explanation
Step 1 We can fill the 1s into the Karnaugh map directly from
y y′
the expression. It is not necessary to add the 0s.
x 1 1

x′ 1

Step 2 Complete the shading of the 1s.

y y′

x 1 1

x′ 1

Step 3 Block labels: Now read off the labels of the coloured blocks:
 Red x  The common label for the 1s in the red block is x.
 Green y  The common label for the 1s in the green block is y.
 Together x ∨ y  Combine the block labels using ∨.
The simplified expression
is x ∨ y.

 Karnaugh maps involving three variables

A Karnaugh map for three variables x, y and z can be labelled as shown.

yz y′z y′z′ yz′

x′

Notes:
 The order of the labels yz, y z, y z , yz along the top is important. There is only one
change from one label to the next.
 You need to imagine that this Karnaugh map is wrapped around into a cylinder so that the
xyz and xyz cells are adjacent and the x yz and x yz cells are adjacent.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 23E Karnaugh maps 641

The technique for three variables is similar to that for two variables. We use the truth table or
the expression to fill the 1s into the Karnaugh map. Then we cover the 1s using blocks.

Blocks in Karnaugh maps

 You may use an m × n block in a Karnaugh map if both m and n are powers of 2.
(So you may use 1 × 1, 1 × 2, 1 × 4, 2 × 1, 2 × 2 and 2 × 4 blocks.)
 You always try to form the biggest blocks that you can, and to use the least number of
blocks that you can.

Examples of correct shading

yz y′z y′z′ yz′ yz y′z y′z′ yz′ yz y′z y′z′ yz′

x 1 1 x 1 1 1 x 1 1

x′ 1 1 x′ 1 1 1 x′ 1 1

Examples of incorrect shading

Blocks too small Blocks too small Too many blocks
yz y′z y′z′ yz′ yz y′z y′z′ yz′ yz y′z y′z′ yz′

x 1 1 x 1 1 1 x 1 1

x′ 1 1 x′ 1 1 1 x′ 1 1

Example 20
Simplify (x ∧ y ∧ z) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ).

Solution Explanation
In this example, the blue shading shows a
yz y′z y′z′ yz′
1 × 2 block that wraps around the back of
x 1 1 1 the ‘cylinder’.
x′ 1

Labels of the coloured blocks: The common labels for the 1s in the red
 Red x ∧ z  block are x and z . So the label of the red
 Green y ∧ z block is x ∧ z .
 Blue x ∧ y We find the other labels similarly, and
The simplified expression is combine the block labels using ∨.

(x ∧ y) ∨ (x ∧ z ) ∨ (y ∧ z )

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 642 Chapter 23: Logic and algebra 23E

Example 21
Write a minimal Boolean expression for the following truth table.

x y z f (x, y, z)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0

Solution Explanation
We first fill the 1s from the rightmost column of the
yz y′z y′z′ yz′
truth table into the Karnaugh map.
x 1 1
For example, row 1 of the truth table corresponds to
x′ 1 1 1 x ∧ y ∧ z and thus to the x y z cell.

Labels of the coloured blocks:

 Red y
 Green x ∧ z
A minimal expression is
f (x, y, z) = (x ∧ z ) ∨ y .

Note: A Boolean function can have more than one minimal expression. There can be
different correct ways to choose the blocks on a Karnaugh map.

Exercise 23E

Example 19 1 Simplify each of the following using a Karnaugh map:

a (x ∧ y) ∨ (x ∧ y)
b (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y )
c (x ∧ y) ∨ (x ∧ y ) ∨ (x ∧ y )

Example 20, 21 2 Simplify each of the following using a Karnaugh map:

a (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z )
b (x ∧ y ∧ z) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z )
c (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z )

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 Chapter 23 review 643

Review
Chapter summary

Boolean algebra
 Basic examples of Boolean algebras:
• the set of all subsets of a set with the operations ∪, ∩ and 
• the set {0, 1} with the operations ∨, ∧ and  .

x y x∨y x y x∧y x x
0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1

 A Boolean expression is an expression formed using ∨, ∧ and  , such as (x ∨ y) ∧ (y ∧ z) .

 Two Boolean expressions are equivalent if they give the same Boolean function on {0, 1}.

Logical connectives
 Or  And  Not
A B A∨B A B A∧B A ¬A
T T T T T T T F
T F T T F F F T
F T T F T F
F F F F F F

 Implies  Equivalence
A B A⇒B A B A⇔B
T T T T T T
T F F T F F
F T T F T F
F F T F F T

 Two statements are logically equivalent if they have the same truth values.
 A tautology is a statement which is true under all circumstances.
 A contradiction is a statement which is false under all circumstances.
 The converse of A ⇒ B is the statement B ⇒ A.
 The contrapositive of A ⇒ B is the statement ¬B ⇒ ¬A.

Logic circuits
 ‘Or’ gate (∨)  ‘And’ gate (∧)  ‘Not’ gate (¬)

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 644 Chapter 23: Logic and algebra
Review

Short-answer questions
1 Which of the following statements are true?
√
a 2 is rational. b π is not irrational.
√ √
c 2 is rational and π is irrational. d 2 is rational or π is irrational.
√ √
e If 2 is rational, then π is irrational. f If π is irrational, then 2 is rational.

2 For each statement (P), write down the negation (¬P):

a It is raining. b It is not raining.
c 2+3>4 d x = 5 and y = 5
e x = 3 or x = 5 f It is not raining or it is not windy.

3 The logical connective ‘exclusive or’ is denoted by ⊕. Truth table for ‘exclusive or’
The statement A ⊕ B is true when either A or B is true,
A B A⊕B
but not both. The truth table for ⊕ is shown on the right.
T T F
Construct a truth table for each of the following
T F T
compound statements:
F T T
a A ⊕ (A ⊕ B)
b A ⊕ (A ∨ B) F F F

4 Construct a truth table to show that the statement ¬A ⇒ (A ⇒ B) is a tautology.

5 For each pair of Boolean expressions, prove that the two expressions are equivalent by:
i showing that they represent the same Boolean function on {0, 1}
ii using the axioms and properties of Boolean algebras.
a x ∨ (x ∧ y) and x ∨ y b (x ∨ y) ∧ (x ∨ y) and y

6 Draw a circuit using logic gates for each of the following:

a ¬A ∨ B b A ∧ (B ∨ C) c (A ∧ ¬B) ∨ (B ∧ ¬A)

7 Let P be the statement: If a < b, then a3 < b3 .

a Write down the converse of P. b Write down the contrapositive of P.

Multiple-choice questions
1 The blue region of the Venn diagram is
A B B A ∪ B C A ∩ B
D A ∩ B E A ∪ B

A B

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 Chapter 23 review 645

The dual of A ∩ (A ∪ B) = ∅ is

Review
2
A B ∩ (B ∪ A) = ∅ B A ∪ (A ∩ B) = ∅ C A ∪ (A ∩ B) = ξ
D A ∩ (A ∪ B ) = ξ E A ∩ (A ∪ B) = ξ

3 Which of the following Boolean expressions y

represents the switching circuit shown? x
 
A (x ∧ y ∧ z) ∨ x B x ∧ (y ∨ z ∨ x )
  z

C (x ∨ x ) ∧ (y ∨ z) D x ∧ (y ∨ z) ∨ x
E x ∧ (y ∨ z) ∧ x
x′

4 Which of the following is not an identity of Boolean algebra?

A x∧x= x B x∧y=y∧x C (x ∧ y) = x ∧ y
D x ∧ (x ∧ y) = x ∧ y E 0∧x=0

5 Which of the following Boolean expressions x y z f (x, y, z)

corresponds to the truth table shown on the right?
0 0 0 0
A (x ∧ y ∧ z) ∨ (x ∧ y ∧ z)
0 0 1 1
B (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z )
0 1 0 0
C (x ∧ y ∧ z) ∨ (x ∧ y ∧ z )
0 1 1 0
D (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z)
E (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) 1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0

For Questions 6 and 7, let P be the statement ‘I will pass Specialist Mathematics’ and
let S be the statement ‘I study hard’.

6 Which of the following corresponds to the statement ‘If I study hard, then I will pass
Specialist Mathematics’?
A S ⇔P B S ∨P C P⇒S D S ⇒P E S ∧P

7 Which of the following is not equivalent to the statement ‘I will not pass Specialist
Mathematics unless I study hard’?
A P⇒S B ¬P ∨ S C ¬S ⇒ ¬P D S ∨ ¬P E P∧S

8 Which of the following Boolean expressions

X
represents the logic circuit shown?
A (X ∧ Y) ∨ Z B (¬X ∧ ¬Y) ∨ Z Y
C ¬(X ∧ Y) ∨ Z D (¬X ∨ ¬Y) ∧ Z
E ¬X ∧ (¬Y ∨ Z) Z

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 646 Chapter 23: Logic and algebra
Review

9 The minimal Boolean expression represented by the yz y′z y′z′ yz′

Karnaugh map shown is
x 1 1 1 1
A x ∨ (y ∧ z ) B x ∧ (y ∨ z )
C x ∨ (y ∧ z) D x ∧ (y ∨ z) x′ 1
  
E x ∨ (x ∧ y ∧ z )

Extended-response questions
1 A light in a stairwell is controlled by two switches: one at the bottom of the stairs and
one at the top. If both switches are off, then the light should be off. If either of the
switches changes state, then the light should change state. In this question, we will
create a switching circuit to represent such a two-way switch.
a Use x and y to denote the two switches. Use 0 for ‘off’ x y Light
and 1 for ‘on’. Complete the table on the right so that it
0 0 0
describes the operation of the circuit.
0 1
b Based on your table for part a, write down a Boolean
expression that represents the circuit. 1 0
c Draw the switching circuit that is represented by your 1 1
Boolean expression from part b.

2 Let B be the set of all factors of 30. Thus

B = {1, 2, 3, 5, 6, 10, 15, 30}
It can be shown that axioms 1, 2 and 3 of Boolean algebras hold for B, with the
operation ∨ as LCM (lowest common multiple) and the operation ∧ as HCF (highest
common factor). In this question, we will show that axioms 4 and 5 hold, in order to
complete the proof that B is a Boolean algebra.
a i The identity element for LCM must be a number  in B such that LCM(x, ) = x
for all x ∈ B. What is ?
ii The identity element for HCF must be a number h in B such that HCF(x, h) = x
for all x ∈ B. What is h?
b For each x ∈ B, define x = 30 ÷ x. By completing the following table, show that this
operation  is complementation in B.

x 1 2 3 5 6 10 15 30

x
LCM(x, x )
HCF(x, x )

Note: Can you see what is special about the number 30 here? Consider its prime
factorisation. What goes wrong if you try using the number 12 instead?

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 Chapter 23 review 647

Review
3 A committee with three members reaches its decisions by using a voting machine.
The machine has three switches (x, y, z); one for each member of the committee. If
at least two of the three members vote ‘yes’ (1), then the machine’s light goes on (1).
Otherwise, the light is off (0).
a Construct a table with entries 0s and 1s that describes the operation of the voting
machine.
b Give a Boolean expression for the voting machine, based on your table for part a.
c Use a Karnaugh map to simplify the Boolean expression obtained in part b.
d Draw a circuit for the voting machine using logic gates, based on your simplified
Boolean expression from part c.

4 Ternary logic In Boolean logic, there are two truth values: true (1) and false (0).
In ternary logic, there are three truth values: true (1), false (0) and don’t know (d).
The basic example of a ternary algebra is the set {0, d, 1} with the operations ∨, ∧ and 
given by the following tables.
 Or (∨)  And (∧)  Not ( )
∨ 0 d 1 ∧ 0 d 1 x x
0 0 d 1 0 0 0 0 0 1
d d d 1 d 0 d d d d
1 1 1 1 1 0 d 1 1 0

Note that d = d, since if we don’t know whether a statement is true, then we don’t
know whether its negation is true. Ternary logic has applications in electronic
engineering and database query languages.
a Evaluate each of the following:
i d∨0 ii (d ∧ 0) iii (d ∨ 0) ∧ (d ∨ 1)
b Give counterexamples to show that the laws x ∨ x = 1 and x ∧ x = 0 for Boolean
algebras do not hold for the ternary algebra {0, d, 1}.
c Prove that the De Morgan law (x ∨ y) = x ∧ y holds for the ternary algebra {0, d, 1}.
Hint: Construct a truth table to show that (x ∨ y) and x ∧ y represent the same
function on {0, d, 1}. Since there are two variables, each with three possible
values, the truth table will have 3 × 3 = 9 rows.

&DPEULGJH6HQLRU0DWKV$& ,6%1‹(YDQVHWDO &DPEULGJH8QLYHUVLW\3UHVV

6SHFLDOLVW0DWKHPDWLFV<HDU
3KRWRFRS\LQJLVUHVWULFWHGXQGHUODZDQGWKLVPDWHULDOPXVWQRWEHWUDQVIHUUHGWRDQRWKHUSDUW\
 Answers 717

Answers
Extended-response questions ii x y z y ∨ z x ∧ (y ∨ z)
1 a p a b 0 0 0 0 0
0.1 0.03 0.17 0 0 1 1 0
0.2 0.11 0.29 0 1 0 1 0
0.3 0.19 0.41 0 1 1 1 0
0.4 0.29 0.51 1 0 0 0 0
0.5 0.38 0.62 1 0 1 1 1
0.6 0.49 0.71 1 1 0 1 1
b i p̂ = 0.34 ii p = 0.3 or p = 0.4 1 1 1 1 1

23A → 23B
2 a iii mean ≈ 50, s.d. ≈ 1.12
b iii mean ≈ 50, s.d. ≈ 0.71 d i x y
c iii mean ≈ 50, s.d. ≈ 0.50

Chapter 23 y′ z

ii x y z a= x∨y 
b=y∨z a∧b
Exercise 23A 0 0 0 1 0 0
3 a (A ∩ ∅) ∪ (A ∪ ξ) = ξ 0 0 1 1 1 1
b If A ∪ B = ξ, then A ∩ B = A . 0 1 0 0 1 0
c A∪B⊇ A∩B 0 1 1 0 1 0
4 a i x y 1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 1 1 1
z 1 1 1 1 1 1
ii x y z x ∧ y (x ∧ y) ∨ z 5 a x y
0 0 0 0 0
0 0 1 0 1 z
0 1 0 0 0
0 1 1 0 1
y′
1 0 0 0 0
1 0 1 0 1 x
1 1 0 1 1 b x y z a = x ∧ y b = (z ∨ x) ∧ y a ∨ b
1 1 1 1 1
0 0 0 0 0 0
b i 0 0 1 0 1 1
y
0 1 0 0 0 0
0 1 1 0 0 0
x y
1 0 0 0 1 1
x 1 0 1 0 1 1
ii x 1 1 0 1 0 1
y x ∨ y x ∧ y (x ∨ y) ∧ (x ∧ y)
1 1 1 1 0 1
0 0 0 0 0
0 1 1 0 0
Exercise 23B
1 0 1 0 0
1 1 1 1 1 3 a x y y x ∧ y  f (x, y)
0 0 1 0 0
c i z 0 1 0 0 0
1 0 1 1 1
x 1 1 0 0 0

Cambridge Senior Maths AC ISBN 978-1-316-63608-4 © Evans et al. 2017 Cambridge University Press
Specialist Mathematics Year 11 Photocopying is restricted under law and this material must not be transferred to another party.
 718 Answers
23C

b x y z x ∨ y y ∨ z z ∨ x f (x, y, z) 6 a A B ¬(A ∨ B) ¬A ∧ ¬B
0 0 0 0 0 0 0 T T F F
0 0 1 0 1 1 0 T F F F
0 1 0 1 1 0 0 F T F F
Answers

0 1 1 1 1 1 1 F F T T
1 0 0 1 0 1 0 b A ¬(¬A)
1 0 1 1 1 1 1
T T
1 1 0 1 1 1 1
F F
1 1 1 1 1 1 1
c A A∨A
4 a (x ∧ y ) ∨ (x ∧ y ) = y ∧ (x ∨ x )
T T
= y ∧ 1
F F
= y
d A B A ∨ B ¬(¬A ∧ ¬B)
The circuit can be simplified to a y switch
T T T T
b (x ∧ y) ∨ (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y ) T F T T
= (x ∧ (y ∨ y )) ∨ (x ∧ (y ∨ y )) F T T T
= (x ∧ 1) ∨ (x ∧ 1) F F F F
= x ∨ x e A B A ∧ B ¬(¬A ∨ ¬B)
=1 T T T T
The globe is always on; the circuit can be a T F F F
single wire with no switches F T F F
5 a (x ∧ y ) ∨ (x ∧ y) ∨ (x ∧ y) F F F F
b (x ∧ y ∧ z ) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ f A B A ∧ ¬B ¬(¬A ∨ B)
(x ∧ y ∧ z )
T T F F
Exercise 23C T F T T
F T F F
1 a Your eyes are not blue.
F F F F
b The sky is not grey.
c This integer is even. 10 a A B A ∧ B (A ∧ B) ⇒ A
d I do not live in Switzerland. T T T T
e x≤2
T F F T
f This number is greater than or equal to 100.
F T F T
2 a It is dark or it is cold.
F F F T
b It is dark and cold. c It is light and cold.
d It is light or hot. e It is good or light. b A B A ∨ B (A ∨ B) ⇒ A
f It is light and hard. g It is dark or hard. T T T T
3 a B∧A b D∨C T F T T
c ¬C ∧ D d ¬A ∧ ¬B F T T F
e ¬D ∧ ¬C f B∨A F F F T
4 a It is wet or rough. b It is wet and rough.
c A B ¬A ¬B C: ¬B ∨ ¬A C ⇒ A
c It is dry and rough. d It is dry or smooth.
e It is difficult or dry. T T F F F T
f It is dry and inexpensive. T F F T T T
g It is wet or inexpensive. F T T F T F
5 a x is a prime number or an even number. F F T T T F
b x is divisible by 6. d A B ¬B ¬B ∧ A (¬B ∧ A) ⇒ A
c x is 2.
T T F F T
d x is an even number greater than 2.
e x is not 2. T F T T T
f x is not prime. F T F F T
g x is neither prime nor divisible by 6. F F T F T
h x is not divisible by 6.

Cambridge Senior Maths AC ISBN 978-1-316-63608-4 © Evans et al. 2017 Cambridge University Press
Specialist Mathematics Year 11 Photocopying is restricted under law and this material must not be transferred to another party.
 Answers 719

Answers
e A B ¬A B ∨ ¬A (B ∨ ¬A) ⇒ ¬A b i If public transport improves, then I was
T T F T F elected.
ii If public transport does not improve,
T F F F T
then I was not elected.
F T T T T
c i If I qualify as an actuary, then I passed
F F T T T the exam.
f A B C: ¬B ∨ ¬A D: ¬B ∧ A C ⇒ D ii If I do not qualify as an actuary, then I
T T F F T failed the exam.
T F T T T Exercise 23D

23D
F T T F F
1 a A
F F T F F
B
g A B C: ¬B ∨ A D: ¬(B ∧ A) C ⇒ D
T T T F F b A
T F T T T
B
F T F T T
F F T T T c P
h A B ¬B ¬B ⇒ A ¬B ∧ (¬B ⇒ A) Q
T T F T F
R
T F T T T
F T F T F d A
F F T F F
B
13 (A ∪ B) = A ∩ B
Note: Equivalent to A
e A
A B

14 a A B A↓B B↓A B
T T F F
T F F F
F T F F f A
F F T T
b A A ↓ A ¬A B
T F F
F T T
C
c Note: A ↓ A is equivalent to ¬A by part b
Note: Equivalent to A ∨ B
A B ¬A ↓ ¬B A ∧ B
T T T T 2 a ¬X ∨ (X ∧ Y) ≡ ¬X ∨ Y
T F F F X Y ¬X X ∧ Y ¬X ∨ (X ∧ Y)
F T F F 0 0 1 0 1
F F F F 0 1 1 0 1
d A 1 0 0 0 0
B ¬(A ↓ B) A ∨ B
1 1 0 1 1
T T T T
T F T T b ¬A ∧ (A ∨ B) ≡ ¬A ∧ B
F T T T A B ¬A A ∨ B ¬A ∧ (A ∨ B)
F F F F 0 0 1 0 0
15 a i If x is an even integer, then x = 6. 0 1 1 1 1
ii If x is not an even integer, then x  6. 1 0 0 1 0
1 1 0 1 0

Cambridge Senior Maths AC ISBN 978-1-316-63608-4 © Evans et al. 2017 Cambridge University Press
Specialist Mathematics Year 11 Photocopying is restricted under law and this material must not be transferred to another party.
 720 Answers
23E → 23 review

c ¬(A ∧ B) 7 a If a3 < b3 , then a < b.

A B A ∧ B ¬(A ∧ B) b If a3 ≥ b3 , then a ≥ b.
0 0 0 1 Multiple-choice questions
0 1 0 1 1B 2C 3D 4 C 5 A
1 0 0 1 6D 7E 8 B 9 A
1 1 1 0 Extended-response questions
1 a x y Light
Exercise 23E
0 0 0
1 a y b x  ∨ y c x ∨ y  0 1 1
2 a (x ∧ y ) ∨ (x ∧ z) ∨ (x ∧ y ∧ z ) 1 0 1
b (x ∧ y) ∨ (x ∧ z ) 1 1 0
c (x ∧ y ) ∨ (x ∧ z ) ∨ (y ∧ z)
Answers

b (x ∧ y) ∨ (x ∧ y )

or (x ∧ z) ∨ (x ∧ y) ∨ (y ∧ z )
c x¢ y

Chapter 23 review
Short-answer questions
x y¢
1 True: d, e
2 a It is not raining. b It is raining. 2 a i  = 1 ii h = 30
c 2+3≤4 d x  5 or y  5 b LCM(x, x ) = 30 = h, for all x ∈ B;
e x  3 and x  5 (i.e. x  {3, 5}) HCF(x, x ) = 1 = , for all x ∈ B
f It is raining and windy. 3 a x y z Light
3 a A B A ⊕ B A ⊕ (A ⊕ B) 0 0 0 0
T T F T 0 0 1 0
T F T F 0 1 0 0
F T T T 0 1 1 1
F F F F 1 0 0 0
Note: A ⊕ (A ⊕ B) ≡ B 1 0 1 1
b A B A ∨ B A ⊕ (A ∨ B) 1 1 0 1
T T T F 1 1 1 1
T F T F b (x ∧ y ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y ∧ z ) ∨
F T T T (x ∧ y ∧ z)
c (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x)
F F F F
d x
6 a A
y
B
b A
z
B
4 a i d ii 1 iii 0
C
b d ∨ d = d  1 and d ∧ d = d  0
c A

Cambridge Senior Maths AC ISBN 978-1-316-63608-4 © Evans et al. 2017 Cambridge University Press
Specialist Mathematics Year 11 Photocopying is restricted under law and this material must not be transferred to another party.