Decrease Boolean Expression

Question

I have an expression, suppose

a = 1 && (b = 1 || b != 0 ) && (c >= 35 || d != 5) && (c >= 38 || d = 6) 

I expect it to be reduced to

 a = 1 && b != 0 && (c >= 38 || d = 6) 

Does anyone have any suggestions? Pointers to any algorithm?

Nota Bene: The Carnot or Quine-McCluskey map is not an option here, I think. Because these methods do not handle gray cases. I mean, an expression can only be reduced as long as something like: A or 'or nothing, or say black or white or a missing color. But here I have gray shades, as you guys see.

Solution: I wrote a program for this in Clojure. I used a map card containing a function as a value. This is very convenient, just a few rules for several combinations, and you are good. Thanks for your helpful answers.

Answer 1

I think you can achieve what you want using the Restriction Restriction Rules . You will need to write rules that simplify OR and AND expressions.

The main difficulty will be checking for restrictions, which tells you which parts you can drop. For example, (c> = 35 || d! = 5) && (c> = 38 || d = 6) simplifies to (c> = 38 || d = 6), because the former is connected with the latter, i.e. . the latter is more specific. For OR expressions, you will need to choose a more general part.

Google found a document on the CHR extension with access control for user restrictions . I don’t know enough CHR to be able to tell you if you need such an extension.

Answer 2

I believe that such things are done regularly in logical programming constraints . Unfortunately, I'm not experienced enough to provide more accurate data, but this should be a good starting point.

The general principle is simple: an unbound variable can have any value; since you test it for inequalities, the set of possible values ​​is limited to one or more intervals. When / if these intervals converge to a single point, this variable is tied to this value. If, OTOH, any of these inequalities is considered unsolvable for each value in the intervals, a logic [programming] error occurs.

See also this , for example, how it is done in practice using swi-prolog. We hope you find links or links to the main algorithms so that you can play them on your platform of choice (perhaps even when searching for ready-made libraries).

Update: I tried to reproduce your example using swi-prolog and clpfd, but did not get the expected results, only close ones. Here is my code:

 ?- [library(clpfd)]. simplify(A,B,C,D) :- A #= 1 , (B #= 1 ; B #\= 0 ) , (C #>= 35 ; D #\= 5) , (C #>= 38 ; D #= 6). 

And my results, with backtracking (line breaks inserted for readability):

 10 ?- simplify(A,B,C,D). A = 1, B = 1, C in 38..sup ; A = 1, B = 1, D = 6, C in 35..sup ; A = 1, B = 1, C in 38..sup, D in inf..4\/6..sup ; A = 1, B = 1, D = 6 ; A = 1, B in inf.. -1\/1..sup, C in 38..sup ; A = 1, D = 6, B in inf.. -1\/1..sup, C in 35..sup ; A = 1, B in inf.. -1\/1..sup, C in 38..sup, D in inf..4\/6..sup ; A = 1, D = 6, B in inf.. -1\/1..sup. 11 ?- 

So, the program gave 8 results, among those you were interested in (5th and 8th):

 A = 1, B in inf.. -1\/1..sup, C in 38..sup ; A = 1, D = 6, B in inf.. -1\/1..sup. 

Others were redundant and could possibly be eliminated using simple, automated logic rules:

 1st or 5th ==> 5th [B == 1 or B != 0 --> B != 0] 2nd or 4th ==> 4th [C >= 35 or True --> True ] 3rd or 1st ==> 1st ==> 5th [D != 5 or True --> True ] 4th or 8th ==> 8th [B == 1 or B != 0 --> B != 0] 6th or 8th ==> 8th [C >= 35 or True --> True ] 7th or 3rd ==> 3rd ==> 5th [B == 1 or B != 0 --> B != 0] 

I know this is a long way to go for a common solution, but as I said, I hope this is the beginning ...

PS I used "regular" AND and OR ( , and ; ) because clpfd ( #/\ and #\/ ) gave a very strange result that I couldn’t understand myself ... maybe someone more experienced might throw a little light on it ...