[ACCEPTED]-Simplify boolean expression algorithm-boolean-expression
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.
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.
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.
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.
First shot using Google found this paper:
http://hopper.unco.edu/KARNAUGH/Algorithm.html
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
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.