Boolean Functions Simplification
(Logic Minimization)

News

Site visits: 582693

Now supporting multi-level minimization up to 64 inputs/64 outputs with redesigned Quine-McCluskey and BDD programs.
Check some input data and result files...
A simple 5 input/5 output example is available to show the different ways of using the bfunc simplifiers...

Software and Links

bfunc for MSDOS: bfunc.zip - Boolean functions simplification (logic minimization) programs using Quine-McCluskey and BDD methods. This ZIP archive contains 32 bit executables that run on Linux or MS-Windows systems. It also includes input files, table generators, some documentation, etc.
espresso for MSDOS: espres23.zip - a MSDOS version of the well known logic minimization program (version 2.3).
"How Stuff Works" about boolean logic (nice introductory stuff)
Quine-McCluskey algorithm (in Wikipedia.org)
Logic design
KVD Demo (nice Java applet about Karnaugh Maps) Quine McCluskey minimization
Examples - Several input and output files from bfunc and espresso
Information - Information about bfunc parameters and constants
MS-Windows software - Old MS-Windows programs...

About

bfunc is a package for constructing or simplifying Boolean Functions from binary Truth (State) Tables, generating several kinds of output, from Truth Tables to Symbolic Equations, Binary Decision Trees, etc.
It can be considered an alternative to the Karnaugh Map method of simplifying boolean functions, etc.

This software package was originally written in Pascal (1986), but after translated to C using the p2c program (1989). This development started in my last year in the Engineering Faculty of Porto and was continued at INESC-Porto.
The code is available to everybody. Please send a message to António Costa if interested...

Available implementations are:

Global - Boolean Simplification of all the output functions simultaneously (multi-level), using the Quine-McCluskey method, and generation of:
- Truth Table (optional);
- Symbolic Equations (optional);
- General Statistics (optional).
Local - Boolean Simplification of each output function (two-level), independently of the others, using the Quine-McCluskey method, and generation of:
- Truth Table (optional);
- Symbolic Equations (optional);
- General Statistics (optional).
Quasi-optimal Local - Boolean Simplification of each output function, using the Binary Decision Diagram method (two-level), and generation of:
- Binary Decision Tree (optional);
- Symbolic Equations (optional);
- General Statistics and Tree Evaluation Statistics (optional).

Example data

7 Segment Decoder
18-MAY-1988
############# Inputs ############
B3 HIGH Code MSBit
B2 HIGH Code 2nd MSBit
B1 HIGH Code 3rd MSBit
B0 HIGH Code LSBit
############ Outputs ############
A HIGH 0 Segment 1
B HIGH 0 Segment 2
C HIGH 0 Segment 3
D HIGH 0 Segment 4
E HIGH 0 Segment 5
F HIGH 0 Segment 6
G HIGH 0 Segment 7
############ Options ############
Read Mode =0
Table/Tree=0
Equations =3
Statistics=0
########## Truth table ##########
0000 1111110 '0'
0001 0110000 '1'
0010 1101101 '2'
0011 1111001 '3'
0100 0110011 '4'
0101 1011011 '5'
0110 1011111 '6'
0111 1110000 '7'
1000 1111111 '8'
1001 1111011 '9'
1010 1110111 'A'
1011 0011111 'b'
1100 1001110 'C'
1101 0111101 'd'
1110 1001111 'E'
1111 1000111 'F'

This input file defines all data for a 7 Segment Decoder. Things to notice:

there are 4 input signals, all active high (binary code);
there are 7 output signals, all active high (one for each segment);
we want the NOT SUM OF PRODUCTS form of equations, for all outputs;
we only want the equations;
we describe how the inputs affect the outputs through the truth table, with 1 term per line (in this example, each term is equal to a minterm).

Global Simplification

##### Boolean Functions

Total Terms           : 15
Total Prime Imps      : 22
1st reduced Prime Imps: 14
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 1
<Redundant> Prime Imps: 0
<Essential> Prime Imps: 15

##### Boolean Equations

TERM_1=/B2*/B1*B0
TERM_2=/B3*B1*B0

2 Term Common Expressions

PRIME_1=/B3*B2*/B1*/B0
PRIME_2=TERM_1*/B3
PRIME_3=B3*B2*/B1*/B0
PRIME_4=B3*/B2*B1*B0
PRIME_5=B3*B2*/B1*B0
PRIME_6=B3*B2*B1
PRIME_7=/B3*B2*/B1*B0
PRIME_8=/B3*/B2*B1*/B0
PRIME_9=TERM_2

9 Prime Imps Common Expressions

/A=PRIME_1
  +PRIME_2
  +PRIME_4
  +PRIME_5

/B=PRIME_3
  +PRIME_4
  +PRIME_6
  +PRIME_7
  +B2*B1*/B0

