Logic Circuits and Boolean Algebra

🔁 19.02 Sequential logic circuits

Every circuit in this book so far has been a combinational circuit: its output depends only on the input values. In a sequential circuit the output depends on the inputs and on the previous output. That feedback is what lets a circuit remember.

🔒 The SR flip-flop

The SR flip-flop, or latch, is a simple sequential circuit. It can be built with two NAND gates or two NOR gates. Figure 19.05 shows the NOR version.

The two gates are cross-coupled: each output feeds back into the other gate. This has interesting consequences.

• Suppose R, S, Q and Q′ were all 0. That contradicts itself: a NOR gate with two 0 inputs outputs 1.
• Q and Q′ both 1 is also impossible, because a NOR gate outputs 0 if either input is 1.
• So the flip-flop is a two-state device: either Q = 1 and Q′ = 0, or the reverse.

The two rows of Table 19.03 where S and R are both 0 mean no signal is being input. Take the state Q = 1, Q′ = 0 with S = R = 0:

• the top NOR gate has inputs R = 0 and Q′ = 0, so it outputs 1 (Q stays 1);
• the bottom NOR gate has inputs S = 0 and Q = 1, so it outputs 0 (Q′ stays 0).

The state is self-consistent: it is the set state. The same argument works for the unset state, Q = 0 and Q′ = 1. S and R stand for set and reset: S = 0, R = 1 turns a set state into an unset state, and S = 1, R = 0 turns an unset state into a set state.

Table 19.03 A representation of a truth table for an SR flip-flop

This is why an SR flip-flop can store 1 bit, and so could be a component of RAM: a value is held, but it can be changed. There are no rows for S = 1 and R = 1, because that leads to an invalid state with Q and Q′ both 0. The circuit must be protected from receiving a signal on R and S at the same time.

The NAND gate version has a similar structure, but the labelling is different: setting is done with S = 0 and R = 1 and resetting with R = 0 and S = 1 (its inputs are "active low").

⏱️ The JK flip-flop

Besides the invalid state, a circuit can end up in an uncertain state if the inputs do not arrive at quite the same time. To prevent this, a circuit can have a clock pulse input, which gives a better chance of synchronising the inputs. The JK flip-flop is an example.

Remember that a NAND gate gives a 1 unless all its inputs are 1. In the unset state, Q = 0 and Q′ = 1, the circuit is stable:

• the clock and K both input 0 (the book prints "R" here; in a JK flip-flop it is K);
• so the top-left NAND gate outputs 1;
• which gives two 1 inputs to the top-right NAND gate;
• ensuring Q = 0.

If J now becomes 1 and the clock pulse switches to 1:

• the top-left NAND gate has all its inputs at 1, so it outputs 0;
• this makes the top-right NAND gate output 1 for Q;
• now the bottom-right NAND gate has two 1 inputs, so Q′ becomes 0.

So J is a set input, and by a similar argument K is a clear input. Like the SR flip-flop it stores one bit, with one important difference: if J and K are both 1, Q and Q′ are toggled (they swap values). No combination of inputs leaves the stored value uncertain, so the JK flip-flop is more reliable.

Table 19.04 Part of the truth table for a JK flip-flop

🧮 19.03 Boolean algebra basics

Chapter 4 (Section 4.01) introduced logic expressions: propositions joined by Boolean operators. Boolean algebra is a simpler way to write them, plus a set of rules for manipulating them.

With any algebra you must be clear what the symbols mean. Here are four meanings of 1 + 1:

In Boolean algebra 1 means TRUE, 0 means FALSE and + means OR. So the fourth line reads TRUE OR TRUE is TRUE.

Notations vary: AND and OR are sometimes written ∧ and ∨, and A AND B can be written A.B or AB. This book uses the dot. NOT A, the inverse of A, is written A.

📜 The laws (identities) Table 19.05

Don't worry if some of the names are unfamiliar. Notice that every identity except one has an AND form and an OR form, and you can turn one into the other by swapping each 0 with 1 and each AND with OR. For example 0.A = 0 (FALSE AND A is FALSE) becomes 1 + A = 1 (TRUE OR A is TRUE).

Some identities look like ordinary algebra, with AND acting like multiplication and OR like addition. That is why we talk about products and sums in Boolean algebra.

De Morgan's laws look complicated but are easy to rationalise: the inverse of a product becomes the sum of the inverses, and the inverse of a sum becomes the product of the inverses ("break the bar, change the sign").

