This lesson is a continuation of Lesson 2.  In this lesson we will explore some of the basic theorems of Boolean Algebra.   There is little difference between the theorems discussed here and the laws presented in the preceding lesson.  We will use the same procedures to prove their correctness, namely exhaustive induction and experimental verification.  We   will proceed from the basic theorems to canonical forms for Boolean expressions and functions.

The following table gives some of the basic theorems of Boolean Algebra.

Equation	Theorem
(ab)’ = a’+b’	Demorgan’s Laws
(a+b)’ = a’b’	Demorgan’s Laws
a+a = a	Idempotency
aa = a	Idempotency
(a’)’ = a	Involution
a+1 = 1	Absorption
a•0 = 0	Absorption
a+ab = a	Absorption
a(a+b) = a	Absorption

Use the following windows to construct verification circuits for each theorem, and simulate each circuit with all possible inputs.

Enter your circuits here.

Once a circuit is complete, type your inputs in the box below.

Canonical Forms

When creating a switching circuit, the first step is to derive a Boolean expression that describes the behavior of the circuit.  A common starting point is a list of the input combinations that will produce the value one.  The first step is to create a Boolean expression for each input combination.  This expression will have the value one for the particular input combination, and the value zero for every other input combination. An expression of this type is called a minterm.  To create a minterm for a particular input combination, simply AND all input variables together, and complement the variables that correspond to the zero inputs.  For the input combination a=0, b=1, c=0, d=1 we would create the minterm a'bc'd. A complete expression for the function can be created by ORing all minterms together.   Because both AND and OR are commutative and associative, the order of the variables and minterms is unimportant, and parentheses are not required.

It is also possible to start with a list of all input combinations that produce the value zero.  In this case, we create a maxterm for each input combination. To create a maxterm for an input combination, OR all input variables together, and complement the variables that correspond to the one inputs.  Thus for the input combination  a=0, b=1, c=0, d=1 we would create the minterm a+b'+c+d'. A maxterm has the value zero for the chosen input combination and the value one for every other input combination. The complete expression for the function is created by ANDing all maxterms together.  Because AND has precedence over OR, each maxterm must be enclosed in parentheses.

The following table lists all minterms and maxterms for three-input functions.

One common method for specifying Boolean Functions is as a truth table, such as the following. At this point we will assume that the truth table has been created by carefully considering the requirements of a particular design.  In later lessons, we will perform an analysis of requirements to create such tables.

Input Combination	Value	Minterm
0,0,0	0
0,0,1	1	a’b’c
0,1,0	1	a’bc’
0,1,1	0
1,0,0	0
1,0,1	0
1,1,0	1	abc’
1,1,1	1	abc

In the truth table, we have retained the minterms for those input combinations that should produce the value one.  The complete function specification can be created by adding up these minterms.  The result would be f(a,b,c)=a'b'c+a'bc'+abc'+abc.

A similar procedure can be used to create a function specification that is a product of maxterms.  We begin with the following table for the same function.

Input Combination	Value	Maxterm
0,0,0	0	a+b+c
0,0,1	1
0,1,0	1
0,1,1	0	a+b’+c’
1,0,0	0	a’+b+c
1,0,1	0	a’+b+c’
1,1,0	1
1,1,1	1

In this case we have retained the maxterms for the input combinations that must produce the output zero.  To create the complete function specification, we multiply the maxterms together.  Because AND has precedence over OR, it is necessary to use parentheses around each maxterm.  The complete function specification is f(a,b,c)=(a+b+c)(a+b’+c’)(a’+b+c)(a’+b+c’).

It is possible to translate either of these specifications into FHDL.   Doing so will enable us to use the editor windows to verify the correctness of our function specifications, and our FHDL coding.  The sum of maxterms specification is translated into FHDL as follows.

Spec1:	circuit
	inputs	a,b,c
	outputs	q
n1:	not	a,ap
n2:	not	b,bp
n3:	not	c,cp
a1:	and	(ap,bp,c),x1
a2:	and	(ap,b,cp),x2
a3:	and	(a,b,cp),x3
a4:	and	(a,b,c),x4
o1:	or	(x1,x2,x3,x4),q
	endcircuit

Generally when constructing a circuit for a Boolean function, we assume that both the complemented and uncomplemented form of each input is already available.  This is often true when constructing a large circuit out of several Boolean functions.  However, when simulating in FHDL, it is better to supply only the uncomplemented form of the inputs, and use NOT gates to create the complemented forms.  This will simplify the simulation process.

Note that when converting a Boolean expression into FHDL, it is possible to use AND and OR gates with an arbitrary number of inputs.  In a real circuit, there will usually be a limit on the number of inputs that a gate can have.   This is known as the fanin limit. Also note that it is necessary to assign names to the outputs of the AND gates, x1, x2, x3, and x4.  These names can be chosen at random, but the same names must be used for the outputs of the AND gates and the inputs of the OR gate.  Names can consist of an arbitrary string of letters and numbers, but must begin with a letter. There is a limit of 500 characters for each name.

It is also possible to convert the sum of maxterms expression into FHDL.  The following FHDL specification illustrates how this is done. (a+b+c)(a+b’+c’)(a’+b+c)(a’+b+c’)

Spec2:	circuit
	inputs	a,b,c
	outputs	q
