PHL310 Valid Reasoning II, past assignments

Past Assignments
28 January
Here is a rough 14-week plan for us.

  • 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 January
I'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.
  1. If both Nemo and Jaws are fish, then neither Patrick nor Mr. Krab are.
  2. All men are mortal.
  3. Premises: (P --> Q), (R--> Q), (P v R). Conclusion: Q.
  4. Conclusion: ((P-->Q) --> (~Q --> ~P)
  5. Premises: ∀x(Fx --> Gx), ∃xFx. Conclusion: ∃xGx

9 February
Here'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 of A Concise Introduction to Logic, and answer the following questions from the book:
  1. Chapter 2 question 5.
  2. Chapter 3 question 1a and question 2a.
  3. Chapter 4 question 1.
  4. 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).
Conclusion: ¬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".

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 February
We 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 February
Last two track homework! Do one of the following.

1. Read chapters 6-11 of A 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!)

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 February
Read chapter 20 of A Concise Introduction to Logic.
23 February
Do 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 be any sentence (not just an atomic sentence).

27 February
Do 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. derive (m3) in system S5
  2. derive (m4) in system S5
  3. derive (m5) in the combination of systems M and Brouwer.
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.

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.
  1. (<>[]P → []P) this is the S5 dual, we prove a few times; you prove it again here
  2. [](<>[]P → []P) necessitation on the theorem on line 1
  3. ([](<>[]P → []P) → ([]<>[]P → [][]P) axiom (m2)
  4. ([]<>[]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 March
Read 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 March
I'll have extra office hours: 2-4.
9 March
Homework. 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. (C → (D → E)), D |-- (C → E)
  2. (A → B), (B → C) |-- (A → C)
1 is easy. 2 is less easy.
11 March
Now 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 March
27 March
Midterm. Modal logic. Using the three axioms of standard propositional logic. The Deduction Theorem. Completeness of the Propositional Logic.
30 March
Read chapter 16 of A Concise Introduction to Logic. (If quantifiers are only a dim memory for you, or -- heaven forbid, something unseen! -- read chapters 12-16 of the book.)
1 April
Read parts 2.1 and 2.2 of Mendelson.
8 April
Homework. In two tracks, since some of you have done quantifiers and some have not.

The newbie track. From chapter 13, do problems 1, 2, and 3.

The old hand track. From chapter 16, do problems 3, 4, and 5.
13 April
I'll be in Virginia. Here's a homework you can do for Friday; class time might be a good time to get together and work on it.
  1. Do problems 1, 2, and 3 of chapter 14.
  2. Do problems 1 and 2 of chapter 15.
  3. Prove the following theorems.
    1. (∀x∀yFxy → ∃x∃yFxy)
    2. (∃x∃yFxy → ∃y∃xFxy)
15 April
24 April
Read section 3.1 of chapter 3 of Mendelson.

Quick homework: Using only the axiom system (as outlined on page 62), and deduction theorem prove:

  • (∀x1(¬C(x1) → ¬B(x1)) → ∀x1(B(x1) → C(x1)))
Hint: look at A3. Also, you can us A4 to replace a bound variable with a free one (e.g., the equivalent of our arbitrary object in the natural deduction system). You might try proving it in the natural deduction system, and then translating the proof over to our axiom system.
27 April
Let's play with S to get a feel for it. Using just the axioms of S (page 150 in the latest edition of our book) prove that
  1. 2+2 = 4 (In the object language, this means you'll prove that 0''+0''=0''''. (To be even more accurate, something like Af1f2f20f2f20f2f2f2f20, where A is an arity two predicate meaning identity, f2 is the arity one successor function, and f1 is the arity two addition function. But ignore all that; I mention it only to show our parentheses are irrelevant and there only for our convenience. That is: the parenthesis that surround a function disappear when we replace the function with its referent, so don't be confused by this.) (Hint: look at S5 and S6.)
  2. 2 x 2 = 2 + 2 (Hint: look at S8; the dot is multiply.)
We allow free substition of identicals throughout your proofs, so you can always replace a term with an identical term. What that means is that you can have proofs like the following proof, given as a simplistic example, that 1+0=0+1:
1. 0' + 0 = 0' ....... Axiom S5
2. 0 + 0' = (0 + 0)' ...... Axiom S6
3. 0 + 0 = 0 ...... Axiom S5
4. 0 + 0' = 0' ...... substitution of identicals, 2, 3
5. 0' + 0 = 0 + 0' ...... substitution of identicals, 1, 4
Let's introduce the following principle: we won't care about the order of the elements in the function + or *. That's a bit of a cheat, but we know it's true that they give the same answer either way, so let's make our lives easier. Thus, we'll say x+0 can be freely substituted for 0+x, and so on.

Chris asked the following question: wouldn't it be great to have an axiom that let's you show x * 1 = x? The answer is that you can derive this quickly, for any case. Consider x * 1 = (x * 0) + x, according to axiom S8. But then we can quickly use axiom S7 and S5, and our principle above of not caring about order for the functions + and *, to get to x * 1 = x. Combine that insight with a look at S8, and you're almost there to show 2 * 2 = 4.
6 May
Prove the following, using natural/intuitive set theory and our definitions (and any axioms you want to use, from NBG or ZFC). Your proof will be written out as a paragraph explanation (don't bother to try to do a proof in the object language with numbered steps). Use any rules from the natural deduction system.
  1. Problem 4.7b from the book; that is, prove that ∀x∀y({x}={y} ↔ x=y)
  2. Problem 4.10c; that is, prove that X⊆Y ↔ X∩Y = X
  3. Problem 4.10d; that is, prove that X⊆Y ↔ X∪Y = Y
  4. Problem 4.10i; that is, prove that X∩∅ = ∅
8 May
Review. Bring questions.