Problem in Tomassi
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.
(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.
Comments (6)
assume P
assume (P--> ~Q)
Deduce ~(P & Q)
A sort of reductio.
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)
(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.