Text Book: M. Morris Mano, Digital Design, 5th Edition
Additional Readings: Lectures, slides, tutorials
Course Outline - Week 2: Boolean Algebra and Logic Gates
Introduction
Basic Definitions
Axiomatic Definition of Boolean Algebra
Basic Theorems and Properties of Boolean Algebra
Boolean Functions
Canonical and Standard Forms
Other Logic Operations
Digital Logic Gates
Integrated Circuits
📜 Historical Background
The development of Boolean algebra has revolutionized digital logic and computer science:
George Boole (1854): Developed Boolean algebra in his work "An Investigation of the Laws of Thought"
E. V. Huntington (1904): Formulated the postulates that formally define Boolean algebra
Claude Shannon (1938): Applied Boolean algebra to electrical switching circuits in his master's thesis
1940s-1950s: Boolean algebra became the mathematical foundation for digital circuit design
Modern Era: Boolean algebra underpins all digital computing, from simple logic gates to complex microprocessors
These developments created the mathematical foundation for the digital revolution.
1. Introduction to Boolean Algebra
🔬 What is Boolean Algebra?
Because binary logic is used in all of today's digital computers and devices, the cost of the circuits that implement it is an important factor addressed by designers—be they computer engineers, electrical engineers, or computer scientists. Finding simpler and cheaper, but equivalent, realizations of a circuit can reap huge payoffs in reducing the overall cost of the design.
Mathematical methods that simplify circuits rely primarily on Boolean algebra. Therefore, this chapter provides a basic vocabulary and a brief foundation in Boolean algebra that will enable you to optimize simple circuits and to understand the purpose of algorithms used by software tools to optimize complex circuits involving millions of logic gates.
📝 Importance in Digital Design
Boolean algebra is essential for:
Circuit Optimization: Simplifying logic expressions to reduce component count
Cost Reduction: Cheaper circuit implementations
Performance Improvement: Faster circuit operation
Reliability Enhancement: Fewer components mean fewer failure points
Automated Design: Foundation for CAD tools that optimize complex circuits
2. Basic Definitions
🔢 Mathematical Foundations
Boolean algebra, like any other deductive mathematical system, may be defined with a set of elements, a set of operators, and a number of unproved axioms or postulates.
A set of elements is any collection of objects, usually having a common property. If \( S \) is a set, and \( x \) and \( y \) are certain objects, then the notation \( x \in S \) means that \( x \) is a member of the set \( S \) and \( y \notin S \) means that \( y \) is not an element of \( S \).
2.1 Sets and Binary Operators
🧮 Binary Operators
Definition
A binary operator defined on a set \( S \) of elements is a rule that assigns, to each pair of elements from \( S \), a unique element from \( S \).
Consider the relation \( a * b = c \). We say that \( * \) is a binary operator if:
It specifies a rule for finding \( c \) from the pair \((a, b)\)
\( a, b, c \in S \)
Examples
Valid: Addition on natural numbers: \( 2 + 3 = 5 \) where \( 2, 3, 5 \in \mathbb{N} \)
Invalid: Subtraction on natural numbers: \( 2 - 3 = -1 \) but \( -1 \notin \mathbb{N} \)
2.2 Algebraic Postulates
🧮 Closure Property
Closure
A set \( S \) is closed with respect to a binary operator if, for every pair of elements of \( S \), the binary operator specifies a rule for obtaining a unique element of \( S \).
Associative Law
A binary operator \( * \) on a set \( S \) is said to be associative whenever:
\[ (x * y) * z = x * (y * z) \quad \text{for all } x, y, z \in S \]
Commutative Law
A binary operator \( * \) on a set \( S \) is said to be commutative whenever:
\[ x * y = y * x \quad \text{for all } x, y \in S \]
3. Axiomatic Definition of Boolean Algebra
🔍 Formal Definition
In 1854, George Boole introduced a systematic treatment of logic and developed for this purpose an algebraic system now called Boolean algebra. In 1938, C. E. Shannon introduced a two-valued Boolean algebra called switching algebra, in which he demonstrated that the properties of bistable electrical switching circuits can be represented by this algebra.
For the formal definition of Boolean algebra, we shall employ the postulates formulated by E. V. Huntington in 1904.
3.1 Huntington Postulates
🧮 Boolean Algebra Postulates
Postulate 1: Closure
The structure is closed with respect to the operator \( + \) and the operator \( \cdot \).
Postulate 2: Identity Elements
There exists an element \( 0 \in B \) such that for every \( x \in B \):
\[ x + 0 = x \]
There exists an element \( 1 \in B \) such that for every \( x \in B \):
\[ x \cdot 1 = x \]
Postulate 3: Commutative Law
For every \( x, y \in B \):
\[ x + y = y + x \]
\[ x \cdot y = y \cdot x \]
Postulate 4: Distributive Law
For every \( x, y, z \in B \):
\[ x \cdot (y + z) = (x \cdot y) + (x \cdot z) \]
\[ x + (y \cdot z) = (x + y) \cdot (x + z) \]
Postulate 5: Complement
For every \( x \in B \), there exists an element \( x' \in B \) such that:
\[ x + x' = 1 \]
\[ x \cdot x' = 0 \]
3.2 Two-Valued Boolean Algebra
Example: Two-Valued Boolean Algebra
Define a two-valued Boolean algebra with elements 0 and 1, where:
The theorems of Boolean algebra can be shown to hold for the two-valued Boolean algebra defined in the previous section. They can be proved by perfect induction—that is, by verifying that they hold for all possible combinations of the values of the variables involved.
4.1 Duality Principle
💡 Duality Principle
Every algebraic expression deducible from the postulates of Boolean algebra remains valid if the operators and identity elements are interchanged.
In a two-valued Boolean algebra, the dual of an algebraic expression is obtained by interchanging OR and AND operators and replacing 0's with 1's and 1's with 0's.
Example: The dual of \( x + (y \cdot z) = (x + y) \cdot (x + z) \) is \( x \cdot (y + z) = (x \cdot y) + (x \cdot z) \)
4.2 Fundamental Theorems
Theorem
Statement
Dual
1a
\( x + x = x \)
1b
\( x \cdot x = x \)
2a
\( x + 1 = 1 \)
2b
\( x \cdot 0 = 0 \)
3
\( (x')' = x \)
(Involution)
4a
\( x + (y + z) = (x + y) + z \)
4b
\( x \cdot (y \cdot z) = (x \cdot y) \cdot z \)
5a
\( x + (x \cdot y) = x \)
5b
\( x \cdot (x + y) = x \)
6a
\( x + (x' \cdot y) = x + y \)
6b
\( x \cdot (x' + y) = x \cdot y \)
7a
\( (x + y)' = x' \cdot y' \)
7b
\( (x \cdot y)' = x' + y' \)
Proof of Theorem 1a: \( x + x = x \)
\[ x + x = (x + x) \cdot 1 \quad \text{(Postulate 2b)} \]
The precedence for evaluating Boolean expressions is:
Parentheses: Operations inside parentheses
NOT: Complement operation
AND: Logical multiplication
OR: Logical addition
Example: In the expression \( F = A + B \cdot C' \), the operations are performed as:
Complement C: \( C' \)
AND: \( B \cdot C' \)
OR: \( A + (B \cdot C') \)
5. Boolean Functions
🔤 Boolean Expressions
A Boolean function is an expression formed with binary variables, the two binary operators OR and AND, the unary operator NOT, parentheses, and an equal sign. For a given value of the variables, the function can be either 0 or 1.
5.1 Algebraic Manipulation
Example: Simplifying Boolean Expressions
Simplify the Boolean function: \( F = x'y'z + x'yz + xy' \)
Standard Forms: Terms may not contain all variables
Sum of products (SOP): AND terms ORed together
Product of sums (POS): OR terms ANDed together
Examples:
SOP: \( F = xy + x'z + yz' \)
POS: \( F = (x+y)(x'+z)(y+z') \)
7. Other Logic Operations
🔤 16 Functions of Two Variables
There are \( 2^{2^n} \) functions for n binary variables. For two variables, there are \( 2^{2^2} = 16 \) possible Boolean functions.
7.1 16 Functions of Two Variables
Function
Symbol
Name
Comments
F0 = 0
Null
Binary constant 0
F1 = xy
x·y
AND
x and y
F2 = xy'
x/y
Inhibition
x but not y
F3 = x
Transfer
x
F4 = x'y
y/x
Inhibition
y but not x
F5 = y
Transfer
y
F6 = x'y + xy'
x⊕y
XOR
x or y but not both
F7 = x + y
x+y
OR
x or y
F8 = (x+y)'
x↓y
NOR
Not-OR
F9 = (x'y + xy')'
x⊙y
Equivalence
x equals y
F10 = y'
Complement
Not y
F11 = x + y'
x⊂y
Implication
If y then x
F12 = x'
Complement
Not x
F13 = x' + y
x⊃y
Implication
If x then y
F14 = (xy)'
x↑y
NAND
Not-AND
F15 = 1
Identity
Binary constant 1
7.2 Special Logic Operations
📝 Important Special Functions
NAND (Not AND): \( F = (xy)' \) - Universal gate
NOR (Not OR): \( F = (x+y)' \) - Universal gate
XOR (Exclusive OR): \( F = x⊕y = x'y + xy' \)
XNOR (Exclusive NOR): \( F = x⊙y = xy + x'y' \)
Properties of XOR:
\( x⊕0 = x \)
\( x⊕1 = x' \)
\( x⊕x = 0 \)
\( x⊕x' = 1 \)
Commutative: \( x⊕y = y⊕x \)
Associative: \( (x⊕y)⊕z = x⊕(y⊕z) \)
8. Digital Logic Gates
🔌 Logic Gate Implementation
A gate is a digital circuit with one or more input signals but only one output signal. Gates implement Boolean functions. The basic gates used in digital logic are AND, OR, and NOT. Additional useful gates are NAND, NOR, XOR, and XNOR.
8.1 Standard Logic Gates
Gate
Algebraic Function
Truth Table
AND
F = x · y
x y | F 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1
OR
F = x + y
x y | F 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1
NOT
F = x'
x | F 0 | 1 1 | 0
NAND
F = (x · y)'
x y | F 0 0 | 1 0 1 | 1 1 0 | 1 1 1 | 0
NOR
F = (x + y)'
x y | F 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 0
XOR
F = x ⊕ y
x y | F 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0
XNOR
F = x ⊙ y
x y | F 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 1
8.2 Multiple Input Gates
📝 Gates with More Than Two Inputs
Most logic gates can have more than two inputs. The AND and OR operations are both associative and commutative, so:
AND: \( x \cdot y \cdot z = (x \cdot y) \cdot z = x \cdot (y \cdot z) \)
OR: \( x + y + z = (x + y) + z = x + (y + z) \)
The NAND and NOR operations are associative but not commutative, so:
NAND: \( (x \cdot y \cdot z)' \) is not the same as \( ((x \cdot y)' \cdot z)' \)
Multiple-input NAND is defined as the complement of the AND operation
The XOR operation is both commutative and associative, so multiple-input XOR gates are possible.
8.3 Positive and Negative Logic
💡 Logic Level Conventions
Positive Logic: Higher voltage represents 1, lower voltage represents 0
Negative Logic: Higher voltage represents 0, lower voltage represents 1
Example: The same physical gate can implement different logical functions depending on the logic convention:
Positive logic AND = Negative logic OR
Positive logic OR = Negative logic AND
Positive logic NAND = Negative logic NOR
Positive logic NOR = Negative logic NAND
9. Integrated Circuits
💾 Levels of Integration
An integrated circuit (IC) is a small silicon semiconductor crystal, called a chip, containing the electronic components for the digital gates. The various gates are interconnected inside the chip to form the required circuit.
9.1 Levels of Integration
Level
Abbreviation
Gates per Chip
Examples
Small-scale integration
SSI
1 to 10
Basic gates, flip-flops
Medium-scale integration
MSI
10 to 100
Decoders, counters, registers
Large-scale integration
LSI
100 to 10,000
Small memories, simple processors
Very large-scale integration
VLSI
10,000 to 1,000,000
Large memories, complex processors
Ultra large-scale integration
ULSI
Over 1,000,000
Modern microprocessors, GPUs
9.2 Digital Logic Families
📝 Logic Families
TTL (Transistor-Transistor Logic):
Widely used, good speed and noise immunity
Standard 5V operation
Various subfamilies: Standard, Low-power, Schottky
CMOS (Complementary Metal-Oxide Semiconductor):
Low power consumption
High noise immunity
Wide range of supply voltages
Dominant technology for modern ICs
ECL (Emitter-Coupled Logic):
Very high speed
High power consumption
Used in high-speed applications
9.3 Computer-Aided Design
💡 CAD Tools for Digital Design
Modern digital design relies heavily on computer-aided design (CAD) tools:
Schematic Capture: Graphical entry of circuit diagrams
Hardware Description Languages (HDL): VHDL, Verilog for textual circuit description
Simulation: Testing circuit behavior before fabrication
Synthesis: Automatic generation of circuit from HDL description
Place and Route: Automatic layout of circuits on chips
These tools enable designers to create complex circuits with millions of gates efficiently and reliably.
Frequently Asked Questions
❓ Why is Boolean algebra important for digital logic design?
Boolean algebra is fundamental to digital logic design because:
Mathematical Foundation: Provides the mathematical framework for analyzing and designing digital circuits
Circuit Simplification: Enables optimization of logic expressions to reduce component count and cost
Universal Implementation: Any Boolean function can be implemented using basic logic gates
Automated Design: Forms the basis for CAD tools that design complex digital systems
Error Detection: Helps identify and eliminate logic hazards and race conditions
Without Boolean algebra, modern digital systems with millions of gates would be impossible to design and optimize.
❓ What is the difference between minterms and maxterms?
The main differences between minterms and maxterms are:
Feature
Minterms
Maxterms
Definition
AND term with all variables
OR term with all variables
Representation
Function = 1
Function = 0
Notation
mi
Mi
Form
Sum of Products (SOP)
Product of Sums (POS)
Complement
Uncomplemented if 1 in truth table
Complemented if 1 in truth table
Relationship
∑(minterms)
∏(maxterms) for same function
For any Boolean function, the set of minterms where the function equals 1 and the set of maxterms where the function equals 0 are complementary.
❓ Why are NAND and NOR gates called universal gates?
NAND and NOR gates are called universal gates because any Boolean function can be implemented using only NAND gates or only NOR gates. This property makes them extremely valuable in digital design:
OR: NOR followed by NOT: \( ((x + y)')' = x + y \)
AND: Using DeMorgan's theorem: \( (x' + y')' = x \cdot y \)
This universality property simplifies manufacturing and inventory since a single type of gate can be used to build any digital circuit.
📚 Master Boolean Algebra and Logic Gates
Understanding Boolean algebra and logic gates is fundamental to digital logic design, computer engineering, and computer science. These concepts form the building blocks for all digital systems, from simple circuits to complex microprocessors.
