Boolean Algebra

Table of Contents
1. Introduction
2. Basic Laws and Properties of Boolean Algebra
3. Sub-Algebra (Sub-Boolean Algebra)
4. Isomorphic Boolean Algebras
5. Standard Properties - Ordered List
6. Boolean Functions
7. Canonical Forms and Expression of Boolean Functions
8. Simplification Techniques
9. Simple Worked Example - Algebraic Simplification
10. Applications of Boolean Algebra
11. Final Summary
View more

Introduction

A Boolean algebra is a complemented distributive lattice. It is usually denoted by (B, ∧, ∨, ', 0, 1), where B is a set on which two binary operations ∧ (logical AND, sometimes written as • or *) and ∨ (logical OR, sometimes written as +) and a unary operation ' (complement) are defined. The elements 0 and 1 are the least and greatest elements (also called null and unity) of B, and they are distinct.

Because (B, ∧, ∨) is a complemented distributive lattice, every element of B has a unique complement. The complement of an element a ∈ B is denoted a' and satisfies a ∨ a' = 1 and a ∧ a' = 0.

Basic Laws and Properties of Boolean Algebra

• Commutative laws: a ∨ b = b ∨ a; a ∧ b = b ∧ a.
• Associative laws: a ∨ (b ∨ c) = (a ∨ b) ∨ c; a ∧ (b ∧ c) = (a ∧ b) ∧ c.
• Distributive laws: a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c); a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c).
• Identity laws: a ∨ 0 = a; a ∧ 1 = a.
• Null laws: a ∧ 0 = 0; a ∨ 1 = 1.
• Idempotent laws: a ∨ a = a; a ∧ a = a.
• Absorption laws: a ∨ (a ∧ b) = a; a ∧ (a ∨ b) = a.
• Complement laws: a ∨ a' = 1; a ∧ a' = 0.
• Involution law: (a')' = a.
• De Morgan's laws: (a ∧ b)' = a' ∨ b'; (a ∨ b)' = a' ∧ b'.

Sub-Algebra (Sub-Boolean Algebra)

Let (B, ∧, ∨, ', 0, 1) be a Boolean algebra and let A ⊆ B. Then (A, ∧, ∨, ', 0, 1) is a sub-algebra of B if A itself is a Boolean algebra; that is, A contains the elements 0 and 1 of B, and A is closed under the operations ∧, ∨ and complement '.

Example: Consider the Boolean algebra D70 whose Hasse diagram is shown in the figure below.

In this algebra, the subsets A = {1, 7, 10, 70} and B = {1, 2, 35, 70} are sub-algebras of D70, because each contains 0 and 1 (with the notation used in D70) and is closed under ∧, ∨ and complement '.

Note: A subset of a Boolean algebra may be a Boolean algebra by itself, but it is a sub-algebra of the larger algebra only if it is closed under the same operations and contains the same 0 and 1 elements as the larger algebra.

Isomorphic Boolean Algebras

Two Boolean algebras B and B1 are isomorphic if there exists a bijection f : B → B1 that preserves the Boolean operations. That is, for all a, b ∈ B:

• f(a ∨ b) = f(a) ∨ f(b)
• f(a ∧ b) = f(a) ∧ f(b)
• f(a') = f(a)'

Example: Two distinct two-element Boolean algebras are isomorphic.

• The first is the power set algebra derived from P(S) under union and intersection. Let S = {a}. Then P(S) = {∅, {a}} forms a Boolean algebra with two elements.
• The second is the two-element algebra {1, p} (here p is a prime number) under the divisibility order: 1 ∧ p = 1, 1 ∨ p = p, with complements 1' = p and p' = 1.

There exists a bijection that maps ∅ ↔ 1 and {a} ↔ p, preserving ∨, ∧ and complement; hence the two algebras are isomorphic.

Standard Properties - Ordered List

1. Order relation: a ≤ b iff a ∨ b = b.
2. a ≤ b iff a ∧ b = a.
3. Idempotent laws: a ∨ a = a; a ∧ a = a.
4. Commutative laws: a ∨ b = b ∨ a; a ∧ b = b ∧ a.
5. Associative laws: a ∨ (b ∨ c) = (a ∨ b) ∨ c; a ∧ (b ∧ c) = (a ∧ b) ∧ c.
6. Absorption laws: a ∨ (a ∧ b) = a; a ∧ (a ∨ b) = a.
7. Identity laws: a ∨ 0 = a; a ∧ 1 = a.
8. Null laws: a ∧ 0 = 0; a ∨ 1 = 1.
9. Distributive laws: a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c); a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).
10. Complement laws: 0' = 1; 1' = 0; a ∨ a' = 1; a ∧ a' = 0.
11. Involution law: (a')' = a.
12. De Morgan's laws: (a ∧ b)' = a' ∨ b'; (a ∨ b)' = a' ∧ b'.

Note:

1. For every a ∈ B, 0 ≤ a ≤ 1.
2. Every element b in B has a unique complement b'.

Boolean Functions

In the Boolean algebra (B, ∨, ∧, ', 0, 1), a mapping from B^n to B specified by a Boolean expression in n variables is called a Boolean function. For the two-valued Boolean algebra {0, 1}, any function f : {0,1}^n → {0,1} is a Boolean function.

Example 1: The table below shows a function f from {0,1}^3 to {0,1}.

Example 2: The table below shows a function f from {0,1,2,3}^2 to {0,1,2,3}.

Note: A Boolean function can always be described in tabular form (truth table). An alternative is to specify the function by a Boolean expression using variables, their complements and the operations ∨, ∧.

Canonical Forms and Expression of Boolean Functions

Every Boolean function can be expressed in canonical forms. Two common canonical forms are:

• Sum of Products (SOP): f is expressed as a disjunction (∨) of minterms where each minterm is a conjunction (∧) of all variables in either direct or complemented form. SOP corresponds to listing the input rows where the function value is 1.
• Product of Sums (POS): f is expressed as a conjunction (∧) of maxterms where each maxterm is a disjunction (∨) of all variables in either direct or complemented form. POS corresponds to listing the input rows where the function value is 0.

Canonical expressions are useful for theoretical analysis and for converting functions into digital circuits. They can be simplified using Boolean laws to obtain minimal expressions.

Simplification Techniques

Boolean expressions are simplified to reduce circuit complexity. Standard techniques include:

• Algebraic simplification using the basic laws and identities of Boolean algebra (commutative, associative, distributive, absorption, De Morgan, involution, etc.).
• Tabular methods such as the Quine-McCluskey method for systematic minimisation of minterms.
• Graphical methods such as Karnaugh maps (K-maps) for up to about six variables to visually combine adjacent minterms and eliminate variables.

When simplifying a Boolean expression, present the reasoning stepwise and show each algebraic transformation clearly so correctness can be followed.

Simple Worked Example - Algebraic Simplification

Simplify the expression f = a ∨ (a ∧ b).

Apply the absorption law directly.

f = a.

This shows that a ∨ (a ∧ b) simplifies to a by the absorption law; a visual or circuit interpretation is that the presence of a alone determines the output regardless of b.

Applications of Boolean Algebra

• Design and analysis of digital circuits and logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR).
• Switching theory and switching networks.
• Computer logic design: combinational circuits (adders, multiplexers, decoders) and sequential circuits (flip-flops, registers) use Boolean functions and simplification.
• Boolean algebra underpins digital systems, programming conditions, database query logic and set algebra analogies.

Final Summary

Boolean algebra formalises logic with operations ∨, ∧ and complement ' on a set B with distinguished elements 0 and 1. It obeys a fixed set of algebraic laws (commutative, associative, distributive, absorption, identity, null, complement, involution and De Morgan). Subsets that contain 0 and 1 and are closed under the operations form sub-algebras. Boolean functions map tuples of Boolean values to Boolean values and are represented by truth tables, canonical SOP/POS expressions, and simplified using algebraic rules, Karnaugh maps or tabular methods. These concepts are the mathematical foundation for digital logic and switching circuits.