Boolean Algebra and Logic Circuits

A processor can only carry out a very small number of different operations on binary data, and you will start to see this when you solve problems in assembly language. These operations are just combinations of three basic operations: adding, shifting and flipping. If you understand how adding works, you will properly understand what happens in a computer’s Arithmetic and Logic Unit (ALU).

A binary half adder is a circuit that adds two single-bit binary numbers together. The possible calculations are:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10

The last calculation is the interesting one: its answer cannot be stored in a single bit. The result of 1 + 1 is 0 carry 1.

Now put this into a truth table with two inputs and two outputs. The inputs, A and B, are the two bits being added. The outputs are S and C: S is the sum (the result of the addition as a single bit) and C is the carry bit.

The carry column is produced by the logic A AND B, and the sum column is produced by the logic A XOR B. Using this, you can build the circuit that takes two single-bit numbers and adds them together: an XOR gate gives the sum and an AND gate gives the carry. This circuit is the binary half adder.

A half adder can only add two single-bit numbers. To add bigger numbers, a more complicated circuit is needed. Think about adding 101 + 111 in binary (5 + 7 in denary).

So to add two bits reliably in any column, three inputs are needed: the two bits, and the carry-in from the previous column. The circuit gives two outputs: the sum of the bits, and a carry-out to the next column. This circuit is a full adder, and it has this truth table:

You can build a full adder from two half adders. The first half adder works out A + B. The second half adder adds the sum from the first half adder to the carry-in from the previous column, which gives the final sum S. If either half adder has made a carry-out, the final carry-out must be 1, so the carry-outs of the two half adders go into an OR gate to give the final carry-out.

Binary full adders can be combined to build circuits that add very long binary numbers.

A gate can have more than two inputs. A three-input AND gate outputs 1 only when all three inputs are 1. A three-input OR gate outputs 1 when at least one input is 1. With three inputs there are 2³ = 8 combinations, so the truth table has 8 rows.

When you complete a truth table for a longer expression or a logic circuit, work out each part in its own column first, then combine the columns.

You do not need to know this circuit for the exam, but it shows how full adders can be chained together to add numbers with more than one bit.

You can think of a full adder as one functional block with three inputs (A, B and Cin) and two outputs (Sum and Cout).

You can then chain together as many full adders as you need. The carry-out from one column feeds into the carry-in of the next column.

The diagram below shows a four-bit binary adder. The four-bit binary number A (split into the bits A0 to A3) is added to the four-bit binary number B, to give the four-bit binary number S and the final carry C4. The right-hand column is a half adder, because nothing is carried into the first column. The value of C4 can be used to control a status register, to show an overflow (a number that is too big to be represented using the current representation).

All the circuits so far are combinational circuits (sometimes called combination circuits): their outputs depend only on their current inputs.

Flip-flops are different. They are sequential circuits: their outputs depend not only on the current inputs but also on the sequence of past inputs. A flip-flop lets a previous output value be stored, so it acts as a simple memory device. This memory is volatile: it does not keep its state when the power is switched off.

Sequential circuits can be asynchronous or synchronous:

• In an asynchronous circuit, the inputs are processed as soon as they arrive.
• In a synchronous circuit, the operations are controlled by a clock.

The clock in a computer system is an oscillator that produces a continuous stream of alternating signals, read as 1s and 0s. This clock signal is carried to every component of the computer system, to keep their operations in step. The time taken for one complete signal, one high (1) and one low (0), is called a clock cycle.

An SR flip-flop is a simple one-bit memory device. It is an asynchronous sequential circuit built from two cross-coupled NOR gates: the output of each gate feeds back in as an input to the other gate. A similar circuit can be built with NAND gates.

The circuit has two inputs, S and R. S is used to SET the device and R is used to RESET it. It also has two outputs, Q and NOT Q.

• When S = 1 and R = 0, the output Q is 1: S sets the flip-flop.
• When S = 0 and R = 1, the output Q is 0: R resets the flip-flop.
• After it has been set or reset, when S = 0 and R = 0, the previous value of Q is kept by the feedback loop until the circuit is set or reset again. This is how the circuit acts as a one-bit memory device.

The circuit must not allow both inputs to be 1. If you follow the logic, S = 1 and R = 1 would make both Q and NOT Q equal 0, which is contradictory. This is called an illegal state.

