• SynodOfDordt
    7
    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
    8.7k
    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
    7
    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
    8.7k
    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
    5.8k
    (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
    7
    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
    5.8k
    Glad you got it!
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment

Welcome to The Philosophy Forum!

Get involved in philosophical discussions about knowledge, truth, language, consciousness, science, politics, religion, logic and mathematics, art, history, and lots more. No ads, no clutter, and very little agreement — just fascinating conversations.