in reply to simplify logical equations

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!

Replies are listed 'Best First'.
Re^2: simplify logical equations
by ysth (Canon) on Oct 19, 2004 at 10:30 UTC
    (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.

Re^2: simplify logical equations
by thealienz1 (Pilgrim) on Oct 19, 2004 at 09:07 UTC

    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.