How to transform this formula to DNF form?

Question

I'm having troubles with converting this formula to DNF form:

$[(p \vee q) \Rightarrow (q \vee r)] \Rightarrow [(p \Rightarrow q) \wedge \sim r]$

I've changed it to something like this (with steps):

$\sim[(p \vee q) \Rightarrow (q \vee r)] \vee [(\sim p \vee q) \wedge \sim r]$

$(p \vee q) \wedge (\sim q \wedge \sim r) \vee (\sim p \vee \sim r) \vee (q \wedge \sim r)$

$p \vee q \wedge (\sim q \wedge \sim r) \vee (\sim p \vee \sim r) \vee (q \wedge \sim r)$

What should I do next to convert it finally into CNF? I thought about the distributivity law, but I don't know how to use it in that example. I hope I didn't make any error in my calculations. Could you please help me? I will be very grateful.

Answer 1

As @Vasya suggested, let's try a truth table.

The values for $p,\,q,\,r$ that make the statement true are $FFF, FTF, TFF, TTF$. Therefore, the DNF is $(\neg p\land\neg q\land \neg r)\lor(\neg p\land q\land \neg r)\lor(p\land\neg q\land \neg r)\lor(p\land q\land \neg r)$. Of course, this can be simplified to $\neg r$.

Answer 2

As suggested, a truth-table will always work.

But, if you want to stick to algebra:

First, you have some small mistakes. You have:

$(p \vee q) \wedge (\sim q \wedge \sim r) \vee (\sim p \vee \sim r) \vee (q \wedge \sim r)$

But that should be:

$(p \vee q) \wedge (\sim q \wedge \sim r) \vee (\sim p \color{red}\land \sim r) \vee (q \wedge \sim r)$

Also, you have a mix of $\lor$'s and $\land$'s here, so make sure to use parentheses. Looking at the statement before, we understand they must go here:

$ \color{red}((p \vee q) \wedge (\sim q \wedge \sim r)\color{red}) \vee (\sim p \land \sim r) \vee (q \wedge \sim r)$

OK so what you really have is:

$ ((p \vee q) \wedge (\sim q \wedge \sim r)) \vee (\sim p \land \sim r) \vee (q \wedge \sim r)$

Now, first we can drop a pair of parentheses:

$ ((p \vee q) \wedge \sim q \wedge \sim r) \vee (\sim p \land \sim r) \vee (q \wedge \sim r)$

Then, a handy equivalence principle is:

Reduction

$p \lor (\sim p \land q) = p \lor q$

We can apply Reduction to the start of the statement to get:

$ (p \wedge \sim q \wedge \sim r) \vee (\sim p \land \sim r) \vee (q \wedge \sim r)$

Now, there is also:

Nested Reduction

$(p \land r) \lor (\sim p \land q \land r) = (p \land r) \lor (q \land r)$

We can apply Nested Reduction to get:

$ (\sim q \wedge \sim r) \vee (\sim p \land \sim r) \vee (q \wedge \sim r)$

OK, now we use:

Adjacency

$(p \lor q) \land (p \lor \sim q) = p$

Applying Adjacency gets you:

$ \sim r \vee (\sim p \land \sim r)$

OK, finally we use

Absorption

$p \lor (p \land q) = p$

and with that, your statement becomes just

$\sim r$

OK, so that's still pretty involved ... but once you get used to some of these more advanced equivalence principles, you can simplify these expressions pretty quickly. In fact, I can tell you I personally got the answer more quickly this way than using a truth-table.