Boolean Algebra: Operations and Laws

Introduction

Boolean algebra is the mathematical foundation for digital logic and computer hardware. It provides a formal system for:

• Designing digital circuits
• Simplifying logical expressions
• Analyzing switching networks
• Optimizing logic gates
• Building computers

In this article, we’ll explore Boolean algebra operations, laws, and applications.

Boolean Values and Operations

Boolean Values

Boolean algebra uses two values:

0 (false, off, low)
1 (true, on, high)

Basic Operations

AND (Conjunction):

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
Notation: A · B, A ∧ B, AB

OR (Disjunction):

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1
Notation: A + B, A ∨ B

NOT (Negation):

NOT 0 = 1
NOT 1 = 0
Notation: A', ¬A, Ā

Truth Tables

AND Truth Table:

A | B | A·B
--|---|----
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1

OR Truth Table:

A | B | A+B
--|---|----
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

NOT Truth Table:

A | A'
--|--
0 | 1
1 | 0

Boolean Algebra Laws

Commutative Laws

AND: A · B = B · A OR: A + B = B + A

Associative Laws

AND: (A · B) · C = A · (B · C) OR: (A + B) + C = A + (B + C)

Distributive Laws

AND over OR: A · (B + C) = A·B + A·C OR over AND: A + (B · C) = (A + B) · (A + C)

Identity Laws

AND: A · 1 = A OR: A + 0 = A

Null/Domination Laws

AND: A · 0 = 0 OR: A + 1 = 1

Idempotent Laws

AND: A · A = A OR: A + A = A

Involution Law

Double Negation: (A’)’ = A

Complement Laws

AND: A · A’ = 0 OR: A + A’ = 1

De Morgan’s Laws

AND: (A · B)’ = A’ + B' OR: (A + B)’ = A’ · B'

Absorption Laws

AND: A · (A + B) = A OR: A + (A · B) = A

Consensus Laws

AND: A·B + A’·C + B·C = A·B + A’·C OR: (A+B)·(A’+C)·(B+C) = (A+B)·(A’+C)

Boolean Expression Simplification

Example 1: Simple Simplification

Expression: A · B + A · B'

Simplification:

