Logic, Truth Tables and Switching Circuits Challenge

Age 11 to 18

Published March 2008,April 2008,February 2011.

Introduction

So that you can build and test your own circuits and see how the circuits relate to the language of logic used in mathematics you need to open the interactivity Circuit Maker and use it as you work through this article.

If you want a very simple introduction to truth tables you might like to start with Truth Tables and Electronic Circuits but this article also provides an introduction to the subject and does not assume any prior knowledge of truth tables or circuits.

 In this article you will find explanations of circuits and how they correspond to the logical language we use to discuss mathematics. You will be challenged to summarise the workings of the circuits by filling in blanks in the corresponding truth tables.  This diagram gives a summary of the information you will need to build your own circuits. There is another version of the article here with the answers to the challenges. This is the first of a series of articles on mathematical logic which will show that truth tables, set theory, Boolean algebra and electronic circuits are essentially equivalent; that is, theorems that can be proved in one system have their counterparts in the other systems. In subsequent articles we shall see how Boolean algebra is used in designing electronic circuits. In this article we begin to explore the links between electronic circuits and mathematical logic.

Although logic does not model language perfectly it does form a useful system that, in practice, is the basis of most of the communication of mathematical ideas between working mathematicians. Logical conventions are used to overcome the ambiguities and inadequacies of language. The philosophical aspects of the subject are rather more subtle and complicated and we shall not dwell on them.

A proposition is a statement that has exactly one of the truth values 'true' or 'false'. A ${\it propositional}$ ${\it function}$ is a sentence involving variables, for example "She is the Queen of England" and "$x$ is greater than 7". These functions become propositions when meanings are substituted for the variables ('she' and '$x$' in the above examples).

Before we go on to experiment with circuits we need a notation to record and summarize the combinations of propositions used in logical arguments and also the combinations of switches used in circuits.

We use small letters $p, q, r...$ to represent propositions. If the proposition $p$ is true it is said to have the truth value 1 (or sometimes T) and if false the truth value 0 (or F). Propositional logic is concerned with compound propositions formed from given propositions by means of the ${\it connectives}$ 'not', 'and', 'or', 'if ... then' and combinations of these connectives, for example 'if and only if'.

In circuit diagrams each switch is either 'on' (representing the number 1) or 'off' (representing the number 0). Combinations of switches called ${\it logical}$ ${\it gates}$ represent the logical ${\it connectives}$.

Logical arguments are a combination of propositions, and circuits are a combination of switches that control the flow of current. Modern computers not only store data in the form of '0's and '1's, on which they perform arithmetic, but perform many highly complex tasks that we have come to take for granted. Studying the relation between truth tables and circuits will help us to understand a little of the underlying principles behind the design and programming of computers.

${\bf Negation}$

Now it is time to use Circuit Maker to make some of your own circuits and find out how the logic gates work.

 First, connect a switch to a lamp as in Fig. 1 and click on the switch several times to change it from 1 to 0 and back to 1. Observe that the light goes on when the switch registers 1 and the light goes off when the switch registers 0. Fig. 1 Fig. 2 Now put a NOT gate into the circuit between the switch and the lamp, as shown in Fig. 2, and observe what happens when you change the switch from 1 to 0.
Given a proposition $p$, the ${\it negation}$ not-$p$, written $\neg p$, is the proposition demonstrated by this circuit and defined by the following truth table. $$\begin{array}{ccc}p & \neg p \\ 1 & 0 \\ 0 & 1 \end{array}$$
${\bf Conjunction}$

The logical connective 'and' is used to make a compound proposition from two component propositions. For example if we speak the truth when we say "Today is Friday and it is raining" then both of the component propositions are true. If either or both are false then the compound proposition is false.
 Make and test the circuit shown in Fig 3. and fill in the truth table replacing the question marks with 1's to record when the lamp lights up and 0's to record when the lamp goes off. Fig. 3 $$\begin{array}{ccc}p &q & p\wedge q \\ 1 &1 &?\\ 1 &0 &?\\ 0 &1 &?\\ 0 &0 &? \\ \end{array}$$

