Boolean algebra and logic circuits

Boolean algebra is the algebra of two values, 0 and 1, with the operations AND (written \( xy \) or \( x \land y \)), OR (\( x + y \) or \( x \lor y \)) and NOT (\( \bar x \)). Its laws look like ordinary algebra with a few surprises. Both operations are commutative and associative, each distributes over the other, \( x + 0 = x \) and \( x \cdot 1 = x \), and \( x + \bar x = 1 \), \( x\bar x = 0 \). The surprises are idempotence \( x + x = x \), absorption \( x + xy = x \), and distributivity of OR over AND, \( x + yz = (x + y)(x + z) \), which fails for numbers. De Morgan's laws \( \overline{x + y} = \bar x\,\bar y \) and \( \overline{xy} = \bar x + \bar y \) complete the list.

Every Boolean function can be written in sum-of-products (disjunctive normal) form: for each row of the truth table where the function is 1, write the product (the minterm) that is 1 only in that row, and OR them together. So a function of \( n \) variables is determined by its truth table, and there are \( 2^{2^n} \) of them: \( 2^n \) rows, each with an output of 0 or 1. The example is the multiplexer \( pq + \bar p r \): it outputs \( q \) when \( p = 1 \) and \( r \) when \( p = 0 \).

Simplifying an expression means fewer gates. Minterms that differ in one variable merge: \( xy + x\bar y = x(y + \bar y) = x \). The consensus law \( xy + \bar x z + yz = xy + \bar x z \) removes a redundant term. For a handful of variables, a Karnaugh map arranges the truth table so that mergeable minterms sit next to each other; for more, algorithms such as Quine-McCluskey do the same systematically.

A logic circuit wires gates together, and arithmetic is built this way. A half adder adds two bits: the sum bit is \( x \oplus y \) (exclusive or) and the carry is \( xy \). A full adder also takes an incoming carry \( c \): sum \( x \oplus y \oplus c \) and carry \( xy + c(x \oplus y) \). Chaining \( n \) full adders adds two \( n \)-bit numbers, and NAND gates alone can build every one of these, because NOT, AND and OR can all be made from NAND.

Picture it: a truth table is a column of switches, one row per input combination. A sum-of-products circuit has one AND gate per lit row, each recognising its row, feeding a single OR gate that lights the output whenever any row matches.

Think it: to prove a Boolean identity you may either use the laws or check all \( 2^n \) rows; both are complete methods. Every law has a dual, obtained by swapping AND with OR and 0 with 1, and the dual of a true identity is true. That halves the list of laws to remember.