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
Re: simplify logical equations
by Corion (Patriarch) 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:
- Bring the equation correctly into a sorted form by (correctly!) exploiting the commutativity of AND and OR.
- 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! | [reply] [d/l] |
|
(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.
| [reply] [d/l] [select] |
|
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. | [reply] [d/l] [select] |
|
| [reply] |
Re: simplify logical equations
by zentara (Archbishop) on Oct 19, 2004 at 11:54 UTC
|
| [reply] |
Re: simplify logical equations
by periapt (Hermit) on Oct 19, 2004 at 13:18 UTC
|
| [reply] |
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
- ...
| [reply] [d/l] [select] |
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
| [reply] [d/l] |
|
|