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)
[download]

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)
[download]

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)
[download]

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)
[download]

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.

Maybe Math::Logic would help you?

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
• ...

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
[download]