1
$\begingroup$

I'm doing some revision for my upcoming logic exam and I stumbled upon this question from an old exam paper which has me scratching my head.

enter image description here

The fact that there are no conditionals in either of the 2 premises is the problem - the solution doesn't seem to flow very well. I would assume this can be solved by assuming negations and then concluding with contradictions but I am going around in circles.

Any help would be greatly appreciated!

Thanks

$\endgroup$
  • $\begingroup$ Hint: Your prove will need a lot of disjunction eliminations: To prove $A \lor B \therefore C$, you start two new subproofs, one with the premise $A$, and one with the premise $B$, and in each of the subproofs you derive the conclusion $C$. Then you can apply $\lor E$ on the premise $A \lor B$ and the two subproofs, and conclude $C$. Here, you will need a nesting of $\lor E$ proofs, the outermost of which will have the form $C = P \lor S$. So start your proof with a last rule $\lor E$ and two subproofs $P \therefore P \lor S$ and $(Q \land R) \therefore P \lor S$, then fill in the details. $\endgroup$ – lemontree May 4 at 16:23
1
$\begingroup$

As a general observation, a normalized (≈ simplified) proof of $A_1, ..., A_n \therefore B$ will usually have in the first half elimination rules on the connectives that occur in the premises $A_1, ..., A_n$, and in the second half introduction rules for the connectives that occur in the conclusion $B$, and in the middle or towards the end possibly applications involving $\bot$ or LEM.
Imagine it as a kind of hourglass shape on the complexity of formulas: You deconstruct the premises by use of approporiate elimination rules until you arrive at formulas of least complexity (the center of the hourglass), then you assemble the pieces back together to the conclusion by use of appropriate introduction rules. Unfortunately, this hourglass shape is not so nicely visible in Fitch style proofs as compared to e.g. Gentzen-style tree proofs, and $\lor$ and $\bot$ often destroy some of the symmetry (for example in this proof, applications of introduction rules on the connective in the conclusion formula, $\lor I$, will occur in the middle rather than towards end of the proof), but it's a place to start.

Since your premises consists of disjunctions, your proof will start with many $\lor E$'s (= disjunction eliminations). It is in no way unusual that there are no conditionals in your premises; modus ponens (which is nothing but $\to$ elimination) may be one of the easiest rules, but if ther are no $\to$'s in your premises but $\lor$'s and $\land$'s instead, then you will simply need the rules for eliminating $\lor$ and $\land$ instead. It is perfectly well possible to construct a proof of an argument without conditionals, you just need the right rules to use.

So take a close look at how the $\lor E$ rule works:

The ieda of $\lor E$ is that in order to prove $A \lor B \therefore C$, we derive $C$ from both the assumption $A$ and the assumption $B$, then conclude that since we know that one out of $A$ or $B$ must be true, we can be sure that $C$ holds, no matter which of $A$ or $B$ is actually true. So we start two new subproofs, one with the premise $A$, and one with the premise $B$, and in each of the subproofs derive the conclusion $C$. Then we can apply $\lor E$ on the premise $A \lor B$ and the two subproofs $A \therefore C$ and $B \therefore C$, and conclude $C$:

enter image description here

For the proof of $P ∨ (Q ∧ R), (¬Q ∨ ¬R) ∨ S ∴ P ∨ S$, you will need a nesting of such $\lor E$ proofs.

The outermost one will have the conclusion $C = P \lor S$, so you start your proof with two subproofs $P \therefore P \lor S$ and $(Q \land R) \therefore P \lor S$, and set the last rule application to $\lor E$:

enter image description here

Note how the $\lor E$ rule cites the disjunctive premise $P \lor (Q \lor R)$ in line 1 and the lines of the two subproofs, $P \therefore P \lor S$ and $(Q \land R) \therefore P \lor S$.

In deconstructing the second premise $(\neg Q \lor \neg R) \lor S$, you will get another disjunction elimination which is nested into the subproof for $Q \land R \therefore P \lor S$:

enter image description here

And not much surprisingly, to get $\neg Q \lor \neg R \therefore P \lor S$ (= to fill in the ? on line 9), you will need yet another $\lor E$. In this part you will need to use the information you got out of the assumption $Q \land R$ (= the information to be filled for in the ? on line 7). Note also how I mentioned that in the middle of the proof you might have to work with $\bot$.

Now try to fill in the ?'s. Once you have the outer skeleton, it should be relatively easy to complete the details of the subproofs.

$\endgroup$
  • $\begingroup$ Again, thanks so much @lemontree! I actually managed to figure it out after your initial (short) post, as I didn't want to feel that I'm being spoonfed. My result is pretty much identical to your last post, with the missing bits filled in, obviously. Thank you for not giving me the full answer initially - figuring it out myself is obviously the best way for me to get used to how these proofs work. I feel like I'm really getting the hang of this now! You have been a great help, thank you! $\endgroup$ – Gerhardus Carinus May 4 at 17:36
  • $\begingroup$ That's good to hear. Maybe you find the hourglass analogy I just edited into the first part of my post helpful for future purposes, in case you haven't read the edit yet. $\endgroup$ – lemontree May 4 at 17:40
  • 1
    $\begingroup$ @RayLittleRock You're misunderstanding what that derivation shows. That $A \lor B \therefore C$ is in general not a tautology is obvious. But that picture does not show a derivation for some concrete formula with propositional letters $A, B, C$: It shows the general pattern of a disjunction elimination proof for formulas of the form $A \lor B$, $C$, where in a concrete derivation which has the shape of this derivation sketch, each of $A$, $B$, $C$ will be instantiated to a concrete formula. $A, B, C$ are not concrete formulas, but variables which stand for concrete instances of formulas... $\endgroup$ – lemontree May 26 at 19:55
  • 1
    $\begingroup$ ... for which the derivation will work. You immediately see in the subsequent explanation that for concrete instances of these formulas (here: $A = P, B = Q \land R, C = P \lor S$), a derivation of the form $A \lor B \therefore C$ is very well possible. In that case, the two subproofs which were left empty in the derivation scheme showing the general pattern of $\lor E$ can be filled with formulas obtained from the concrete formula instances. If you read the full post, you will see that what you think is a "wrong" derivation is just an illustration of how the $\lor E$ rule works in general... $\endgroup$ – lemontree May 26 at 19:55
  • 1
    $\begingroup$ ... where $A, B, C$ are just placeholders for formulas we don't know yet. $\endgroup$ – lemontree May 26 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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