[ACCEPTED]-Simplify boolean expression algorithm-boolean-expression

Accepted answer
Score: 10

You might be interested in K-maps and the Quine–McCluskey algorithm.

I think 3 SymPy is able to solve and simplify boolean 2 expressions, looking at the source might 1 be useful.

Score: 7

Your particular example would be solved 11 by an SMT solver. (It'd determine that no setting 10 of the variables could make the expression 9 true; therefore it's always false. More-general 8 simplification is out of scope for such 7 solvers.) Showing that an expression is 6 equivalent to true or false is of course NP-hard 5 even without bringing arithmetic into the 4 deal, so it's pretty cool that there's practical 3 software for even this much. Depending on 2 how much arithmetic knowledge is in scope, the 1 problem may be undecidable.

Score: 5

There are two parts to this problem, logical 8 simplification and representation simplification.

For 7 logical simplification, Quine-McCluskey. For 6 simplification of the representation, recursively 5 extract terms using the distribution identity 4 (0&1|0&2) == 0&(1|2).

I detailed 3 the process here. That gives the explanation 2 using only & and |, but it can be modified 1 to include all boolean operators.

Score: 3

Is the number of possible distinct values 12 finite and known? If so you could convert 11 each expression into a boolean expression. For 10 instance if a has 3 distinct values then 9 you could have variables a1, a2, and a3 where 8 a1 being true means that a == 1, etc. Once you 7 did that you could rely on the Quine-McCluskey 6 algorithm (which is probably better for 5 larger examples than Karnaugh maps). Here 4 is some Java code for Quine-McCluskey.

I can't speak 3 to whether this design would actually simplify 2 things or make them more complicated, but 1 you might want to consider it at least.

Score: 2

First shot using Google found this paper:


Of 7 course, that does not deal with non-boolean 6 subexpressions. But this latter part in 5 its general form is really hard, since there 4 is definitely no algorithm to check if an 3 arbitrary arithmetic expression is true, false 2 or whatever. What you are asking for goes 1 deeply into the field of compiler optimization.

More Related questions