Bring the following formula into an equivalent DNF: $\psi := ((\neg (A_o \vee A_1) \vee A_2) \wedge \neg A_4)$

52 Views Asked by At

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$... :(

1

There are 1 best solutions below

0
On BEST ANSWER

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!