# Converting a Proposition to DNF using proof systems

I have been attempting to convent a prop to DNF using a group of common rules, i have applied them all but i think i should be able to get it smaller, This is what I've got so far. Thanks! $$(p \wedge (q \vee \neg p)) \rightarrow (q \wedge \neg (s \wedge r))$$ First, I remove the implication, as $p \rightarrow q$ is logically equivalent to $\neg p \vee q$;

$$\neg (p \wedge (q \vee \neg p)) \vee (q \wedge \neg (s \wedge r))$$ Now I use the double negation rule to remove the extra nots

$$\neg (p \wedge (q \vee p)) \vee (q \wedge (s \wedge r))$$

Apply De Morgan's Laws

$$(\neg p \wedge (q \vee p)) \wedge (\neg q \wedge (s \wedge r))$$ Use the distributive property to separate functions

$$(\neg (p \wedge q) \vee (p \wedge p)) \wedge (\neg (q \wedge s) \vee (q \wedge r))$$

$p \wedge p$ is logically equivalent to $p$

$$(\neg (p \wedge q) \vee (p)) \wedge (\neg (q \wedge s) \vee (q \wedge r))$$

Apply De Morgan's Laws some more

$$(\neg p \vee \neg q) \vee p) \wedge (\neg q \vee \neg s) \vee (\neg q \vee \neg r))$$

-
I don't believe your third line at all. What rule, exactly, were you applying? It's hard to follow since there aren't any explicit double negations in there. –  Kevin Carlson Aug 7 '12 at 2:56
well theres a NOT at the start, I assumed that not would "cancel" out the others, as the not is over the entire function –  user972183 Aug 7 '12 at 3:32
No, it's only over the first disjunct. Are you studying this material in a course right now? You've got some basic misunderstandings that would be much easier for an instructor to help you with in person than us on here. –  Kevin Carlson Aug 7 '12 at 3:39
Nope, This isn't course work, I'm just trying to learn about some CS concepts, If you can recommend a book that covers this stuff thatd be great –  user972183 Aug 7 '12 at 3:42
Well, the text I'd go to to learn logic would be Kleene, Mathematical Logic, but that's probably higher-powered than you need. I don't have enough experience to advise, but if you Google around on things like "logic for computer scientists" I'm sure you'll find something good, probably even free. –  Kevin Carlson Aug 7 '12 at 3:49

You may get DNF this way: $$(p\wedge(1\vee\neg p))\rightarrow(q\wedge\neg(s\wedge r)) =$$ (using $x\rightarrow y = \neg x\vee y$ equality) $$= \neg(p\wedge(q\vee\neg p))\vee(q\wedge(\neg s\vee\neg r)) =$$ (using $\neg(x\wedge y)=\neg x\vee\neg y$ equality) $$= \neg p\vee\neg(q\vee\neg p)\vee(q\wedge(\neg s\vee\neg r)) =$$ (using $x\wedge(y\vee z) = (x\wedge y)\vee(x\wedge z)$ and $\neg(x\wedge y)=\neg x\vee\neg y$ equalities) $$= \neg p\vee(\neg q\wedge p)\vee(q\wedge\neg s)\vee(q\wedge\neg r).$$