Re: Truth table evaluation (Benjamin Cohen )
Sat, 26 Feb 1994 20:48:24 GMT

          From comp.compilers

Related articles
Truth table evaluation (Philip Riebold) (1994-02-25)
Re: Truth table evaluation (1994-02-26)
Re: Truth table evaluation (1994-02-26)
Re: Truth table evaluation (1994-02-28)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (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.


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)

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 2200 Mission College Blvd
(408) 765-4977 Santa Clara, CA 95052

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.