${\bf Disjunction}$

In everyday language we often use 'or' inclusively as in "If you want to buy cereals or soft drinks go to aisle 7 in the supermarket" when we expect people who want to buy both cereals and soft drinks to go to that aisle as well as people wanting to buy just one of them. On other occasions we use 'or' exclusively to offer two alternatives expecting the listener to choose just one of them as in "Do you want steak for dinner or chicken?". The meaning is usually clear from the context but to avoid any ambiguity in mathematics the logical connective 'or' is always used inclusively and never exclusively.

Given any two propositions $p$ and $q$ the ${\it disjunction}$ $p$ or $q$, (written $p \vee q$) is given in the following truth table. Fig.4 Make the circuit shown in Fig 4. and fill in the blanks in the truth table replacing the question marks with 1's and 0's.. $$\begin{array}{ccc}p &q & p\vee q \\ 1 &1 &?\\ 1 &0 &?\\ 0 &1 &?\\ 0 &0 &? \\ \end{array}$$

${\bf Compound}$ ${\bf propositions}$

Truth tables for more complicated compound propositions can be formed from the simpler ones. For example, the following truth table and circuit (Fig 5) show that $\neg(p\vee q)$ has the same truth values as $\neg p \wedge \neg q$. Make the circuit and fill in the missing values in the truth table. Fig. 5 $$\begin{array}{ccc} p &q & p\vee q & \neg (p\vee q) & \neg p & \neg q & \neg p \wedge \neg q \\ 1 &1 &1 &? &0 &0 &? \\ 1 &0 &1 &? &0 &1 &? \\ 0 &1 &1 &? &1 &0 &? \\ 0 &0 &0 &? &1 &1 &? \\ \end{array}$$

Now see if you can devise a circuit to correspond to the following truth table which shows that $\neg (p\wedge q)$is equivalent to $\neg p \vee \neg q$.

$$\begin{array}{ccc} p &q & p\wedge q & \neg (p\wedge q) & \neg p & \neg q & \neg p \vee \neg q \\ 1 &1 &1 &0 &0 &0 &0 \\ 1 &0 &0 &1 &0 &1 &1 \\ 0 &1 &0 &1 &1 &0 &1 \\ 0 &0 &0 &1 &1 &1 &1 \\ \end{array}$$

${\bf XOR,}$ ${\bf NAND,}$ ${\bf NOR}$ ${\bf and}$ ${\bf XNOR}$

Next we investigate some of the other logical gates used in circuitry. Then we shall discuss other important logical connectives such as 'implies', often expressed as 'if... then' as in " if I go to the shops then I'll buy you some ice-cream". After that we shall be able to relate the circuits to the language of logical arguments and also see how circuits can be built to perform simple operations such as addition.

Now experiment with the circuits for XOR, NAND, NOR and XNOR and complete the following truth table replacing the question marks with 1's and 0's.

$$\begin{array}{ccc} p &q &p XOR q & p NAND q &p NOR q & p XNOR q \\ 1 &1 &? &? &? &? \\ 1 &0 &? &? &? &? \\ 0 &1 &? &? &? &? \\ 0 &0 &? &? &? &? \\ \end{array}$$

Comparing these tables to what we have already discovered we see that p NOR q means 'not(p or q)', that is $\neg (p\vee q)$, and it is also equivalent to $\neg p \wedge \neg q$.

Also p NAND q means 'not(p and q)', that is $\neg (p\wedge q)$, and it is also equivalent to $\neg p \vee \neg q$.

${\bf Implication}$

Thinking about what we mean by 'if p then q' we see that this rules out the possibility that p is true and q is false. If I make the promise " if I go to the shops then I'll buy you some ice-cream" but I go to the shop and do not buy the ice-cream then I have broken my promise. So, denoting 'if p then q' by $p \Rightarrow q$, the truth table for 'if p then q' must include the line:

$$\begin{array}{ccc} p &q & p \Rightarrow q \\ 1 &0 &0 \\ \end{array}$$

