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

  • 0
    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.2012-08-07
  • 0
    well theres a NOT at the start, I assumed that not would "cancel" out the others, as the not is over the entire function2012-08-07
  • 0
    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.2012-08-07
  • 0
    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 great2012-08-07
  • 0
    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.2012-08-07

1 Answers 1