Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

simplify logical equations

by thealienz1 (Pilgrim)
on Oct 19, 2004 at 08:47 UTC ( #400434=perlquestion: print w/replies, xml ) Need Help??

thealienz1 has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks

I have been working a program for quite some time now, and well I have gotten to a certain point, which I have stumped myself. What else is new?

Currently I am running a program that generates logical equestions, for example: a0 AND a1 OR d0. My program uses AND, OR for operators and a0,a1,d0,d1,d2,d3 for variables. I noticed as my program runs I get into a certain problem. Becuase my equations progressivly get bigger and bigger I get stuck with enormous equations, but some that have repeating values.

By repeating values take a look at the following equation:
a0 AND a0 OR d1 OR d1 AND d0

This equations can be simplified to a simpler equation:
a0 OR d1 AND d0
because value that are AND with itself or ORed is just its original value.

I was using regex, but just wanted to see others solution to the problem.

Regards,
Justin Archie

Replies are listed 'Best First'.
Re: simplify logical equations
by Corion (Pope) on Oct 19, 2004 at 08:55 UTC

    This really depends on what you consider "simplified". If you mean just the basic eliminations of a OR a, then you can easily approach that with a two step algorithm:

    1. Bring the equation correctly into a sorted form by (correctly!) exploiting the commutativity of AND and OR.
    2. Use a regex or anything else to substitute a AND a by a and a OR a by a

    If you want a more thourough reduction of terms, for example, a reduction of a AND b OR NOT a AND b to b (assuming standard precedence of AND like * and OR like +), then you will have to employ some less braindead techniques, like bringing the expression into conjunctive (AND terms connected by OR) or disjunctive (OR terms connected by AND) normal form, sorting the terms and then reading off the truth table and eliminating the variables that have no bearing on the result.

    b OR a AND b OR c AND a # first, add parentheses for better disambiguation: (b) OR (a AND b) OR (c AND a) # now, sort the AND terms alphabetically, exploiting # the commutativity of AND (b) OR (a AND b) OR (a AND c) # sort the outer terms alphabetically, exploiting # the commutativity of OR (a AND b) OR (a AND c) OR (b) # this is the conjunctive normal form (I think)

    The above term has a true value if any of the AND terms have a true value. To get at the disjunctive normal form, do the same thing except that you want to have the OR inside and the AND on the outside - beware of the precedence though!

      (a AND b) OR (a AND c) OR (b)
      Since "OR b" is there, the "(a AND b)" can be dropped, since it will only be true when b is. This yeilds: (a AND c) OR b, but I have no idea how you would do that programmatically; perhaps build an n-dimensional truth table (where n is the number of variables) and come up with an algorithm to efficiently render that back into boolean terms.

        You can approach that by "simple" stepwise elimination:

        1: (a AND b) OR (a AND c) OR (b)

        We know that the term evaluates true iff one of the OR terms evaluates to a true value. So if we start looking at b, we know that the term evaluates true whenever b has a true value. Therefore, we can rewrite it as

        2: b OR (X)

        where X is the result of the evaluation of the term 1: with b a false value:

        3: b OR (a AND false) OR (a AND c) OR (false)

        Now, we can apply one round of simplification again, replacing Y AND false by false and false OR Z by Z (modulo commutativity):

        4: b OR (a AND c)

        How one would really encapsulate the reduction of such terms to a "appealing" form in the sense that it has the fewest number of variables or whatever, I don't know, but I guess the idea is to split up any term X OR Yinto the form (true OR Y) OR (false OR Y)

        and then simplifying again, for Y being an atomar truth variable. Whenever you can't find a suitable Y, you have to create a synthetic truth variable Y' := Y'' AND Y''', where Y'' and Y''' are (possibly synthetic) truth variables. This amounts more or less to building the complete truth table.

      I see your logic, but as of right now I have neither the brain power or now how to implement that solution in Perl. Thanks though... I will try.

Re: simplify logical equations
by zentara (Archbishop) on Oct 19, 2004 at 11:54 UTC
    Do a google or groups.google search for DeMorgan's Laws. It is a set of simple rules for reducing logic equations to their simplest form. They are used by logic circuit designers all the time to convert all their logic to nor or nand gates,to facilitate circuit design. It would seem that some Perl Coder would have incorporated them into a module by now, but maybe there is a roadblock.

    Maybe Math::Logic would help you?


    I'm not really a human, but I play one on earth. flash japh
Re: simplify logical equations
by periapt (Hermit) on Oct 19, 2004 at 13:18 UTC

    There are a couple of algorithms that do what you are asking. Karnaugh Maps and the Quine-McClusky Method are two that I can think of. Q-M is more suited to computer solutions I think. There doesn't seem to be a CPAN module that implements it though. Freshmeat has a project for it at http://freshmeat.net/projects/qmc/. Maybe you should shell out the simplification stage?

    PJ
    use strict; use warnings; use diagnostics;
Re: simplify logical equations
by Anonymous Monk on Oct 19, 2004 at 12:25 UTC

    Hmm, do AND and OR have the same precedence, or doesn't it matter at all?

    As in, can you repost your original equation, but with brackets added?
    I see too many possiblities to interpret it. For example:

    • ((a0 AND a0) OR (d1 OR d1)) AND d0 ==> (a0 OR d1) AND d0
    • (a0 AND a0) OR ((d1 OR d1) AND d0) ==> a0 OR (d1 AND D0)
    • a0 AND (a0 OR d1 or d1) AND d0 ==> a0 AND d0
    • a0 AND (a0 OR (d1 OR (d1 AND d0))) ==> a0
    • ...

Re: simplify logical equations
by TedPride (Priest) on Oct 19, 2004 at 12:32 UTC
    Well, depends on what you're going to be doing with the expressions. If the object is to generate complex expressions and then simplify them as much as possible, not worrying about cycles (maybe the result will be used millions of times in future programs?), then you can divide the expression into sections and test each section for all possible combinations of true / false, replacing sections that are always true or always false with a 1 or 0. If on the other hand you just want to get the results of a complex expression in as efficient a manner as possible, you can do something like the following:
    my %vals = ('AND' => '&&', 'OR' => '||', 'XOR' => '^', 'NOT' => '!'); my $logic; while ($logic = <DATA>) { chomp($logic); while(<DATA>) { chomp; last if (!$_); split(/ = /); $vals{@_[0]} = @_[1]; } print "$logic\n"; $logic =~ s/(\w+)/$vals{$1}/g; print "$logic\n"; print eval($logic) . "\n\n"; } __DATA__ a0 OR d1 AND d0 a0 = 1 d1 = 0 d0 = 1 d1 AND e1 AND f0 e1 = 1 f0 = 0

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://400434]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (4)
As of 2019-10-19 07:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?