PHL310 Valid Reasoning II, past assignments




Past Assignments
January: Here's your first assignment: send me a digital head shot, via email to delancey@oswego.edu. Name the file after yourself, lastnamefirstname. For example, "SmithJoe.jpg." If you don't have a digital camera or don't know anyone who has one, no foul; it's just to help me learn peoples names, and also to compare your photo to the FBI wanted lists. Thanks! NOTE: I can't know who the photo is of if you send it from your cellphone without naming the file or adding some kind of text message! -- it arrives with an ID like 1313125736

February 2 complete the following problems, write them up, and bring me your answers to hand in at the beginning of class. Note the natural way to prove the first three is using direct derviation for 1, conditional derivation for 2, indirect derivation for 3, and combination of all those for 4, and then something special for 5.
  1. Premises: (P --> Q), (S ^ ~T), (T v P), (~R --> ~S).
    Conclusion: (Q ^ R)
  2. Premises: (~R v T), (T --> Q), ((Q ^ S) <--> V), (V <--> P).
    Conclusion: ((R ^ S) --> P)
  3. Premises: (~P v Q), (Q --> S), ~S.
    Conclusion: ~P
  4. Conclusion: (~(P ^ Q) <--> (~P v ~Q)). This theorem is known as one of De Morgans Theorems.
  5. Prove that we don't need "^", "v", and "<-->" if we have "~" and "-->". You'll do this with a separation of cases argument, and there are 3 cases ("^", "v", and "<-->"). Thus, show that you can produce the same truth table for "^" using just "~" and "-->"; and so on. Note that this is your first argument in our metalanguage and proving something about our object language; thus, it is a different kind of proof than those above.
#4 is cruel. Consider it a stretch opportunity, as they say in the corporate world. Here are some hints. Prove both directions. Each direction is a conditional, so you'll do two conditional derivations and then you'll join their two conclusions together to get your main conclusion using the rule conditional-to-biconditional. (If you get stumped, show me you see how the form goes, and then I'll give you most of the credit for it -- what matters is you see the direction to go in, more than seeing the steps.) Note that the right to left direction is easy: if you assume ~P v ~Q you can then do an indirect derivation of ~(P ^ Q) and get a contradiction quickly from the assumption of ~~(P ^ Q). The other direction is hard! Do a conditional derivation, assume ~(P ^ Q) and then do an indirect derivation of (~P v ~Q). This means you'll assume ~(~P v ~Q). Now, prove P using an indirect derivation (you'll be able to contradict your assumption of ~(~P v ~Q)). Now prove Q using a similar indirect dervication. Put these together, and you contradiction your assumption for conditional derirvation of ~(P ^ Q)! Tough, but I've handed it to you on a platter!

February 11 homework. Prove the following. Problems #2, 3, and 4 are easy but special; these sentences will become very familiar to you later. Remember you can do proofs within proofs; so that problem #2 will require a conditional proof within a conditional proof; same for #3. #4 will likely require a conditional proof with an indirect proof inside it.
  1. Premises: (P --> (T ^ ~Q)), ~T v R. Conclusion: ~(P ^ (R <--> Q)).
  2. Conclusion: (Q --> (P --> Q))
  3. Conclusion: ((P --> (Q --> R)) --> ((P --> Q) --> (P --> R)))
  4. Conclusion: ((~P --> ~Q) --> ((~P --> Q) --> P))
  5. We can symbolize alternative denial with a "|". Then, (P|Q) means one or the other or both of P and Q are false. Show that you need only this one connective and can use it to define all our usual connectives. That means making five truth tables. It's ugly do-able after we go over the last problem of the last homework. (FYI: another sole sufficient connective is the joint denial, usually shown as an arrow pointing down, which means both sentences are false. But let's do alternative denial.)
Puzzle: here's the Smullyan puzzle I told you, concerning relations. If Arabians are friends only with Arabians, and friendship is symmetric, not transitive, and not reflexive, can you say if there are any Arabians with exactly the same number of friends?