As the following example shows true conclusions can be proved by valid arguments from false premises and so we should expect 'false $\Rightarrow$ true' to be true.

We shall prove the proposition '2=1 $\Rightarrow$ 2=2'. Of course 2=2 is true (by definition) but the following argument proves this as a consequence of a false hypothesis.

By the symmetry of equality if 2=1 then 1=2. By the transitivity of equality it follows that, having shown 2=1 and 1 = 2, then 2 = 2.

This establishes a second line in the truth table for implication.

$$\begin{array}{ccc} p &q & p \Rightarrow q \\ 1 &0 &0 \\ 0 &1 &1 \\ \end{array}$$

There might still be some doubt in the reader's mind about why the definition of 'false' implies 'true' is 'true'. It could not be false because then we would have $p \Rightarrow q$ logically the same as $q\Rightarrow p$ which is not the case. Consider for example $x=1 \Rightarrow x> 0$ which is true whereas $x> 0 \Rightarrow x=1$ is false, so we have no choice but to make this definition for $p \Rightarrow q$.

Also 'if x then x' is true whether x is true or false so we must have the complete truth table as follows.

$$\begin{array}{ccc} p &q & p \Rightarrow q \\ 1 &1 &1 \\ 1 &0 &0 \\ 0 &1 &1 \\ 0 &0 &1 \\ \end{array}$$

It is convenient to have a single connective which combines $p \Rightarrow q$ and $q \Rightarrow p$. This connective is the ${\it bi-conditional}$ 'p if and only if q' (written $p \Leftrightarrow q$)and defined by the truth table:

$$\begin{array}{ccc} p &q & p\Leftrightarrow q \\ 1 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \\ \end{array}$$

We observe that in the truth table for $p \Leftrightarrow q$ this compound proposition is true precisely in those circumstances in which p and q have the same truth values and this is given by the logic gate p XNOR q. Also observe that the logic gate p XOR q is equivalent to $\neg(p \Leftrightarrow q)$.

Note that p XOR q is 'the exclusive or', true when either p is true or when q is true but not when they are both true. In everyday language we often use the exclusive or, as in "do you want steak or chicken for dinner?", but to the mathematician who, by convention, uses only the inclusive or, the logical answer is " yes" if he wants meat for dinner and "no" if he does not want meat.

${\bf Tautologies}$

If the truth value of a compound proposition is always true for all possible combinations of truth values of the given propositions, then the compound proposition is called a tautology. The following truth table and circuit show that $p \vee \neg p$ is a tautology. This is called the Law of the Excluded Middle because either $p$ is true or $\neg p$ is true and there is no third alternative. Fig. 7 $$\begin{array}{ccc} p & \neg p & p \vee \neg p \\ 1 &0 &1 \\ 0 &1 &1 \\ \end{array}$$

${\bf The}$ ${\bf Sheffer}$ ${\bf stroke}$

The five connectives $\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow$ can be defined by one symbol called the Sheffer stroke which was devised by H.M.Sheffer in 1913. At the time it was simply a piece of pure mathematics, but later it has had applications in designing electronic circuits from assemblies of a single component, the NAND gate. We have already seen that p NAND q is equivalent to 'not p or not q' or, equivalently, 'not (p and q)' and that it has the following truth table.

$$\begin{array}{ccc} p &q &p NAND q \cr && Sheffer stroke \cr 1 &1 &0 \cr 1 &0 &1 \cr 0 &1 &1 \cr 0 &0 &1 \cr \end{array}$$

The negation $\neg p$ is equivalent to p NAND p.

The disjunction $p \vee q$ is equivalent to $(p NAND p)NAND(q NAND q)$.

Can you make up three circuits, using only the NAND gate, that are equivalent to the conjunction $\wedge$, to the conditional $\Rightarrow$ and to the bi-conditional $\Leftrightarrow$?

If you have worked through this article you should now be able to solve the problems Simple Counting Machine, Adding Machine and Circular Circuitry and not just by trial and error, and you should be able to explain the circuits.