Further Boolean Logic and Truth Tables

In module 1 we looked at a couple of basic circuits and some truth tables. We used truth tables to represent the inputs and outputs of circuits. However, we can also use truth tables to design circuits to do what we want. Take the following problem, for instance:

Let the binary digits be x_1, x_2, x_4.

Think about how to design a circuit which satisfies this. A way to do this is to consider how the truth values of each digit might affect the divisibility of the number (for example, if x_1 = 0, then the number is divisible by 2, so it is not prime unless the number is 2 itself).

Another, more universally applicable method is to write down the intended inputs and outputs in a truth table to systematically create a boolean expression which results in the desired behaviour.

We can represent the current problem in a table as follows (here, we are using H and L to represent true and false respectively, as a lot of truth tables you may encounter in datasheets use these to represent the HIGH and LOW logic levels):

There are a few different ways to go about deriving a circuit from this truth table.

Method 1

One way which will work on this truth table is to split up the table into two parts—one where x_4 is 0 and one where x_4 is 1—such that we can reduce this problem to two expressions in two variables each. In this case, this would be the top and bottom halves of the table

What expression matches the above circuit when x_4 = 0?

x_2 \cdot x_1

x_2 + x_1

x_2

x_1

Loading...

What expression matches the above circuit when x_4 = 0?

x_2 \cdot x_1

x_2 + x_1

x_2

x_1

Loading...

We need a way to connect these two circuits. For this we will use a circuit that is known as a multiplexer. We will use a simple version for now, and we will see it again in more depth in exercise 3.

A 1-bit multiplexer has the following behaviour: 3 bits of input, a,b,s, with s referring to the select bit. It has one bit of output. If s = 0, then the output is equal to a. If s = 1, then the output is equal to b.

This can be achieved with the following circuit:

(s \cdot b) + (\bar s \cdot a)

We can apply this to the truth table above to get the following:

y \equiv (\bar x_4 \cdot x_2) + (x_4 \cdot x_1)

Unfortunately, this method will not always work, especially on truth tables with more than three variables. This is because there is not necessarily an obvious pattern for more complex circuits. For that, we will need another, more general, method.

Method 2: Sum of Products

This method relies on the fact that you can express a single row in the truth table with AND and NOT gates. Here, we will construct an expression for each row in the table which has a HIGH output and connect them together to obtain the final circuit.

Let us take the following problem as an example:

Construct a circuit which plays a simplified version of FizzBuzz*. Let's say the input is HIGH if and only if the input is a multiple of 3 or a multiple of 7

Let the inputs be x_8,x_4,x_2,x_1 and let the output be y

This gives us the following truth table:

Here, we can go row by row and, for each row where the output is HIGH, create an expression which is true only for that set of values.

As an example, let us take the row where the input is 6. Since we can see that 6 = 0 \cdot 8 + 1 \cdot 4 + 1 \cdot 2 + 0 \cdot 1, we can deduce that y is HIGH if all of the following hold:

x_8 \equiv 0, x_4 \equiv 1, x_2 \equiv 1, and x_1 \equiv 0.

Since we want to be able to join these with a connective, let us make each term a true expression.

\bar x_8 \equiv 1, x_4 \equiv 1, x_2 \equiv 1, and \bar x_1 \equiv 1.

Since we want all of these to be true at once, we can connect them with AND gates.

\bar x_8 \cdot x_4 \cdot x_2 \cdot \bar x_1 \equiv 1

This is an expression that's true if and only if the input is 6.

Now, we can go through each other row with a HIGH output and create a similar expression.

What is the full list of values for which we will be making a sum of products expression? Express the answer as a python list containing only values of type int.

Loading...

For each of these, create one circuit which gives an output of HIGH only if the input is the given number

Upload a picture of the logic diagram for each of these.

We want our final expression to be HIGH when any of the expressions are HIGH.

What single connective should be used?

AND

OR

NAND

NOR

XOR

Loading...

Now, we can make the final circuit Upload a picture of the final circuit

*FizzBuzz is a common programming problem adapted from a children's game where players take turns calling out numbers, but when you are on a multiple of 3, you must call out Fizz instead of the number, and on a multiple of 5, you must call out Buzz instead of the number. On multiples of 3 and 5 i.e. multiples of 15, you must call out FizzBuzz instead of the number. For this problem, we have changed the divisibility rule from 5 to 7 to make the problem slightly more interesting.