## PHL310 Valid Reasoning II, past assignments

Past Assignments28 JanuaryHere is a rough 14-week plan for us.

Week

- 1-2. Natural deduction system review.
- 3-4. Natural deduction system: multiple quantifiers and functions.
- 5. Introduction to some basic set theory.
- 6. Axiomatic system for propositional logic. Proofs with the axiomatic system.
- 7. Mathematical induction. Proving completeness of propositional logic.
- 8. Axiomatic system for quantified logic.
- 9. Brief on proving completeness of quantified logic.
- 10. The Dedekind axioms (AKA the Peano axioms).
- 11. Axiomatic set theory.
- 12. Modal logic. Basic systems.
- 13. Modal logic semantics.
- 14. Applying modal logic to philosophical problems. Also: deontic logic, logic of time.
30 JanuaryI'd like to see what system you learned, and where you are at. Five problems, just for me to see. The first two are just translations into some kind of formal logic. For problem 1, use a propositional logic (the smallest things in your language will be sentences). For problem two, use a quantified logic with predicates. For 3-5, generate a proof (a syntactic proof, not a truth table). Use whatever rules or proof methods you remember.

- If both Nemo and Jaws are fish, then neither Patrick nor Mr. Krab are.
- All men are mortal.
- Premises: (P --> Q), (R--> Q), (P v R). Conclusion: Q.
- Conclusion: ((P-->Q) --> (~Q --> ~P)
- Premises: ∀x(Fx --> Gx), ∃xFx. Conclusion: ∃xGx

9 FebruaryHere's a homework with two tracks, since some of us are catching up and some remember the material well. If remember the propositional logic, do (or at least try) track 2. Else do track 1.

1.Read chapters 1 through 5 ofA Concise Introduction to Logic, and answer the following questions from the book:

- Chapter 2 question 5.
- Chapter 3 question 1a and question 2a.
- Chapter 4 question 1.
- Chapter 5 questions 1 and 2d.
2.We can make use of a theorem -- or of a special sentence called an "axiom" -- in the following way. If you replace every occurence of a sentence in a theorem or axiom with a different sentence (but the same replacement in each case), you also get a theorem or axiom. So, if ((P → Q) → (¬Q → ¬P)) is a theorem, you can replace P with R, and Q with (S v T) and get the following theorem: ((R → (SvT)) → (¬(SvT) → ¬R)).

It turns out that we can do away with indirect derivation if we allow ourselves certain sentences as axioms (an axiom is a sentence that we assume--it's like a very special premise; but we treat it the way we treat theorems in that we'll allow versions or instances of it).

Prove the following:Premises: (R → S), (¬S v ¬R).But prove it without using indirect derivation, but rather a direct derivation and also by using the following (((P → Q) ^ (P → ¬Q)) → ¬P) as your axiom. (If you feel stuck, first prove it using indirect derivation, and then look at your proof and think of how you can use that axiom....) The way to use the axiom is: any time you like, you can write down either (((P → Q) ^ (P → ¬Q)) → ¬P), or you can write a sentence that is made from that by replacing each P with some sentence, and each Q with some sentence. Your justification on the right is "axiom".

Conclusion: ¬R.

Try this one if you feel ambitious. Using that axiom, can you prove without indirect derivation:Premises: (P → R), (Q → R), (P v Q).

Conclusion: R.

11 FebruaryWe agreed to a revised schedule, which will allow us to review and learn new stuff at the same time:

- Natural deduction system review: propositional logic.
- Propositional modal logic. Basic systems. Also: some very basic set theory.
- Propositional modal logic semantics.
- Applying modal logic to philosophical problems. Also: deontic logic, logic of time.
- Axiomatic system for propositional logic. Proofs with the axiomatic system.
- Mathematical induction. Proving completeness of propositional logic.
- Natural deduction system: multiple quantifiers and functions.
- Axiomatic system for quantified logic.
- Brief on proving completeness of quantified logic.
- The Dedekind axioms (AKA the Peano axioms).
- Axiomatic set theory.

13 FebruaryLast two track homework! Do one of the following.

1.Read chapters 6-11 ofA Concise Introduction to Logic. Do problems:

- Chapter 6, problems 1a, 1b, 1c, 2b, 2c.
- Chapter 7, problems 3c and 3e
- Chapter 8, problem 1f
- Chapter 9, problem 2a (hard one!)

2.It turns out that we can say everything that can be said in the propositional logic using just two connectives: ¬ and →. Prove this by making expressions equivalent to (P v Q) and (P ^ Q) and (P ↔ Q) that use only negation and conditionals. Make truth tables to show that your expressions have the same meaning as the disjunction, conjunction, or biconditional, respectively.

16 FebruaryRead chapter 20 ofA Concise Introduction to Logic.23 FebruaryDo problem 2 of chapter 20.

I've been asked for some hints (write me if you need others). I'll write [] for the necessity box and P for phi.

Regarding 2.2, how would you show ([]P ↔ [][]P) in S4? Well, you would of course show ([]P → [][]P) and then show ([][]P → []P) and use the bicondition rule to put those together. Note that in S4 you already have as an axiom ([]P → [][]P); that is an instance of axiom (M4). Now look closely at axiom (M1). Remember that the PHI can beanysentence (not just an atomic sentence).

27 FebruaryDo problem 3 of chapter 20.

Some hints.

This is really 3 problems. After some reflection, I think this is the easiest order to do them in:1 and 2 will prove that from S5 you get Brouwer & M combined; and 3 will prove that from Brouwer & M combined you can get S5.

- derive (m3) in system S5
- derive (m4) in system S5
- derive (m5) in the combination of systems M and Brouwer.

For 1: note that we've proved lots of times that (P → <>P). But (m5) is (<>P → []<>P). What does the chain rule give you?

For 2: this one is hard. To do it, why not fill in the blanks of this proof. I can't draw fitch bars, so we need to be careful about dependencies.

- (<>[]P → []P) this is the S5 dual, we prove a few times; you prove it again here
- [](<>[]P → []P) necessitation on the theorem on line 1
- ([](<>[]P → []P) → ([]<>[]P → [][]P) axiom (m2)
- ([]<>[]P → [][]P) modus ponens 2, 3

Now note, we have proven that in S5 we have as a theorem axiom (m3) -- that is, we have (P → []<>P). An instance of this theorem is ([]P → []<>[]P). Chain rule!

For 3: OK, this one is less hard, but still challenging. Some tricks will be required! Consider this. The following is a theorem we can prove using (m4): (<><>P --> <>P). I think we proved that but prove it again. Since it's a theorem, you have by necessitation that [](<><>P --> <>P) (for justification you can write, "theorem, necessitation"). Now, consider what you'll get using axiom (m2) if that is the antecedent of an instance of (m2) (remember that the antecedent is the 'if' part of a conditional--and (m2) is a conditional). Finally, note that this is an instance of (m3): (<>P-->[]<><>P). Think about chain rule.

2 MarchRead sections 1.1 through 1.4 of Mendelson. That's not a lot, since there are a lot of questions in there; 1.4 will be challenging, but just familiarize yourself with the material, and look closely at the axioms.6 MarchI'll have extra office hours: 2-4.9 MarchHomework. Prove the following. If you get stumped, you may use the deduction theorem and you will receive a particle of credit, but for full credit you must prove them with Axioms 1-3 and modus ponens alone. (In fact, you'll never need Axiom 3.)1 is easy. 2 is less easy.

- (C → (D → E)), D |-- (C → E)
- (A → B), (B → C) |-- (A → C)
11 MarchNow that we've review the material, re-read sections 1.1 through 1.4 of Mendelson. In class, we'll continue the completeness proof.23 MarchCompleteness!