MODULE 13
Boolean Algebra
Use AND, OR, NOT, XOR, NAND, NOR, XNOR (or & | ! ^ ' symbols). Example: A AND B OR NOT C
Examples:
A XOR B · A NAND B · (A OR B) AND NOT C
Understanding Boolean Algebra
Boolean algebra is the mathematics of binary values (0/1, true/false) and the operations AND, OR, and NOT that combine them. It is the direct mathematical foundation of digital electronics: every logic gate, processor, and digital circuit is, underneath, a physical implementation of a boolean expression. Simplifying these expressions using boolean laws reduces real hardware cost and improves circuit speed.
Key Definitions & Formulas
- Boolean variable: a value that is either 0 (false) or 1 (true).
- AND (·): result is 1 only if both inputs are 1.
- OR (+): result is 1 if at least one input is 1.
- NOT (complement, x̄): flips 0 to 1 and 1 to 0.
- De Morgan's laws: (A·B)̄ = Ā+B̄, and (A+B)̄ = Ā·B̄.
- Sum of Products (SOP): a boolean expression written as OR'd together AND terms, directly derivable from a truth table.
Worked Example
Simplifying A·B + A·B̄ using the distributive law: factor out A to get A·(B + B̄), and since B + B̄ is always 1 (a tautology), the whole expression reduces to just A — a smaller circuit that computes the exact same result with fewer gates.
Where This Is Used
- Digital circuit design and simplification (fewer gates = cheaper, faster hardware).
- CPU and processor architecture design.
- Programming language boolean expression optimization by compilers.
- Search engine query logic (AND/OR/NOT search operators).