## PHL310 Valid Reasoning II, past assignments

30 AugustPlease do the following!

- 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
8 SeptemberTwo sets of questions!

A.Some practice problems. If you feel very comfortable with your logic from PHL111 or the equivalent, you can skip these questions. Or do any that you would like some help reviewing. I'll correct them and get them back to you.

- Premises: (P → Q), (S ^ ¬T), (T v P), (~R → ¬S).

Conclusion: (Q ^ R)- Premises: (¬P v Q), (Q → S), ¬S.

Conclusion: ¬P- Premises: (¬R v T), (T → Q), ((Q ^ S) ↔ V), (V ↔ P).

Conclusion: ((R ^ S) → P).- Conclusion: ((P v Q) → (¬P → Q))
- Premises: (P → R), (Q → S), (¬R ^ ¬S).

Conclusion: ¬(P v Q).- Conclusion: ¬(P ^ ¬P).
- Conclusion: (¬(P ^ Q) ↔ (¬P v ¬Q)).
- Premise: ¬Fa, ∀x(Fx v Gx), ∀y(Gy → Hy). Conclusion: Ha.
- Premise: ∃x(Jx ^ Kx), ∀x(Jx → Lx), ∀x(Kx → Mx). Conclusion: ∃x(Lx ^ Mx).
- Premises: ∀x(Fx → Gx), ∀x(Gx → Hx) Conclusion: ∀x(Fx → Hx)
- Premises: ∀x(Fx → Gx), ∀x(Hx → Ix) Conclusion: ∀x((Fx ^ Hx) → (Gx ^ Ix))
B.Please do all of these questions. For 1-5, just provide a key and a translation. For 6-9, do the proof.

- Some number is bigger than some number.
- Every number is bigger than every number.
- Every number is bigger than some number.
- Some number is bigger than every number.
- There is no biggest number.
- (∀x∀yFxy → ∃y∃xFxy)
- (∀x∃y(Fx → ∃z(Gz → Hy)) → ((∃xFx ^ ∀xGx) → ∃xHx))

Hint: this is a big conditional! Do conditional derivation. The consequent (the then side) is a big conditional; do another conditional derivation. You'll have a lot of assumptions left with which to prove ∃xHx. Remember to do EIs before your UIs. I use p, q, r... as names of indefinite objects.- If A ⊆ B and B ⊆ A, then A = B.

Hint. Take as two premises that A ⊆ B and B ⊆ A. That means by definition you can assert at any time, ∀x(x ∈ A → x ∈ B) and at any time you can assert ∀x(x ∈ B → x ∈ A). (That's what A ⊆ B and B ⊆ A mean, respectively.) Then prove that ∀x(x ∈ A ↔ x ∈ B).- A ∪ {} = A.

Some hints. You'll be proving ∀x((x ∈ A v x ∈ {}) ↔ x ∈ A). So do a universal derivation inside of which you show ((x' ∈ A v x' ∈ {}) ↔ x' ∈ A); to do that show first ((x' ∈ A v x' ∈ {}) → x' ∈ A) and then show (x' ∈ A → (x' ∈ A v x' ∈ {})) and use bicondition (or an equivalent rule). For the first conditional, use our axiom or principle that ∀x ¬ x ∈ {}, from which you get ¬ x' ∈ {}.

15 SeptemberSome problems for our axiomatic approach.

- Are negation and the conditional all we really need? Prove it! Show that you can create a formula using just negation(s) and conditional(s) that have the same truth table as: conjunction, disjunction, and the biconditional.
- Using our three axioms and MP alone, prove: { (A → (B → C)), (A → B) } |-
_{L}(A → C). Do this one without the deduction theorem.- Using our three axioms alone, prove: {} |-
_{L}((A → B) → ((C → A) → (C → B))). Try to do this using deduction theorem at most once.

For many of these proofs, note this useful trick: if you have as a line φ, note that axiom 1 lets you say (φ → (ψ → φ)) and then with MP you get (ψ → φ). In other words, with axiom 1, if you have some sentence φ you can always in two steps get (anything → φ).- Using our three axioms alone, prove: {} |-
_{L}(B → (¬B → C)). This one is hard to do with straight axioms, but using the deduction theorem twice it is not so hard.25 SeptemberHere are some extra-credit problems, not required. These are all important because we will use each to prove completeness. Prove using only axioms and deduction theorem (and maybe if you feel stuck the chain rule and interpolation metatheorems):Chain rule metatheorem is: {(A → B), (B → C) } |- (A → C)

