INF107

Boolean Algebra

Just as with integers or real numbers, there are certain laws that help us manipulate expressions, in order to simplify them or to prove them equivalent. Most of the following laws should be familiar to you, and it should now become clear why we chose $\cdot$ and $+$ for conjunction and disjunction, respectively. In the following, $a,b,$ and $c$ are Boolean variables.

Laws for disjunction and conjunction

For the two monotone operators $+$ and $\cdot$, the following laws apply:

Associativity $$\begin{array}{rl}a+(b+c)& =(a+b)+c\\ a\cdot (b\cdot c)& =(a\cdot b)\cdot c\end{array}\text{\hspace{1em}(AssocOr)(AssocAnd)}$$

Commutativity $$\begin{array}{rl}a+b& =b+a\\ a\cdot b& =b\cdot a\end{array}\text{\hspace{1em}(CommOr)(CommAnd)}$$

Neutral elements $$\begin{array}{rl}a+0& =a\\ a\cdot 1& =a\end{array}\text{\hspace{1em}(Zero)(One)}$$

Annihilation $$\begin{array}{rl}a+1& =1\\ a\cdot 0& =0\end{array}\text{\hspace{1em}(AnnOr)(AnnAnd)}$$

Idempotence $$\begin{array}{rl}a+a& =a\\ a\cdot a& =a\end{array}\text{\hspace{1em}(IdemOr)(IdemAnd)}$$

Distributivity $$\begin{array}{rl}a+(b\cdot c)& =(a+b)\cdot (a+c)\\ a\cdot (b+c)& =(a\cdot b)+(a\cdot c)\end{array}\text{\hspace{1em}(DistrOr)(DistrAnd)}$$

Absorption $$\begin{array}{rl}a+(a\cdot b)& =a\\ a\cdot (a+b)& =a\end{array}\text{\hspace{1em}(AbsOr)(AbsAnd)}$$

Non-monotone Laws

If we add negation, these additional laws apply:

Complementary $$\begin{array}{rl}a+\overline{a}& =1\\ a\cdot \overline{a}& =0\end{array}\text{\hspace{1em}(ComplOr)(ComplAnd)}$$

Double negation $$\overline{\overline{a}}=a\text{\hspace{1em}(DoubleNeg)}$$

De Morgan $$\begin{array}{rl}\overline{a+b}& =\overline{a}\cdot \overline{b}\\ \overline{a\cdot b}& =\overline{a}+\overline{b}\end{array}\text{\hspace{1em}(DeMorgan1)(DeMorgan2)}$$

Showing Equivalence with Truth Tables

In order to show that two Boolean terms are indeed euqivalent, we can just establish their truth tables and compare them line by line. Let's show the first De Morgan law for example:

And the right hand side:

From Truthtable to Boolean Expression

Now if we want to do the reverse, how can we come up with a Boolean equation from a truth table? Consider the following truth table:

Disjunctive Normal Form

We can read each line of the truth table as follows: If $a$ is zero and $b$ is zero, then $z$ is zero; if $a$ is zero and $b$ is one, then $z$ is one; etc. We can represent each line as a conjunction (also called product), such as $\overline{a}\cdot \overline{b}$ for the first line, $\overline{a}\cdot b$ for the second line etc. Now in order to get a one at the output, at least one of the conditions for a one must apply. In other words, we can take the disjunction (the sum) of the products of all the lines leading to a one at the output:

$$z=\overline{a}\cdot b+a\cdot \overline{b}$$

This form of Boolean expression is called sum-of-products (SOP) form, or disjunctive normal form (DNF). Each complete product term (in which all of the variables appear), is also called a minterm. The above recipe works for any Boolean function with $N$ variables. However, since it starts with a truth table and translates each line leading to a one, the resulting expression is of exponential size (in $N$) in general.

Conjunctive Normal Form

As a matter of fact, we can also use the remaining lines of the truth table, those leading to zero, to construct a Boolean expression. We just need to negate the respective minterms and take the conjunction. Intuitively, we are saying that if none of these "forbidden" minterms applies, then the result must be one, otherwise it will be zero. Consider again the truth table from the beginning of the section. Starting from the first and last line, we obtain:

$$z=(\overline{\overline{a}\cdot \overline{b}})\cdot (\overline{a\cdot b})$$

Applying De Morgan's law on each negated minterm, we obtain:

$$z=(a+b)\cdot (\overline{a}+\overline{b})$$

This form of Boolean expression is called product-of-sums (POS) form or conjunctive normal form (CNF).

Rewriting and Logic Minimization

Instead of establishing the truth tables for two Boolean expressions, we can also apply the laws of Boolean Algebra in order to transform (rewrite) one expression into the other one symbolically. As an example, let's show that the DNF and CNF we just derived are indeed equivalent, starting with the CNF:

$$\begin{array}{rlrl}& (a+b)\cdot (\overline{a}+\overline{b})& & \text{by (DistrAnd)}\\ =& (a+b)\cdot \overline{a}+(a+b)\cdot \overline{b}& & \text{by (DistrAnd)}\\ =& a\cdot \overline{a}+b\cdot \overline{a}+a\cdot \overline{b}+b\cdot \overline{b}& & \text{by (ComplAnd)}\\ =& 0+b\cdot \overline{a}+a\cdot \overline{b}+0& & \text{by (Zero)}\\ =& b\cdot \overline{a}+a\cdot \overline{b}& & \text{by (CommAnd)}\\ =& \overline{a}\cdot b+a\cdot \overline{b}& & \end{array}$$

Another application of this rewriting is logic minimization. Indeed, if we want to create a combinatorial circuit from a Boolean function specification, each operator in the Boolean expression will become a logic gate. If we find an equivalent expression with less operators, this will lead to a cheaper implementation. Instead of rewriting expressions manually, there are several algorithms that can be used for systematic and automated logic minimization, such as Quine McCluskey or Karnaugh maps. The study of these algorithms is beyond the scope of this lecture.