A boolean algebra is a mathematical system denoted by \(\langle B, 0, 1, +, \cdot, ' \rangle\). The zero and unit elements are symbolic only.
| Symbol | Operation | Term |
|---|---|---|
| \(x'\) | NOT | complement |
| \(x \cdot y\) | AND | product |
| \(x + y\) | OR | sum |
| Term | Sum | Product |
|---|---|---|
| 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:
| \(x\) | \(y\) | \(f(x,y)\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
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\).