6
$\begingroup$

when I use Simplify or FullSimplify in Mathematica it often simplifies it using all the existing boolean operations. For example, consider the following: 

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.

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!

|improve this question
$\endgroup$
  • $\begingroup$ You may not be aware of an optional argument to Simplify called ExcludedForms. That can let you tell Simplify that Xor cannot be considered as part of the solution. Simplify uses LeafCount, which is roughly a count of the number of symbols needed to write an expression, to determine what is simplest. Without using Xor I'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
  • $\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
5
$\begingroup$

You could try giving Simplify a ComplexityFunction option that discourages 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:

FullSimplify[
    !u && !v && !w && !x,
    ComplexityFunction -> (LeafCount[#]+10000Count[#, _Xor,{0,Infinity}]&),
    TransformationFunctions -> {Automatic, BooleanConvert[#,"OR"]&}
]

(* !(u || v || w || x) *)
|improve this answer
$\endgroup$
  • $\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
2
$\begingroup$

perhaps 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)

|improve this answer
$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.