March 2: some practice of UI, EG, EI, and universal derivation. Try to prove the following; I'll use "\/" to mean some (the backwards E) and "/\" to mean all (the upside-down A):
  1. Premise: ~Fa, /\x(Fx v Gx), /\y(Gy --> Hy). Conclusion: Ha.
  2. Premise: \/x(Jx ^ Kx), /\x(Jx <--> Lx), /\x(Kx --> (Mx ^ Nx)). Conclusion: \/x(Lx ^ Mx).
  3. Premises: /\x(Fx <--> Gx), /\x(Gx <--> Hx) Show: /\x(Fx <--> Hx)
  4. Premises: /\xFx, /\xGx. Conclusion: /\x(Fx ^ Gx)
  5. Premises: /\x(Fx --> Gx), /\x(Hx --> Ix) Show: /\x((Fx ^ Hx) --> (Gx ^ Ix))

4 March, 5:00 p.m. REVIEW SESSION: we'll review any or even all of the problems below. I'll work on getting a room.

Practice: here are some problems that people can try for practice. Do as many as you like for practice, or any that look hard for you, and then maybe in the future we can do a session of reviewing and practicing them.
  1. Premises: (~~P --> S), P. Show: ~~S.
  2. Premises: ~(T --> R), ((P --> V) --> (T --> R)). Show: ~(P --> V).
  3. Premises: (~P --> V), ~V, (P --> Q). Show: Q.
  4. Premises: (~(R --> S) --> V), ((R --> S) --> Q), ~Q. Show: V.
  5. Premises: (P --> R), (R --> Q). Show: (P --> Q).
  6. Premises: (S --> R), (P --> S). Show: (~R --> ~P).
  7. Premises: (~P --> ~S), S. Show: P.
  8. Premises: ~(P --> Q), ((R --> T) --> (P --> Q)). Show: ~(R --> T).
  9. Premises: (P --> Q), (Q --> R), (R --> S), (S --> T), ~~P. Show: T.
  10. Premises: (~(R --> S) --> V), ((R --> S) --> Q), ~Q. Show: V.
  11. Premises: (P --> R), (T --> P), (S --> T), ~R. Show: ~S.
  12. Premises: (R --> Q), (Q --> S), (P --> R). Show: (P --> S).
  13. Premises: (P --> S), (Q --> P), (~R --> Q). Show: (~S --> R).
  14. Premises: ((T v R) <--> S), (S ^ ~Q), (T <--> Q). Show: R.
  15. Premises: (P <--> R), (R ^ ~S), (S v T). Show: ((Q v P) ^ T).
  16. Show: (~Q --> ~(P ^ Q))
  17. Show: (Q --> R) --> ((P --> Q) --> (P --> R))
  18. Show: ~(P --> Q) <--> (P ^ ~Q)
  19. Show: (P ^ Q) <--> ~(~P v ~Q)
  20. Premises: (P ^ R), (P --> S), (Q --> ~(S ^ R)). Show: ~Q
  21. Show: ((P ^ ~Q) --> ~(P --> Q))
  22. Show: (~(R --> T) --> ~T)
  23. Premises: (P <--> R), (R <--> S), (S <--> Q). Show: (P <--> Q).
  24. Make the truth table for the following sentence: (~(P v Q) <--> (~P ^ ~Q)).
  25. Make the truth table for the following sentence: (~(P ^ Q) <--> (~P v ~Q)).
  26. Make a truth table for the following sentence: ((~P --> Q) <--> ~R).
  27. Make a truth table for the following sentence: ((R ^ S) <--> (P v S)).
  28. Show the following argument is not valid using a truth table. Premises: (P v Q), P. Conclusion: ~Q.
  29. Show the following argument is not valid using a truth table. Premises: (~R --> S). Conclusion: ~R.
  30. Show the following argument is not valid using a truth table. Premises: ~(T --> V). Conclusion: ~T.
  31. Show the following argument is not valid using a truth table. Premises: ~(R^S). Conclusion: ~R.
  32. Show the following argument is not valid using a truth table. Show that this is not a tautlogy: ((P ^ Q) <--> (P v Q))
  33. Premises: /\x(Fx --> Gx), FC. Conclusion: GC.
  34. Premises: /\x(Fx <--> Gx), /\x(Gx <--> Hx), FA. Conclusion: HA.
  35. Premises: /\x(Gx v Hx), ~HB. Conclusion: \/xGx.
  36. Premises: /\x(Fx --> (Gx ^ P)), /\xFx. Conclusion: P.
  37. Premises: /\x(Q v (Gx v Hx)), /\x~Gx, ~Q. Conclusion: HC.
  38. Show: /\z(Fz <--> Gz). Premises: /\x(Fx <--> Hx), /\y(Hy <--> Gy).
  39. Show: VxFx. Premises: Vx(Gx ^ Hx), /\x(Gx --> Jx), /\x((Hx ^ Jx) --> Fx).
  40. Show: Vx(Gx ^ ~Hx). Premises: \/x~Hx, /\x(Gx v Hx).
  41. Show: /\x(Fx --> Gx) --> (/\xFx --> /\xGx)
  42. Show: ~/\xFx <--> \/x~Fx
