Velocity Reviews > Java > How to simplify logical expressions?

# How to simplify logical expressions?

Gerhard Rapp
Guest
Posts: n/a

 07-29-2003
Hello all.

I'm writing a program that identifies some kind of objects in a data
repository. These objects have conditions. For instance ((r=NN) and (x=AR))
or something like that. In some cases the conditions of two or more objects
should be combined. E.g. ((r=NN) and (x=AR)) combined with (r=NN) combined
with (x=L) should evalutate to ((r=NN) or (x=L)).

Has anyone solved a problem like that before? May be someone can at least
give a hint?

Thanks
Gerhard

Chris Smith
Guest
Posts: n/a

 07-30-2003
Gerhard Rapp wrote:
> I'm writing a program that identifies some kind of objects in a data
> repository. These objects have conditions. For instance ((r=NN) and (x=AR))
> or something like that. In some cases the conditions of two or more objects
> should be combined. E.g. ((r=NN) and (x=AR)) combined with (r=NN) combined
> with (x=L) should evalutate to ((r=NN) or (x=L)).
>
> Has anyone solved a problem like that before? May be someone can at least
> give a hint?

I did in fact solve a similar problem recently. Roedy is right, of
course: working with a semantic form such as an expression tree, as
opposed to a flat text format, is absolutely essential.

My advice is to get yourself a good book on boolean algebra. In
particular, DeMorgan's law, and the properties of distributability of
boolean operators should be useful. Using those two properties plus
some form of sorting of terms, it's possible to transform any logical
statement into a single canonical form with only three levels of
operators: OR, AND, and NOT. That makes it easier to eliminate
redundant subexpressions, recognize logical inverses and equivalencies
in simplifying).

It's also important to note (and I initially forgot when approaching the
problem) that (A and B) is equivalent to (A and (B, if A is true)), and
that (A or B) is equivalent to (A or (B, if A is false)). That
simplifies a lot of things away by producing tautologies and

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

Peter Schoaff
Guest
Posts: n/a

 07-30-2003
"Gerhard Rapp" <(E-Mail Removed)> wrote in message news:<bg6re1\$df7\$01\$(E-Mail Removed)-online.com>...
> Hello all.
>
> I'm writing a program that identifies some kind of objects in a data
> repository. These objects have conditions. For instance ((r=NN) and (x=AR))
> or something like that. In some cases the conditions of two or more objects
> should be combined. E.g. ((r=NN) and (x=AR)) combined with (r=NN) combined
> with (x=L) should evalutate to ((r=NN) or (x=L)).
>
> Has anyone solved a problem like that before? May be someone can at least
> give a hint?
>
> Thanks
> Gerhard

Do a search on Karnaugh Map. It's a method of minimizing a boolean
expression from an n-variable truth table.