🧩 Worked Example 19.01

Using the algebra to simplify an expression cannot be learned as a routine. It needs some lateral thinking.

⚖️ Equivalence checker

Simplified something? Check it here: the checker builds a truth table for both expressions. Use letters for inputs, . (or nothing) for AND, + for OR, and ' after a letter or bracket (or ! before it) for NOT. Example: A + A'.B.

🧾 19.04 Creating an expression directly from a truth table

One formal approach is the sum-of-products method. You write a minterm for each row of the truth table whose output is 1, then OR the minterms together.

For the half adder (Table 19.01), only one row gives C = 1: A = 1 and B = 1. The product is A.B, and the sum of products has just this one term:

Two rows give S = 1, so its sum of products has two minterms:

A 0 in a row is written as the inverse of that input.

Sometimes the laws can be applied straight to parts of the table. Suppose a truth table contains these two rows:

X is 1 whether C is 0 or 1, so there must be a minterm with no reference to C: A.B.

🔌 The Boolean algebra representation of a logic circuit

The same ideas can turn a circuit diagram into an expression: use the truth tables of the individual gates, then simplify with the algebra.

WORKED EXAMPLE 19.02

Creating a Boolean algebra logic expression for a half adder circuit

1. A and B go into a NAND gate with output W. The first three rows of the NAND truth table give 1, so the sum of products has three minterms: W = A.B + A.B + A.B
2. W and A go into a NAND gate to give X. Treat NAND as AND followed by NOT. The AND gives the product of the inputs: A.(A.B + A.B + A.B)
3. The distributive and inverse laws simplify this: 0 + 0 + A.A.B, which is simply A.B
4. Now apply the NOT, using the AND form of De Morgan's law, which turns A.B into A + B: X = A + B
5. The same laws applied to the other intermediate NAND gate give: Y = A + B
6. Finally A + B and A + B go into the last NAND gate. The AND part gives the product: (A + B).(A + B)
7. Instead of multiplying it out, apply De Morgan's law directly to perform the inverse: S = A.B + A.B ✔This is exactly the expression we got from the truth table, so the algebra has been used correctly.

Show next step↺ Start again

🗺️ 19.05 Karnaugh maps (K-maps)

A Karnaugh map is a way of creating a Boolean expression from a truth table. It is usually much easier than writing minterms with sum of products and, used correctly, it gives the simplest possible expression.

A	B	X
0	0	0
0	1	1
1	0	1
1	1	1

Table 19.06 The truth table for the OR operand

Sum of products gives:

X = A.B + A.B + A.B

That is not obviously A + B, although the algebra could show it. The K-map is simpler. Each cell holds the output X for one combination of A and B:

The rules for reading a K-map

• Only cells containing a 1 are considered.
• Groups of 1s are identified where possible; a group is a row, a column or a rectangle.
• Groups must contain 2, 4, 8 and so on cells.
• Each group should be as large as possible.
• Groups can overlap, and all overlapping groups must be used.
• If a cell cannot be put in any group, it is treated as a group on its own.
• Within each group, keep only the inputs whose value stays constant throughout the group.

In Figure 19.08 there is a column group and a row group. In the column, B stays the same but A changes, so B is kept. In the row, A stays the same. The expression is the sum of what is kept:

The K-map found the OR expression without any algebra.

🧩 Worked Example 19.03

WORKED EXAMPLE 19.03

Using a K-map to interpret a three-input problem

A	B	C	X
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Table 19.07 A sample truth table with three inputs

Before using any method, look for trends. Whenever B = 1, X is 1, so the answer should be "B + something".

Sum of products gives five minterms:

A.B.C + A.B.C + A.B.C + A.B.C + A.B.C

There are two ways to lay out the K-map. Here the input values are combined in the columns: rows for A, columns for B and C.

The column labels do not follow binary order. They follow the Gray code sequence (00, 01, 11, 10), where only one bit changes each time.

The first group is the square of four 1s (blue rectangle). In it A changes and C changes, but B is constant, so only B is kept, as predicted.

That seems to leave the top-left cell, BC = 00, isolated. It is not, because K-maps wrap round. BC = 01 is next to it but holds a 0. Its other neighbour is BC = 10, at the far end of the row. So there is a row group of BC = 00 and BC = 10 (the dotted partial outlines). In it A stays the same, B changes and C stays the same, so the product is A.C. Adding the B from the other group:

A.C + B

That is much simpler than the five-minterm expression from the truth table.

🔬 K-map lab

Tap cells to set them to 1 or 0. The lab finds the largest groups (coloured dots show which groups each cell belongs to) and writes the simplest sum of products. The small number in each cell is its row number in the truth table.

🧠 Extension Question 19.02

📌 Summary

• Binary addition can be carried out using a half adder or a full adder circuit.
• SR or JK flip-flop circuits can be used to store a bit value.
• There are Boolean algebra laws that can be used to simplify logic expressions.
• The sum-of-products method can be used to create an equivalent logic expression containing minterms from a truth table.
• A Karnaugh map is a representation of a truth table that allows a simplified logic expression to be derived from it.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

1 a Consider the circuit below. (i) Identify the three different logic gates used. (ii) Complete the truth table for the inputs shown for A and B.[2] [5]›

(i) OR, AND, NOT.

(ii) The top path is A + B; the AND gate gives A.B (which is also R); the NOT gives A.B; the final AND gives S.

A	B	A + B	A.B	A.B	S	R
0	0	0	0	1	0	0
0	1	1	0	1	1	0
1	0	1	0	1	1	0
1	1	1	1	0	0	1

2 b Consider the circuit below. (i) Write a Boolean algebra expression for the output from the first AND gate. (ii) Write a Boolean algebra expression for the output from the OR gate. (iii) Using De Morgan's law, write the logic expression for the output from the NOT gate.[2] [3] [4]›

(i) A.B (the AND truth table is 1 only when both inputs are 1).

(ii) A + B. By sum of products: A.B + A.B + A.B, which simplifies to A + B.

(iii) A + B = A.B (OR form of De Morgan's law).

Teacher's note: the final gate gives X = A.B.A.B = 0, so this circuit always outputs 0. The question only asks about the intermediate outputs.

4 b An SR flip-flop is constructed using two NAND gates. (i) Complete the truth table for the SR flip-flop. (ii) One of the combinations should not be allowed to occur. State the values of S and R that should not be allowed. Justify your choice.[4] [3]›

(i) Q = NAND(S, Q), Q = NAND(R, Q):

	S	R	Q	Q
Initially	1	0	0	1
R changed to 1	1	1	0	1
S changed to 0	0	1	1	0
S changed to 1	1	1	1	0
S and R changed to 0	0	0	1	1

(ii) S = 0 and R = 0. A NAND gate outputs 1 if any input is 0, so both Q and Q become 1. That breaks the rule that Q is the complement of Q, and when S and R return to 1 the final state depends on which input changes first, so it is unpredictable.

5 a A half adder has the truth table X Y → A B: 0 0 → 0 0, 0 1 → 0 1, 1 0 → 0 1, 1 1 → 1 0. The logic circuit below is constructed from two of them. (i) Complete the truth table for this logic circuit. (ii) State the name given to this logic circuit. (iii) Name the labels usually given to J and K. Explain why your answers are appropriate labels for these outputs.[2] [1] [4]›

In this half adder, output A is the AND (carry) and B is the XOR (sum). The first half adder gives P.Q and P⊕Q; the second gives (P⊕Q).R and P⊕Q⊕R; J ORs the two carries.

(i)

P	Q	R	P.Q	P⊕Q	(P⊕Q).R	J	K
0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	1
0	1	0	0	1	0	0	1
0	1	1	0	1	1	1	0
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	0
1	1	0	1	0	0	1	0
1	1	1	1	0	0	1	1

(ii) A full adder.

(iii) J = carry out (Cout) and K = sum (S). K is 1 when an odd number of P, Q, R are 1: the sum bit of adding three bits. J is 1 when two or more of the inputs are 1: the carry to the next column. R acts as the carry in from the previous column.

5 b (i) Write down the Boolean expression corresponding to the logic circuit below. (ii) Use Boolean algebra to simplify the expression given in part b(i). Show your working.[2] [4]›

(i) X = A.((A + B).C)

(ii)

X = A.(A + B).C  (associative) = (A.A + A.B).C  (distributive) = (A + A.B).C  (idempotent) = A.C  (absorption)

Or in one step: A.(A + B) = A by the AND form of absorption, so X = A.C.

Cambridge International AS & A Level Computer Science 9608, Paper 32 Q5, November 2016