Note that "/\x" is K&M speak for all x, and "\/x" is K&M speak for some x.

March 6: read Mendelson sections 1.1 through 1.6. The password is "cd310".

March 20: proofs in the axiomatic system. First two practice problems for your own edification; I won't ask you to hand them in. (1)Make truth tables for our three axioms to convince yourself that they are tautologies. (2) Using just substitution to find instances of our three axioms, and modus ponens, show:
  • (~~B --> B)
  • (~B --> ~A) --> (A --> B)
These problems are actually proven in your book. Do the following: try them on your own; then look at the book's proof; then see if you can fill in the blanks (that is, show the steps that lean on lemmas). Next, some real problems I will ask you to hand in. Show the following:
  1. (A --> (B --> C)), (A --> B) |-L (A --> C)
  2. |-L ((A --> B) --> ((C --> A) --> (C --> B)))
  3. |-L (P --> (~P --> Q))
I'll allow you the chain rule to make things simpler. This is known as corollary 1.10a in your book. For problem 3, I'll allow the deduction theorem (this means that you can do the equivalent of a conditional derivation). Also, for problem three, note how like problem 1.11c this is.

April 6 Brief quiz in class. Topic is axiomatic propositional logic. Call the propositional logic we studied, L.
  • What are the axioms of L?
  • Proving basic theorems (such as those listed as Lemma 1.11a, b, c, d on page 38 in Mendelson), using only axioms and the deduction theorem (as conditional derivation); or proving the chain rule (corollary 1.10a on page 38) with axioms alone.
  • What is soundness for L? Is L sound? How do we know that L is sound or not sound?
  • What is completeness for L? Is L complete? Assuming the weird lemma, how can we prove completeness? Do so, if L is complete.
  • What does it mean to say a propositional logic is consistent? Is L consistent? How do we know?

