Implementing Boolean Functions

Modified: April 12, 2003

Introduction

From the first set of notes in this section, we said there were 2^{2^km} functions given k-bit inputs and m-bit outputs.

That's a lot of functions. For example, the number of functions with 2 bits of inputs and 1 bit of output is 16. For 10 bits, there are 2¹⁰²⁴ different functions!

However, we don't make a gate for each different Boolean function. In fact, very few Boolean functions have gates associated with it. Of the 16 possible, 2- bit input, 1-bit output Boolean functions, only 6 are gates (AND₂, OR₂, XOR₂, NAND₂, NOR₂, XNOR₂). Here's an amazing fact---you only need three gates to implement all Boolean functions.

Let's repeat that once again: you only need three gates to implement all Boolean functions.

If you find that hard to believe, it's true, and it's quite amazing. In particular, we're only going to need AND₂, OR₂, and NOT. Any Boolean function can be constructed using an arbitrary number of inputs plus an arbitrary number of these gates.

Implementing a Specific Kind of Truth Table

Let's consider a specific kind of truth table. In particular, this truth table will have exactly one set of values for which the output is 1. The rest of the inputs will output to 0.

Here's an example.

Row	x₂	x₁	x₀	z
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	0
4	1	0	0	0
5	1	0	1	1
6	1	1	0	0
7	1	1	1	0

In the truth table above, row 5 has output 1. The rest of the rows have output 0.

Literals

How can we construct a Boolean function that has the behavior described by the truth table above?

Before we answer this question, let's define a literal.

Definition A literal is either a variable or its negation. Thus, both x and \x are literals. (\x is x, preceded by a prime, which indicates negation).

We'll assume that \\x or \\\x are not literals, even though they are equivalent to literals.

There are some interesting properties of literals.

Suppose you want a Boolean expression whose output is 1 when the input is 1 and whose output is 0 when the input is 0. That expression is just a positive literal. Thus, z = x gives you the behavior you want.
What about the opposite? Suppose you want a Boolean expression whose output is 0 when the input is 1 and whose output is 1 when the input is 0. That expression is just a negative literal. Thus, z = \x gives you the behavior you want.

The use of positive and negative literals will help us construct a Boolean function to implement the truth table above.

Constructing Minterms.

We want to construct a Boolean function that is specified by the truth table above. In particular, we want an Boolean function where x₂ = 1 AND x₁ = 0 AND x₀ = 1.

To construct this function, it looks like we need to AND some subexpressions. That's true.

Consider the following Boolean function: x₂ * x₁ * x₀. This function is the conjuction (or ANDing) of three positive literals. We use multiplication to indicate AND₂.

When does this function produce 1 as output? It produces it when x₂ = 1 AND x₁ = 1 AND x₀ = 1. For any other combination of values, the output is 0.

Consider the following Boolean function: \x₂ * \x₁ * \x₀. This function is the conjuction (or ANDing) of three negative literals.

When does this function produce 1 as output? It produces it when x₂ = 0 AND x₁ = 0 AND x₀ = 0. For any other combination of values, the output is 0.

In fact, any conjunction (ANDing) of three literals produces a truth table with exactly one 1 as output. That makes sense, because AND suggests that all the literals have to be true in order for the entire expression to be true.

Let's define this kind of conjunction, and call it a minterm.

Definition A minterm of k variables is a conjunction of k literals, where each variable shows up exactly once.

A minterm produces a truth table that has exactly one 1 as output.

To construct a minterm, look at the row of the truth table you want to have output 1. If the value of the variable is 1, use a positive literal. If the value of the variable is 0, use a negative literal.

For example, in the truth table above, you have: x₂ = 1 AND x₁ = 0 AND x₀ = 1. Thus, you need literals: x₂, \x₁, and x₀. Conjoin them together, and you get: x₂ \x₁ x₀.

Constructing Boolean Expressions for Arbitrary Truth Tables

We've come up with a way of writing a Boolean function for truth tables with a single 1 as output. We use a minterm. However, that's a very particular kind of truth table. What if a truth table has more than a single 1 as output? How do we come up with a Boolean function for that?

