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?
Best Answer
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}$$