24 April: please hand in your answer to the next three easy questions.
  1. Here's the "hello world" of induction problems. Solutions are ubiquitous, so I'm asking you to use the honor system and give it a try all on your own. Suppose we have a language with an extension like the Dedekind axioms and now you can just do natural mathematics (no need to attempt this axiomatically). Then an equation that I believe Gauss proved when he was a kid will be a theorem: 1 + 2 + 3 + ... + n = (n2+n) /2. Show this using mathematical induction. It can be done, by the way, with weak induction or strong/complete induction. Hints: remember that 1 is your base case; and also, factor (n2+n) /2 to (n*(n+1))/2; let n be your induction case, and then you'll be proving this is true for n+1. More hints: What will your proof step be like? Well, note that you get to assume that 1+2+3... +n = (n*(n+1))/2. Now, for sake of illustration, let's suppose the next number is z. Then we can see that the sum 1+2+3+... +n+z is (n*(n+1))/2 + z, assuming our induction hypothesis. Thus, you've proved the n+1th case if you can show that (z*(z+1))/2 = (n*(n+1))/2 + z. OK, you can do that if you can find a way to say z that will allow you to solve. And that's obvious: what is z, after all, in relation to n? (This can be done with what we called "weak mathematical induction" -- where our induction hypothesis holds for arbitrary n, and does not require strong mathematical induction where we assume the theorem is true for all j < n.)

  2. Suppose the elements of our domain are natural numbers. Answer the following:
    a. What will some (at least 3) of the elements of the interpretation of the predicate ">" (greater than) be? (That is, what are some tuples of elements from our domain satisfy this predicate?)

    b. What will some (at least 3) of the mappings of elements of the interpretation of the function "-" (subtraction) be? (That is, for some tuples of elements from our domain, what are they mapped to?)
    Remember that we use angle brackets for ordered sets.

  3. Prove that t=t is a theorem of the Dedekind axioms. Note that I'm using "t" here to stand for any term, like we used "A" to stand for any sentence. (Hint: it can be done using just our axioms A10 and A6 and MP a few times. Remember the trick with axiom proofs: think backwards, asking, what conditional might I make use of that has t=t as a consequent?)
Example: I promised an example of an induction problem. Consider the claim that 1 + 3 + 5 + ... (2n - 1) = n2. Your base case is the first odd number, which is 1. 1 = 12. Our induction hypothesis is that the sum up to the nth odd number, which has value (2n - 1), is n2. The n + 1th case is the sum up to the odd number after the nth odd number. Since the nth odd number has value (2n - 1), the odd number after that has value (2n - 1 + 2). So, we need to show that (n+1)2 = n2 + (2n - 1 + 2) -- on the left side we have put n+1 into our equation, and on the right side we have our observation about the nature of the sum up to the next odd after our induction case, and our goal now is to show they are the same. Note then that, (n+1)(n+1) = n2 + (2n + 1). And then, n2 + 2n + 1 = n2 + 2n + 1. Q. E. D.

May 4: I'll be out of town, but I recommend you get together in class and discuss the homework problems.

