Problem in Tomassi

SynodOfDordt

This is a rather modest question from a rather modest logician. I am not a logician mainly, but I recently decided to keep it up as a hobby. I have been reviewing my old undergraduate textbook, Logic by Paul Tomassi, and there is a tricky question which I cannot see my way to solving. Simply, I have to find a proof for the following sequent in propositional logic:

(P & Q) --> ~R : R --> (P --> ~Q)

I must do so in a line-by-line format, with each line having a line-number, a dependency number, the formula in question, and the rule by which the formula is used. The book claims that this proof should be 11 lines long when completed. The problem is that, at this stage, there is only a limited set of rules to make use of. These are limited to: &-introduction, &-elimination, modus ponens, conditional proof (ie. assuming the antecedent of a conditional in order to infer its consequent), double-negation-introduction, double-negation-elimination, and modus tollens.

Here is all I have managed so far: seeing that the conclusion is a conditional, I assume "R" for a conditional proof. As the consequent of this is also a conditional, I assume the antecedent of this, also, which is "P". My assumption "R" allows me (via the intermediate step of double-negation-introduction) to enact modus tollens on the premise, to get the negation of the antecedent, ~(P & Q). It ends up looking like this:

{1} 1. (P & Q) --> ~R Premise
{2} 2. R Assumption for conditional proof
{3} 3. P Assumption for conditional proof
{2} 4. ~~R DNI
{1,2} 5. ~(P & Q) MT

And that's it! I can't see my way towards doing anything else, with the rules I have. Obviously my short-term goal is to somehow infer "~Q" by means of my assumption "P". Once done, everything else should fall into place nicely. But how I do that with the available rules, I do not know. I would be appreciative for help, thank you.

EDIT: my post was automatically formatted in such a way that the lines of my proof became more bunched together than I had originally intended. Apologies for this.

tim wood

By truth table, It's only a little bit tedious to set up. But it works. (It doesn't matter if your colon is an "and" or implication.)

SynodOfDordt

The exercise calls for the proof to be presented in the line-by-line format I used above. It has to be like that.

unenlightened

Without actually doing it, It seems to me that you might manage along these lines:
assume P
assume (P--> ~Q)
Deduce ~(P & Q)

A sort of reductio.

fdrake

(P & Q) --> ~R : R --> (P --> ~Q)

I've used theorem intro and missed a few steps, if you needed to you could prove the theorems:
(A) (P->Q) <-> (~P or Q) <-> (~Q->~P)
(B) ~(P & Q) <-> (~P or ~Q)

(1) Assume P&Q --> ~R
(2) Assume R
(3) Z-->U |- ~U --> ~Z (theorem intro, modus ponens->modus tollens in A (first and last equivalence)
(3) R-->~(P&Q) (1,3)
(4)~(P&Q)->(~P or ~Q) (theorem intro, from B, de morgan's law)
(5) ~(P&Q) (2,3)
(6) (~P or ~Q) (theorem intro from A, first and second equivalence)
(7) (P->~Q) (theorem intro from A, second and 3 equivalence + double negation elimination)
(8) R--> (P-->~Q) (2,7)

SynodOfDordt

Thank you for the suggestions, though the question calls for me to use only the rules I stipulated above. It is interesting, though: in the textbook where this exercise appears, this question is posed before the reader is introduced to reductio ad absurdum. I am inclined to think that this is a mistake, though. The reason is that the proof can be completed easily enough once reductio is introduced into one's arsenal of rules, and this results in a proof of exactly 11 lines, which is just the number of lines that the textbook indicates is correct. With reductio, the proof I arrived at goes something like this:

(P & Q) --> ~R : R --> (P --> ~Q)

1. (P & Q) --> ~R (Premise)
2. R (Assumption for conditional proof)
3. P (Assumption for conditional proof)
4. Q (Assumption for reductio)
5. ~~R (Double-negation introduction on 2.)
6. ~(P & Q) (Modus tollens 1,5)
7. P & Q (&-Introduction 3,4)
8. (P & Q) & ~(P & Q) (&-Introduction 6,7)
9. ~Q (Reductio 4,8)
10. P --> ~Q (Conditional proof 3,9)
11. R --> (P --> ~Q) (Conditional proof 2,10)

Hopefully that'll do it.

fdrake

Glad you got it!

Problem in Tomassi

Welcome to The Philosophy Forum!

Categories

More Discussions