Re^2: simplify logical equations

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

Comment on Re^2: simplify logical equations Select or Download Code

Replies are listed 'Best First'.
Re^3: simplify logical equations by Corion (Patriarch) on Oct 19, 2004 at 10:48 UTC
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 Y`into 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]

Replies are listed 'Best First'.

Re^3: simplify logical equations
by Corion (Patriarch) on Oct 19, 2004 at 10:48 UTC

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):

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]