2
$\begingroup$

I have to find out the CNF of $$\begin{matrix} f(x,y,z)&=&(x\wedge y)\vee(x\wedge z),\end{matrix}$$ where $f$ is a Boolean function.


$$\begin{matrix}&f(x,y,z)&=&(x\wedge y)\vee(x\wedge z)&1\\ &&=&x\wedge(y\vee z)&2\\ &&=&(x\vee0_B\vee0_B)\wedge(y\vee z\vee 0_B)&3\\ &&=&(x\vee(y\wedge\overline y)\vee(z\wedge\overline z))\wedge(y\vee z\vee(x\wedge\overline x))&4\\ &&=&(((x\vee y)\wedge(x\vee\overline y))\vee(z\wedge\overline z))\wedge((y\vee z\vee x)\wedge(y\vee z\vee\overline x))&5\\ &&=&(x\vee y\vee z)\wedge(x\vee\overline y\vee\overline z)\wedge(x\lor y\lor z)\wedge(\overline x \lor y\lor z)&6\\ &&=&(x\vee y\vee z)\wedge(\overline x\vee y\vee z)\wedge(x\vee\overline y\vee\overline z),\end{matrix}$$ 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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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:

$$\begin{align}x &= (x\vee y\vee z)\wedge(x\vee y\vee\bar z)\wedge(x\vee \bar y\vee z)\wedge(x\vee\bar y\vee \bar z) \\ y\vee z &= (x\vee y\vee z)\wedge(\bar x\vee y\vee z) \end{align}$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – manooooh
    Commented Jul 26, 2018 at 19:19
1
$\begingroup$

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 $(x\vee y\vee z)\wedge(\overline x\vee y\vee z)\wedge(x\vee\overline y\vee\overline 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 $(x\vee y\vee z)\wedge(\overline x\vee y\vee z)\wedge(x\vee\overline y\vee\overline z)\,$ is not a CNF of $(x\wedge y)\vee(x\wedge z)$.

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

\begin{align} ((x \lor y) \land (x \lor \overline{y})) \lor (z \land \overline{z}) \dots &= ((x \lor y) \lor (z \land \overline{z})) \land ((x \lor \overline{y}) \lor (z \land \overline{z})) \dots \\ &= (x \lor y \lor z) \land (x \lor y \lor \overline{z}) \land (x \lor \overline{y} \lor z) \land (x \lor \overline{y} \lor \overline{z}) \dots \end{align}

Therefore, a CNF of $(x\wedge y)\vee(x\wedge z)$ where all clauses contain exactly one occurrence of each variable is \begin{equation}\tag{1} (x \lor y \lor z) \land (x \lor y \lor \overline{z}) \land (x \lor \overline{y} \lor z) \land (x \lor \overline{y} \lor \overline{z}) \land (\overline{x} \lor y \lor z) \end{equation}

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – manooooh
    Commented Jul 26, 2018 at 19:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .