# Re: Truth table evaluation

## bcohen@cad721.intel.com (Benjamin Cohen )Sat, 26 Feb 1994 20:48:24 GMT

From comp.compilers

Related articles
Truth table evaluation philip@livenet.ac.uk (Philip Riebold) (1994-02-25)
Re: Truth table evaluation norman@flaubert.bellcore.com (1994-02-26)
Re: Truth table evaluation bcohen@cad721.intel.com (1994-02-26)
Re: Truth table evaluation ashok@cse.iitb.ernet.in (1994-02-28)
| List of all articles for this month |

 Newsgroups: comp.compilers From: bcohen@cad721.intel.com (Benjamin Cohen ) Keywords: logic Organization: Product Devel Technology, INTeL Corporation, Santa Clara, CA References: 94-02-189 Date: Sat, 26 Feb 1994 20:48:24 GMT

You can transform the expression into Sum-of-Products notation. The truth
table will be true for each product term, and false elsewhere. Of course,
the transformation may be more expensive than evaluation in some cases.
Do you need the complete truth table ? This method will produce a truth
table with don't cares. You can expand them manually if you need the
complete table.

The transformation is just a matter of applying all your de Morgan's,
multiplying out all of the product terms, combining like literals, and
dropping any terms that contain a literal in both the normal and negated
form. You may want to keep track of duplicate terms in intermediate
expressions and drop these as they appear.

ex.

b NOT c AND a OR NOT b NOT c OR AND /(a+/bc)(/b+c)

apply de Morgan's recursively

a NOT b AND a NOT c NOT AND OR b NOT c OR AND (/ab+/a/c)(/b+c)

multiply and cancel terms

a NOT b AND c AND a NOT b NOT AND c NOT AND OR /abc+/a/b/c

so your truth table (reduced) is

a b c F(a,b,c)
F T T T
F F F T

and F everywhere else.

This works well for equations whose value is mostly F with only a sparse
number of T. For equations with sparse F, transform to Product-of-Sums.
If you can't predict - you may be better off doing the evaluation.
--
Benjamin C. Cohen Intel Corporation Mailstop: RN4-39
bcohen@scdt.intel.com 2200 Mission College Blvd
(408) 765-4977 Santa Clara, CA 95052
--

Post a followup to this message