4
$\begingroup$

Prove that $$\lnot r\Rightarrow \lnot p,\lnot(q\lor r),s\Rightarrow(p\lor q)\models\lnot s $$

I'm completely stuck on this one. Only natural deduction inference rules can be used, no de morgan's law etc. The premises given all seem to be really irrelevant, and since we can't use transformational proof techniques, all the implications turn the first and third expressions into essentially garbage, and without de Morgan's law the second one seems useless too. How should I proceed?

$\endgroup$
3
  • $\begingroup$ Sorry, typo.... $\endgroup$
    – ithisa
    Jun 3, 2013 at 18:39
  • $\begingroup$ There is an assumption here that "natural deduction" starts with a well-defined set of inference rules. I suspect there are lots of different sets of inference rules that one can start with. Do you have a list of inference rules we can start from? $\endgroup$
    – Thomas Andrews
    Jun 3, 2013 at 18:46
  • $\begingroup$ I don't know your system's rules of inference, but it probably is highly likely that you can prove ($\lnot$(p $\lor$ q) -> ($\lnot$ p $\land$ $\lnot$ q)) and the like, and then use modus ponens to infer from one formula to the other just as you do when using what you call "de Morgan's law". $\endgroup$
    – Doug Spoonwood
    Jun 4, 2013 at 2:31

2 Answers 2

Reset to default
3
$\begingroup$

Hint: After listing your given premises, start by assuming $\lnot\lnot s$ or $s$, and derive a contradiction, using your premises. E.g.

premises
$\quad\vdots\quad$

  • $|$ Assume $s$

    • $\quad p\lor q$

EDIT: We can get assumption down to needing to find a contradiction from $p$. But, as noted in the comments, unless there is a typo in the questions statement, as written, this is not provable, as there exists a model (see Henno's comment) $p, s$ true, $q, r$ false, in which we have all premises true, but the conclusion false.

EDIT EDIT: Looks like we are now "good to go"...see comments.

$\endgroup$
16
  • $\begingroup$ That's what I tried. Immediately got stuck at $(p\lor q)$, not knowing what to do next, since no inference rule fits it. $\endgroup$
    – ithisa
    Jun 3, 2013 at 18:20
  • $\begingroup$ $q$ cannot hold (as that implies $(q \lor r)$), so $p$ must hold $\endgroup$
    – Henno Brandsma
    Jun 3, 2013 at 18:23
  • $\begingroup$ How to express that in propositional logic? Remember that de Morgan's is not allowed, and de Morgan's must be used to derive your result. $\endgroup$
    – ithisa
    Jun 3, 2013 at 18:25
  • $\begingroup$ From $p \lor q$ you need to use disjunction elimination (by cases): pursuing each case ("if p...then.... and "if q ...then...") From $q$, you can use disjunction introduction to get $q \lor r$ which contradicts the second premise, so we have that p must hold. Assuming p... $\endgroup$
    – amWhy
    Jun 3, 2013 at 18:26
  • 1
    $\begingroup$ @Eric feel free to check back if you have any further questions. Lots of natural logic proofs entail the need for using assumptions(sometimes repeatedly) to prove an implication, to arrive at a contradiction, etc. $\endgroup$
    – amWhy
    Jun 3, 2013 at 18:49
1
$\begingroup$

In classical logic, you can derive a contradiction and then either introduce or get rid of a negation. Since you want to get a negation, you consequently might want to assume "s" and then derive a contradiction.

Anytime you have a disjunction, see if you can get both disjuncts to lead to the same conclusion, and then use disjunction elimination.

For your problem, here's an outline of a proof in one system, though I don't know what your rules say exactly, so I don't know what a proof will look like exactly in your system.

1 | s assumption (I assume s, so that I can try and find a contradiction.)

2 | (p $\lor$ q) (I'd hope I don't need the proof analysis as to how I got this)

3 || q assumption (I choose q, since if I have ¬(q∨r), I can easily get the negation of q)

4 || (q $\lor$ r) (disjunction introduction on 3)

5 | $\lnot$q (contradiction from one of the premises and 4)

6 || p assumption

7 | (p->p) (6-6 conditional introduction)

8 || q assumption (I want (q->p), so I start with q))

9 ||| $\lnot$p assumption (I want p, so I assume its negation since I already have a contradiction)

10|| p (6 and 8 contradict each other)

11| (q->p) (8-10 conditional introduction

12| p (2, 7, 11 disjunction elimination)

Now, that I have "p", I can get "r" in the same scope as "p" via the first premise (either I have modus tollens as a rule of inference, or I assume $\lnot$ r and derive a contradiction which gives me r). Then, since I have "r" I use disjunction introduction to (q $\lor$ r). But, that gives us a contradiction within the same scope as s. So, then we can introduce the negation of s within the same scope as the premises for this problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .