How to simplify logical expressions?

G

Gerhard Rapp

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
 
C

Chris Smith

Gerhard said:
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
(which make for contradictions or tautologies, and are immensely helpful
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
contradictions in subexpressions.

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

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
 
P

Peter Schoaff

Gerhard Rapp said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top