Boolean Algebra

Introduction

Boolean algebra is the mathematical study of operations on the truth values true and false, typically denoted 1 and 0. Developed by George Boole in the mid-19th century as an algebraic approach to logic, it has become fundamental to digital circuit design, computer science, and mathematical logic.

Unlike ordinary algebra where variables range over numbers, Boolean algebra operates on a two-element set with operations corresponding to logical conjunction (AND), disjunction (OR), and negation (NOT). These three operations, combined with the laws governing them, provide a complete framework for reasoning about propositions and designing digital systems.

Basic Definitions

A Boolean algebra consists of a set B together with two binary operations ∧ (meet/AND) and ∨ (join/OR), a unary operation ¬ (complement/NOT), and two distinguished elements 0 and 1 satisfying certain axioms.

The simplest Boolean algebra is the two-element algebra B={0,1} where the operations are defined by truth tables. We interpret 1 as true and 0 as false.

Fundamental Operations

Conjunction (AND)

The conjunction of x and y written x∧y or x⋅y or simply x*y equals 1 if and only if both x=1 and y=1

0∧0=0,0∧1=0,1∧0=0,1∧1=1

Disjunction (OR)

The disjunction x∨y (also written x+y equals 1 if at least one of x or y equals 1

0∨0=0,0∨1=1,1∨0=1,1∨1=1

Negation (NOT)

The negation ¬*x (also written (x) or (x^′) flips the value:

¬*0=1,¬*1=0

Laws of Boolean Algebra

The operations of Boolean algebra satisfy a collection of laws that parallel and extend the laws of ordinary algebra.

Identity Laws

x∨0=x*x∧1=x

The element 0 is the identity for OR, and 1 is the identity for AND.

Domination Laws

x∨1=1*x∧0=0

Idempotent Laws

x∨x=x*x∧x=x

Complement Laws

x∨¬*x=1*x∧¬*x=0

Double Negation

¬*(¬*x)=x

Commutative Laws

x∨y=y∨x*x∧y=y∧x

Associative Laws

(x∨y)∨z=x∨(y∨z)*(x∧y)∧z=x∧(y∧z)

Distributive Laws

x∧(y∨z)=(x∧y)∨(x∧z)

x∨(y∧z)=(x∨y)∧(x∨z)

Note that the second distributive law has no analog in ordinary algebra: addition does not distribute over multiplication.

De Morgan's Laws

Two of the most important laws in Boolean algebra relate negation to the binary operations:

¬*(x∨y)=¬*x∧¬*y

¬*(x∧y)=¬*x∨¬*y

In words: the negation of a disjunction is the conjunction of the negations, and vice versa. De Morgan's laws allow us to push negations inward through expressions, converting ANDs to ORs and ORs to ANDs.

Absorption Laws

x∨(x∧y)=x*x∧(x∨y)=x

The absorption laws show that a term can absorb a more restrictive term containing it.

Derived Operations

Several useful operations can be defined in terms of AND, OR, and NOT.

Exclusive OR (XOR)

The exclusive or of x and y is true when exactly one of them is true:

x⊕y=(x∧¬*y)∨(¬*x∧y)

XOR corresponds to addition modulo 2:
0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0.

Implication

The logical implication x→y (if x then y is defined as:

x→y=¬*x∨y

An implication is false only when the hypothesis is true and the conclusion is false.

Biconditional

The biconditional x↔y (x if and only if y is true when x and y have the same value:

x↔y=(x→y)∧(y→x)=(x∧y)∨(¬*x∧¬*y)

Note that x↔y=¬*(x⊕y) the biconditional is the negation of XOR.

Normal Forms

Any Boolean expression can be written in standardized forms that facilitate analysis and circuit implementation.

Disjunctive Normal Form (DNF)

A Boolean expression is in disjunctive normal form if it is an OR of ANDs. Each AND term (called a minterm) is a conjunction of literals, where a literal is a variable or its negation. For example:

(x∧y∧¬*z)∨(x∧¬*y∧z)∨(¬*x∧y∧z)

Conjunctive Normal Form (CNF)

A Boolean expression is in conjunctive normal form if it is an AND of ORs. Each OR term (called a maxterm or clause) is a disjunction of literals. For example:

(x∨y∨¬*z)∧(x∨¬*y∨z)∧(¬*x∨y∨z)

Every Boolean function has unique representations in both DNF and CNF using all variables. These canonical forms are useful for comparing functions and for circuit design.

Functional Completeness

A set of Boolean operations is functionally complete if every Boolean function can be expressed using only operations from that set. The set {∧,∨,¬} is functionally complete.

Remarkably, smaller sets are also complete. The NAND operation x↑y=¬*(x∧y) alone is functionally complete, since:

¬*x=x↑x,x∧y=(x↑y)↑(x↑y),x∨y=(x↑x)↑(y↑y)

Similarly, NOR x↓y=¬*(x∨y) is functionally complete. This has practical importance: digital circuits can be built using only NAND gates or only NOR gates.

Summary

Boolean algebra provides the mathematical foundation for digital logic and propositional reasoning. The three fundamental operations—AND (∧, OR (∨, and NOT (¬—operate on truth values and satisfy algebraic laws including commutativity, associativity, distributivity, and De Morgan's laws.

Every Boolean function can be expressed in disjunctive normal form (OR of ANDs) or conjunctive normal form (AND of ORs). The NAND and NOR operations are each individually functionally complete, meaning any Boolean function can be expressed using only one of these operations.

Boolean algebra unifies the study of logic, set theory, and digital circuits, providing algebraic tools for reasoning about propositions and designing computational systems.