Is it ok this CNF of a Boolean function?

up vote
2
down vote

favorite

I have to find out the CNF of $$beginmatrix f(x,y,z)&=&(xwedge y)vee(xwedge z),endmatrix$$ where $f$ is a Boolean function.

$$beginmatrix&f(x,y,z)&=&(xwedge y)vee(xwedge z)&1\
&&=&xwedge(yvee z)&2\
&&=&(xvee0_Bvee0_B)wedge(yvee zvee 0_B)&3\
&&=&(xvee(ywedgeoverline y)vee(zwedgeoverline z))wedge(yvee zvee(xwedgeoverline x))&4\
&&=&(((xvee y)wedge(xveeoverline y))vee(zwedgeoverline z))wedge((yvee zvee x)wedge(yvee zveeoverline x))&5\
&&=&(xvee yvee z)wedge(xveeoverline yveeoverline z)wedge(xlor ylor z)wedge(overline x lor ylor z)&6\
&&=&(xvee yvee z)wedge(overline xvee yvee z)wedge(xveeoverline yveeoverline z),endmatrix$$
where $0_B$ is the first element.

I have to make sure that all the terms refer to all variables involved.

Anyway WolframAlpha says another thing... What am I doing wrong?

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

asked Jul 26 at 5:43

manooooh

374213

add a commentÂ |Â

up vote
2
down vote

favorite

I have to find out the CNF of $$beginmatrix f(x,y,z)&=&(xwedge y)vee(xwedge z),endmatrix$$ where $f$ is a Boolean function.

I have to make sure that all the terms refer to all variables involved.

Anyway WolframAlpha says another thing... What am I doing wrong?

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

asked Jul 26 at 5:43

manooooh

374213

add a commentÂ |Â

up vote
2
down vote

favorite

I have to find out the CNF of $$beginmatrix f(x,y,z)&=&(xwedge y)vee(xwedge z),endmatrix$$ where $f$ is a Boolean function.

I have to make sure that all the terms refer to all variables involved.

Anyway WolframAlpha says another thing... What am I doing wrong?

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

asked Jul 26 at 5:43

manooooh

374213

I have to find out the CNF of $$beginmatrix f(x,y,z)&=&(xwedge y)vee(xwedge z),endmatrix$$ where $f$ is a Boolean function.

I have to make sure that all the terms refer to all variables involved.

Anyway WolframAlpha says another thing... What am I doing wrong?

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

asked Jul 26 at 5:43

manooooh

374213

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

edited Jul 26 at 6:48

Taroccoesbrocco

3,38941331

asked Jul 26 at 5:43

manooooh

374213

asked Jul 26 at 5:43

manooooh

374213

asked Jul 26 at 5:43

manooooh

374213

add a commentÂ |Â

2 Answers
2

active

oldest

votes

up vote
1
down vote

accepted

In general, formulas do not have a unique conjunctive normal form (CNF), see an example here. So, in general, the fact that you get another CNF does not imply automatically that you are wrong. The important thing is that all CNF's you get should be equivalent.

In this particular case, you should notice that actually in line 2 (after applying the distributivity law to line 1) you already have a CNF $x land (y lor z)$ and so you can stop there.

Moreover, the formula in your last line $(xvee yvee z)wedge(overline xvee yvee z)wedge(xveeoverline yveeoverline z),$ is not equivalent to $x land (y lor z)$ (indeed, consider the truth assignment $v$ where $v(x) = v(y) =bot$ and $v(z) = top$). This means that you actually did something wrong and $(xvee yvee z)wedge(overline xvee yvee z)wedge(xveeoverline yveeoverline z),$ is not a CNF of $(xwedge y)vee(xwedge z)$.

Your mistake is between lines 5 and 6. You should write:

beginalign
((x lor y) land (x lor overliney)) lor (z land overlinez) dots &= ((x lor y) lor (z land overlinez)) land ((x lor overliney) lor (z land overlinez)) dots \
&= (x lor y lor z) land (x lor y lor overlinez) land (x lor overliney lor z) land (x lor overliney lor overlinez) dots
endalign

Therefore, a CNF of $(xwedge y)vee(xwedge z)$ where all clauses contain exactly one occurrence of each variable is
beginequationtag1
(x lor y lor z) land (x lor y lor overlinez) land (x lor overliney lor z) land (x lor overliney lor overlinez) land (overlinex lor y lor z)
endequation

Using truth tables, you can easily prove that formula $(1)$ is equivalent to $x land (y lor z)$, so both are CNF of $(xwedge y)vee(xwedge z)$.

edited Jul 26 at 7:07

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

Thank you! Btw I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:18

add a commentÂ |Â

up vote
2
down vote

What am I doing wrong?

Not recognising that line 2 is the CNF you seek. You should have stopped there.

The distribution from line 5 to 6 dropped several terms also.

If you must include all literals or their negations in each conjunct, then observe that:

$$beginalignx &= (xvee yvee z)wedge(xvee yveebar z)wedge(xvee bar yvee z)wedge(xveebar yvee bar z)
\ yvee z &= (xvee yvee z)wedge(bar xvee yvee z)
endalign$$

edited Jul 27 at 2:24

answered Jul 26 at 6:09

Graham Kemp

80k43275

