Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

migrated from Aug 11 '11 at 0:31

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

what language is this? – Dave Aug 10 '11 at 21:12
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. – Pascal Cuoq Aug 10 '11 at 21:15
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 ? – Eddy Aug 10 '11 at 21:34
you meant $(\neg o \vee \neg r)$ – Olivier Bégassat Aug 11 '11 at 4:49
40 pages to get to this point? – 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
share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.