Boolean Algebra and Logic Operations
Boolean logic is the mathematical foundation of all digital circuits. Every computation a computer performs ultimately reduces to operations on binary values — 0 (false) and 1 (true). George Boole formalized this algebra in 1854, and Claude Shannon later showed in 1937 that it maps directly onto electrical switching circuits.
Fundamental Operations
There are six core logic operations, each defined by a truth table:
| A | B | AND | OR | XOR | NAND | NOR | NOT A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
- AND (A · B): output is 1 only when both inputs are 1.
- OR (A + B): output is 1 when at least one input is 1.
- NOT (A̅ or ¬A): inverts the input.
- XOR (A ⊕ B): output is 1 when inputs differ (exclusive or).
- NAND: NOT of AND — outputs 0 only when both inputs are 1.
- NOR: NOT of OR — outputs 1 only when both inputs are 0.
De Morgan's Laws
These two laws allow you to convert between AND and OR expressions:
- ¬(A · B) = ¬A + ¬B — the complement of a product equals the sum of the complements.
- ¬(A + B) = ¬A · ¬B — the complement of a sum equals the product of the complements.
De Morgan's laws are essential for circuit simplification. They let you replace AND gates with OR gates (and vice versa) by pushing inversions through.
Boolean Algebra Identities
Key simplification rules include:
- Identity: A · 1 = A, A + 0 = A
- Null: A · 0 = 0, A + 1 = 1
- Idempotent: A · A = A, A + A = A
- Complement: A · ¬A = 0, A + ¬A = 1
- Absorption: A + (A · B) = A, A · (A + B) = A
- Distributive: A · (B + C) = (A · B) + (A · C)
Canonical Forms
Any Boolean function can be expressed in two standard forms:
- Sum of Products (SOP): OR of AND terms. Each AND term (minterm) corresponds to a row where the output is 1. Example: F = A̅B + AB̅ + AB
- Product of Sums (POS): AND of OR terms. Each OR term (maxterm) corresponds to a row where the output is 0. Example: F = (A + B)(A̅ + B̅)
SOP and POS forms are the starting point for gate-level circuit design — you read the truth table, write the canonical form, then simplify using Boolean algebra or Karnaugh maps.
Real-Life: Alarm System Logic
Consider a home alarm system with three sensors: Door (D), Window (W), and Motion (M). The alarm should trigger when:
- The door is opened AND motion is detected: D · M
- OR the window is opened: W
The Boolean expression is: Alarm = (D · M) + W
Using De Morgan's law, you could equivalently express the "no alarm" condition: ¬Alarm = ¬W · (¬D + ¬M) — the alarm stays silent when the window is closed AND (the door is closed OR there is no motion).
In hardware design, Boolean logic is used everywhere:
- CPU control units use Boolean equations to decide which datapath signals to activate for each instruction
- Error detection: parity bits use XOR — XOR all bits together and if the result is 1, an error occurred
- Address decoding: memory chips use AND/OR logic to determine if an address falls within their range
- Arithmetic: binary addition is built from XOR (sum bit) and AND (carry bit)