Boolean algebra and De Morgan’s laws

Learning goals

• Simplify a circuit using Boolean algebra.
• Verify De Morgan’s laws with a truth table.

An identity must hold for every input.

The identities are a & 1 = a, a | 0 = a, a & 0 = 0 and a | 1 = 1. Repeating an input gives a & a = a and a | a = a. In contrast, a ^ a = 0.

a | (a & b) simplifies to a. If a is 1, the result is 1; if a is 0, both terms are 0. Reasoning by cases explains the identity without memorization.

Moving an inversion changes the operation.

De Morgan’s laws state ~(a & b) = (~a | ~b) and ~(a | b) = (~a & ~b). Moving NOT inside the parentheses exchanges AND and OR.

These rules apply to bitwise operations of matching width. NAND has the same 0/1 truth table as OR with both inputs inverted. Gate count alone does not determine physical area or speed.