/C=PRIME_3
  +PRIME_6
  +PRIME_8

/D=PRIME_1
  +PRIME_2
  +B2*B1*B0
  +B3*/B2*B1*/B0

/E=PRIME_1
  +PRIME_7
  +PRIME_9
  +TERM_1

/F=PRIME_2
  +PRIME_5
  +PRIME_8
  +PRIME_9

/G=PRIME_3
  +/B3*/B2*/B1
  +TERM_2*B2

Local Simplification

##### Boolean Functions

Total Terms: 15

##### Function A

Total Local Terms     : 4
Total Prime Imps      : 4
1st reduced Prime Imps: 4
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 4

##### Boolean Equation

/A=B3*/B2*B1*B0
  +B3*B2*/B1*B0
  +/B3*/B2*/B1*B0
  +/B3*B2*/B1*/B0

##### Function B

Total Local Terms     : 6
Total Prime Imps      : 5
1st reduced Prime Imps: 4
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 4

##### Boolean Equation

/B=B3*B1*B0
  +B2*B1*/B0
  +B3*B2*/B0
  +/B3*B2*/B1*B0

##### Function C

Total Local Terms     : 4
Total Prime Imps      : 3
1st reduced Prime Imps: 3
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 3

##### Boolean Equation

/C=B3*B2*B1
  +B3*B2*/B0
  +/B3*/B2*B1*/B0

##### Function D

Total Local Terms     : 5
Total Prime Imps      : 4
1st reduced Prime Imps: 4
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 4

##### Boolean Equation

/D=B2*B1*B0
  +B3*/B2*B1*/B0
  +/B3*/B2*/B1*B0
  +/B3*B2*/B1*/B0

##### Function E

Total Local Terms     : 6
Total Prime Imps      : 3
1st reduced Prime Imps: 3
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 3

##### Boolean Equation

/E=/B3*B0
  +/B2*/B1*B0
  +/B3*B2*/B1

##### Function F

Total Local Terms     : 5
Total Prime Imps      : 4
1st reduced Prime Imps: 4
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 4

##### Boolean Equation

/F=/B3*B1*B0
  +/B3*/B2*B0
  +/B3*/B2*B1
  +B3*B2*/B1*B0

##### Function G

Total Local Terms     : 4
Total Prime Imps      : 3
1st reduced Prime Imps: 3
2nd reduced Prime Imps: 0
3rd reduced Prime Imps: 0
<Essential> Prime Imps: 3

##### Boolean Equation

/G=/B3*/B2*/B1
  +/B3*B2*B1*B0
  +B3*B2*/B1*/B0

There is also a small amount of information about the simplification, but the equations are slightly different from each method, because in GLOBAL mode, the program searches for partial logical products (first) and global logical products (after), and then shares them between the output functions (this is the multi-level phase).

A third possibility is to generate a Binary Decision Tree, which is converted to standard Sum of Products (this conversion step also reduces the number of literals, and, in some special cases, the number of logical products). Please note that the equation's set obtained may be, sometimes, not as fully optimized as if generated in LOCAL mode. Although, these particular cases are very rare and tend to disappear if the number of input variables grows (more than 7).

Quasi-optimal Local Simplification

##### Boolean Functions

Total Minterms: 15

##### Function A

Tree Compression: 0.0 %
Tree Density    : 89.47 %
Tree Depth      : 5
Total Nodes     : 11
Total Leaves    : 4

##### Boolean Equation

/A=/B3*/B2*/B1*B0
  +/B3*B2*/B1*/B0
  +B3*/B2*B1*B0
  +B3*B2*/B1*B0

Total Prime Imps: 4

##### Function B

Tree Compression: 17.2 %
Tree Density    : 87.18 %
Tree Depth      : 5
Total Nodes     : 10
Total Leaves    : 5

##### Boolean Equation

/B=/B3*B2*/B1*B0
  +B2*B1*/B0
  +B3*B1*B0
  +B3*B2*/B0
  +B3*B2*B1

Total Prime Imps: 5

##### Function C

Tree Compression: 25.81 %
Tree Density    : 82.61 %
Tree Depth      : 5
Total Nodes     : 7
Total Leaves    : 3

##### Boolean Equation

/C=/B3*/B2*B1*/B0
  +B3*B2*/B0
  +B3*B2*B1

Total Prime Imps: 3

##### Function D

Tree Compression: 19.5 %
Tree Density    : 91.18 %
Tree Depth      : 5
Total Nodes     : 10
Total Leaves    : 4

##### Boolean Equation

/D=/B2*/B1*B0*/B3
  +/B2*B1*/B0*B3
  +B2*/B1*/B0*/B3
  +B2*B1*B0

