Sorry, I am just preparing some notes for my students and want to double check I have my facts right before I give the notes to them. So these are my premises:

  1. $\lnot p\rightarrow o$
  2. $s\rightarrow r$
  3. $\lnot (o\land r)$
  4. $\lnot p$

And I want : $\lnot s$

So, casually, we can get from $\lnot p$ to $o$ using Modus Ponens, proving $o$.

$\lnot(o\land r)$ is the same as $\lnot o\lor\lnot r$.

Using simplification we can assert from this that ¬r is true.

From this we can get to $\lnot s$ using Modus tollens.

Is this correct ? I am tired from writing ~40 pages of notes and am nearly positive I have missed something here.


migrated from stackoverflow.com Aug 11 '11 at 0:31

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ what language is this? $\endgroup$ – Dave Aug 10 '11 at 21:12
  • 1
    $\begingroup$ Dave's question seems to be tongue-in-cheek, but there is a serious questions there. You could be using any of several axiomatics. What is an axiom in one is a theorem in the other. $\endgroup$ – Pascal Cuoq Aug 10 '11 at 21:15
  • 1
    $\begingroup$ I'm so happy I'm not in that class and also that I'm clueless about where to find all those characters on my keyboard. Shouldn't this question be better off at math.stackechange.com ? $\endgroup$ – Eddy Aug 10 '11 at 21:34
  • $\begingroup$ you meant $(\neg o \vee \neg r)$ $\endgroup$ – Olivier Bégassat Aug 11 '11 at 4:49
  • $\begingroup$ 40 pages to get to this point? $\endgroup$ – Christian Blatter Aug 11 '11 at 9:27

The task is to prove $\neg s$ from the assumptions (1)-(4).

Proof 1 (by deduction, Modus Ponens):

These are true facts:

  • $\neg p $ by (4)
  • $o$ by (1)
  • $\neg r$ by (3) in the equivalent form $\neg o \vee \neg r$ (De Morgans's Law), and the proved $o$
  • $\neg s$ by (2) in the equivalent form $\neg r \rightarrow \neg s$ (negation of implication) and the proved $\neg r$

Proof 2 (by contradiction):

These are true facts:

  • $s$ by assumption (negation of $\neg s$ which should be proven)
  • $r$ by (2)
  • $\neg o$ by (3) in the equivalent form $\neg o \vee \neg r$ (De Morgans's Law) and the proved $r$
  • p by (1) in the equivalent form $\neg o \rightarrow p$ (negation of implication) and the proved $\neg o$
  • proved $p$ contradicts the fact (4) $\neg p$, hence the assumption $s$ is false and $\neg s$ must true

¬ (o∧r) is NOT the same as (¬o ∧ ¬r), it is the same as (¬o $\lor$ ¬r) (see De Morgans's Laws)

So here (¬o $\lor$ ¬r) is the equivalent to ¬r since o is true

Then s is false due to the s → r rule.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.