- (A → ¬¬A)
- (A → (¬B → ¬(A → B)))
- (¬ A → (A → B))
- ((A → B) → ((¬A → B) → B))

Interpolation metatheorem is: {(A → (B → C)), B } |- (A → C)

29 SeptemberHere are a few pages on completeness that I mentioned.2 OctoberDo problems 5a, 5b, 5d of chapter 17 of A Concise Introduction to Logic.6 OctoberNote revised due date.

Do problem 6 of chapter 17 of A Concise Introduction to Logic.

Note: I have a conflict in the afternoon, and cannot stay for my whole office hours. I will need to leave around 3:30.

I was asked for hints. You're proving three things. First, that you can derive m5 using only m1, m2, m3, and m4. Second, that you can derive m3 using only m1, m2, and m5. Third, that you can derive m4 using only m1, m2, and m5.

The second one is perhaps easiest. Prove (φ → <> φ); and consider chain rule.

The first is perhaps next easiest. Consider that with m4 you can prove (<><>φ → <>φ). Now with necessitation you get [](<><>φ → <>φ). With m2 what can you derive from that? Finally, consider the following instance of m3: (<>φ → []<><> φ). Invoke the power of chain rule!

What about the third one? I think that's toughest. Note that in S5 we can prove (φ → []<>φ). An instance of this theorem is ([]φ → []<>[]φ). Keep in mind the handy equivalence (¬<>¬φ ↔ []φ). With the following instance of m5, (<>¬φ → []<>¬φ), and a lot of contraposition and messing with DN and using that handy equivalence, you can get (<>[]φ → []φ). With necessitation and m2, you can get ([]<>[]φ → [][]φ). Chain rule!October 9Some practice problems. No need to hand these in, but bring your attempts and we'll review them together.

- In system M, prove theorem (<>[]P → <>P)
- In system Brouwer, prove theorem (<>[]P → P)
October 11Midterm. Simple proofs with the three axioms of standard propositional logic. The Deduction Theorem. Completeness of the Propositional Logic using Kalmar's Lemma. Meaning of completeness and consistency. Simple proofs in modal logic. Basics of modal logic semantics.

Here is our handout on modal logics.13 OctoberData on the first test: mean score 27/50; stdev 15; range 5-50. Please note that logic is all about practice! The average for people who did all homeworks was 30/50. The average for those who did just 3 or fewer of the homeworks was 15.

I also emailed to you an approximate midterm grade. Remember to keep up on the homeworks. They help you to be a good citizen!

As threatened, I put the slides of our review (suitably fixed) here.

Section 17.6 of my book has the axioms L4 and L5.18 OctoberHere is a homework for us due at the beginning of class. It includes some concepts, some review, and then our new stuff. I'll try to do this from now on, to ensure we all have practice on past material.

- Suppose we have an axiom system K, and we discover that it is inconsistent (we prove some theorem φ and we also prove a theorem ¬φ). Of course we want to fix the system. What should our strategy be? What kind of action will a fix require? (Remember, this is an axiom system, like our PL.)
- Using system PL (that is, just axioms L1-L3 and modus ponens, and without DT) show {¬Q, (¬¬P → Q), (¬R → P) } |-- R
- Using any techniques of a natural deduction system, prove the following theorem in S5: [](¬ Q → ¬ P) |--
_{S5}(<>P → []<>Q).- Using any natural deduction system tools, prove that: ∀x(¬x ∈ A → ¬x ∈ A ∩ B)
- Prove using just L1-L5, MP, and DT, and GEN: ∀x
_{1}(B(x_{1}) → C(x_{1})) → (∀x_{1}B(x_{1}) → ∀x_{1}C(x_{1}))- Prove using just L1-L5, MP, and DT, and GEN: ∀x
_{1}(¬C(x_{1}) → ¬B(x_{1})) → ∀x_{1}(B(x_{1}) → C(x_{1}))By the way: here is a version of DT more elegant than I stated in class (this from Mendelson):Suppose S is a set of premises, and φ and ψ are particular sentences. If a deduction showing S ∪ {φ} |-- ψ involves no application of generalization (GEN) of which the quantified variable is free in φ, then S |-- (φ → ψ)I put into BlackBoard a few relevant pages from an excellent logic text. You can use them to review and reassess the stuff that was on the test with respect to PL.19 OctoberGuest speaker J. D. Trout will speak on "Explanation, Truthiness, and the False Climb to Knowledge." This will be a fascinating talk on epistemology and philosophy of science. Extra-credit sign up sheet in the back. The talk is at 4:00 pm, will last less than an hour, and is in the Marano Campus Center auditorium.

