1
$\begingroup$

Question is from the book: Discrete Mathematical Structures with Applications to CS by Tremblay and Manohar. It is an exercise problem. But, unfortunately, there is no help available on answers, or solutions of this book. I have tried to solve this problem but couldn't get the desired conclusion.

Premise 1: $P \rightarrow Q$,

Premise 2: $(\neg Q \lor R) \wedge \neg R$

Premise 3: $ \neg (\neg P \wedge S)$

Conclusion: $ \neg S$

Solution:

  1. $(\neg Q \lor R)$ $\wedge$ $-R$..............[Introducing Premise 2]

  2. $(\neg Q \lor R)$.........................[Tautologically Implies, 1, Simplification]

  3. $Q \rightarrow R$.............................[Tautologically Implies, 2, Converting Disjuction To Implication]

  4. $P \rightarrow Q$.............................[Introducing Premise 1]

  5. $P \rightarrow R$.............................[Tautologically Implies, 4, 3, Transitivity Law]

  6. $ \neg (\neg P \wedge S)$.......................[Introducing Premise 3]

  7. $P \lor \neg S$............................[Tautologically Implies, 6, DeMorgan's Law]

  8. $ \neg S \lor P$............................[Tautologically Implies, 7, Commutative Law]

  9. $S \rightarrow P$............................[Tautologically Implies, 8, Converting Disjuction to Implication]

  10. $S \rightarrow R$............................[Tautologically Implies, 9, 5, Transitivity]

  11. $\neg S \lor R$............................[Tautologically Implies, 10, Converting Implication to Disjuction]

What wrong I did? I am getting $\neg S \lor R$ instead of $\neg S $

$\endgroup$
  • 1
    $\begingroup$ You didn't take much benefit from premisse $2$. That's why you didn't get the desired conclusion. But your reasonning is Correct. $\endgroup$ – hamam_Abdallah Jul 2 '20 at 21:19
2
$\begingroup$

hint

From premisse $ 2$, use distributivity to get $ \lnot Q \wedge \lnot R$ because $ R\wedge \lnot R $ is false.

by simplification, you have $ \lnot Q$.

by contrapositive of premmisse $ 1$, you get $ \lnot P.$

Finally, using premisse $ 3$, De Morgan's law and disjunctive syllogism, you have the conclusion $\lnot S$.

$\endgroup$
  • $\begingroup$ There it is... I really missed that one out. $\endgroup$ – Ubi hatt Jul 2 '20 at 21:23
  • $\begingroup$ How do we get $\neg Q$ from $\neg Q\land\neg R$? $\endgroup$ – Invisible Jul 3 '20 at 11:42
  • $\begingroup$ @Croissant by simplification . $\endgroup$ – hamam_Abdallah Jul 3 '20 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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