Total Prime Imps: 4

##### Function E

Tree Compression: 50.0 %
Tree Density    : 86.36 %
Tree Depth      : 5
Total Nodes     : 7
Total Leaves    : 3

##### Boolean Equation

/E=/B3*B2*/B1
  +/B3*B0
  +B0*/B2*/B1

Total Prime Imps: 3

##### Function F

Tree Compression: 20.0 %
Tree Density    : 87.50 %
Tree Depth      : 5
Total Nodes     : 9
Total Leaves    : 4

##### Boolean Equation

/F=/B3*/B2*B0
  +/B3*/B2*B1
  +/B3*B1*B0
  +B3*B2*/B1*B0

Total Prime Imps: 4

##### Function G

Tree Compression: 24.24 %
Tree Density    : 88.0 %
Tree Depth      : 5
Total Nodes     : 8
Total Leaves    : 3

##### Boolean Equation

/G=/B3*/B2*/B1
  +/B3*B2*B1*B0
  +B3*B2*/B1*/B0

Total Prime Imps: 3

The Quine-McCluskey Method

The Quine-McCluskey Method gives an algorithm to simplify a logical expression that is in disjunctive normal form, to obtain an equivalent minimal disjuction of conjuctions (sum of products). It is based on repeated applications of the distributive law and the fact that p OR (NOT p) is always true. For example: (denoting (NOT x) by ~x)

xyz + x~yz = x(y + ~y)z = x(TRUE)z = xz

Thus the two minterms can be simplified to one term with one fewer character. The Quine-McCluskey method gives us a systematic way of selecting the pairs that we use for this simplification.

The Rewrite Step

The first step in the process is to rewrite each minterm using 1's and 0's in place of the literals. A literal itself (say x) is replaced by 1 and its negation (~x) is replaced by 0. Then xyz becomes 111 and ~xyz becomes 011, and w~xy~z becomes 1010. This representation is called the bit string form.

We illustrate the Method with an example. Suppose we are given the logical expression

xyz + ~x~yz + x~yz + ~x~y~z + ~xyz

to simplify. We convert each minterm to its bit string form and arrange them in a table ordered according to the number of 1's that appear in the bit string. The minterm with the largest number of 1's in its bit string appears first and the rest appear in order of decreasing numbers of 1's in the bit strings.

No. Minterm	Bit String   	Number of 1's
1   xyz		111		3
2   x~yz        101		2
3   ~xyz	011		2
4   ~x~yz	001		1
5   ~x~y~z	000		0

The Reduction Step

If two bit strings agree in all but one bit (like 111 and 101), the two corresponding minterms agree in all but one literal, and that literal appears in one minterm and its negation appears on the other minterm. Using the two minterms numbered 1 and 2, with bitstrings 111 and 101, as an example, we have xyz and x~yz, which is the example given above. This simplifies to xz, with y eliminated from the minterm. We want to keep track of which literal was eliminated so we denote the bit string of xz by 1-1, the dash indicating that the y was eliminated. Since xyz + xyz = xyz, we can use xyz as many times as we wish to eliminate literals, so we use it again combining the terms numbered 1 and 3. We now expand our table to be:

#'s Used| Term   | Bit String | # of 1's |
--------|--------|------------|----------|
1       | xyz    | 111        | 3        |
2       | x~yz   | 101        | 2        | 
3       | ~xyz   | 011        | 2        | 
4       | ~x~yz  | 001        | 1        | 
5       | ~x~y~z | 000	      | 0        | 
--------|--------|------------|----------|
1,2     | xz     | 1-1        | 2        |
1,3     | yz     | -11        | 2        |
2,4     | ~yz    | -01        | 1        |
3,4     | ~xz    | 0-1        | 1        |
4,5     | ~x~y   | 00-        | 0        |
------------------------------------------

The new terms all contain two literals. We next apply the same procedure to eliminate those terms that have bit strings differing in one bit. Looking at the list of bit strings in the last column, we see that the strings in rows marked 1,2 and 3,4 differ in one bit, and the strings in rows marked 1,3 and 2,4 differ by one bit. Using rows marked 1,2 and 3,4, we get a new row for which the bit string is --1, the corresponding term is z, and we now used 1,2,3,4 (having combined 1,2 and 3,4). Thus we have the new entry

 
	  REDUCTION TABLE
#'s Used |Term    | Bit String | # of 1's |
---------|--------|------------|----------|
1        | xyz    | 111        | 3        |
2        | x~yz   | 101        | 2        | 
3        | ~xyz   | 011        | 2        | 
4        | ~x~yz  | 001        | 1        | 
5        | ~x~y~z | 000	       | 0        | 
---------|--------|------------|----------|
1,2      | xz     | 1-1        | 2        |
1,3      | yz     | -11        | 2        |
2,4      | ~yz    | -01        | 1        |
3,4      | ~xz    | 0-1        | 1        |
4,5      | ~x~y   | 00-        | 0        |
---------|--------|------------|----------|
1,2,3,4  | z      | --1        | 1        |
-------------------------------------------

