Unit 2: Boolean Algebra and Logic gates

Digital electronics rests on two-valued (binary) logic, formalised by George Boole (1854) and applied to switching circuits by Claude Shannon (1938). Every circuit in this unit manipulates variables that take only the values 0 (LOW, false) and 1 (HIGH, true).

• Binary variable: A quantity taking exactly one of two values, 0 or 1; e.g. a switch that is open (0) or closed (1).
• Logic function: A mapping from n binary inputs to a binary output, fully described by a truth table of 2ⁿ rows.
• Positive logic convention: The higher voltage represents 1 and the lower voltage represents 0; used throughout unless stated otherwise.
• Completeness: {AND, OR, NOT} is a functionally complete set; so are {NAND} alone and {NOR} alone.
• Duality principle: Any valid Boolean identity remains valid if AND↔OR and 0↔1 are interchanged simultaneously.

II. Logic Gates — the physical primitives of Boolean operations

A logic gate is an electronic circuit that produces one output determined by the Boolean operation on its inputs.

A. Basic gates

• AND: Output is 1 only when all inputs are 1; Y = A·B. Series switches.
• OR: Output is 1 when any input is 1; Y = A + B. Parallel switches.
• NOT (inverter): Output is the complement of the input; Y = A′. Single input.

B. Universal gates

• NAND: Y = (A·B)′; AND followed by inversion. Output 0 only when all inputs 1.
• NOR: Y = (A+B)′; OR followed by inversion. Output 1 only when all inputs 0.
• Universality: Any function can be built from NAND alone or NOR alone, minimising IC types on a board.

C. Exclusive gates

• XOR: Y = A⊕B = A′B + AB′; output 1 when inputs differ. Basis of half-adder sum.
• XNOR: Y = (A⊕B)′= AB + A′B′; output 1 when inputs agree. Acts as equality comparator.

III. Truth Table — the exhaustive behavioural specification

A truth table lists the output for every possible input combination, making it the unambiguous definition of a function.

A. Construction and reading

• Row count: n inputs give 2ⁿ rows; a 3-variable function needs 8 rows.
• Ordering: Inputs written in binary count order (000, 001, …) so each row has a decimal index.
• Minterm/maxterm tagging: Rows where output = 1 mark minterms; rows where output = 0 mark maxterms.

Example for Y = A⊕B:

A B | Y
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

IV. Boolean Algebra — the laws for manipulating logic expressions

Boolean algebra provides the axioms and theorems that let one expression be transformed into an equivalent, often simpler, one.

A. Postulates and basic laws

• 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.
• Commutative / Associative / Distributive: e.g. A(B+C) = AB + AC.

B. Absorption and consensus theorems

• Absorption: A + AB = A; the redundant term AB is swallowed.
• Second absorption: A + A′B = A + B.
• Consensus: AB + A′C + BC = AB + A′C; the term BC is redundant.

C. DeMorgan's theorems

• First: (A·B)′ = A′ + B′.
• Second: (A+B)′ = A′·B′.
• Use: Convert AND-based expressions to OR-based ones and enable all-NAND or all-NOR realisation.

V. Canonical and Standard form Representation

A function can be written so that either every term contains every variable (canonical) or terms may contain fewer (standard).

A. Canonical forms

• Sum of minterms (SOP): OR of minterms where output = 1; each minterm has all variables. Written F = Σm(1,3,5).
• Product of maxterms (POS): AND of maxterms where output = 0; each maxterm has all variables. Written F = ΠM(0,2,4,6,7).
• Minterm form: literal true → variable, literal false → complement; e.g. row 101 → AB′C.
• Maxterm form: the complement rule; e.g. row 101 → (A′+B+C′).

B. Standard forms

• Standard SOP: Sum of product terms not required to be full minterms; e.g. F = AB + C.
• Standard POS: Product of sum terms not required to be full maxterms; e.g. F = (A+B)(C).
• Conversion: Expand a standard term to canonical by multiplying by (x + x′) for each missing variable x.

VI. SOP and POS Simplification

Simplification reduces literal and gate count while preserving the truth table, lowering cost and propagation delay.

1. SOP simplification: Combine product terms differing in one variable using XY + XY′ = X; target a two-level AND–OR network.
2. POS simplification: Combine sum terms differing in one variable using (X+Y)(X+Y′) = X; target a two-level OR–AND network.

• Algebraic route: Apply absorption, consensus and DeMorgan repeatedly; e.g. AB + AB′ + A′C = A + A′C = A + C.
• Relationship: SOP and POS of the same function are duals; the minterm set and maxterm set are complementary index sets.

VII. Implementation of Boolean Functions

A simplified expression is mapped to hardware using available gate types.

A. Two-level implementation

• AND–OR: Direct realisation of SOP; product terms formed by AND gates feed one OR gate.
• OR–AND: Direct realisation of POS; sum terms formed by OR gates feed one AND gate.

B. Universal-gate implementation

• NAND–NAND: An SOP expression maps directly to two NAND levels — apply DeMorgan so AB + CD = ((AB)′(CD)′)′.
• NOR–NOR: A POS expression maps directly to two NOR levels by the dual argument.
• Advantage: Uniform gate type simplifies fabrication and inventory.

Example — implement F = AB + C:

Level 1: N1 = (AB)′ , N2 = (C)′
Level 2: F  = (N1 · N2)′ = AB + C   (all NAND)

VIII. K-Map — graphical minimisation by adjacency

The Karnaugh map is a grid arrangement of a truth table that makes adjacent minterms visually groupable, giving minimal SOP or POS directly.

A. Structure and Gray-code ordering

• Size: 2ⁿ cells; 2-var (4), 3-var (8), 4-var (16).
• Gray code: Row and column labels change one bit at a time (00, 01, 11, 10) so physically adjacent cells differ in one variable.
• Wrap-around: Left–right and top–bottom edges are adjacent; corners of a 4-variable map form a valid group.

B. Grouping rules

• Group size: Only powers of two — 1, 2, 4, 8 — may be circled.
• Larger is better: A group of 2ᵏ cells eliminates k variables; the largest legal groups give the fewest literals.
• Cover completely: Every 1 must lie in at least one group; overlap between groups is allowed to enlarge them.
• Prime implicant: A group that cannot be enlarged; an essential prime implicant is the only one covering some minterm.

C. Reading SOP and POS

• SOP: Group the 1s; a variable that stays constant across a group appears (true if 1, complemented if 0).
• POS: Group the 0s; read each group as a sum term using the complementary rule.

Example — F = Σm(0,1,2,3) on a 3-variable map: the four cells form one group of four with A constant at 0, giving F = A′.

IX. Don't Care — exploiting unspecified outputs

A don't-care condition is an input combination that never occurs or whose output is irrelevant, marked X (or d) in the truth table and K-map.

A. Origin and notation

• Cause: Invalid codes (e.g. BCD inputs 1010–1111) or outputs unused by later logic.
• Notation: F = Σm(1,3,7) + Σd(0,5), where the d set lists don't-care indices.

B. Use in minimisation

• Free choice: Each X may be treated as 1 or 0, whichever yields larger K-map groups.
• Rule: Include an X in a group only when it enlarges an existing group of 1s; never form a group made solely of Xs.
• Benefit: Fewer literals and gates than forcing every unspecified output to a fixed value.

C. Applications and limitations

• Applications: BCD-to-seven-segment decoders, code converters and sequential-circuit next-state logic all rely on don't-cares for economy.
• Limitation: A don't-care assigned as 1 still produces a definite hardware output for that input; if such a combination can occur unexpectedly, the resulting value must be safe for the system.