n1:	not	a,ap
n2:	not	b,bp
n3:	not	c,cp
o1:	or	(a,b,c),x1
o2:	or	(a,bp,cp),x2
o3:	or	(ap,b,c),x3
o4:	or	(ap,b,cp),x4
a1:	and	(x1,x2,x3,x4),q
	endcircuit

It is possible to specify truth tables in a more compact form by specifying the list of inputs for which the function has the value one, or the list of inputs for which the function has the value zero.  Values are expressed in decimal rather than binary. The list of ones for the preceding function would be written as follows. S(1,2,6,7).  The list of zeros would be specified as P(0,3,4,5).

The sum of minterms and product of maxterms are examples of two canonical forms used to specify Boolean functions.  The sum of minterms is an example of a more general form known as sum of products. The sum of products form is similar to the sum of minterms, but some terms may not contain every variable.  The function f(a,b,c)=a+bc is an example of the sum of products form.  The sum of products form is also known as Disjunctive Normal Form or DNF.

Similarly, the product of minterms is an example of the product of sums form.  In product of sums form, it is not necessary for each variable to appear in each factor, as in the specification f(a,b,c)=(a+b)(b'+c').  The product of sums form is also known as Conjunctive Normal Form or CNF.

The circuits produced from the sum of products and product of sums forms are known as two-level circuits, because the input signals must flow through no more than two gates to reach the output.  (The NOT gates used to produce complemented inputs are not counted.)

You should now try some of this on your own. The following table gives the truth table for three Boolean functions. Construct two circuits for each function, one that is a sum of minterms, and one that is a product of maxterms. Simulate both circuits using the windows supplied above.

Minimization of Boolean Functions

Although it is possible to specify any Boolean function in sum of minterms form, the expressions are often much more complicated than necessary.   Consider the following truth table.

Input Combination	Value	Minterm
0,0,0	1	a'b'c'
0,0,1	1	a'b'c
0,1,0	1	a'bc'
0,1,1	1	a'bc
1,0,0	0
1,0,1	0
1,1,0	1	abc'
1,1,1	1	abc

This would result in a function specification of f(a,b,c)=a'b'c+a'b'c+a'bc'+a'bc+abc'+abc.  The equivalent circuit would contain six AND gates, and one six-input OR gate.  The OR gate would probably exceed fanin limits and have to be broken into two OR gates as follows.

o1:	or	(x1,x2,x3),z1
o2:	or	(z1,x4,x5,x6),q

Using the laws of Boolean Algebra, and the theorems listed above, it is possible to simplify the sum of minterms expression.

a'b'c' + a'b'c + a'bc' + a'bc + abc' + abc	Original expression
a'(b'c' + b'c + bc' + bc) + abc' + abc	Distributive law
a'(b'(c' + c) + bc' + bc) + abc' + abc	Distributive law
a'(b'1 + bc' + bc) + abc' + abc	Or inverse law
a'(b' + bc' + bc) + abc' + abc	Or Identity
a'(b' + b(c' + c)) + abc' + abc	Distributive law
a'(b'+b1)+abc'+abc	Or inverse law
a'(b'+b)+abc'+abc	Or Identity
a'1+abc'+abc	Or inverse law
a'+abc'+abc	Or Identity
a'+ab(c'+c)	Distributive law
a'+ab1	Or inverse law
a'+ab	Or Identity

Although this expression a'+ab is far simpler than the original, requiring only one two-input AND gate and one two-input OR gate, it is not the simplest expression we could derive for this function.  There are several ways we could proceed, but the clearest is to begin with the original expression, and apply the Idempotency law to the terms a'bc' and a'bc.  This would result in the following derivation.

a'b'c' + a'b'c + a'bc' + a'bc + abc' + abc	Original expression
a'b'c' + a'b'c + a'bc' + a'bc' + a'bc + abc' + abc	Idempotency
a'b'c' + a'b'c + a'bc' + a'bc' + a'bc + a'bc + abc' + abc	Idempotency
a'b'c' + a'b'c + a'bc' + a'bc + a'bc' + a'bc + abc' + abc	Commutative Law
a' + a'bc' + a'bc + abc' + abc	As above
a' + b(a'c' + a'c + ac' + ac)	Distributive law
a' + b	Similar to above

The missing steps in this derivation are left as an exercise for the reader.

It is also possible to apply the absorption law to the expression a'+ab to obtain a' + a'b + ab, which reduces to a' + (a' + a)b, giving the same result.

The laws given in this lesson and in lesson 2 can be used to reduce complex Boolean expressions to simpler forms.

The following functions are more complicated than necessary. Simplify these functions using the theorems listed above and the basic laws described in Lesson 2. Once you have reduced these functions, construct two circuits, one corresponding to the original expression, and one corresponding to the reduced expression. Simulate each using all input combinations to verify that they are the same.

ab+ab'

(a+b)(a+b')

abc+a'b+abc'

The course continues with Lesson 4.

---

Text Editor windows are implemented with BenetTec's AllText 4.5 control.
Drawings are from the Dover Old Fashioned Clip Art series.
Except as noted above, this page, its contents and ActiveX controls are Copyright (c) 1999, Peter M. Maurer
For comments and complaints send mail to Peter_Maurer@Baylor.edu.
Home page http://cs.baylor.edu/~maurer