The SR flip-flop can be unstable if the inputs do not arrive at the same time. This can be improved by using a clock signal to synchronise the gates’ operation.

An SR flip-flop can also be made by cross-coupling two NAND gates, but then the hold and forbidden (illegal) states are the other way round: the hold state is when both inputs are 1, and the illegal state is when both inputs are 0. It is an active-low SR flip-flop: an input does its job when it is 0, not 1. So its inputs are labelled NOT S and NOT R (S and R with a bar over them), and this version is called the NOT R NOT S flip-flop.

The important point about a NAND gate is that its dominating input is 0: if any of its inputs is 0, the output is 1, whatever the other input is. The output is 0 only if all the inputs are 1. With this in mind, the NAND-based flip-flop works like this:

In practice, a clock (enable) input is usually added, so the flip-flop can only change state when the clock signal allows it. This is called a clocked SR flip-flop, and it is what “SR flip-flop” normally means.

The JK flip-flop is the most widely used flip-flop. It is more stable than an SR flip-flop and more flexible than a D-type flip-flop. It has two inputs, J and K, as well as the clock signal (Clk), so it has four functions: SET, RESET, HOLD and TOGGLE.

When the clock signal is low (0), the outputs do not change. When the clock signal is high (1):

• J = 0 and K = 0: there is no change to Q (HOLD).
• J = 0 and K = 1: the flip-flop is RESET, so Q = 0.
• J = 1 and K = 0: the flip-flop is SET, so Q = 1.
• J = 1 and K = 1: the value of Q will toggle (change to the opposite value).

Because J = 1 and K = 1 toggles Q instead of giving contradictory outputs, the JK flip-flop prevents the illegal states that cannot be allowed in an SR flip-flop.

Several JK flip-flops can be used to make shift registers in a computer system, and a simple binary counter can be made by connecting several JK flip-flops together.

Boolean algebra is a formal way of writing logical statements. It was introduced by George Boole, an English mathematician, in his book “The Mathematical Analysis of Logic” (1847).

In Boolean algebra the basic logic gate operations (AND, OR, XOR and NOT) are replaced with symbols. In these notes AND is written as a dot (A . B), OR as a plus (A + B), and NOT is written in words (NOT A, or NOT(A . B) for a whole bracket). In the book and in exam papers, NOT is drawn as a bar over the letter or over the bracket.

Knowing the Boolean identities (next section) lets us simplify logic statements. For example, a complicated circuit made of 20 logic gates may simplify to only 5 or 6 gates, which makes the circuit cheaper to manufacture.

Boolean identities are equivalences that are true for every possible set of input values. Each law comes as a pair: one for AND and one for OR.

Most of the identities make common sense when they are turned into sentences. The idempotence laws say that "I will go to bed if I am tired or I am tired" reduces to just "I will go to bed if I am tired". The inverse laws say that "it is the weekend and it is not the weekend" is always False.

One pair of laws that is less linked to common sense or basic mathematics is De Morgan’s laws, named after the nineteenth-century British mathematician Augustus De Morgan.

To simplify an expression, apply one law at a time and name the law you used at each step.

Try these guided questions before looking at the last step, which gives the answer.

Answer to guided question 3, one law at a time:

A Karnaugh map (also called a K-map) is a version of a truth table for a Boolean expression, laid out in a way that makes the expression easier to simplify.

Take the expression A + (A . B). Its truth table is:

The truth table has four rows because there are two inputs, so 2² combinations of 1s and 0s. Each row shows the output for one combination of input values.

A Karnaugh map is a variation on a truth table, arranged so that:

• the number of output cells matches the number of rows in the truth table
• the possible input values for the variables in the expression form the row and column headings
• the output for each combination of input values is written where its row and column meet.

Here is the Karnaugh map for A + (A . B). The values of A are the column headings and the values of B are the row headings. Where a row and a column meet is the output for those inputs.

In a Karnaugh map you circle groups of 1s whose size is a power of 2 (1, 2, 4 or 8 cells, but not 3, 5 or 6). Here there is only one group: the two 1s in the column where A = 1. As it is the only group, the expression simplifies to A.

These are the steps for drawing the Karnaugh map of A + (A . B):

