Boolean Function — Definition, Formula & Examples

A Boolean function is a function whose inputs and output are each either 0 or 1 (false or true). It defines a rule that takes one or more binary values and produces exactly one binary value.

A Boolean function of $n$ variables is a mapping $f : \{0,1\}^n \to \{0,1\}$ . Every such function can be completely specified by a truth table with $2^n$ rows and can be expressed as a combination of the basic Boolean operations AND ( $\land$ ), OR ( $\lor$ ), and NOT ( $\lnot$ ).

Key Formula

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

Where:

$n$ = The number of binary input variables
$f$ = The Boolean function mapping each input combination to 0 or 1

How It Works

You specify a Boolean function by listing what output it produces for every possible combination of input values. For two variables, there are

2^2 = 4

input combinations, so the truth table has 4 rows. Any Boolean function, no matter how many variables it has, can be written as a Boolean expression using AND, OR, and NOT. This fact is guaranteed by the functional completeness of

\{\land, \lor, \lnot\}

. Two Boolean expressions that produce the same truth table represent the same Boolean function.

Worked Example

Problem: Define a Boolean function f(x, y) that outputs 1 exactly when the inputs differ. Write its truth table and a Boolean expression.

Build the truth table: List all four input pairs and assign output 1 when x and y are different.

\begin{array}{cc|c} x & y & f(x,y) \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array}

Derive a Boolean expression: Identify the rows where f = 1. Row 2 gives the term (NOT x) AND y; row 3 gives x AND (NOT y). OR these together.

f(x,y) = (\lnot x \land y) \lor (x \land \lnot y)

Recognize the operation: This expression is the exclusive OR (XOR) of x and y, often written x ⊕ y.

f(x,y) = x \oplus y

Answer: The Boolean function f(x, y) = x ⊕ y outputs 1 when exactly one input is 1, and 0 otherwise.

Why It Matters

Boolean functions are the mathematical foundation of digital circuit design — every logic gate implements one. In computer science courses on algorithms and complexity, problems are often framed as evaluating or satisfying Boolean functions (e.g., the SAT problem). They also appear directly in database query optimization and programming conditional logic.

Common Mistakes

Mistake: Confusing the number of possible functions with the number of input combinations. Students sometimes think two variables yield only 4 Boolean functions.

Correction: Two variables give

2^2 = 4

input rows, but there are

2^{2^2} = 16

distinct Boolean functions of two variables, since each row's output can independently be 0 or 1.