A boolean algebra is a mathematical system denoted by \(\langle B, 0, 1, +, \cdot, ' \rangle\). The zero and unit elements are symbolic only.
|\(x \cdot y\)||AND||product|
|\(x + y\)||OR||sum|
|commutative||\(x + y = y + x\)||\(x \cdot y = y \cdot x\)|
|associative||\(x + (y+z) = (x+y)+z\)||\(x \cdot (y \cdot z) = (x \cdot y) \cdot z\)|
|distributive||\(x \cdot (y + z) = (x \cdot y) + (x \cdot z)\)||\(x + (y \cdot z) = (x + y) \cdot (x + z)\)|
|identity||\(x + 0 = x\)||\(x \cdot 1 = x\)|
|complement||\(x + x' = 1\)||\(x \cdot x' = 0\)|
|idempotent||\(x + x = x\)||\(x \cdot x = x\)|
|boundedness||\(x + 1 = 1\)||\(x \cdot 0 = 0\)|
|involution||\((x')' = x\), \(0' = 1\),\(1'=0\)|
|absorption||\(x+x \cdot y = x\)||\(x \cdot (x + y) = x\)|
|De Morgan’s||\((x + y)' = x' \cdot y'\)||\((x \cdot y)' = x' + y'\)|
Within all boolean algebra’s the duality principle states that any equality has a dual where each OR and AND operators are interchanged and zero and unit elements are swapped. For example, from \(x + x' = 1\) it also holds that \(x \cdot x' = 0\).
A boolean function holds a mapping from one or more Boolean input values to a Boolean output value.
For \(n\) input values there are \(2^n\) possible Combinations. For example, a 3 input function \(f(x,y,z)\) can be represented as a 8-row truth table. | \(x\) | \(y\) | \(z\) | \(f(x,y,z)\) | | — | — | — | ———- | | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 1 |
In place of a truth table, a functions may also be expressed algebraically. In this form there may be many equivalent representations For example:
May be represented as \[ f(x,y) = x + x' \cdot y \] or \[ f(x,y) = x + y \]
By convention, these expressions will be represented in standard forms.
Sum of products \(f(x,y,z) = xy + xz + yz\)
Product of sums \(f(x,y,z) = (x+y)(x+z)(y+z)\)
The sum of products can be formed from a truth table via the following process: 1. focus on the variables that make the function 1 2. if an input equals 1 it appears un-complemented 3. if an input equals 0 it is complemented in the expression 4. the function is then expressed as the sum of products of all terms for which \(f = 1\).