EXERCISE 2.3.1. Provide a justification (rule and line numbers) for each line of these proofs. 1) A B NO -A = C CO A V - A A B B VC A = (B VC) 8 -A 9 C 10 BVC 11 -A = (B VC) 12 BVC2) LH -0 2 LV -O CO L 4 L OT L - L 6 -0 = L L\f\f\fEXERCISES 2.3.2. Write a twocolumn proof of each of the following deductions: 1)P:> (QVR), Q=>S, R=>S, P:>S' 2)Q:(Q=>P), Q=>P 3) MV (N=>M), IM=> uN 4)R=> (R:(R=>(R:Q))), .'.R=>(QVP) 5)AVB,A:C,B=>D,O=>E,D:E, .'.E Hypotheses: The Pope is here if and only if the Queen is here. The Queen is here if and only if the Registrar is here. Conclusion: The Pope is here if and only if the Registrar is here. Hypotheses: If Jim is sick, he should stay in bed. If Jim is not sick, he should go outside to play. Conclusion: Jim should either stay in bed or go outside to play. Hypotheses: If the King will sing, then the Queen will sing. If the King and the Queen will both sing, then the Prince and the Princess will also sing. If the King and the Queen and the Prince and the Princess will all sing, then the party will be fun. Conclusion: If the King Will sing, then the party Will be fun. Hypotheses: If the Pope is here, then either the Queen is here or the Registrar is here. If the Queen is here, then the Spy is here. If the Registrar is here, then the Spy is here. Conclusion: If the Pope is here, then the Spy is here. EXERCISES 2.4.3. Provide a justication (rule and line numbers) for each line of these proofs. \f( P V - Q ) = - R 4) 2 Q = P 3 R Q P PV -Q 5 00 - 0 01 R R & -R Q 10 PV -Q 11 -R 12 R & -R 13 -R\fEXERCISES 2.4.4. Give a twocolumn proof of each of these deductions. 1) Q :~ (Q 85 e). so 2) J: m], J 3) U=> X, V => |X, I(U&V) 4) (MVN) => uT, |T=> uM, M Hypotheses: If Alice is here, then Bob is here. 5) If Bob is here, then Carol is here. If Carol is here, then Bob is not here. Conclusion: Alice is not here. EXERCISE 2.5.2. Give a twocolumn proof of the deduction A: (3&0), A, 0 Work backwards from what you want. The ultimate goal is to derive the conclusion. Look at the conclusion and ask what the introduction rule is for its main logical operator. This gives you an idea of where you want to be just before the last line of the proof. Then you can treat this line as if it were your goal; we call it a subgoal because it represents partial progress toward the true goal. Ask what you could do to derive the subgoal. For example: 0 If your conclusion is l & 23, then you need to gure out a way to prove l and a way to prove 93. o If your conclusion is a conditional J4 if 13, plan to use the :intro rule. This requires starting a subproof in which you assume )4. In the subproof, you want to derive Q3. 0 The last of the four mazes in Exercise 2.5.1 is easy if you work backwards from the nish, instead of forward from the start. EXERCISE 2.5.3. Give a twocolumn proof of the deduction (PVQ) => (R858), (RVS) => (P&Q), P=> Q Try breaking the proof down into cases. If it looks like you need an additional hypothesis (A) to prove what you want, try considering two cases: since A V A is a tautology (\"Law of Excluded Middle\"), it sufces to prove that A and oil each yield the desired conclusion. EXERCISE 2.5.4. Give a twocolumn proof of the deduction PiQ, wPiR, (QVR):S, 5' Look for useful subgoals. Working backwards is one way to identify a worthwhile sub goal, but there are others. For example7 if you have 521 2 you should think about whether you can obtain .54 somehow, so that you can apply =>elimination. EXERCISE 2.5.5. Give a twocolumn proof of the deduction (RVS) => (PVQ), uQ, R: P Change what you are looking at. Replacement rules can often make your life easier; if a proof seems impossible, try out some different substitutions. For example: 0 the Rules of Negation should become second nature; they can often transform an assertion into a more useful form. 0 Remember that every implication is logically equivalent to its contrapositive. The contrapositive may be easier to prove as a conclusion, and it might be more useful as a hypothesis. EXERCISE 2.5.6. Give a twocolumn proof of the deduction P, P a Q), Q v R, R 2. Twocolumn proofs 47 Do not forget proof by contradiction. If you cannot nd a way to show something directly, try assuming its negation, and then look for a contradiction. For example, instead of proving )4 V Q3 directly, you can assume both nl and n13, which is likely to make the work easier. EXERCISE 2.5.7. Give a two-column proof of the deduction P=>Q, Q:>P, P Repeat as necessary. After you have made some progress, by either deriving some new assertions or deciding on a new goal that would represent substantial progress, see what the above strategies suggest in your new situation. Persist. Try different things. If one approach fails, try something else. When solving a difcult maze, you should expect to have to backtrack several times, and the same is true when doing proofs. EXERCISES 2.5.8. Give a twocolumn proof of each of these deductions. 2)P:>(QVR), Q=>.P,R:>S, .'.P:>S