### PHL310 Valid Reasoning II, past assignments

30 January
1. Translate the following into symbolic propositional logic: If both Nemo and Jaws are fish, then neither Patrick nor Mr. Krab are.
2. Translate the following into quantified logic: All men are mortal.
3. Prove the following, using a syntactic proof. Premises: (P → Q), (R ↔ Q), (P v R). Conclusion: Q.
4. Prove the following, using a syntactic proof. Conclusion: ((P → Q) → (¬Q → ¬P)
5. Prove the following, using a syntactic proof. Premises: ∀x(Fx → Gx), ∃xFx. Conclusion: ∃xGx
Please write it up and hand it in at the beginning of class. Reviewing these will help me to see where each of us is at, what systems you learned, and so on.

We are going to be reviewing propositional logic this day. For review, you might find it helpful to read the first chapters of A Concise Introduction to Logic. Chapter 10 provides a concise 3-page summary of an entire natural deduction system propositional logic
1 February
Please note that unfortunately I cannot have my office hours this day. Email me if that causes any difficulties for you.
8 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. Don't use theorems just yet; we'll start using those later.
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)).
12. Prove that we only need ¬ and → as connectives. To do this, identify a complex sentence equivalent to "and", "or", and "if and only if", where the sentence is composed of atomic sentences and ¬ and →.
There will be a Philosophy Club meeting, Feb 8 at 4:00PM, in MCC 210. They will be watching an episode of Star Trek: The Next Generation. The episode is entitled “The Measure of a Man”. The episode revolves around the rights and possibility of consciousness in synthetic beings. Stop by for a thought provoking discussion and some free food.
15 February
Read: "On Denoting" by Bertrand Russell. Bring it to class so that we can review it together.

Here are our pop-quiz questions. Translate, into something like our contemporary natural deduction system quantified logic, the phrases:
1. "C(all men)" means "'If x is human, then C(x) is true' is always true."
2. "C(no men)" means "'If x is human, then C(x) is false' is always true."
3. "C(some men)" means "It is false that 'C(x) and x is human' is always false."
18 February
Complete the following.

A. Proofs. Prove the following.
1. Premise: ¬Fa, ∀x(Fx v Gx), ∀y(Gy → Hy). Conclusion: Ha.
2. Premise: ∃x(Jx ^ Kx), ∀x(Jx → Lx), ∀x(Kx → Mx). Conclusion: ∃x(Lx ^ Mx).
3. Premises: ∀x(Fx → Gx), ∀x(Gx → Hx) Conclusion: ∀x(Fx → Hx)
4. Premises: ∀x(Fx → Gx), ∀x(Hx → Ix) Conclusion: ∀x((Fx ^ Hx) → (Gx ^ Ix))
5. (∀x∀yFxy → ∃y∃xFxy)
6. (∀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.
B. Translations. Translate the following. For all of these, you may assume that your domain of discourse is people/humans.
1. Someone is taller than someone.
2. Everyone is taller than everyone.
3. Everyone is taller than someone.
4. Someone is taller than everyone.
5. No one is taller than everyone.
6. One human is pope.
7. Two humans are pope.
27 February
Some optional/extra-practice problems. Prove the following. You can use DeMorgans, and also our quantifier negation rules (that tell us ¬∀xφx is equivalent to ∃x¬φx; and that ¬∃xφx is equivalent to ∀x¬φx).
1. (∃x(Fx ^ ¬ Gx) → ¬∀x(Fx → Gx))
2. (¬∃xFx → ∀x(Fx → Gx))
3. (∀x(Fx → (Gx v Hx)) → (∀x(Fx --> Gx) v ∃x(Fx ^ Hx)))
If you feel mighty, you can prove the biconditional form of the theorem in problem 3: (∀x(Fx → (Gx v Hx)) ↔ (∀x(Fx --> Gx) v ∃x(Fx ^ Hx))). You can use also the theorem that (¬(φ → ψ) ↔ (φ ^ ¬ψ)).

Here's a brain teaser. Can you express:
1. There is no Pope or exactly two Popes.
2. There are not two Popes (but there may be more than or fewer than two).
Just a reminder that my textbook covers quickly the quantified logic in chapters 11-16. Chapter 17 also has some of the material that we will be covering next.
6 March
My apologies: I have a meeting in the afternoon so I can only have my office hours from 1-3pm (instead of the usual 130-430 pm).

Prove:
1. 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))
2. 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))
3. 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))
The Career and Internship Fair is today. Register and stop in.
13 March
Some problems for our axiomatic approach.
1. Using our three axioms and MP alone, prove: { (A → (B → C)), (A → B) } |-L (A → C). Do this one without the deduction theorem.
2. 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 → φ).)
3. See if using our three axioms alone, you can prove: {} |-L (B → (¬B → C)). This one is hard to do with straight axioms, but using the deduction theorem twice it is not hard; so, if you are stumped, use DT.
4. Extra-credit: use mathematical induction to prove Show that the sum of the first n odd numbers is n2. (That is, show: 1 + 3 + 5 + ... (2n - 1) = n2.)
15 March
Here 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):
1. (A → ¬¬A)
2. (A → (¬B → ¬(A → B)))
3. (¬ A → (A → B))
4. ((A → B) → ((¬A → B) → B))
Chain rule metatheorem is: {(A → B), (B → C) } |- (A → C)
Interpolation metatheorem is: {(A → (B → C)), B } |- (A → C)

I'll give you all the proofs soon, but if you feel like practicing the logic it can be helpful to convince yourself that these are theorems.