Here is a homework for us due at the beginning of class.

- We can prove that our first order logic, with just the five axioms L1-L5, is complete and consistent. We cannot prove that Zermelo-Frankel set theory is complete, and we cannot prove that it is consistent. What must be the source of this difference between the basic FOL and ZFC?
- Using any of our tools, prove: (A ⊆ B ↔ A ∩ B = A)

Hint: it is sufficient to prove:

(∀x(x ∈ A → x ∈ B) ↔ ∀x((x ∈ A ^ x ∈ B) ↔ x ∈ A))- Using any of our tools, prove: (A ⊆ B ↔ A ∪ B = B)

Hint: it is sufficient to prove:

(∀x(x ∈ A → x ∈ B) ↔ ∀x((x ∈ A v x ∈ B) ↔ x ∈ B))- We can define "-" in the following way: ∀x(x ∈ A - B ↔ (x ∈ A ^ ¬ x ∈ B)).

Using any of our tools, prove: (A ⊆ B ↔ A - B = {})

Hint: it is sufficient to prove:

(∀x(x ∈ A → x ∈ B) ↔ ¬∃x(x ∈ A ^ ¬ x ∈ B))- Create a counterexample: give an example of sets A and B, or use a Venn diagram to show some A and B, for which the following is false: (A - B = B - A). Explain how your example sets are a counterexample.

We'll review the homework, and set theory.

We'll be working on arithmetic for the next several weeks. Using the Peano axioms, we can construct arithmetic out of our FOL and a handful of axioms. Amazing.

A Smullyan:

Will you either truthfully answer no to this question, or falsely answer yes, or pay me two million dollars?

Here is a homework for us due at the beginning of class.

- What is a number? What is 3, for example?
- Using our system and SI and communitivity, prove that (2 * (1 + 1)) = 4
- Using any of our tools, prove that: ((A-B = {} ^ B-A = {}) → A=B)

To prove this, it will be sufficient to prove:

((∀x((x∈A ^ ¬x∈B) ↔ x ∈ {}) ^ ∀x((x∈B ^ ¬x∈A) ↔ x ∈ {})) → ∀x(x∈A ↔ x∈B))

Let's have a test, just to help us practice set theory and peano arithmetic. It'll have a conceptual question; a proof in FOL (using axioms 1-5); a proof in set theory; and a proof in Peano Arithmetic. I'll make it very short! Last one was too long.

Test. The range was 3-40; the mean 27. I thought the first question was interesting but most people found it incomprehensible, so I'm going to count it as extra-credit (so the test is x/30 not x/40 for score x). We should review proofs more, I guess. But we can go over the test in class.

If we have time, we can discuss quantified modal logic. What the heck is the deal with those quantifiers and stuff? How do we distinguish []∀xFx and ∀x[]Fx?

Some practice. (I corrected a typo in this after our class, so if you tried this before please note the corrected version below.) Using the Barcan formula and any natural natural deduction system rules (and you can assume S5 and thus the S5 axioms, if that helps), prove:The Barcan formula is: (∀x[]φx → []∀xφx).

- (<>∃xFx → ∃x<>Fx)

Remember that (¬∀x¬φx ↔ ∃xφx) and (¬∃x¬φx ↔ ∀xφx).

We will continue our discussion of game theory, and introduce the idea of the Nash equilibrium.

Our slides from class are here.

Here's a problem for us, given that we have introduced a very simplified idea of the Nash equilibrium (call it a "simple Nash equilibrium"). Two questions. We will consider two games. From Rousseau, the stag hunt: two players must decide bewteen hunting stag (which requires 2 hunters) or hunting hare (which you can do alone). From von Neumann, matching pennies, where two players show pennies, and one gets them both if they match, the other gets them both if they don't match.

For each of the two games that I drew here, which are called The Stag Hunt and Matching Pennies: Does the game have any Nash equilibria? If so, what are the Nash equilibria (which profiles)?

Here's an extra credit question: if you were in a repeated Prisoner's Dilemma with the same player, where you did not know when iterations of the game would stop, should your strategy change? This is a question that has perplexed many thinkers....

Extra optional review anything everything session in MCC 220 (the IPAC conference room) from 2:30 - 4:00 PM.

By request, here are my slides on some of our modal logic issues.