0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Kevin Carlson
    Commented Aug 7, 2012 at 2:56
  • $\begingroup$ well theres a NOT at the start, I assumed that not would "cancel" out the others, as the not is over the entire function $\endgroup$
    – user972183
    Commented Aug 7, 2012 at 3:32
  • $\begingroup$ 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. $\endgroup$
    – Kevin Carlson
    Commented Aug 7, 2012 at 3:39
  • $\begingroup$ 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 $\endgroup$
    – user972183
    Commented Aug 7, 2012 at 3:42
  • $\begingroup$ 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. $\endgroup$
    – Kevin Carlson
    Commented Aug 7, 2012 at 3:49

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .