0
$\begingroup$

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.

  • 0
    @Christian: I assume the correct answer is "by mistake"... :-) I have corrected that. Thanks!2011-08-11

2 Answers 2

3

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
2

¬ (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.