home

Boolean algebra

A boolean algebra is a mathematical system denoted by \(\langle B, 0, 1, +, \cdot, ' \rangle\). The zero and unit elements are symbolic only.

Notation

Symbol Operation Term
\(x'\) NOT complement
\(x \cdot y\) AND product
\(x + y\) OR sum

Laws

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'\)

Duality

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\).

Boolean functions

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 |

Algebraic forms

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\).