convert boolean formula to DNF

Question

This is the given formula:

¬(¬(d -> a) ∧ (¬a -> b ∧ b))

Here's what I did so far:

1. ¬(¬(¬d ∨ a) ∧ (a ∨ b ∧ b))
2. ¬((d ∧ ¬a) ∧ (a ∨ b))
3. (¬d ∨ a) ∨ (!a ∧ !b)

How can I proceed from step 3 to get the DNF?

Answer 1

Your work is fine, and it is in DNF form, which we can see by using parentheses to better show each of the disjuncts:

$$(¬d \lor a) \lor (\lnot a \land \lnot b) $$ $$\equiv (\lnot d) \lor (a) \lor (\lnot a \land \lnot b)\tag{DNF}$$ $$\equiv \lnot d \lor (a \lor (\lnot a \land \lnot b))$$ $$\equiv \lnot d \lor (\underbrace{(a\lor \lnot a)}_{\large\text{True}}\land (a \lor \lnot b))\tag{distrubution}$$ $$\equiv \lnot d \lor (\text{True} \land (a \lor \lnot b))$$

$$\equiv \lnot d \lor a\lor \lnot b\tag{DNF}$$

That is, we've arrived at the disjuntive normal form of you original proposition. DNF is a disjunction (or'ing) of terms that are:

• literals, including negated literals, and/or
• conjuctions of literals and/or negated literals, as we see in the $(\lnot a \land \lnot b)$ term above.
• Also, for developing "full DNF form" one needs to try to arrive at a DNF with each variable appearing only once in one disjunct.