Thank you! I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:19

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: "69"
;
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: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863100%2fis-it-ok-this-cnf-of-a-boolean-function%23new-answer', 'question_page');

);

Post as a guest

Name

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
1
down vote

accepted

In this particular case, you should notice that actually in line 2 (after applying the distributivity law to line 1) you already have a CNF $x land (y lor z)$ and so you can stop there.

Your mistake is between lines 5 and 6. You should write:

Using truth tables, you can easily prove that formula $(1)$ is equivalent to $x land (y lor z)$, so both are CNF of $(xwedge y)vee(xwedge z)$.

edited Jul 26 at 7:07

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

Thank you! Btw I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:18

add a commentÂ |Â

up vote
1
down vote

accepted

In this particular case, you should notice that actually in line 2 (after applying the distributivity law to line 1) you already have a CNF $x land (y lor z)$ and so you can stop there.

Your mistake is between lines 5 and 6. You should write:

Using truth tables, you can easily prove that formula $(1)$ is equivalent to $x land (y lor z)$, so both are CNF of $(xwedge y)vee(xwedge z)$.

edited Jul 26 at 7:07

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

Thank you! Btw I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:18

add a commentÂ |Â

up vote
1
down vote

accepted

In this particular case, you should notice that actually in line 2 (after applying the distributivity law to line 1) you already have a CNF $x land (y lor z)$ and so you can stop there.

Your mistake is between lines 5 and 6. You should write:

Using truth tables, you can easily prove that formula $(1)$ is equivalent to $x land (y lor z)$, so both are CNF of $(xwedge y)vee(xwedge z)$.

edited Jul 26 at 7:07

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

In this particular case, you should notice that actually in line 2 (after applying the distributivity law to line 1) you already have a CNF $x land (y lor z)$ and so you can stop there.

Your mistake is between lines 5 and 6. You should write:

Using truth tables, you can easily prove that formula $(1)$ is equivalent to $x land (y lor z)$, so both are CNF of $(xwedge y)vee(xwedge z)$.

edited Jul 26 at 7:07

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

edited Jul 26 at 7:07

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

answered Jul 26 at 6:19

Taroccoesbrocco

3,38941331

Thank you! Btw I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:18

add a commentÂ |Â

Thank you! Btw I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:18

Thank you! Btw I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:18

add a commentÂ |Â

up vote
2
down vote

What am I doing wrong?

Not recognising that line 2 is the CNF you seek. You should have stopped there.

The distribution from line 5 to 6 dropped several terms also.

If you must include all literals or their negations in each conjunct, then observe that:

$$beginalignx &= (xvee yvee z)wedge(xvee yveebar z)wedge(xvee bar yvee z)wedge(xveebar yvee bar z)
\ yvee z &= (xvee yvee z)wedge(bar xvee yvee z)
endalign$$

edited Jul 27 at 2:24

answered Jul 26 at 6:09

Graham Kemp

80k43275

Thank you! I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:19

add a commentÂ |Â

up vote
2
down vote

What am I doing wrong?

Not recognising that line 2 is the CNF you seek. You should have stopped there.

The distribution from line 5 to 6 dropped several terms also.

If you must include all literals or their negations in each conjunct, then observe that:

$$beginalignx &= (xvee yvee z)wedge(xvee yveebar z)wedge(xvee bar yvee z)wedge(xveebar yvee bar z)
\ yvee z &= (xvee yvee z)wedge(bar xvee yvee z)
endalign$$

edited Jul 27 at 2:24

answered Jul 26 at 6:09

Graham Kemp

80k43275

Thank you! I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:19

add a commentÂ |Â

up vote
2
down vote

What am I doing wrong?

Not recognising that line 2 is the CNF you seek. You should have stopped there.

The distribution from line 5 to 6 dropped several terms also.

If you must include all literals or their negations in each conjunct, then observe that:

$$beginalignx &= (xvee yvee z)wedge(xvee yveebar z)wedge(xvee bar yvee z)wedge(xveebar yvee bar z)
\ yvee z &= (xvee yvee z)wedge(bar xvee yvee z)
endalign$$

edited Jul 27 at 2:24

answered Jul 26 at 6:09

Graham Kemp

80k43275

What am I doing wrong?

Not recognising that line 2 is the CNF you seek. You should have stopped there.

The distribution from line 5 to 6 dropped several terms also.

If you must include all literals or their negations in each conjunct, then observe that:

$$beginalignx &= (xvee yvee z)wedge(xvee yveebar z)wedge(xvee bar yvee z)wedge(xveebar yvee bar z)
\ yvee z &= (xvee yvee z)wedge(bar xvee yvee z)
endalign$$

edited Jul 27 at 2:24

answered Jul 26 at 6:09

Graham Kemp

80k43275

edited Jul 27 at 2:24

answered Jul 26 at 6:09

Graham Kemp

80k43275

answered Jul 26 at 6:09

Graham Kemp

80k43275

answered Jul 26 at 6:09

Graham Kemp

80k43275

Thank you! I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:19

add a commentÂ |Â

Thank you! I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:19

Thank you! I said in the question "I have to make sure that all the terms refer to all variables involved". I was aware about the second line.
â€“Â manooooh
Jul 26 at 19:19

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

ukmuiik