Re: Walking a boolean tree to produce matching inputs

I would go top down.

The minimal solutions of:

... an AND expression are the smallest combinations of minimal solutions of subexpressions.
... an OR expression are the smallest of the minimal solutions of subexpressions.
.... an ATOM is the ATOM

A = min ([OR, green, yellow]) = min (min( "green") + min("yello") ) = min { {green}, {yellow} }
B = min ([OR, light, banana]) = min (min( "light") + min("banana")) = min { {light}, {banana} }
C = min( [AND, A, B]) = min ( A x B ) = min { {green}, {yellow} } x { {light}, {banana} }

It gets complicated if ATOMs are repeated, so you'll have to compute all possible solutions to find the minimas.

e.g. min ( ( a or b ) and ( a or c ) ) = { {a} } cause {a} x {a} = {a} and the other solutions like {b,a}, etc are bigger

HTH! :)

Cheers Rolf

( addicted to the Perl Programming Language)

updates

please note that this is related to transforming and minimizing terms. This rings a bell ... we used something like the Horner scheme to solve such tasks at my first year in university... :)

you can also approach this with logical operations on bit-vectors representing the truth tables, but be aware that already 10 atoms would require 1024 bit strings to do so.

Comment on Re: Walking a boolean tree to produce matching inputs Select or Download Code


Just another Perl shrine
	PerlMonks