0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to MSE! Use distributivity. $\endgroup$ – Wuestenfux Oct 27 '18 at 16:18
0
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.