Simplifying boolean algebra without using certain operations
Simplifying boolean algebra without using certain operations
when I use Simplify or FullSimplify in Mathematica it often simplifies it using all the existing boolean operations. For example, consider the following:
Simplify
FullSimplify
FullSimplify[! (x && y && z) && ! (x && ! y && ! z) && ! (! x && ! y && z)]
Simplify[! (x && y && z) && ! (x && ! y && ! z) && ! (! x && ! y && z)]
Both the code segment above are going to output the following:
! (x ⊻ z ⊻ (x && y) ⊻ (z && y) ⊻ (z && x && y))
I do not want the Xor gates in the solution. Is there a way we can give restrictions to the two functions, such that it gives the simplest possible formula but without using other gates except Or, Not, and And.
Xor
Or
Not
And
I've tried BooleanMinimize with "CNF" and "DNF", but these two things do not mean that the formula is the simplest (in terms of numbers of operation). I simply want a "Simplify" that does not use other operators except Not, And, and Or. Thanks!
BooleanMinimize
Not
And
Or
Simplify
ExcludedForms
Simplify
Xor
Simplify
LeafCount
Xor
$begingroup$
The expression may not be necessarily simpler than using
Xor. However what I want here is that the "simplest possible form" without Xor. Which can be solved using ExcludedForms argument. Thank you for your reply.$endgroup$
– Naufal Fikri
Sep 9 '18 at 8:31
Xor
Xor
ExcludedForms
2 Answers
2
You could try giving Simplify a ComplexityFunction option that discourages Xor:
Simplify
ComplexityFunction
Xor
Simplify[
!(x&&y&&z)&&!(x&&!y&&!z)&&!(!x&&!y&&z),
ComplexityFunction->(LeafCount[#]+10000Count[#, _Xor,0,Infinity]&)
]
(x && ! y && z) || (! x && (y || ! z)) || (y && ! z)
Addendum
(The OP asked about another expression)
I don't know which boolean transformations are built in to Simplify/FullSimplify, but you can add more with the option TransformationFunctions. So:
Simplify
FullSimplify
TransformationFunctions
FullSimplify[
!u && !v && !w && !x,
ComplexityFunction -> (LeafCount[#]+10000Count[#, _Xor,0,Infinity]&),
TransformationFunctions -> Automatic, BooleanConvert[#,"OR"]&
]
(* !(u || v || w || x) *)
$begingroup$
This did the trick and does exactly what I want it to do! Thank you. Although for some reason it does not always give out the "simplest". Most notably there are a lot of cases where this does not "simplify" using De Morgan's laws, it keeps
(!u && !v && !w && !x) while in fact it can be simplified to !(u || v || w || x), assuming that LeafCount[!u] = 2 (due to the terms !u and u)... Is my understandingof LeafCount wrong?$endgroup$
– Naufal Fikri
Sep 10 '18 at 8:10
(!u && !v && !w && !x)
!(u || v || w || x)
LeafCount[!u] = 2
!u
u
LeafCount
perhaps BooleanMinimize?
BooleanMinimize
BooleanMinimize[! (x && y && z) && ! (x && ! y && ! z) && ! (! x && ! y && z)]
(x && ! y && z) || (! x && y) || (! x && ! z) || (y && ! z)
BooleanMinimize[! (x && y && z) && ! (x && ! y && ! z) && ! (! x && ! y && z), "CNF"]
(! x || ! y || ! z) && (! x || y || z) && (x || y || ! z)
$begingroup$
Thanks for the answer, however this just converts them into CNF and DNF instead of simplifying the formula as minimal as possible. Consider If I try to minimize
(x || (y && t)) && z then using BooleanMinimize gives (t || x) && (x || y) && z and (t && y && z) || (x && z) for "CNF" and "DNF" respectively. Which is more complex (has more repeated terms) than the original formula.$endgroup$
– Naufal Fikri
Sep 8 '18 at 16:17
(x || (y && t)) && z
BooleanMinimize
(t || x) && (x || y) && z
(t && y && z) || (x && z)
Thanks for contributing an answer to Mathematica Stack Exchange!
But avoid …
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
$begingroup$
You may not be aware of an optional argument to
SimplifycalledExcludedForms. That can let you tellSimplifythatXorcannot be considered as part of the solution.SimplifyusesLeafCount, which is roughly a count of the number of symbols needed to write an expression, to determine what is simplest. Without usingXorI'm not sure I see any expression with fewer symbols that is equivalent to your problem. Can you show the simplest result with fewer symbols?$endgroup$
– Bill
Sep 8 '18 at 17:28