P310 Valid Reasoning II
Professor: Craig DeLancey
Office: CC217
Email: craig.delancey@oswego.edu


Current Assignments
6 February
Here are some problems to try. Each is in propositional logic. Translate 1-4. Try to do 5 and 6 with a direct proof; 7 and 8 with a conditional proof; and 9 and 10 with an indirect proof.
  1. Tom will go to London or Paris but not both.
  2. Tom will go to London if and only if he goes to New York or Newark.
  3. Tom will go to London only if he doesn't get arrested.
  4. Tom will go to Paris provided that he doesn't get arrested.
  5. Premises: (P --> Q), (S ^ ~T), (T v P), (~R --> ~S).
    Conclusion: (Q ^ R)
  6. Premises: (~P v Q), (Q --> S), ~S.
    Conclusion: ~P
  7. Premises: (~R v T), (T --> Q), ((Q ^ S) <--> V), (V <--> P).
    Conclusion: ((R ^ S) --> P).
  8. Conclusion: ((P v Q) --> (~P --> Q))
  9. Premises: (P --> R), (Q --> S), (~R ^ ~S).
    Conclusion: ~(P v Q).
  10. Conclusion: ~(P ^ ~P).
  11. Extra credit: Conclusion: (~(P ^ Q) <--> (~P v ~Q)).


Tentative assignments
11 February
Multiple quantifiers.



Some of the 2009 class assignments
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 11: exam in class from 10:30 a.m. - 12:30 p.m. Questions can include any of the question on the first quiz, and also questions concerning:
  • What are the axioms of K?
  • What is a model for a quantified logic? What in the model is used to represent the semantics of: a constant (or name); a predicate; a function?
  • Suppose a domain, give examples of the ordered sets in a hypothetical model for some example functions or predicates.
  • What is a conservative extension? If we add something to our language by definition alone, is our language able to do more?
  • What are some interpretations of [] and <>? What do you think are reasonable axioms to propose for different interpretations, and why?
  • What is a Kripke model for a modal logic? Can you explain it to your roommate?
  • Difference between a Leibniz model (where [] means true in all possible worlds) and a Kripke model (where [] means true in all accessible worlds).
  • Proving some very simple things in a given modal system, like S4.
I would like you to know A1 through A5, but will give you A15 through A19. Remember a conservative extension is one that doesn't add anything new; for example, it was a conservative extension to L to add to it "v" ("or") as a connective, because we defined (PvQ) as (~P-->Q) and we already had "~" and "-->" in our language.