Chapter 2: Boolean Algebra and Logic Gates
Introduction to Boolean Algebra
Boolean algebra is the mathematical foundation of digital logic. Unlike the algebra you learned in high school, which deals with continuous variables and numbers, Boolean algebra deals with discrete variables that take only two values: 0 (false) and 1 (true). Every digital circuit can be described, analyzed, and optimized using Boolean algebra, making it indispensable for digital engineers.
1. Fundamental Boolean Operations
The AND Operation
The AND operation produces a 1 output only when all inputs are 1. Truth table: 0 AND 0 = 0, 0 AND 1 = 0, 1 AND 0 = 0, 1 AND 1 = 1. In Boolean notation, we use a dot (·) or sometimes no symbol at all: A · B or AB.
The OR Operation
The OR operation produces a 1 output when any input is 1. Truth table: 0 OR 0 = 0, 0 OR 1 = 1, 1 OR 0 = 1, 1 OR 1 = 1. In Boolean notation, we use a plus sign (+): A + B.
The NOT Operation
The NOT operation (inversion) produces the opposite output. Truth table: NOT 0 = 1, NOT 1 = 0. In Boolean notation, we use an overbar or apostrophe: A' or Ā.
2. Basic Boolean Laws
Identity Laws
A + 0 = A (OR-ing with 0 gives A), A · 1 = A (AND-ing with 1 gives A), A + A = A (OR-ing with itself is A), A · A = A (AND-ing with itself is A).
Null (Domination) Laws
A + 1 = 1 (OR-ing with 1 always gives 1), A · 0 = 0 (AND-ing with 0 always gives 0).
Idempotent Laws
These are sometimes called "special cases" of identity: A · A = A, A + A = A. The result is always the variable itself.
Involution Law (Double Negation)
(A')' = A. Inverting twice brings you back to the original.
Commutative Laws
Order doesn't matter: A + B = B + A, A · B = B · A. Whether you OR or AND variables in different orders, the result is the same.
Associative Laws
Grouping doesn't matter: (A + B) + C = A + (B + C), (A · B) · C = A · (B · C). The result is the same regardless of which operations you perform first.
Distributive Laws
A · (B + C) = AB + AC (AND distributes over OR), A + BC = (A + B)(A + C) (OR distributes over AND). These are essential for both simplifying and expanding Boolean expressions.
De Morgan's Laws
(A + B)' = A' · B' (NOT of OR equals AND of NOTs), (A · B)' = A' + B' (NOT of AND equals OR of NOTs). These laws are critically important for simplifying expressions with multiple levels of negation.
Absorption Laws
A + AB = A, A(A + B) = A. A variable "absorbs" redundant terms that include it.
Consensus Theorem
AB + A'C + BC = AB + A'C. The consensus term BC is redundant and can be removed.
3. Logic Gates
AND Gate
Implements the AND operation. Multiple inputs, one output. Output is 1 only when all inputs are 1. Symbol: a flat-top curved shape.
OR Gate
Implements the OR operation. Multiple inputs, one output. Output is 1 when any input is 1. Symbol: a pointy curved shape.
NOT Gate (Inverter)
Implements the NOT operation. Always has one input and one output. Produces the opposite of its input. Symbol: a triangle with a small circle at the output.
NAND Gate
Implements NOT-AND (A · B)'. This is actually more commonly used than AND in real circuits because it's easier to implement with certain technologies. NAND is a universal gate—you can build any digital circuit using only NAND gates.
NOR Gate
Implements NOT-OR (A + B)'. Like NAND, NOR is universal and can implement any Boolean function. NOR is particularly common in certain technologies.
XOR Gate (Exclusive OR)
Output is 1 when inputs are different. Truth table: 0 XOR 0 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, 1 XOR 1 = 0. Boolean expression: A · B' + A' · B (or A ⊕ B).
XNOR Gate (Exclusive NOR)
Output is 1 when inputs are the same. It's the complement of XOR. Boolean expression: (A ⊕ B)' = AB + A'B'.
4. Truth Tables
Creating Truth Tables
A truth table systematically shows the output for every possible combination of inputs. For n inputs, you need 2^n rows. For a 3-input system (8 combinations), list inputs from 000 to 111, and for each combination, apply the logic operation to determine the output.
Using Truth Tables for Analysis
Truth tables help verify that a circuit or Boolean expression works as intended. They're also useful for converting between different representations of logic functions.
5. Minterms and Maxterms
Understanding Minterms
A minterm is a product (AND) of all variables, in either normal or complemented form, that produces output 1 for exactly one input combination. For a 3-variable function, minterm m5 (written as A'BC) corresponds to input combination 101 (where A=1, B=0, C=1 in the standard labeling, or listed as 101 in order).
Sum of Minterms (SOP) Form
Any Boolean function can be expressed as a sum of minterms. From a truth table, identify all rows with output 1, convert each to its minterm, and OR them together. This is called canonical sum-of-products (SOP) form and is unique for each function.
Understanding Maxterms
A maxterm is a sum (OR) of all variables in either normal or complemented form that produces output 0 for exactly one input combination. Maxterm M0 for a 3-variable function is (A+B+C), which is 0 only when all inputs are 0.
Product of Maxterms (POS) Form
Any Boolean function can be expressed as a product of maxterms. From a truth table, identify all rows with output 0, convert each to its maxterm, and AND them together. This is canonical product-of-sums (POS) form.
Relationship Between SOP and POS
A function in SOP form lists which input combinations give 1. A function in POS form lists which combinations give 0 (and implicitly, all others give 1). These are complementary representations of the same function.
6. Boolean Expression Simplification
Algebraic Simplification
Using Boolean laws and theorems, you can simplify complex expressions. Look for patterns: complement pairs (A + A' = 1, AA' = 0), absorption, consensus, etc. Simplification reduces the number of gates needed, saving cost and power.
Practical Example
Simplify: A'BC + ABC + AB'C + ABC'. Start with common factors: BC(A' + A) + AC(B' + B) = BC + AC. This uses the identity A + A' = 1. Further: C(B + A). With three variables and various operations, this simplifies to just two gates instead of requiring multiple AND and OR gates.
Conclusion
Boolean algebra is the language of digital design. Master the fundamental operations, laws, and gate types, and you can analyze and design any combinational digital circuit. Truth tables, minterms, and maxterms give you systematic ways to convert between different representations. And simplification techniques help you create efficient circuits. These tools form the foundation for everything else you'll learn in digital logic design.