Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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))$$

share|cite|improve this question
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). $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.