A digital signal represents a binary variable. The name of the signal is generally associated with the output terminal of the device from which it originates and is the name of the variable. A variable may be a function of other variables. One expression might be x = f(y, z). Every Boolean expression evaluates to a quantity 0 or 1. A variable may itself be a function of other variables. Or we may choose to represent a function by a single variable. Only three operations are permissible:

1. NOT, x': if x = 0, then x' = 1 and if x = 1, then x' = 0.
2. AND, × (may also be implied by adjacency of two arguments): fg = 1 only if f = g = 1; if either (or both) f or g has a value 0, then fg = 0.
3. OR, +: f + g = 1 if either or both f or g has a value 1; f + g = 0 only if f = g = 0.

Canonical Forms
Given a table representing an expression we can easily derive canonical forms, either sum-of-products (designed to recognize a specific input combination for which the table of combinations requires a 1) or product-of-sums (designed to detect a specific input combination for which the table of combinations requires a 0).

Sum-of-products: f = x'y'z' + x'yz' + xy'z' + xyz' + xyz. A disjunction of minterms.
Product-of-sums: f ' = x'y'z + x'yz + xy'z => f = (x'y'z + x'yz + xy'z)' = (x + y + z')(x + y' + z')(x' + y + z').
f  = (x + y + z')(x + y' + z')(x' + y + z'). A conjunction of maxterms.
Both of these functions are equivalent as they were designed from the same table of combinations.

Repeated application of Table 1 Theorem 10.b allows reduction of the above forms to simply: f = xy + z'
This minimization technique is easily applied using Karnaugh maps for variables numbering 4 or less.

The problem of synthesizing a gate network can lead to many equivalent circuits, some more complex than others. Consider the simple EXCLUSIVE OR, Å ,