Boolean Functions and Logic Gates — Mathematics Knowledge System

Overview

A Boolean function is a function that takes n Boolean inputs (each either 0/false or 1/true) and produces a single Boolean output. Because each input is one of 2 values and there are n inputs, there are 2ⁿ possible input combinations, and because the output for each combination can independently be 0 or 1, there are 2^(2ⁿ) distinct Boolean functions of n variables — 4 functions of one variable, 16 of two variables, 256 of three, and so on. A logic gate is the physical (or circuit-diagram) realization of a Boolean function: an AND gate realizes the function x∧y, an OR gate realizes x∨y, a NOT gate (inverter) realizes ¬x. Every Boolean function, no matter how complicated, can be built by wiring together a small number of these primitive gates, which is exactly how digital computers implement arithmetic and logic in hardware.

Intuition

Think of a Boolean function as a truth table waiting to be built out of hardware, and a logic gate as one physical Lego brick implementing one small piece of that table (AND, OR, NOT). Since {AND, OR, NOT} — or even the single gate NAND alone — can reproduce every row of any truth table, wiring enough of these bricks together in the right pattern realizes any Boolean function whatsoever, including the adders, comparators, and multiplexers that make up a CPU's arithmetic logic unit. This is why 'NAND is functionally complete' is such a striking fact: an entire computer's combinational logic can, in principle, be built from nothing but copies of a single two-input gate.

Formal Definition

Definition

A Boolean function of n variables is a mapping from {0,1}ⁿ to {0,1}. The core two-input functions and gates are defined by their truth tables; NAND and NOR are each functionally complete on their own (any Boolean function can be built from just one of them):

f : \{0,1\}^n \to \{0,1\}

General Boolean function of n variables

\#\{\text{Boolean functions of } n \text{ variables}\} = 2^{2^n}

Count of distinct n-variable Boolean functions

x \uparrow y = \lnot(x \land y) \quad \text{(NAND)}

NAND gate

x \downarrow y = \lnot(x \lor y) \quad \text{(NOR)}

NOR gate

x \oplus y = (x \land \lnot y) \lor (\lnot x \land y) \quad \text{(XOR)}

XOR gate

Worked Examples

There are 2² = 4 input combinations for two variables.
$(x,y) \in \{(0,0),(0,1),(1,0),(1,1)\}$
Evaluate f at each: f(0,0)=0∧1=0, f(0,1)=0∧0=0, f(1,0)=1∧1=1, f(1,1)=1∧0=0.
$f(0,0)=0,\ f(0,1)=0,\ f(1,0)=1,\ f(1,1)=0$

Answer: Exactly 1 of the 4 rows (x=1, y=0) outputs 1.

Practice Problems

Difficulty 2/10

How many distinct Boolean functions exist for n = 3 input variables?

Difficulty 3/10

Evaluate the XOR gate output x ⊕ y for (x, y) = (1, 1).

Difficulty 5/10

A half-adder circuit computes the sum bit as x ⊕ y and the carry bit as x ∧ y for two input bits x, y. For inputs x = 1, y = 1, what are the sum and carry bits?

Quiz

Summary

A Boolean function maps n Boolean inputs to a single Boolean output; there are 2^(2ⁿ) such functions of n variables.
Logic gates (AND, OR, NOT, NAND, NOR, XOR) are physical/circuit realizations of specific small Boolean functions.
NAND and NOR are each functionally complete: every Boolean function can be built from just one of them.
Combinational circuits like half-adders combine simple gates (XOR for sum, AND for carry) to implement arithmetic.

References

WebsiteWikipedia — Boolean function
WebsiteWikipedia — Logic gate