# How to convert formula to DNF and CNF?

I have to convert the following formula to a DNF and CNF:

$$((x→y)→(z→¬x))→(¬y→¬z)$$

Removing the arrows and using DeMorgan Laws, I ended up with:

$$((¬x \vee ¬y) \wedge (z \wedge x)) \vee (y \wedge ¬z)$$

Using the associative law I ended up with:

$$((¬x \vee ¬y) \wedge (y \wedge ¬z)) \vee ((z \wedge x) \wedge (y \wedge ¬z))$$

Now this is where I'm stuck. I'm not entirely sure whether or not I just did something wrong along the way. This looks kind of like a DNF, and since it has both y and not y on the left and z and not z on the right, it looks reminescent of a contradiction, but I am kind of stuck as neither of the two terms is a conjunction of atoms, but rather of smaller formulas.

• Welcome to MSE! Use distributivity. – Wuestenfux Oct 27 '18 at 16:18

First, some things are going wrong in your initial steps already:

$$((x \to y)\to(z\to \neg x))\to (\neg y \to \neg z)$$

becomes:

$$\neg (\neg (\neg x \lor y) \lor (\neg z\lor \neg x)) \lor (\neg \neg y \lor \neg z)$$

which becomes:

$$((\neg x \lor y) \land \neg (\neg z\lor \neg x)) \lor (y \lor \neg z)$$

and thus:

$$((\neg x \lor y) \land (z\land x)) \lor (y \lor \neg z)$$

... which is different from what you had.

Now, by Association, we can drop parentheses:

$$((\neg x \lor y) \land z \land x) \lor y \lor \neg z$$

This is not yet in DNF, since you have a disjunction as a conjunct on the left. This is basically what you were struiggling with.

Well, when you have disjunctions as part of conjunctions, you can simply Distribute the conjunction over the disjunction, so you get:

$$((\neg x \land z \land x) \lor (y \land z \land x)) \lor y \lor \neg z$$

And we can drop some more parentheses:

$$(\neg x \land z \land x) \lor (y \land z \land x) \lor y \lor \neg z$$

and now it is nicely in DNF .... though it can still be simplified further:

The term on the left contains both $$x$$ and $$\neg x$$, and hence is a contradiction, and hence can be removed completely. Also, the $$y$$ term absorbs the $$y \land z \land x$$ term, so that latter term can be removed as well, leaving you with:

$$y \lor \neg z$$