Unit 2: Boolean algebra and combinational circuits
Digital Circuits & Logic Design notes · PTU syllabus (BSIT204/BSBC303)
On this page
Unit summary
Boolean algebra simplifies logic, and combinational circuits perform arithmetic. This unit covers Boolean algebra theorems, SOP and POS forms, Karnaugh map simplification, half and full adders and subtractors, the parallel binary adder and the binary adder/subtractor.
After this unit you can
- Apply Boolean theorems
- Write expressions in SOP and POS forms
- Simplify expressions with K-maps
- Design adders and subtractors
PTU syllabus topics
- Boolean algebra theorems
- SOP and POS forms
- K-map simplification
- half/full adders and subtractors
- parallel binary adder
- binary adder/subtractor
De Morgan's theorems
(A + B)' = A'B' and (AB)' = A' + B'
Absorption
A + AB = A
Half adder
Sum = A ⊕ B, Carry = AB
Full adder
Sum = A ⊕ B ⊕ Cin, Cout = AB + Cin(A ⊕ B)
Topic 1
Boolean algebra theorems
Boolean algebra works on the values 0 and 1 with three operations: AND (·), OR (+) and NOT ('). Its laws let us reduce a long expression to a shorter equivalent one.
- Identity
- A + 0 = A ; A·1 = A
- Null
- A + 1 = 1 ; A·0 = 0
- Idempotent
- A + A = A ; A·A = A
- Complement
- A + A' = 1 ; A·A' = 0
- Absorption
- A + AB = A ; A(A + B) = A
- De Morgan
- (A + B)' = A'B' ; (AB)' = A' + B'
Example
Simplify Y = AB + AB'. Y = A(B + B') = A·1 = A.
Example
Simplify Y = A + A'B. Using A + A'B = (A + A')(A + B) = 1·(A + B), so Y = A + B.
Topic 2
SOP and POS forms
- Sum of Products (SOP): product terms ORed together, e.g. Y = AB + A'C. Each product term in which every variable appears is a minterm.
- Product of Sums (POS): sum terms ANDed together, e.g. Y = (A + B)(A' + C). Each full sum term is a maxterm.
- From a truth table, SOP is written from the rows where Y = 1; POS from the rows where Y = 0.
Example
If Y = 1 for rows 1, 2 and 3 of a 2-variable table (A'B, AB', AB), then Y = Σm(1, 2, 3) = A'B + AB' + AB, which simplifies to A + B.
SOP expressions are realised with an AND-OR circuit (or NAND-NAND); POS with an OR-AND circuit (or NOR-NOR).
Topic 3
Karnaugh map simplification
A K-map is a grid representation of a truth table in which adjacent cells differ by only one variable (Gray code order: 00, 01, 11, 10). Grouping adjacent 1s removes the variable that changes, giving the simplest SOP.
- 1
Draw the map
2ⁿ cells for n variables
- 2
Fill the 1s
From the minterms
- 3
Group the 1s
In 1, 2, 4, 8 … cells, as large as possible
- 4
Allow overlaps and wrap-around
Edges are adjacent
- 5
Write one term per group
Keep only variables that don't change
- 6
OR the terms together
Example
Y = Σm(0, 1, 2, 3) for two variables fills the whole map, so Y = 1. For three variables, Y = Σm(1, 3, 5, 7) forms a group of four where C = 1 throughout, so Y = C.
Exam tip
Groups must be rectangles of size 1, 2, 4 or 8. Always draw the map with Gray code labels and circle every group.
Topic 4
Half and full adders
A half adder adds two bits A and B and gives a Sum and a Carry.
- Sum = A ⊕ B, Carry = A·B
- It cannot add a carry coming in from a previous stage.
A full adder adds three bits: A, B and the carry-in Cin.
- Sum = A ⊕ B ⊕ Cin
- Cout = AB + Cin(A ⊕ B)
- A full adder can be built from two half adders and an OR gate.
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
(Partial table: the full table has 8 rows.)
Topic 5
Half and full subtractors
A half subtractor subtracts B from A: Difference = A ⊕ B, Borrow = A'B. A full subtractor also handles a borrow-in (Bin): Difference = A ⊕ B ⊕ Bin, Borrow = A'B + Bin(A ⊕ B)'.
Exam tip
Notice that Sum and Difference have the same expression; only the carry/borrow expressions differ. Examiners often ask you to compare them.
Topic 6
Parallel binary adder and binary adder/subtractor
A parallel binary adder adds two n-bit numbers using n full adders connected in a chain: each stage's carry-out feeds the next stage's carry-in (a ripple-carry adder). A 4-bit adder uses four full adders. A binary adder/subtractor uses XOR gates on the B inputs and a control line M:
- M = 0: XOR passes B unchanged and Cin = 0, so the circuit computes A + B.
- M = 1: XOR inverts B (1's complement) and Cin = 1 adds one, giving the 2's complement of B, so the circuit computes A − B.
Example
0101 (5) − 0011 (3): 2's complement of 0011 is 1101. 0101 + 1101 = 1 0010; discard the final carry, result 0010 = 2.
Key terms
- Boolean algebra
- Algebra of binary variables and logic operations
- Minterm
- Product term in which every variable appears once
- K-map
- Grid for simplifying Boolean expressions
- Full adder
- Circuit adding three bits
- Ripple carry
- Carry passed from one adder stage to the next
Quick revision
- Boolean laws and De Morgan's theorems.
- SOP (minterms), POS (maxterms); canonical forms.
- K-map grouping rules (1, 2, 4, 8 cells; wrap-around; don't cares).
- Half adder: S = A ⊕ B, C = AB; full adder; subtractors.
- 4-bit parallel adder; adder/subtractor with XOR gates.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State De Morgan's theorems.
- Q2.Distinguish SOP and POS.
- Q3.State the rules for grouping in a K-map.
- Q4.Write the sum and carry expressions of a half adder.
- Q5.How many half adders make a full adder?
- Q6.How does an adder/subtractor use XOR gates?
Long-answer questions
- Q1.Explain Boolean algebra theorems with proofs.
- Q2.Simplify a four-variable expression using a K-map (numerical).
- Q3.Design half and full adders and subtractors.
- Q4.Explain the parallel binary adder and the binary adder/subtractor.
Stuck on this unit?
Message SBS on WhatsApp for help with Digital Circuits & Logic Design, or to ask about studying B.Sc IT at Synetic.