Chapter 1: Boolean Algebra
Introduction to Boolean Algebra
In the mid-nineteenth century, the English mathematician George Boole developed a system of logic that would later become the bedrock of modern digital computing. This system, known as Boolean algebra, is a mathematical framework for dealing with variables that can only hold one of two possible values: true or false. In the context of digital electronics, these values are represented by binary digits, or bits, 1 (representing a high voltage level) and 0 (representing a low voltage level).
Boolean algebra provides the rules and theorems necessary to analyze and simplify digital logic circuits. By representing the behavior of logic gates and circuits with mathematical expressions, engineers and designers can optimize circuit design, reduce complexity, and minimize cost. This chapter introduces the fundamental concepts, operations, laws, and simplification techniques of Boolean algebra, which are essential for understanding the design and operation of all digital systems.
Fundamental Operations
At the heart of Boolean algebra are three fundamental operations: NOT, AND, and OR. These operations are the elementary building blocks of all digital logic. Each operation is performed by an electronic circuit called a logic gate.
The NOT Operation (Inversion)
The NOT operation is the simplest, operating on a single variable to invert its value. If the input is 0, the output is 1, and vice-versa. This is also known as inversion or complementation.
- Symbolic Representation: The NOT of a variable A is written as A (read as “A bar”).
- Logic Gate: The circuit performing this is an Inverter or NOT gate.
| Input (A) | Output (A) |
|---|---|
| 0 | 1 |
| 1 | 0 |
The AND Operation
The AND operation combines two or more variables. The output is 1 only if all inputs are 1. If any input is 0, the output is 0.
- Symbolic Representation: A AND B is written as
A · Bor simplyAB.
| A | B | A · B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The OR Operation
The OR operation also combines variables. The output is 1 if at least one of its inputs is 1. The output is 0 only when all inputs are 0.
- Symbolic Representation: A OR B is written as
A + B.
| A | B | A + B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Derived and Universal Gates
While AND, OR, and NOT are fundamental, we can combine them to create other useful gates. The NAND and NOR gates are particularly special because they are “universal”—any Boolean function can be implemented using only NAND gates or only NOR gates. The XOR and XNOR gates are also common, serving crucial roles in arithmetic and comparison circuits.
The NAND Gate (NOT-AND)
The NAND gate produces the opposite output of an AND gate. The output is 0 only when all inputs are 1.
- Symbolic Representation:
A · B
| A | B | A · B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The NOR Gate (NOT-OR)
The NOR gate produces the opposite output of an OR gate. The output is 1 only when all inputs are 0.
- Symbolic Representation:
A + B
| A | B | A + B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
The XOR Gate (Exclusive-OR)
The Exclusive-OR gate produces a 1 only when its inputs are different. It is widely used in circuits that perform arithmetic operations, such as adders and parity checkers.
- Symbolic Representation:
A ⊕ B, which is equivalent toAB + AB.
| A | B | A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The XNOR Gate (Exclusive-NOR)
The Exclusive-NOR gate is the complement of the XOR gate. It produces a 1 only when its inputs are the same, making it a useful “equality detector.”
- Symbolic Representation:
A ⊕ B, which is equivalent toAB + AB.
| A | B | A ⊕ B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Boolean Expressions and Functions
A Boolean expression is formed by combining Boolean variables with the logical operations. A Boolean function is an expression that specifies the relationship between a set of input variables and one or more output variables. The value of the function can be determined by substituting the input values and evaluating using the order of operations (precedence): Parentheses, then NOT, then AND, then OR.
Example: Evaluate the function F(A, B, C) = A + BC for A=1, B=0, C=1.
- NOT: Evaluate B. Since B=0, B=1.
- AND: Evaluate BC. This becomes 1 · 1 = 1.
- OR: Evaluate A + (BC). This becomes 1 + 1 = 1.
- Therefore, F(1, 0, 1) = 1.
Laws and Theorems of Boolean Algebra
To manipulate and simplify expressions, we use a set of established laws and theorems. These are fundamental for circuit optimization.
Basic Postulates and Properties
| Law/Theorem | AND Form | OR Form |
|---|---|---|
| Identity Law | A · 1 = A | A + 0 = A |
| Null Law | A · 0 = 0 | A + 1 = 1 |
| Idempotent Law | A · A = A | A + A = A |
| Complement Law | A · A = 0 | A + A = 1 |
| Commutative Law | AB = BA | A + B = B + A |
| Associative Law | (AB)C = A(BC) | (A + B) + C = A + (B + C) |
| Distributive Law | A(B + C) = AB + AC | A + BC = (A + B)(A + C) |
| Absorption Law | A(A + B) = A | A + AB = A |
| De Morgan’s Theorem | AB = A + B | A+B = AB |
| Involution Law | A = A | |
Duality Principle
The duality principle is a powerful concept stating that if a Boolean expression is valid, its dual is also valid. The dual is found by interchanging AND and OR operations, and interchanging 0s and 1s.
De Morgan’s Theorems
De Morgan’s theorems are critical for simplifying expressions involving inverted terms. They show how to distribute a NOT operation across AND or OR operations.
Simplification of Boolean Functions
Simplifying Boolean expressions is a crucial step in digital logic design. A simpler expression leads to a circuit with fewer logic gates, which reduces cost, power consumption, and propagation delay.
Algebraic Manipulation
Example: Simplify F = AB + A(B+C) + B(B+C)
- Distributive Law: F = AB + AB + AC + BB + BC
- Idempotent Law (BB=B): F = AB + AB + AC + B + BC
- Factor out A: F = A(B + B) + AC + B + BC
- Complement Law (B+B=1): F = A(1) + AC + B + BC
- Identity Law (A · 1 = A): F = A + AC + B + BC
- Absorption Law (A+AC=A and B+BC=B): F = A + B
The simplified expression F = A + B is logically equivalent to the original.
Standard and Canonical Forms
To standardize functions for easier comparison and implementation, we use standard forms. A minterm is a product (AND) term containing every variable of a function, either in its true or complemented form. A maxterm is a sum (OR) term containing every variable. These lead to the two canonical forms:
- Canonical Sum of Products (SOP): The function is expressed as a sum (OR) of its minterms. This form is derived from the rows of the truth table where the function output is
1. - Canonical Product of Sums (POS): The function is expressed as a product (AND) of its maxterms. This form is derived from the rows of the truth table where the function output is
0.
Karnaugh Maps (K-maps)
While algebraic manipulation is powerful, the Karnaugh map (K-map) offers a graphical method to simplify expressions. It provides a systematic, visual way to group terms and eliminate redundant variables, which we will explore in a later chapter.
Practice Problems
Test your understanding by simplifying the following Boolean expressions.
Question 1: Simplify the expression F = XY + X(Y + Z) + Y(Y + Z)
Solution:
F = XY + XY + XZ + YY + YZ(Distributive Law)F = XY + XZ + Y + YZ(Idempotent Law: XY+XY=XY and YY=Y)F = XY + XZ + Y(Absorption Law: Y+YZ=Y)F = Y + XZ(Absorption Law: Y+XY=Y)- Final Answer:
F = Y + XZ
Question 2: Use De Morgan’s theorem to simplify F = (A + B + C)D
Solution:
- Let X = A + B + C. The expression is XD.
F = X + D(De Morgan’s Law)- Substitute X back:
F = A + B + C + D - Apply De Morgan’s Law again:
F = (ABC) + D - Final Answer:
F = ABC + D
Question 3: Prove that A + AB = A + B.
Solution:
- Start with the expression:
A + AB - Apply Distributive Law (A + BC = (A+B)(A+C)):
(A + A)(A + B) - Apply Complement Law (A + A = 1):
1 · (A + B) - Apply Identity Law (1 · X = X):
A + B - Final Answer: The expression is proven.
A + AB = A + B
Conclusion
Boolean algebra is the mathematical foundation of digital logic. A thorough understanding of its operations, laws, and simplification techniques is indispensable for any student or practitioner of digital electronics. The principles covered in this chapter will be applied throughout the remainder of this text to analyze, design, and optimize digital circuits of all kinds.