14.1 Boolean algebra and logic operations

Boolean algebra is the mathematical framework behind all digital logic. It uses binary variables (0 and 1) and a small set of operations to describe how digital circuits process information and make decisions. Every gate, chip, and processor you'll encounter in electrical engineering relies on these rules.

Boolean Algebra Fundamentals

Boolean Algebra and Variables

Boolean algebra is a branch of mathematics for manipulating logical expressions that involve binary variables. Unlike regular algebra where a variable like $x$ can be any number, a Boolean variable can only be 0 (false) or 1 (true).

These two values represent the state of a digital system: a switch is on or off, a voltage is high or low, a condition is met or not. Boolean algebra gives you a formal way to combine and manipulate these states using three core operators: AND, OR, and NOT.

Boolean Functions and Expressions

A Boolean function takes one or more Boolean variables as inputs and produces a single Boolean output (0 or 1). You can describe any Boolean function in two main ways:

• Boolean expressions combine variables and operators into a formula. For example, $A \cdot B$ means "A AND B," and $A + B$ means "A OR B."
• Truth tables list every possible combination of inputs alongside the corresponding output. For a function with 2 inputs, the truth table has $2^2 = 4$ rows. For 3 inputs, it has $2^3 = 8$ rows.

Truth tables are especially useful when you need to verify that two different expressions produce the same output for all inputs.

Laws of Boolean Algebra

These laws let you simplify and rearrange Boolean expressions, which directly translates to simpler, cheaper circuits. They work similarly to laws in regular algebra, but with a few surprises.

Commutative Law — The order of operands doesn't matter.

• AND: $A \cdot B = B \cdot A$
• OR: $A + B = B + A$

Associative Law — You can regroup operands without changing the result.

• AND: $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
• OR: $(A + B) + C = A + (B + C)$

Distributive Law — One operator can distribute over another. This is where Boolean algebra differs from regular algebra, because distribution works both ways:

• AND distributes over OR: $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
• OR distributes over AND: $A + (B \cdot C) = (A + B) \cdot (A + C)$

That second form has no equivalent in normal algebra, so pay close attention to it. It comes up often in simplification problems.

Basic Logic Operations

AND Operation

The AND operation returns 1 only if all inputs are 1. If any input is 0, the output is 0. It's denoted by $\cdot$ (a dot) or simply writing variables next to each other ($AB$).

Think of it like two switches wired in series: current flows only when both switches are closed.

OR Operation

The OR operation returns 1 if at least one input is 1. It only outputs 0 when all inputs are 0. It's denoted by $+$.

Think of two switches wired in parallel: current flows if either switch is closed.

NOT Operation

The NOT operation (also called inversion) flips the input: 0 becomes 1, and 1 becomes 0. It's denoted by a bar over the variable: $\bar{A}$.

This is the only basic operation that takes a single input. In circuits, it's implemented with an inverter.

Advanced Logic Operations

XOR Operation

The XOR (exclusive OR) operation returns 1 if exactly one input is 1. When both inputs match (both 0 or both 1), the output is 0. It's denoted by $\oplus$.

XOR is useful whenever you need to detect difference between two signals. It shows up in parity checks for error detection and in binary addition circuits (half adders and full adders).

NAND and NOR Operations

NAND (NOT AND) gives the opposite output of AND. It returns 0 only when all inputs are 1; otherwise it returns 1. It's denoted $\overline{A \cdot B}$.

NOR (NOT OR) gives the opposite output of OR. It returns 1 only when all inputs are 0. It's denoted $\overline{A + B}$.

Both NAND and NOR are called universal gates because you can build any Boolean function using only NAND gates or only NOR gates. This is a big deal in practice: manufacturers can mass-produce a single gate type and use it to construct entire processors. If you're asked to prove universality on an exam, the key is showing you can create AND, OR, and NOT from just one gate type.