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.

  • 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$ Aug 11 '11 at 4:49
  • $\begingroup$ 40 pages to get to this point? $\endgroup$ 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 agree to our terms of service, privacy policy and cookie policy