Unit 3 - Notes

MTH265 7 min read

Unit 3: Boolean Algebra

1. Introduction

Boolean Algebra is a branch of algebra in which the values of the variables are the truth values true and false, usually denoted as $1$ and $0$, respectively. Named after mathematician George Boole, who introduced it in 1854, it forms the mathematical foundation of digital logic design and computer science.

Unlike elementary algebra where variables represent numbers and the primary operations are addition and multiplication, the primary operations of Boolean algebra are conjunction (AND), disjunction (OR), and negation (NOT). It provides the theoretical framework for processing information in modern digital computers, formulating digital logic gates, and simplifying complex logical circuits.

2. Basic Definitions

A Boolean Algebra is a mathematical structure consisting of a set $B$ equipped with two binary operations denoted by $+$ (OR, disjunction) and $\cdot$ (AND, conjunction), one unary operation denoted by $'$ or $\overline{x}$ (NOT, complementation), and two distinct elements $0$ and $1$, such that the following axioms (Huntington postulates) hold for all $x, y, z \in B$ :

Closure:
- $x + y \in B$
- $x \cdot y \in B$
Commutativity:
- $x + y = y + x$
- $x \cdot y = y \cdot x$
Associativity:
- $x + (y + z) = (x + y) + z$
- $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
Identity:
- There exists an element $0 \in B$ such that $x + 0 = x$
- There exists an element $1 \in B$ such that $x \cdot 1 = x$
Distributivity:
- $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$
- $x + (y \cdot z) = (x + y) \cdot (x + z)$
Complement:
- For every $x \in B$ , there exists an element $x' \in B$ such that $x + x' = 1$ and $x \cdot x' = 0$

Note on Notation: The operator $\cdot$ is often omitted, meaning $x \cdot y$ is written as $xy$ .

3. Duality

The Principle of Duality is a fundamental concept in Boolean Algebra. It states that every valid Boolean algebraic equation or identity remains valid if we take its dual.

To find the dual of any Boolean expression, you must:

Change every OR ( $+$ ) to an AND ( $\cdot$ ).
Change every AND ( $\cdot$ ) to an OR ( $+$ ).
Change every $0$ to a $1$.
Change every $1$ to a $0$.
Leave the variables and their complements unchanged.

Example:
The dual of $x + 0 = x$ is $x \cdot 1 = x$ .
The dual of $x \cdot (y + z)$ is $x + (y \cdot z)$ .

Because of the symmetry in the axioms of Boolean algebra, theorems are often proved in pairs (a theorem and its dual).

4. Basic Theorems

From the basic axioms, we can derive several important theorems that are used to simplify Boolean expressions. For every theorem, its dual is also a valid theorem.

