Produce truth tables for logic circuits including half adders and full adders

15.2 Boolean Algebra and Logic Circuits

Learning Objective

Produce accurate truth tables for common combinational circuits – especially the half‑adder and full‑adder – translate Boolean expressions into gate‑level diagrams, simplify expressions with Karnaugh maps, implement using NAND‑only gates, and discuss propagation delay and gate count. Extend the knowledge to simple sequential circuits (flip‑flops) and link the hardware design to algorithmic thinking (AO2) and abstract data types (ADT).

---

1. The Six Fundamental Gates (Cambridge 9618)

Gate	Symbol	Boolean expression	Truth table
NOT		\(\lnot A\)	A \(\lnot A\) 0 1 1 0
AND		\(A\cdot B\)	A B A·B 0 0 0 0 1 0 1 0 0 1 1 1
OR		\(A+B\)	A B A+B 0 0 0 0 1 1 1 0 1 1 1 1
NAND		\(\overline{A\cdot B}\)	A B \(\overline{A·B}\) 0 0 1 0 1 1 1 0 1 1 1 0
NOR		\(\overline{A+B}\)	A B \(\overline{A+B}\) 0 0 1 0 1 0 1 0 0 1 1 0
XOR		\(A\oplus B\)	A B A⊕B 0 0 0 0 1 1 1 0 1 1 1 0

---

2. Half‑Adder

Adds two single‑bit binary numbers (inputs \(A\) and \(B\)). Outputs are Sum and Carry‑out.

2.1 Boolean expressions

• Sum \(S = A\oplus B\)
• Carry \(C = A\cdot B\)

2.2 Truth table

A	B	Sum (A⊕B)	Carry (A·B)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

2.3 Gate‑level diagram

2.4 NAND‑only implementation (syllabus requirement)

The XOR can be realised with four NAND gates; the AND with a single NAND followed by a NOT (implemented by a NAND with its inputs tied together).

\[ A\oplus B = \overline{\overline{A\cdot\overline{B}}\;\cdot\;\overline{\overline{A}\cdot B}} \]

2.5 Propagation delay & gate count

• Standard gate count: 1 XOR + 1 AND = 2 gates.
• NAND‑only gate count: 4 NAND (XOR) + 2 NAND (AND + NOT) = 6 NAND gates.
• Maximum propagation delay: the longest path is through the XOR (typically 2 gate‑delays).

---

3. Full‑Adder

Adds three single‑bit numbers: data bits \(A, B\) and a carry‑in \(C_{\text{in}}\). Outputs are Sum and Carry‑out.

3.1 Boolean expressions

\[ \begin{aligned} \text{Sum}&=A\oplus B\oplus C_{\text{in}}\\[2mm] C_{\text{out}}&=(A\cdot B)\;+\;\bigl(C_{\text{in}}\cdot (A\oplus B)\bigr) \end{aligned} \]

3.2 Truth table

A	B	Cin	Sum (A⊕B⊕Cin)	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

3.3 Construction from two half‑adders + OR gate

3.4 NAND‑only implementation

Replace every XOR, AND and OR with their NAND equivalents. The resulting circuit uses nine NAND gates.

3.5 Propagation delay & gate count

• Standard gates: 2 XOR + 2 AND + 1 OR = 5 gates.
• NAND‑only: 9 NAND gates.
• Maximum propagation delay: 2 gate‑delays for the first XOR, 1 gate‑delay for the second XOR, and 1 gate‑delay for the final OR → typically 4 gate‑delays.

---

4. Simplifying the Carry‑Out with a Karnaugh Map

4.1 Original expression

\[ C_{\text{out}} = (A\cdot B) + \bigl(C_{\text{in}}\cdot (A\oplus B)\bigr) \]

4.2 Karnaugh map (variables \(A,B\) across the top, \(C_{\text{in}}\) on the side)

\(C_{\text{in}}\)	AB
	00	01	11	10
0	0	0	1	0
1	0	1	1	1

4.3 Grouping and simplified expression

• Prime implicants: \(A\cdot B\), \(A\cdot C_{\text{in}}\), \(B\cdot C_{\text{in}}\)

\[ \boxed{C_{\text{out}} = (A\cdot B) + (A\cdot C_{\text{in}}) + (B\cdot C_{\text{in}})} \]

4.4 Verification using Boolean algebra