1. Create a grid. The number of rows and columns depends on the number of variables in the expression.
2. Break up the expression at the ORs. This gives two parts: A, and A . B.
3. Take the first part: write a 1 wherever A is True. This means 1s in both cells of the right-hand column.
4. Take the second part: write a 1 wherever A . B is True. This is the bottom right-hand cell, but there is already a 1 there, so nothing more is needed.
5. Write 0s in the empty cells (or leave them blank).
6. Circle every group of 1s whose size is a power of 2 (groups of 1, 2, 4 or 8 cells).

There is a single circled group of 1s, in the column where A = 1. As it is the only group, the expression simplifies to A.

Note An expression made of AND terms joined by OR, such as A . B + NOT A . B, is called a sum of products. Breaking it up at the ORs, as in step 2, gives one term to place on the map at a time. To write one from a truth table, take each row where the output is 1, write its inputs joined by AND (with NOT on each input that is 0 in that row), then join these terms with +. For example, outputs of 1 in the rows A = 0, B = 1 and A = 1, B = 1 give NOT A . B + A . B.

The circled group shows that the output is 1 whenever B is 1, so the expression simplifies to B.

Here is a map with more than one group of 1s. To find the expression it represents, look at each circled group in turn and see which input or inputs stay the same across the whole group.

• The blue, horizontal group shows that the output is always 1 when B is 0, so this group represents NOT B.
• The red, vertical group shows that the output is always 1 when A is 1, so this group represents A.

Join the expressions for the groups with +. This map represents A + NOT B.

In a Karnaugh map with three inputs, one side of the map represents two of the inputs. Consider the expression (A . B) + (A . B . C). In its map:

• there are four rows for the possible values of the inputs AB
• there are two columns for the possible values of the input C.

It does not matter how you split the inputs, so this map could also be drawn with two rows and four columns. But the order of the input values matters: on a side with two inputs (here AB), only one of the two values may change from one cell to the next. So 01 can never be next to 10, and the order is 00, 01, 11, 10, which is different from the usual order of rows in a truth table.

Now fill in the map:

• Split the expression at the +. This gives A . B and A . B . C.
• Put a 1 in the cells where A . B is True.
• Put a 1 in the cells where A . B . C is True. Here that cell (AB = 11, C = 1) already holds a 1.
• Circle groups whose number of 1s is a power of 2 (1, 2, 4 or 8 cells).

The map is shown in two forms. The map on the right groups the inputs differently, but gives the same result: the grouping of inputs does not matter. The circled group of 1s is where both A and B are 1, so the simplified expression is A . B.

Karnaugh maps in A Level exam questions can have up to four inputs. Take the expression C + (C . A . B . D). In its empty map:

• there are four columns for the possible values of the inputs AB
• there are four rows for the possible values of the inputs CD
• on each side, only one value of each pair changes from one cell to the next (the order 00, 01, 11, 10).

Using the same method as before, place 1s on the map for each of the two parts of the expression: C, and C . A . B . D.

This time there is one big group of eight 1s to circle. It shows that the output is always 1 when C is 1, so the expression simplifies to C.

Here is a four-input Karnaugh map with two overlapping groups of 1s. A 1 may belong to more than one group.

• The large blue group of eight 1s represents C, as in the section before.
• In the red, vertical group, A and B are both always 0. So this group represents NOT A . NOT B.

Join the two expressions with a + (OR) to get the expression this map represents: (NOT A . NOT B) + C.

A group can go off one edge of the map and come back on the opposite edge: the left and right edges count as next to each other, and so do the top and bottom edges. In this map, the two blue groups of two 1s are really a single group of four 1s that wraps around the left and right edges.

You can prove this by looking at the inputs: for every 1 in this group, B is always 0 and C is always 1. So the group represents C . NOT B.

Note In this map every cell in the bottom two rows holds 1, so in a full answer they would be circled as one group of eight (C) and this group of four would not be needed. The map is here to show how a group wraps round the edge.

• The blue group of eight 1s represents C.
• The green group of four 1s wraps round the top and bottom edges, but it does not reach into the row where C = 1 and D = 1. If it did, it would be a group of six 1s, which is not allowed.
• The green group shows that the output is True when B = 1 and D = 0, so it represents B . NOT D.

This gives the full expression C + (B . NOT D).