Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

[(P -> Q) and (~R or S) and (P or R)] -> (~Q -> S).

Steps:
1. ~(~Q -> S)
2. ~Q and ~S
3. ~S
4. ~R or S
5. ~R
6. P -> Q
7. ~Q
8. ~P
9. P or R
10. R
11. ~R and R
12. Therefore: ~Q -> S

I believe what they are looking for in this question is which logical equvilances and rules of inference are used in each step? Can someone assist with this? Thank you.

share|improve this question
1  
How far have you got? Is this homework? –  Orbling Apr 22 '11 at 23:54
    
Note Step 1 is setting up for a proof by contradiction (PC), the negative of the target. You have all the steps, you just have to state how they are inferred from the given facts. –  Orbling Apr 22 '11 at 23:56
    
I have Step 1 as a Contradiction, Steps 4, 6, 9, 12 as Premises... can anyone spot any others? –  Pete Apr 23 '11 at 0:06

2 Answers 2

up vote 2 down vote accepted

Well, this should give you some ideas as to how those steps have been achieved, it may be a bit rough around the edges as it has been about a decade since I last tackled first order logic.

$$ \begin{array} \textrm{Given:} & [(P \to Q) \land (\lnot R \lor S) \land (P \lor R)] \to (\lnot Q \to S) \\ \end{array} $$

$$ \begin{array} \textrm{1.} & \lnot (\lnot Q \to S) & (\textrm{assumption, PC from 12}) \\ 2. & \lnot Q \land \lnot S & (\textrm{Lemma: }\lnot (A \to B) \to A \land \lnot B(1)) \\ 3. & \lnot S & (\land E(2)) \\ 4. & \lnot R \lor S & (\land E(Given)) \\ 5. & \lnot R & (\lor E(3,4)) \\ 6. & P \to Q & (\land E(Given)) \\ 7. & \lnot Q & (\land E(2)) \\ 8. & \lnot P & (\textrm{Modus tollens: }[(A \to B) \land \lnot B] \to \lnot A(6,7)) \\ 9. & P \lor R & (\land E(Given)) \\ 10. & R & (\lor E(8,9)) \\ 11. & \lnot R \land R & (\land I(5,10)) \\ 12. & \lnot Q \to S & (PC(1,11), \lnot E(5,9,11)) \\ \end{array} $$

Step 11 seems unnecessary, as 5 & 9 provide a $\lnot E$ on their own.

The lemma I added on step 2 can be proved via an $\land I$ on both the parts, showing that if $Q$ or $S$ is true (proof by contradiction on the two parts) then $(\lnot Q \to S)$ is true, which gives you a $\lnot E$ on 1.

I find a useful/fun tool for proofs like this is a piece of software called Pandora, produced by successive students and researchers at Imperial College, uses the Box Model proof.

share|improve this answer
    
Thank you, this is kind of what I was looking for, I will be sure to check out Pandora. –  Pete Apr 23 '11 at 4:18
    
@Pete: Quite alright, it was fun; used to be a dab hand at that sort of proof, useful to get the rust off an old skillset. –  Orbling Apr 23 '11 at 8:16
    
@Pete: Is that sufficient for the question, or do you need more help? If sufficient, then would be good to accept the answer, so no more people spend time unnecessarily on it. [Only mention this as you are new.] –  Orbling Apr 23 '11 at 8:39

I simply wanted to point out that in the answer/proof above, we are given the conditional:

$[(P \rightarrow Q) \land (\lnot R \lor S) \land (P \lor R)] \rightarrow (\lnot Q \rightarrow S).$

Technically speaking, you cannot take the antecedent (part before arrow) as a given, and then use "and elimination" or &E, to pull out the antecedent's conjuncts (components joined by "and"), simply by assuming the negation of the conclusion. What is given is an entire sentence, and a conditional simply asserts that if the antecedent holds, then the conclusion/consequence follows. It is perfectly fine to start with assuming the negation of the conclusion. What follows from the negation of the conclusion is the negation of the antecedent.

It should be made explicit, as a step in the proof, that, in addition to assuming the negation of the consequence, we are to assume the truth of the antecedent. That is, we are assuming that the conditional is false, and the only way that a conditional can be false is if the antecedent (the "if" part) is true and the conclusion (the "then" part) is false. Once the antecedent is asserted, as an assumption, then the conjuncts (parts joined by "and") can be used in the proof.

Perhaps I'm splitting hairs, but I think it's worth pointing out.

Actually, I could have been more concise: In the proof above, it is taken as given precisely what we are to prove! To prove the conditional, you can take as given only $(P \rightarrow Q) \land (\lnot R \lor S) \land (P or Q)$ (better yet, use "assumption" as a justification), then argue as above using proof by contradiction. Upon arriving at the contradiction, from which $12$ then follows, what you have ultimately proven is this: IF $\;\;[(P \rightarrow Q) \land (\lnot R \lor S) \land (P \lor R)]\;$ THEN $\;\;(\lnot Q \rightarrow S)$. So technically, there should be a 13th step which is the conclusion of the proof: if (4 & 6 & 9), then 12, justified by "conditional introduction." That is, you have shown that, if 4 and 6 and 9 are all true, then 12 must also be true (i.e, that 12 cannot be true).

I am quite sure that was what was meant in the proof above; but it is really crucial, when first learning logic, that givens, assumptions, conclusions, etc, and the reasoning used, be made crystal clear.

For clarification regarding the move from $\lnot (\lnot Q \rightarrow S)$ to $(\lnot \land \lnot S$):

You may have learned that $(p \rightarrow q)$ is equivalent to $\lnot p \lor q)$. If so, that makes an excellent intermediate step:

$$\lnot(\lnot Q \rightarrow S) \iff \lnot(\lnot\lnot Q \lor S) \iff \lnot(Q \lor S) \iff (\lnot Q and \lnot S)$$ (the last equivalence being an application of DeMorgan).

Pete, I hope I haven't confused you. You may very well have learned different names for the rules and equivalences used here. Textbooks vary in terms their use of such names. The most important thing is that you first understand how to derive/verify them. If you understand the logic, you should recognize the rule, whatever it happens to be named.

share|improve this answer
1  
J.M.: I was trying to stick religiously to the 12 points stated by the OP in his question, and giving minimal proof pointers for the steps taken. You are right of course. My own proof for that statement was somewhat longer. The naming (lack of) conventions in logic really is annoying, I learnt a particular style (most inferences being elimination/introduction) and sometimes find it hard to follow other styles as result. No doubt this makes it hard for novices to find help. –  Orbling Apr 25 '11 at 1:43
1  
@Orbling: I figured so; that's why I stated that I was confident you knew what you were doing. I too found it difficult to stick to the given steps of the proof; it isn't how I would have approached it! You're right about there being no consistent naming convention for rules of inference and such. It is annoying. I learned the elimination/introduction approach while tutoring logic; it took some getting used to. If a question like this comes up again, maybe I'll take the time to list alternative naming conventions so similar posts can be be offered a link to the "translations". –  amWhy Apr 25 '11 at 2:21
1  
J.M.: It is a shame that such confusions exist in the field, as it really is the most enjoyable deductive fun and is spoilt for many. A translation guide would be a useful paper to produce. I have seen some reasonable textbooks on first order logic, but they rarely excel truly - usually due to the author having trouble bringing their knowledge of the domain down to a simplistic level. As philosophers often have to study the subject, who are not necessarily mathematically inclined, this does pose a barrier to entry. –  Orbling Apr 25 '11 at 5:50
    
Complete, however, old. +1 –  Babak S. Jan 29 '13 at 20:49
    
@amWhy I have been voting to undelete and reopen all reasonable questions, but they need more votes. Please peruse the long list of Undelete and Reopen items in the 10K tools and help reverse the destructive campaign. –  Bill Dubuque Aug 5 at 3:48

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.