Logic, Truth Tables and Switching Circuits Challenge

Introduction

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.

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} $$

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} $$

${\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} $$