Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re: Walking a boolean tree to produce matching inputs

by LanX (Cardinal)
on Mar 20, 2014 at 18:56 UTC ( #1079132=note: print w/replies, xml ) Need Help??

in reply to 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)


  • 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.
  • Log In?

    What's my password?
    Create A New User
    Node Status?
    node history
    Node Type: note [id://1079132]
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others meditating upon the Monastery: (7)
    As of 2020-07-03 20:06 GMT
    Find Nodes?
      Voting Booth?

      No recent polls found