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$$.