\[ \begin{aligned} C_{\text{out}} &= (A\cdot B) + C_{\text{in}}\cdot(A\oplus B)\\ &= (A\cdot B) + C_{\text{in}}\cdot\bigl[(A\cdot\overline{B})+(\overline{A}\cdot B)\bigr]\\ &= (A\cdot B) + (A\cdot C_{\text{in}}\cdot\overline{B}) + (B\cdot C_{\text{in}}\cdot\overline{A})\\ &= (A\cdot B) + (A\cdot C_{\text{in}}) + (B\cdot C_{\text{in}}) \qquad(\text{since }X\cdot\overline{X}=0) \end{aligned} \]

---

5. Sequential Extension – Flip‑Flops and a 1‑Bit Register

5.1 SR Flip‑Flop

Symbol	Characteristic equation
	\(Q_{\text{next}} = S + \overline{R}\cdot Q\)

5.2 JK Flip‑Flop

Symbol	Characteristic equation
	\(Q_{\text{next}} = J\cdot\overline{Q} + \overline{K}\cdot Q\)

5.3 1‑Bit Register (store the result of a half‑adder)

Connect the Sum output of a half‑adder to the data input of a JK flip‑flop (J = K = Sum). Clock the flip‑flop each time a new addition is performed. The register holds the Sum until the next clock pulse.

5.4 Propagation delay in sequential circuits

• Combinational part (adder) – as calculated above.
• Flip‑flop – typical clock‑to‑Q delay of 1 gate‑delay (depends on technology).
• Overall delay = combinational delay + flip‑flop delay.

---

6. Algorithmic View (AO2) – Pseudocode & Flowchart for a Full‑Adder

6.1 Pseudocode

READ A, B, Cin                // three input bits
S  ← A XOR B XOR Cin          // Sum
C1 ← A AND B                  // first carry term
C2 ← Cin AND (A XOR B)        // second carry term
Cout ← C1 OR C2               // Carry‑out
OUTPUT S, Cout

Complexity comment: All operations are elementary Boolean gates; the algorithm runs in constant time \(O(1)\) – a requirement for AO2.

6.2 Flowchart

---

7. Linking to Abstract Data Types (ADT) – Building a Multi‑Bit Ripple‑Carry Adder

• ADT used: an array of bits to store the operands and the result.
• Each array element corresponds to a bit position; the full‑adder circuit is instantiated for each position.
• Algorithm (high‑level):
  1. Load the two operand arrays \(A[0..n-1]\) and \(B[0..n-1]\).
  2. Set Cin ← 0.
  3. For i = 0 to n‑1:
     • Compute (S[i], Cout) ← FullAdder(A[i], B[i], Cin).
     • Store S[i] in the result array.
     • Set Cin ← Cout.
  4. Result array S[0..n‑1] holds the sum; Cin after the loop is the final carry‑out.

This demonstrates how a hardware design (full‑adder) maps onto a software‑oriented ADT (array) – a useful bridge for exam questions that ask you to “describe how a 4‑bit adder could be built using the half‑adder and full‑adder blocks”.

---

8. Practice K‑Map Exercise

Problem: Simplify the Boolean function \(F(A,B,C) = \overline{A}B C + A\overline{B}C + A B\overline{C} + A B C\).

Solution steps (students should follow):

1. Write the truth table for the minterms (1 = \(\overline{A}BC\), 2 = \(A\overline{B}C\), 3 = \(AB\overline{C}\), 4 = \(ABC\)).
2. Plot the 1’s on a 3‑variable K‑map (A on the left, BC on the top).
3. Form the largest possible groups (a 4‑group covering minterms 2,3,4, and a 2‑group covering minterms 1 and 2).
4. Write the simplified expression: \(F = AC + AB\).

Students should verify the result by Boolean algebra.

---

9. Summary of Key Points for the Cambridge 9618 Exam

• Know the symbols, Boolean expressions, and truth tables for the six basic gates.
• Be able to construct and interpret truth tables for half‑adders and full‑adders.
• Translate Boolean expressions into gate‑level diagrams; be comfortable with NAND‑only implementations.
• Understand propagation delay and be able to count gates for a given circuit.
• Use Karnaugh maps to simplify carry‑out (or any Boolean function) and justify the simplification algebraically.
• Recognise SR and JK flip‑flops, draw their symbols, and write their characteristic equations.
• Write clear pseudocode/flowcharts for the adder logic – demonstrate constant‑time complexity.
• Link hardware designs to software concepts (arrays as ADTs) when describing multi‑bit adders.

---

References (Cambridge AS & A‑Level Computer Science 9618)

• Section 15.2 – Boolean Algebra and Logic Circuits.
• Section 15.3 – Sequential Logic (flip‑flops, registers).
• Section 19.1 – Algorithms (pseudocode, flowcharts, efficiency).
• Section 10.4 – Abstract Data Types (arrays, stacks, queues).