Question

Consider a Boolean expression Ex,y,z=(x^-z)v(y^z). Find disjunctive and conjunctive normal form.

Answer 1

Let us find the disjunctive normal form of $E(x,y,z)=(x\land\neg z)\lor(y\land z).$

$E(x,y,z)=(x\land\neg z)\lor(y\land z) =(x\land T \land \neg z)\lor(T \land y\land z) \\=(x\land (y\lor \neg y) \land \neg z)\lor((x\lor\neg x) \land y\land z) \\=(x\land y \land \neg z)\lor (x\land \neg y\land \neg z)\lor(x \land y\land z)\lor(\neg x \land y\land z).$

It follows that $(x\land y \land \neg z)\lor (x\land \neg y\land \neg z)\lor(x \land y\land z)\lor(\neg x \land y\land z)$ is a disjunctive normal form of $E(x,y,z).$

Let us find the conjunctive normal form of $E(x,y,z)=(x\land\neg z)\lor(y\land z).$

$E(x,y,z)=(x\land\neg z)\lor(y\land z) =(x\lor y)\land(x\lor z)\land (\neg z\lor y)\land (\neg z\lor z) \\=(x\lor y\lor F)\land(x\lor F\lor z)\land ( F\lor y\lor \neg z)\land T \\=(x\lor y\lor (\neg z\land z))\land(x\lor (\neg y\land y)\lor z)\land ( (\neg x\land x)\lor y\lor \neg z) \\=(x\lor y\lor \neg z)\land(x\lor y\lor z)\land(x\lor \neg y\lor z)\land(x\lor y\lor z)\land ( \neg x\lor y\lor \neg z)\land ( x\lor y\lor \neg z) \\=(x\lor y\lor \neg z)\land(x\lor y\lor z)\land(x\lor \neg y\lor z)\land ( \neg x\lor y\lor \neg z).$

It follows that $(x\lor y\lor \neg z)\land(x\lor y\lor z)\land(x\lor \neg y\lor z)\land ( \neg x\lor y\lor \neg z)$ is a conjunctive normal form of $E(x,y,z).$