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