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

1

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