Show understanding of Boolean algebra

15.2 Boolean Algebra and Logic Circuits

Learning Objective

Demonstrate a clear understanding of Boolean algebra – its laws, identities and simplification techniques – and apply this knowledge to design and analyse both combinational and sequential logic circuits as required by the Cambridge AS & A‑Level Computer Science syllabus.

---

1. Basic Concepts

• Binary values: 0 = FALSE (LOW), 1 = TRUE (HIGH)
• Variables: usually capital letters $A$, $B$, $C$, …
• Fundamental operators (standard notation):
  • AND $X\cdot Y$ or $XY$
  • OR $X+Y$
  • NOT $\overline{X}$

2. Fundamental Laws and Identities of Boolean Algebra

Law	Expression
Identity	$X+0 = X\qquad X\cdot1 = X$
Null	$X+1 = 1\qquad X\cdot0 = 0$
Idempotent	$X+X = X\qquad X\cdot X = X$
Complement	$X+\overline{X}=1\qquad X\cdot\overline{X}=0$
Commutative	$X+Y = Y+X\qquad X\cdot Y = Y\cdot X$
Associative	$(X+Y)+Z = X+(Y+Z)$ $(X\cdot Y)\cdot Z = X\cdot(Y\cdot Z)$
Distributive	$X\cdot(Y+Z)=X\cdot Y+X\cdot Z$ $X+(Y\cdot Z)=(X+Y)\cdot (X+Z)$
De Morgan	$\overline{X+Y}= \overline{X}\cdot\overline{Y}$ $\overline{X\cdot Y}= \overline{X}+ \overline{Y}$

3. Frequently Used Identities

• Absorption $X+X\cdot Y = X\qquad X\cdot (X+Y)=X$
• Consensus $X\cdot Y+\overline{X}\cdot Z+Y\cdot Z = X\cdot Y+\overline{X}\cdot Z$
• Double‑negation $\overline{\overline{X}} = X$
• Redundancy $X+X\cdot\overline{Y}=X$ (and its dual)

4. Canonical Forms

4.1 Sum‑of‑Products (SOP)

A logical OR of one or more AND terms (minterms). Each minterm contains every variable either in true or complemented form.

Obtaining SOP from a truth table:

1. Identify the rows where the function $F$ = 1.
2. Write the corresponding minterm for each such row (e.g. for $A=0,B=1,C=0$ the minterm is $\overline{A}B\overline{C}$).
3. OR all the minterms together.

4.2 Product‑of‑Sums (POS)

A logical AND of one or more OR terms (maxterms). Each maxterm contains every variable either in true or complemented form.

Obtaining POS from a truth table:

1. Identify the rows where $F$ = 0.
2. Write the corresponding maxterm for each such row (e.g. for $A=0,B=1,C=0$ the maxterm is $(A+\overline{B}+C)$).
3. AND all the maxterms together.

Example – Converting POS to SOP

Given $F = (A+\overline{C})(\overline{B}+D)$

1. Expand using distributive law: $F = A\overline{B}+AD+\overline{C}\,\overline{B}+\overline{C}D$.
2. Group terms if possible (here no further reduction). The SOP form is
   $F = A\overline{B}+AD+\overline{B}\,\overline{C}+\overline{C}D$.

5. Simplification Techniques

5.1 Algebraic Manipulation (step‑by‑step)

Example – Simplify $G = A\overline{B}+AB+\overline{A}\,\overline{B}$

1.  $G = A\overline{B}+AB+\overline{A}\,\overline{B}$                     (original)
2.  $= A(\overline{B}+B)+\overline{A}\,\overline{B}$                     (factor A)
3.  $= A\cdot1+\overline{A}\,\overline{B}$                               (complement law)
4.  $= A+\overline{A}\,\overline{B}$                                    (identity)
5.  $= (A+\overline{A})(A+\overline{B})$                               (distributive)
6.  $= 1\cdot(A+\overline{B})$                                          (complement)
7.  $= A+\overline{B}$                                                  (identity)

The minimal SOP is $G = A+\overline{B}$.

5.2 Karnaugh‑Map (K‑map) Minimisation

• Visual grouping of adjacent 1’s (for SOP) or 0’s (for POS).
• Groups must contain $2^n$ cells (1, 2, 4, 8 …).
• Groups may wrap around the edges.
• Each 1 (or 0) must be covered by at least one group; overlapping is allowed if it reduces literals.

5.3 Hybrid Approach

Use algebraic identities to reduce the expression before drawing a K‑map, or use a K‑map to spot patterns that suggest a convenient algebraic manipulation.

6. Karnaugh Maps – Construction & Rules

6.1 General Construction

A K‑map is a rectangular array whose cells represent minterms (SOP) or maxterms (POS). Variable ordering follows Gray code so that adjacent cells differ in only one variable.

4‑variable K‑map layout (variables $AB$ on rows, $CD$ on columns)

	CD
AB	00	01	11	10
00	m0	m1	m3	m2
01	m4	m5	m7	m6
11	m12	m13	m15	m14
10	m8	m9	m11	m10

6.2 Example 1 – 4‑Variable Function

Minimise $F(A,B,C,D)=\displaystyle\sum m(0,2,5,7,8,10,13,15)$

1. Place 1’s in the cells $m0,m2,m5,m7,m8,m10,m13,m15$.
2. Form the largest possible groups:
   • Group 1: $m0,m2,m8,m10$ → $\overline{A}\,\overline{C}$
   • Group 2: $m5,m7,m13,m15$ → $B\,D$
3. Minimal SOP: $\displaystyle F = \overline{A}\,\overline{C}+B\,D$.
4. POS (grouping the 0’s) gives $\displaystyle F = (A+C)\,(\overline{B}+\overline{D})$.

