Simplifying boolean algebra without using certain operations

up vote
6
down vote

favorite

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!

edited Sep 8 at 16:18

asked Sep 8 at 13:54

Naufal Fikri

1334

New contributor

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?
â€“Â Bill
Sep 8 at 17:28

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.
â€“Â Naufal Fikri
Sep 9 at 8:31

add a commentÂ |Â

up vote
6
down vote

favorite

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

edited Sep 8 at 16:18

asked Sep 8 at 13:54

Naufal Fikri

1334

New contributor

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?
â€“Â Bill
Sep 8 at 17:28

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.
â€“Â Naufal Fikri
Sep 9 at 8:31

add a commentÂ |Â

up vote
6
down vote

favorite

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

edited Sep 8 at 16:18

asked Sep 8 at 13:54

Naufal Fikri

1334

New contributor

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

edited Sep 8 at 16:18

asked Sep 8 at 13:54

Naufal Fikri

1334

New contributor

edited Sep 8 at 16:18

asked Sep 8 at 13:54

Naufal Fikri

1334

New contributor

asked Sep 8 at 13:54

Naufal Fikri

1334

asked Sep 8 at 13:54

Naufal Fikri

1334

New contributor

Naufal Fikri is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

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?
â€“Â Bill
Sep 8 at 17:28

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.
â€“Â Naufal Fikri
Sep 9 at 8:31

add a commentÂ |Â

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?
â€“Â Bill
Sep 8 at 17:28

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.
â€“Â Naufal Fikri
Sep 9 at 8:31

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?
â€“Â Bill
Sep 8 at 17:28

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.
â€“Â Naufal Fikri
Sep 9 at 8:31

add a commentÂ |Â

2 Answers
2

active

oldest

votes

up vote
5
down vote

accepted

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

edited yesterday

answered Sep 8 at 17:24

Carl Woll

56.3k272147

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?
â€“Â Naufal Fikri
2 days ago

add a commentÂ |Â

up vote
2
down vote

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)

edited Sep 8 at 14:39

answered Sep 8 at 14:07

kglr

159k8184384

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.
â€“Â Naufal Fikri
Sep 8 at 16:17

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

Naufal Fikri is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f181494%2fsimplifying-boolean-algebra-without-using-certain-operations%23new-answer', 'question_page');

);

Post as a guest

Name

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
5
down vote

accepted

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

edited yesterday

answered Sep 8 at 17:24

Carl Woll

56.3k272147

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?
â€“Â Naufal Fikri
2 days ago

add a commentÂ |Â

up vote
5
down vote

accepted

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

edited yesterday

answered Sep 8 at 17:24

Carl Woll

56.3k272147

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?
â€“Â Naufal Fikri
2 days ago

add a commentÂ |Â

up vote
5
down vote

accepted

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

edited yesterday

answered Sep 8 at 17:24

Carl Woll

56.3k272147

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

edited yesterday

answered Sep 8 at 17:24

Carl Woll

56.3k272147

edited yesterday

answered Sep 8 at 17:24

Carl Woll

56.3k272147

answered Sep 8 at 17:24

Carl Woll

56.3k272147

answered Sep 8 at 17:24

Carl Woll

56.3k272147

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?
â€“Â Naufal Fikri
2 days ago

add a commentÂ |Â

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?
â€“Â Naufal Fikri
2 days ago

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?
â€“Â Naufal Fikri
2 days ago

add a commentÂ |Â

up vote
2
down vote

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)

edited Sep 8 at 14:39

answered Sep 8 at 14:07

kglr

159k8184384

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.
â€“Â Naufal Fikri
Sep 8 at 16:17

add a commentÂ |Â

up vote
2
down vote

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)

edited Sep 8 at 14:39

answered Sep 8 at 14:07

kglr

159k8184384

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.
â€“Â Naufal Fikri
Sep 8 at 16:17

add a commentÂ |Â

up vote
2
down vote

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)

edited Sep 8 at 14:39

answered Sep 8 at 14:07

kglr

159k8184384

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)

edited Sep 8 at 14:39

answered Sep 8 at 14:07

kglr

159k8184384

edited Sep 8 at 14:39

answered Sep 8 at 14:07

kglr

159k8184384

answered Sep 8 at 14:07

kglr

159k8184384

answered Sep 8 at 14:07

kglr

159k8184384

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.
â€“Â Naufal Fikri
Sep 8 at 16:17

add a commentÂ |Â

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.
â€“Â Naufal Fikri
Sep 8 at 16:17

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.
â€“Â Naufal Fikri
Sep 8 at 16:17

add a commentÂ |Â

Naufal Fikri is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Naufal Fikri is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky