3
$\begingroup$

[(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.

  • 0
    I have Step 1 as a Contradiction, Steps 4, 6, 9, 12 as Premises... can anyone spot any others?2011-04-23

2 Answers 2

2

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.

  • 0
    @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.]2011-04-23
5

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.

  • 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.2011-04-25