Sat, 26 Feb 1994 20:48:24 GMT

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.