A · B + A · B'
= A · (B + B')        (Distributive law)
= A · 1               (Complement law)
= A                   (Identity law)

Example 2: De Morgan’s Application

Expression: (A + B)’ · C

Simplification:

(A + B)' · C
= (A' · B') · C       (De Morgan's law)
= A' · B' · C         (Associative law)

Example 3: Complex Expression

Expression: A·B + A·B’·C + A·B·C

Simplification:

A·B + A·B'·C + A·B·C
= A·B + A·B'·C + A·B·C
= A·B·(1 + C) + A·B'·C    (Factor out A·B)
= A·B + A·B'·C            (Identity law: 1 + C = 1)
= A·(B + B'·C)            (Factor out A)
= A·(B + B'·C)
= A·((B + B')·(B + C))    (Distributive law)
= A·(1·(B + C))           (Complement law)
= A·(B + C)               (Identity law)

Boolean Functions

Definition

A Boolean function is a function that maps Boolean inputs to Boolean outputs.

Notation:

f: {0,1}ⁿ → {0,1}
f(A, B, C, ...) = Boolean expression

Examples

Two-Variable Functions:

f(A, B) = A · B        (AND)
f(A, B) = A + B        (OR)
f(A, B) = A · B'       (A AND NOT B)
f(A, B) = (A + B)'     (NOR)

Three-Variable Functions:

f(A, B, C) = A·B + A·C + B·C    (Majority function)
f(A, B, C) = A·B·C + A'·B'·C'   (Parity function)

Truth Table Representation

Example: f(A, B) = A·B + A’·B’:

A | B | A·B | A'·B' | f
--|---|-----|-------|--
0 | 0 | 0   | 1     | 1
0 | 1 | 0   | 0     | 0
1 | 0 | 0   | 0     | 0
1 | 1 | 1   | 0     | 1

Normal Forms

Sum of Products (SOP)

A Boolean expression in SOP form is a sum (OR) of product (AND) terms.

Example:

f(A, B, C) = A·B·C + A·B'·C + A'·B·C

Canonical SOP:

Each term contains all variables (complemented or not)
f(A, B, C) = A·B·C + A·B'·C + A'·B·C

Product of Sums (POS)

A Boolean expression in POS form is a product (AND) of sum (OR) terms.

Example:

f(A, B, C) = (A + B + C) · (A + B' + C) · (A' + B + C)

Canonical POS:

Each term contains all variables (complemented or not)
f(A, B, C) = (A + B + C) · (A + B' + C) · (A' + B + C)

Glossary

• Boolean algebra: Mathematical system for logic
• Boolean value: 0 or 1
• AND operation: Conjunction
• OR operation: Disjunction
• NOT operation: Negation
• Boolean function: Function mapping Boolean inputs to outputs
• Truth table: Table showing all input-output combinations
• Boolean law: Algebraic identity in Boolean algebra
• Simplification: Reducing Boolean expressions
• Normal form: Standardized Boolean expression form
• SOP: Sum of Products
• POS: Product of Sums

Practice Problems

Problem 1: Truth Table

Create a truth table for f(A, B) = A + B'.

Solution:

A | B | B' | A + B'
--|---|----|---------
0 | 0 | 1  | 1
0 | 1 | 0  | 0
1 | 0 | 1  | 1
1 | 1 | 0  | 1

Problem 2: Simplification

Simplify: A·B + A·B’ + A’·B

Solution:

A·B + A·B' + A'·B
= A·(B + B') + A'·B    (Distributive law)
= A·1 + A'·B           (Complement law)
= A + A'·B             (Identity law)
= (A + A')·(A + B)     (Distributive law)
= 1·(A + B)            (Complement law)
= A + B                (Identity law)

Problem 3: De Morgan’s Law

Apply De Morgan’s law to: (A·B·C)'

Solution:

(A·B·C)' = A' + B' + C'

Problem 4: Boolean Function

Express f(A, B, C) = A·B + B·C in POS form.

Solution:

f(A, B, C) = A·B + B·C
= B·(A + C)            (Distributive law)
= (B + 0)·(A + C)      (Identity law)
= (B + A·A')·(A + C)   (Complement law)
= (B + A)·(B + A')·(A + C)  (Distributive law)

Related Resources

Online Platforms

• Khan Academy Computer Science
• Coursera Digital Logic
• MIT OpenCourseWare
• Brilliant.org Computer Science
• Stanford CS103

Interactive Tools

• Boolean Algebra Simplifier - Simplify expressions
• Truth Table Generator - Generate truth tables
• Boolean Expression Evaluator - Evaluate expressions
• Logic Gate Simulator - Simulate gates
• Karnaugh Map Solver - Solve K-maps

Recommended Books

• “Digital Design” by Morris Mano - Comprehensive coverage
• “Boolean Algebra and Its Applications” by Givone - Mathematical approach
• “Introduction to Digital Logic” by Wakerly - Practical approach
• “Switching and Finite Automata Theory” by Kohavi - Theoretical approach
• “Digital Systems” by Tocci, Widmer, Moss - Practical applications

Academic Journals

• IEEE Transactions on Computers
• ACM Transactions on Design Automation
• Journal of Symbolic Logic
• Theoretical Computer Science
• Formal Aspects of Computing

Software Tools

• Logisim - Logic circuit simulator
• Quartus - FPGA design
• Verilog - Hardware description language
• VHDL - Hardware description language
• Graphviz - Graph visualization

Conclusion

Boolean algebra is fundamental to digital logic:

• Operations: AND, OR, NOT form the basis
• Laws: Enable simplification and optimization
• Functions: Map Boolean inputs to outputs
• Normal forms: Standardize expressions
• Applications: Digital circuits and computers

Understanding Boolean algebra is essential for digital design, computer architecture, and logic optimization.

In the next article, we’ll explore Boolean functions and minimization techniques.

---

Next Article: Boolean Functions and Minimization