Combining rows marked 1,3 and 2,4 uses the same terms, and gives the same term, z, so we do not write it in our table. In general, if we have reached the point where the terms contain N literals, we combine those terms, where possible, to obtain terms containing N-1 literals. This continues until no more eliminations can be made. We have finished the reduction step.

The Selection Step

We now make a table in which the original minterms form the column headers.

         |(1) xyz |(2) x~yz |(3) ~xyz |(4) ~x~yz |(5) ~x~y~z |
--------------------------------------------------------------

We look at the Reduction Table and take the term with the fewest number of literals (in the last row). In our case, that is z. We see that minterms 1,2,3,4 were used to obtain it. The term z is now the label for the first row of the new table. We also put an asterisk under each minterm that was used.

         |(1) xyz |(2) x~yz |(3) ~xyz |(4) ~x~yz |(5) ~x~y~z |
--------------------------------------------------------------
z        |  *     |  *      |   *     |   *      |           |

We then go up the Term column of the Reduction Table from the term we have already selected to get to the first row that contains the number of a term that is missing from the list so far obtained. Notice that 5 was missing and this occurs in the row marked 4,5. Thus we write the term ~x~y as the next row label and put asterisks in the columns for minterms 4 and 5.

			   SELECTION TABLE
         |(1) xyz |(2) x~yz |(3) ~xyz |(4) ~x~yz |(5) ~x~y~z |
--------------------------------------------------------------
z        |  *     |  *      |   *     |   *      |           |
~x~y     |        |         |         |   *      |   *       |
--------------------------------------------------------------

We continue this process until we have asterisks in all columns or until we have no more terms in the Term column of the reduction table. We now form the expression obtained by taking the disjunction of all terms that appear as row labels in the Selection Table. Thus our simplified expression is

z + ~x~y

This method works for expressions with any number of literals.

Here is another example using four literals. Simplify

wxyz + wx~yz + wx~y~z + w~xy~z + w~x~y~z

		REDUCTION TABLE
#'s Used  |Term       | Bit String | # of 1's | 
----------|-----------|------------|----------|
1         |wxyz       | 1111       |  4       | 
2         |wx~yz      | 1101       |  3       | 
3         |wx~y~z     | 1100       |  2       |
4         |w~xy~z     | 1010       |  2       |
5         |w~x~y~z    | 1000       |  1       |
----------|-----------|------------|----------|
1,2       | wxz       | 11-1       |  3       |
2,3       | wx~y      | 110-       |  2       |
3,5       | w~y~z     | 1-00       |  1       |
4,5       | w~x~z     | 10-0       |  1       |
-----------------------------------------------

			   SELECTION TABLE
         |(1)wxyz |(2) wx~yz |(3) wx~y~z |(4) w~xy~z |(5) w~x~y~z |
-------------------------------------------------------------------
w~x~z    |        |          |           |  *        |  *         |
wx~y     |        |  *       |  *        |           |            |
wxz      |  *     |  *       |           |           |            |
-------------------------------------------------------------------

w~y~z + wx~y + wxy

This is one possible answer, but we could just as well have chosen w~y~z instead of wx~y, to get the Selection Table

			   SELECTION TABLE
         |(1)wxyz |(2) wx~yz |(3) wx~y~z |(4) w~xy~z |(5) w~x~y~z |
-------------------------------------------------------------------
w~x~z    |        |          |           |  *        |  *         |
w~y~z    |        |          |  *        |           |  *         |
wxz      |  *     |  *       |           |           |            |
-------------------------------------------------------------------

w~x~z + w~y~z + wxz

Thus there are several correct simplifications that are minimal.

Here is the last example.

xyz + x~yz + ~x~y~z

	       REDUCTION TABLE
#'s Used   | Term    | Bit String | # of 1's |
-----------|---------|------------|----------|
1          | xyz     | 111        | 3        | 
2          | x~yz    | 101        | 2        |
3          | ~x~y~z  | 000        | 0        |
-----------|---------|------------|----------|
1,2        | xz      | 1-1        | 2        |

	       SELECTION TABLE
         |(1) xyz |(2) x~yz |(3) ~x~y~z |
-----------------------------------------
xz       |  *     |  *      |           |
~x~y~z   |        |         |  *        |
-----------------------------------------

xz + ~x~y~z

Last update: 7-7-2009
António Costa

Boolean Functions Simplification(Logic Minimization)