Re: Truth table evaluation

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
--

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