Idempotent Laws:
- $x + x = x$
- $x \cdot x = x$
Boundedness (Domination) Laws:
- $x + 1 = 1$
- $x \cdot 0 = 0$
Absorption Laws:
- $x + (x \cdot y) = x$
- $x \cdot (x + y) = x$
Involution (Double Complement) Law:
- $(x')' = x$
De Morgan's Laws:
- $(x + y)' = x' \cdot y'$ (The complement of a sum is the product of the complements)
- $(x \cdot y)' = x' + y'$ (The complement of a product is the sum of the complements)
Uniqueness of Complement:
- The complement $x'$ of any element $x$ is unique.

5. Boolean Algebras as Lattices

Boolean algebras can be formally defined in the context of lattice theory.

A Lattice is a partially ordered set (poset) in which every two elements have a unique supremum (least upper bound, or join) and a unique infimum (greatest lower bound, or meet).

In a Boolean algebra, the join operation is $+$ and the meet operation is $\cdot$ .

We can define a partial order $\le$ on any Boolean algebra $B$ as follows:
$x \le y \iff x \cdot y = x \quad \text{(or equivalently, } x + y = y \text{)}$

Under this partial order, a Boolean Algebra is specifically a Complemented Distributive Lattice:

Lattice: Every pair of elements has a least upper bound ( $+$ ) and a greatest lower bound ( $\cdot$ ).
Distributive: The operations $+$ and $\cdot$ distribute over each other.
Bounded: It has a minimum element $0$ and a maximum element $1$.
Complemented: Every element $x$ has a complement $x'$ such that their join is $1$ and their meet is $0$.

6. Representation Theorem

Stone's Representation Theorem for Boolean Algebras is a foundational theorem which states that every finite Boolean algebra is isomorphic to the Boolean algebra of subsets of some finite set (the power set).

Power Set Algebra: Let $S$ be a set and $P(S)$ be its power set. The structure $(P(S), \cup, \cap, ^c, \emptyset, S)$ forms a Boolean algebra.
Atoms: An element $a \in B$ is called an atom if $a \neq 0$ and there is no element $x \in B$ such that $0 < x < a$ . Atoms are the "indivisible" building blocks of the algebra.
The Theorem: Any finite Boolean algebra $B$ is completely determined by its set of atoms. Specifically, if $B$ has $n$ atoms, it has exactly $2^n$ elements, and it is structurally identical (isomorphic) to the power set of its atoms.
Corollary: Every finite Boolean algebra must have a cardinality that is a power of 2 (e.g., 2, 4, 8, 16).

7. Sum-of-Products Form for Boolean Algebras

To standardize Boolean expressions, we use specific canonical forms. The most common is the Sum-of-Products (SOP) form.

Literal: A variable ( $x$ ) or its complement ( $x'$ ).
Product Term: A logical AND of literals (e.g., $x \cdot y' \cdot z$ ).
Minterm: A product term in which every variable of the function appears exactly once, either in its true or complemented form. For $n$ variables, there are $2^n$ possible minterms.
Sum-of-Products (SOP): An expression that is formed by taking the OR (sum) of multiple product terms (e.g., $xy' + x'z + yz$ ).
Canonical Sum-of-Products (Disjunctive Normal Form - DNF): A Boolean expression expressed as the sum (OR) of minterms.

Any Boolean function can be uniquely represented in canonical SOP form by writing a minterm for each combination of variables where the function evaluates to $1$, and ORing them together.

8. Minimal Boolean Expressions

While the canonical SOP form can perfectly describe a Boolean function, it is rarely the most efficient representation. In computing and digital logic, complex expressions require more physical logic gates, consuming more power and space.

Goal of Minimization: To find an equivalent Boolean expression that contains the minimum number of terms and the minimum number of literals per term.

Methods for minimizing Boolean expressions include:

Algebraic Manipulation: Using theorems like Absorption and Distributivity to simplify expressions manually. (e.g., $xy + xy' = x(y+y') = x \cdot 1 = x$ ).
Karnaugh Maps (K-Maps): A graphical tool that arranges the truth table into a grid where adjacent cells differ by only one variable (Gray code ordering). By grouping adjacent $1$s into blocks of sizes $2^k$ (1, 2, 4, 8...), one can easily extract minimal expressions.
Quine-McCluskey Algorithm: A tabular method suitable for computer programming. It systematically finds all prime implicants and then uses a prime implicant chart to find the minimal set needed to cover the function.

9. Prime Implicants

The concept of prime implicants is central to formal algorithmic minimization (like Quine-McCluskey).

Implicant: A product term that, if true, guarantees that the entire Boolean function is true. Graphically in a K-map, an implicant is any valid rectangular grouping of $1$s (or a single $1$).
Prime Implicant (PI): An implicant that cannot be combined with another implicant to form a term with fewer literals. It is a "maximal" grouping of $1$s in a K-map. You cannot make the group any larger without including $0$s.
Essential Prime Implicant (EPI): A prime implicant that covers at least one minterm (a $1$ in the truth table/K-map) that is not covered by any other prime implicant.

Rule for Minimization:
A minimal Sum-of-Products expression must include all Essential Prime Implicants. Once all EPIs are included, you select the minimum number of remaining non-essential Prime Implicants necessary to cover any remaining $1$s of the function.

Unit 2

Unit 4