As with most problems, the answer is to create solution using the solution we already have. We know that if you have a truth table with a single 1 as output, you use a single minterm. If you have a truth table with m 1's as outputs, it makes sense to use m minterms.

In fact, that's how we do it.

For each row that has a 1 as output, construct a minterm.
OR the minterms together. This is called a sum of minterms, or more generally, a sum of products. A product is a conjunction of 1 or more literals.

The use of the word "sum" refers to OR. This comes from electrical engineers who treat multiplication like AND and addition like OR.

An Example

Row	x₂	x₁	x₀	z
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1
3	0	1	1	0
4	1	0	0	0
5	1	0	1	1
6	1	1	0	0
7	1	1	1	1

In the truth table above, rows 2, 5, and 7 have outputs of 1. We need to construct a minterm for each of the rows.

Row	Minterm
2	\x₂ x₁ \x₀
5	x₂ \x₁ x₀
7	x₂ x₁ x₀

Then, join the minterms with ORs to get the final Boolean function.

z = \x₂ x₁ \x₀ + x₂ \x₁ x₀ + x₂ x₁ x₀

As you've noticed, we've put all the terms together with ORs (written as +). This makes sense. The entire expression is true if any one of the minterms is true.

All Zeroes?

What if the truth table has no 1's as outputs? What if, for all possible input values, the output is always 0? That's when you need to modify the algorithm. Since there are no minterms to create, there are two solutions:

First, you can just define the Boolean function to be 0. This can be considered a constant function that takes no arguments, and always produces a constant value.

z = 0

Or, if you don't want to use constants, you can do:

z = x\x

In this version, you take a positive and negative literal and AND them. There's no way to make a variable and its negation both true.

In general, the z = 0 is preferable because it's simpler.

Canonical Form

As you can see, any truth truth table can be implemented using only AND₂, OR₂, and NOT.

This is considered a canonical or standard form for the truth table. This particular form is called sum of products, or sum of minterms or disjunctive normal form (a disjunct are terms connected by ORs---in this case, the terms are minterms).

Product of Sums

As a thought exercise, consider how to create a Boolean function by looking at rows with 0's in them. You can create maxterms and AND the maxterms together. This is called product of sums or conjunctive normal form.

Product Terms

Notice that we say sum of products. To be precise, we really should say sum of minterms. Recall that a minterm of k variables is a conjunction of k literals where each of the k variables shows up exactly once.

However, a product term is more general than a minterm. A product term is a conjunction of any number of literals. Usually, no variable shows up twice in a product term, though it is a possibility.

The following is an example of a sum of products: x + xy + x\z + \x\yz.

There are four product terms in the sum: x, xy, x\z, and \x\yz. However, the product terms aren't considered minterms because the number of literals isn't the same for all product terms. In a sum of minterms of k variables, all the products terms must have k literals.

We can even allow variables to be repeated in a product term. Thus, we allow x\x as a product term, even though it's not permitted as a minterm, where each variable can only show up once.

There is a similar analog to a product term called a sum term.

Minimization

There are some techniques for minimizing Boolean functions. For example, both Karnaugh Maps and Quine-McCluskey attempt to minimize the number of product terms first, and then to minimize the total number of literals second (if there's a tie using only product terms).

We won't discuss minimization.

Summary

Here are the key points:

A literal is either a Boolean variable or its negation.
Negation of a variable is written with a backslash before the variable (e.g. \x). Some books use an overbar.
AND is written with a multiplication sign, *. Sometimes the multiplication sign is left out, assuming the reader recognizes multiplication as in arithmetic (thus, xy is the same as x * y).
OR is written with a + sign.
Since AND and OR are associative, there's no need to parenthesize expressions consisting solely of ANDs or sole of ORs. All ways of parenthesizing produces equivalent Boolean functions.
A minterm of k variables consists of k literals where each variable shows up exactly once, either as a positive or negative literal. This produces a truth table with exactly one 1 as output.
Any truth table, except the all-zero output truth table, can be written as a sum of minterms, which is also called sum of products and conjunctive normal form.
The all-zero truth table can be written as z = 0.
Boolean functions can be minimized, but we won't do so.

Web Accessibility