Boolean Basics

Overview

The Algebra of Logic

Boolean algebra is a mathematical system for reasoning about true/false values. Invented by George Boole in the 1840s, it became the foundation of digital computer design a century later. Every digital circuit - from a simple light switch to the processor in your phone - is built on Boolean algebra.

Definition

Boolean Algebra

A Boolean algebra consists of a set B = {0, 1} with three operations: • AND (conjunction): x · y or x ∧ y - outputs 1 only when both inputs are 1 • OR (disjunction): x + y or x ∨ y - outputs 1 when at least one input is 1 • NOT (complement): x̄ or ¬x - flips the value (0 becomes 1, 1 becomes 0)

Theorem

Laws of Boolean Algebra

Identity: x + 0 = x, x · 1 = x Null (Domination): x + 1 = 1, x · 0 = 0 Idempotent: x + x = x, x · x = x Complement: x + x̄ = 1, x · x̄ = 0 Involution: (x̄)̄ = x Commutative: x + y = y + x, x · y = y · x Associative: (x + y) + z = x + (y + z) Distributive: x · (y + z) = (x · y) + (x · z) x + (y · z) = (x + y) · (x + z) Absorption: x + (x · y) = x, x · (x + y) = x De Morgan: (x + y)̄ = x̄ · ȳ, (x · y)̄ = x̄ + ȳ

Definition

Boolean Expression

A Boolean expression is a formula built from Boolean variables, constants (0 and 1), and the operations AND, OR, and NOT.

Examples: f(x, y) = x · y + x̄ g(x, y, z) = (x + y) · (ȳ + z)

Example

Evaluating a Boolean Expression

Evaluate f(x, y) = x · ȳ + x̄ · y when x = 1, y = 0:

x · ȳ = 1 · 1 = 1 x̄ · y = 0 · 0 = 0 f = 1 + 0 = 1

This expression is the XOR function - it outputs 1 when exactly one input is 1.

Note

Duality Principle

Every Boolean identity remains valid if you swap + with · and swap 0 with 1 throughout. This is called the duality principle.

Example: The dual of x + 0 = x is x · 1 = x. Both are true!