Lisp: the Quine-McCluskey Algoritm and the Petrick's Method


This article describes a Lisp implementation of the Quine-McCluskey algoritm combined with the Petrick's method.

Please see the original article that describes the Quine-McCluskey algorithm. The Petrick's method was published as A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Bedford, Cambridge, MA, USA: Air Force Cambridge Research Center. AFCRC Technical Report TR-56-110. Unfortunately, I failed to find that report in the archives of the Defense Technical Information Center, apparently this document from 1956 was not digitised.

If you are not familiar with the subject, the best explanation among material that can be found online at no fee, in my opinion, are the slides from the 2003 CMUT329 by Dr. José Nelson Amaral, a professor in the CS Dept. at the University of Alberta, as well as the Handout #5 from 2016 CSEE E6861y by Dr. Steven Novick, a professor of Computer Science at Columbia University, I highly recommend both sources.

This implementation is intended for simplification of Boolean expressions in a formal language, not digital logic, hence it does not support don't care terms.

The distribution package is signed with my PGP key having the fingerprint of D853 E6A9 F0D1 E01C 4833 DF59 75F7 BBFB 009E 3949.

QUINE-MCCLUSKEY Dictionary

PRIME-IMPLICANTS nvars minterm-numbers
Compute prime implicants using the Quine-McCluskey algorithm. nvars specifies the number of variables and minterm-numbers is a list of minterm numbers.
PETRICK nvars implicants
Apply the Petrick's method to a list of prime implicants. nvars is the number of variables and implicants is the list of prime implicants as determined by PRIME-IMPLICANTS.
COMPUTE-TRUTH-TABLE vars form
Compute the truth table (that is, find the minterms) of a Lisp form. vars is a list of variables and form is a Lisp form that is evaluated for all possible combinations of variables given in var.
MINTERMS-TO-LISP vars implicants solutions
Build a Lisp form that corresponds to the shortest solution among those that were determined by PETRICK. vars is a list of variables, implicants is a list of implicants, and solutions is a list of solutions.
QUINE-MCCLUSKEY variables minterm-numbers
Build a List form that corresponds to the simplest solution that was found by application of PRIME-IMPLICANTS, PETRICK, and MINTERMS-TO-LISP.

Usage

Simplification of A̅BC̅D̅ + AB̅C̅D̅ + AB̅CD̅ + AB̅CD + ABC̅D̅ + ABCD:

  1. Translate the expression to Lisp and find its minterms:
    (QM:COMPUTE-TRUTH-TABLE '(A B C D)
                            '(OR (AND (NOT A) B (NOT C) (NOT D))
                                 (AND A (NOT B) (NOT C) (NOT D))
                                 (AND A (NOT B) C (NOT D))
                                 (AND A (NOT B) C D)
                                 (AND A B (NOT C) (NOT D))
                                 (AND A B C D))
    => (4 8 10 11 12 15)
  2. Simplify the expression:
    (QM:QUINE-MCCLUSKEY '(A B C D) '(4 8 10 11 12 15))
    => (OR (AND A C D) (AND A (NOT B) (NOT D)) (AND B (NOT C) (NOT D)))
  3. Translate the result to Boolean notation: ACD + AB̅D̅ + BC̅D̅.

Vadim Penzin, March 17th, 2018


I hereby place this article along with the accompanying source code into the public domain.
You are welcome to contact me by writing to dmcrypt at this domain.
I publish this information in the hope that it will be useful, but without ANY WARRANTY.
You are responsible for any and all consequences that may arise as the result of using this information.