May 8: due at the beginning of class, some problems in modal logic. Since it's our last day, let's go over them right after you hand in -- that's less optimal but since we didn't get to talk about time or ethics questions 4 and 5 are too hard. I'll post hints for 1, 2, and 3 tonight.
  1. Show S5 is equivalent to the combination of Brouwer and S4 (that is, derive A19 from L and A15, A16, A17, A18).
    (This is the hardest problem! I should have listed it last. Note please the following. If you can show that <><>A --> <>A is a theorem -- that is, if you can prove it using nothing but our axioms and MP -- then you can use our new rule necessitation and assert that [](<><>A --> <>A). Now, if you plug that into Axiom 15 as the first half of the conditional that makes up axiom 15, what do you get in a single step with modus ponens? Next please note that you can put <>A in for A in one of our axioms to find an instance; so, for example, <>A --> []<><>A is an instance of Axiom 17 and you can assert it at any time.)
  2. Prove our corollaries of S4 (that means, using just S4 show:)
    1. []A <--> [][]A
    2. <>A <--> <><>A
    (Here are two usefuls facts. (1) Given our definition of <> as ~[]~, and some basic logic, we can just allow you at any time move from ~[]A to <>~A or vice versa; and also from []~A to ~<>A and vice versa. This holds for several modal operators in a string. You can replace in a formula any time you want, say, [][]~A with []~<>A or even ~<><>A. (2) You can use the natural deduction rule contraposition; from P --> Q you can assert ~Q --> ~P and vice versa. Note then the following kinds of tricks you can do:
    1. []~A --> [][]~A ....Instance of A18
    2. ~<>A --> ~<><>A ....1, Equivalence, DN, definition
    3. <><>A --> <>A ....2, contraposition, DN
    Or similarly:
    1. ~A --> []<>~A Instance of A17
    2. ~A --> ~<>[]A Equivalence, definition
    3. <>[]A --> A contraposition, DN
    You can use tricks like these to show several of the corollaries.)
  3. Prove our corollaries of S5 (that means, using just S5 show:)
    1. []A <--> <>[]A
    2. <>A <--> []<>A
    (Remember I'm allowing all the natural deduction methods you want now. Show P <--> Q by using deduction theorem (conditional derivation) twice, and show P --> Q and then show Q-->P, and then conclude via conditional-to-biconditional P<-->Q.)
  4. Given Kripke's semantics (and his claims about the required accessibility relation), why would S5 make a bad logic of time (given our usual assumptions and experience of time)?
  5. If we use our modal operators for a deontic logic (a logic of ethics), and interpret [] as meaning "it should be the case that", and we interpret <> as meaning "it is permissible that", why is M probably not a good logical system to use as our deontic logic?

May 8: some solutions.
  1. Show S5 is equivalent to the combination of Brouwer and S4 (that is, derive A19 from L and A15, A16, A17, A18).
    1. []~A --> [][]~A ....Instance of A18
    2. ~<>A --> ~<><>A ....1, Equivalence, DN, definition
    3. <><>A --> <>A ....2, contraposition, DN
    4. [](<><>A --> <>A) ....3, necessitation
    5. [](<><>A --> <>A) --> ([]<><>A --> []<>A) ....Instance of A15
    6. ([]<><>A --> []<>A) ....MP 4, 5
    7. <>A --> []<><>A .... instance of A17
    8. <>A --> []<>A .... chain rule, 7, 6
  2. Prove our corollaries of S4 (that means, using just S4 show:)
    1. []A <--> [][]A
      1. []A --> [][]A .... axiom A18
      2. [][]A --> []A .... instance of A16
      3. [][]A <--> []A .... conditionals to biconditional, 1, 2
    2. <>A <--> <><>A
      1. []~A --> [][]~A ....Instance of A18
      2. ~<>A --> ~<><>A ....1, equivalence, definition
      3. <><>A --> <>A ....2, contraposition, DN
      4. [][]~A --> []~A ....Instance of A16
      5. ~<><>A --> ~<>A ....4, equivalence, definition
      6. <>A --> <><>A ....5, contraposition, DN
      7. <>A <--> <><>A .... conditionals to biconditional, 3, 6
  3. Prove our corollaries of S5 (that means, using just S5 show:)
    1. []A <--> <>[]A
      1. <>~A --> []<>~A ....Instance of A19
      2. ~[]A --> ~<>[]A ....1, equivalence, definition
      3. <>[]A --> []A .... contraposition, 2
      4. []<>~A <--> <>~A .... instance of A16
      5. ~<>[]A --> ~[]A ....4, equivalence, definition
      6. []A --> <>[]A ....5, contraposition
      7. []A <--> <>[]A .... conditionals to biconditional, 3, 6
    2. <>A <--> []<>A
      1. <>A --> []<>A .... A19
      2. []<>A --> <>A .... instance of A16
      3. <>A <--> []<>A .... conditionals to biconditional, 1, 2
  4. Given Kripke's semantics (and his claims about the required accessibility relation), why would S5 make a bad logic of time (given our usual assumptions and experience of time)?
    Kripke claims S5 must be symmetric. Then, if []A meant A is true now and in the future, the future would include the past! This is because the accessibility relation (which would stand in for time in such a model) would always point both ways.
  5. If we use our modal operators for a deontic logic (a logic of ethics), and interpret [] as meaning "it should be the case that", and we interpret <> as meaning "it is permissible that", why is M probably not a good logical system to use as our deontic logic?
    Surely because something should be true does not entail that it is true. We probably agree that all people should be treated equally by the law, for example; but we'd also probably agree that not all people are treated equally by the law. But M includes axiom A16, that says []A --> A.