Bring the following formula into an equivalent DNF: $$\psi := \Bigg(\Big(\neg (A_o \vee A_1) \vee A_2\Big) \wedge \neg A_4\Bigg)$$ using as less steps as possible when forming it (about $3$ steps at most).

I try this:

$\Bigg(\Big(\neg (A_o \vee A_1) \vee A_2\Big) \wedge \neg A_4\Bigg) \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }$ I will use de Morgan

$\equiv \Bigg(\Big((\neg A_o \wedge \neg A_1) \vee A_2\Big) \wedge \neg A_4\Bigg) \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }$ I will use distributive law

$\equiv \Bigg(\Big((A_2 \vee \neg A_0) \wedge (A_2 \vee \neg A_1)\Big) \wedge \neg A_4\Bigg)\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }$ Use distributive law again

$\equiv \Bigg(\Big((\neg A_4 \wedge A_2) \vee (\neg A_4 \wedge \neg A_0)\Big) \wedge \Big((\neg A_4 \wedge A_2) \vee (\neg A_4 \wedge \neg A_1)\Big)\Bigg)$

But when I see this this is still no DNF I think because the middle $\wedge$... :(


When trying to get to DNF, you want to distribute any $\land$'s over $\lor$'s, not the other way around.

So, from line 2 you should instead proceed as follows:

$\Big((\neg A_o \wedge \neg A_1) \vee A_2\Big) \wedge \neg A_4 \text{ (Distribution)}$

$(\neg A_o \wedge \neg A_1 \wedge \neg A_4) \vee (A_2 \wedge \neg A_4) $

And now it is in DNF!

| cite | improve this answer | |

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.