Re: Truth table evaluation

ashok@cse.iitb.ernet.in (Ashok Sreenivas)Mon, 28 Feb 1994 11:25:54 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: ashok@cse.iitb.ernet.in (Ashok Sreenivas) Keywords: optimize, theory Organization: Computer-Sc-Dept, IIT-Bombay-76, INDIA References: 94-02-189 Date: Mon, 28 Feb 1994 11:25:54 GMT

Philip Riebold (philip@livenet.ac.uk) writes:

: I have an application that generates arbitrary postfix boolean expressions
: such as

: a b AND c b NOT AND OR END

: ... I need to evaluate the truth table for the expression.

As it happens, we did a very similar thing for one of our course projects
here. The approach we adopted was to, in some sense "minimise" the
expression that has to be evaluated. We did this by first reducing the
expression to have only two operators (in our case AND and XOR - all the
others can be expressed as combinations of these). Then we "flattened"
our expression tree so that it looked like this :

XOR ( t1, t2, ... tn)

where each of the ti is either a leaf node or a AND node. Within each of
these subtrees (XOR or AND), we then sorted the operands and applied
trivial reduction rules (such as x XOR x = F, x AND x = x etc.). The
final form is the "minimal" form of the expression, on which you can then
try all combinations of values etc.

Hope this helps.

- Ashok.

Ashok Sreenivas,
Dept. of Computer Sc. and Engg,
IIT, Bombay - 400 076.
(ashok@cse.iitb.ernet.in)
--

Post a followup to this message