6.3 Example 2 – 3‑Variable K‑map with Wrapping & Don’t‑Care

Function $H(A,B,C)=\displaystyle\sum m(1,2,5,6)$, with don’t‑care cells at $m0$ and $m7$.

3‑variable K‑map (AB rows, C columns)

AB \ C	0	1
00	d	1
01	1	d
11	1	1
10	0	0

• Group A (four 1’s wrapping vertically): $m1,m5,m7,m3$ → $\overline{A}C$ (uses don’t‑care $m7$).
• Group B (pair $m2,m6$): $AB$.

Minimal SOP: $\displaystyle H = \overline{A}C + AB$.

7. Designing Combinational Circuits

7.1 Half‑Adder

Inputs	Sum $S$	Carry $C$
$A$, $B$	$S = A\oplus B = A\overline{B}+\overline{A}B$	$C = A\cdot B$

Both expressions are already minimal (verified with 2‑variable K‑maps). The circuit uses one XOR gate (or two AND/OR/NOT gates) for $S$ and one AND gate for $C$.

7.2 Full‑Adder

Inputs	Sum $S$	Carry‑out $C_{out}$
$A$, $B$, $C_{in}$	$S = A\oplus B\oplus C_{in}$	$C_{out}=AB+AC_{in}+BC_{in}$

K‑map minimisation of $C_{out}$ yields the expression shown. The sum can be built from two half‑adders (cascade) plus an OR gate for the final carry.

7.3 Ripple‑Carry Adder (4‑bit)

A cascade of four full‑adders. Each stage $i$ (starting at $i=0$) receives $A_i$, $B_i$ and the carry from the previous stage $C_i$.

C0  →  FA0  →  S0
C1  →  FA1  →  S1
C2  →  FA2  →  S2
C3  →  FA3  →  S3
C4  (final carry‑out)

Diagram (simplified):

The overall SOP for each sum bit is the same as a single full‑adder; the total propagation delay is the sum of the delays of the four stages.

7.4 Multiplexer (2‑to‑1)

Truth table yields $Y = \overline{S}\,D_0 + S\,D_1$ – a classic SOP. Implementation: two 2‑input AND gates, one inverter for $\overline{S}$, and a 2‑input OR gate.

7.5 Decoder (2‑to‑4)

Outputs are the four minterms of the select lines:

• $O_0 = \overline{A}\,\overline{B}$
• $O_1 = \overline{A}\,B$
• $O_2 = A\,\overline{B}$
• $O_3 = A\,B$

Each output is realised with a single 2‑input AND gate; the decoder illustrates the direct mapping from SOP form to hardware.

8. Sequential Logic – Flip‑Flops

Boolean algebra is used to derive the characteristic equations of simple storage elements.

• SR latch (cross‑coupled NOR):
  $Q_{next}=S+\overline{R}\,Q$ (derived by applying the NOR truth table and simplifying with De Morgan).
• JK flip‑flop (edge‑triggered):
  $Q_{next}=J\overline{Q}+ \overline{K}Q$.
• D flip‑flop:
  $Q_{next}=D$ (transparent when clocked). It can be built from a JK flip‑flop by tying $J=D$ and $K=\overline{D}$, demonstrating the use of Boolean identities.

These equations are usually minimised to a small number of NAND or NOR gates, showing the practical value of De Morgan’s theorem for implementing sequential circuits with universal gates.

9. Translating Boolean Expressions to Logic‑Gate Diagrams

Standard gate symbols:

• AND – $\cdot$ (symbol: ∧)
• OR – $+$ (symbol: ∨)
• NOT – $\overline{\phantom{X}}$ (symbol: inverter)
• NAND, NOR, XOR, XNOR – derived using De Morgan’s theorem or truth tables.

Example – Circuit for $F = \overline{A}B + A(C + B)$

1. Invert $A$ → $\overline{A}$.
2. AND $\overline{A}$ with $B$ → term 1.
3. OR $C$ and $B$ → $C+B$.
4. AND the result with $A$ → term 2.
5. OR term 1 and term 2 → $F$.

10. Truth‑Table Construction (Worked Example)

A	B	C	$\overline{A}$	$\overline{A}B$	$C+B$	$A(C+B)$	F
0	0	0	1	0	0	0	0
0	0	1	1	0	1	0	0
0	1	0	1	1	1	0	1
0	1	1	1	1	1	0	1
1	0	0	0	0	0	0	0
1	0	1	0	0	1	1	1
1	1	0	0	0	1	1	1
1	1	1	0	0	1	1	1

11. Practice Questions

1. Simplify using Boolean algebra: $G = A\overline{B} + AB + \overline{A}\,\overline{B}$.
2. Construct a Karnaugh map for $H(A,B,C)=\displaystyle\sum m(1,2,5,6,7)$. Write the minimal SOP expression and draw the corresponding gate diagram.
3. Design a half‑adder and a full‑adder from scratch:
   • Start with a truth table.
   • Derive SOP forms (use K‑maps where helpful).
   • Produce the gate‑level schematic.
4. For the SR latch, derive the characteristic equation $Q_{next}=S+\overline{R}\,Q$ using Boolean identities and verify it with a truth table.
5. Given the POS expression $F = (A + \overline{C})(\overline{B}+D)$, convert it to SOP form and implement the circuit using only NAND gates.
6. Using the 4‑variable K‑map technique, minimise the function $P(A,B,C,D)=\displaystyle\sum m(3,4,6,9,11,12,14)$. State the minimal SOP and POS forms.
7. Design a 4‑bit ripple‑carry adder. Show the interconnection of the four full‑adders and indicate the overall propagation delay in terms of the delay of a single full‑adder.