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.
- Premises: (P --> Q), (S ^ ~T), (T v P), (~R --> ~S).
Conclusion: (Q ^ R)
- Premises: (~R v T), (T --> Q), ((Q ^ S) <--> V), (V <--> P).
Conclusion: ((R ^ S) --> P)
- Premises: (~P v Q), (Q --> S), ~S.
Conclusion: ~P
- Conclusion: (~(P ^ Q) <--> (~P v ~Q)). This theorem
is known as one of De Morgans Theorems.
- 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.
- Premises: (P --> (T ^ ~Q)), ~T v R.
Conclusion: ~(P ^ (R <--> Q)).
- Conclusion: (Q --> (P --> Q))
- Conclusion: ((P --> (Q --> R)) --> ((P --> Q) --> (P --> R)))
- Conclusion: ((~P --> ~Q) --> ((~P --> Q) --> P))
- 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):
- Premise: ~Fa, /\x(Fx v Gx), /\y(Gy --> Hy). Conclusion: Ha.
- Premise: \/x(Jx ^ Kx), /\x(Jx <--> Lx), /\x(Kx --> (Mx ^ Nx)).
Conclusion: \/x(Lx ^ Mx).
- Premises: /\x(Fx <--> Gx), /\x(Gx <--> Hx)
Show: /\x(Fx <--> Hx)
- Premises: /\xFx, /\xGx. Conclusion: /\x(Fx ^ Gx)
- 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.
- Premises: (~~P --> S), P. Show: ~~S.
- Premises: ~(T --> R), ((P --> V) --> (T --> R)). Show: ~(P --> V).
- Premises: (~P --> V), ~V, (P --> Q). Show: Q.
- Premises: (~(R --> S) --> V), ((R --> S) --> Q), ~Q. Show: V.
- Premises: (P --> R), (R --> Q). Show: (P --> Q).
- Premises: (S --> R), (P --> S). Show: (~R --> ~P).
- Premises: (~P --> ~S), S. Show: P.
- Premises: ~(P --> Q), ((R --> T) --> (P --> Q)). Show: ~(R --> T).
- Premises: (P --> Q), (Q --> R), (R --> S), (S --> T), ~~P. Show: T.
- Premises: (~(R --> S) --> V), ((R --> S) --> Q), ~Q. Show: V.
- Premises: (P --> R), (T --> P), (S --> T), ~R. Show: ~S.
- Premises: (R --> Q), (Q --> S), (P --> R). Show: (P --> S).
- Premises: (P --> S), (Q --> P), (~R --> Q). Show: (~S --> R).
- Premises: ((T v R) <--> S), (S ^ ~Q), (T <--> Q). Show: R.
- Premises: (P <--> R), (R ^ ~S), (S v T). Show: ((Q v P) ^ T).
- Show: (~Q --> ~(P ^ Q))
- Show: (Q --> R) --> ((P --> Q) --> (P --> R))
- Show: ~(P --> Q) <--> (P ^ ~Q)
- Show: (P ^ Q) <--> ~(~P v ~Q)
- Premises: (P ^ R), (P --> S), (Q --> ~(S ^ R)). Show: ~Q
- Show: ((P ^ ~Q) --> ~(P --> Q))
- Show: (~(R --> T) --> ~T)
- Premises: (P <--> R), (R <--> S), (S <--> Q). Show: (P <--> Q).
- Make the truth table for the following sentence: (~(P v Q) <--> (~P ^ ~Q)).
- Make the truth table for the following sentence: (~(P ^ Q) <--> (~P v ~Q)).
- Make a truth table for the following sentence: ((~P --> Q) <--> ~R).
- Make a truth table for the following sentence: ((R ^ S) <--> (P v S)).
- Show the following argument is not valid using a truth table. Premises: (P v Q), P. Conclusion: ~Q.
- Show the following argument is not valid using a truth table. Premises: (~R --> S). Conclusion: ~R.
- Show the following argument is not valid using a truth table.
Premises: ~(T --> V). Conclusion: ~T.
- Show the following argument is not valid using a truth table.
Premises: ~(R^S). Conclusion: ~R.
- Show the following argument is not valid using a truth table.
Show that this is not a tautlogy: ((P ^ Q) <--> (P v Q))
- Premises: /\x(Fx --> Gx), FC. Conclusion: GC.
- Premises: /\x(Fx <--> Gx), /\x(Gx <--> Hx), FA. Conclusion: HA.
- Premises: /\x(Gx v Hx), ~HB.
Conclusion: \/xGx.
- Premises: /\x(Fx --> (Gx ^ P)), /\xFx.
Conclusion: P.
- Premises: /\x(Q v (Gx v Hx)), /\x~Gx, ~Q.
Conclusion: HC.
- Show: /\z(Fz <--> Gz).
Premises: /\x(Fx <--> Hx), /\y(Hy <--> Gy).
- Show: VxFx.
Premises: Vx(Gx ^ Hx), /\x(Gx --> Jx), /\x((Hx ^ Jx) --> Fx).
- Show: Vx(Gx ^ ~Hx).
Premises: \/x~Hx, /\x(Gx v Hx).
- Show: /\x(Fx --> Gx) --> (/\xFx --> /\xGx)
- 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:
- (A --> (B --> C)), (A --> B) |-L (A --> C)
- |-L ((A --> B) --> ((C --> A) --> (C --> B)))
- |-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.
- 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.)
- 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.
- 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.
- 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.)
- Prove our corollaries of S4 (that means, using just S4
show:)
- []A <--> [][]A
- <>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:
- []~A --> [][]~A ....Instance of A18
- ~<>A --> ~<><>A ....1, Equivalence, DN, definition
- <><>A --> <>A ....2, contraposition, DN
Or similarly:
- ~A --> []<>~A Instance of A17
- ~A --> ~<>[]A Equivalence, definition
- <>[]A --> A contraposition, DN
You can use tricks like these to show several of the
corollaries.)
-
Prove our corollaries of S5 (that means, using just S5 show:)
- []A <--> <>[]A
- <>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.)
- 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)?
- 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.
- Show S5 is equivalent to the combination of Brouwer
and S4 (that is, derive A19 from L and A15, A16, A17,
A18).
- []~A --> [][]~A ....Instance of A18
- ~<>A --> ~<><>A ....1, Equivalence, DN, definition
- <><>A --> <>A ....2, contraposition, DN
- [](<><>A --> <>A) ....3, necessitation
- [](<><>A --> <>A) --> ([]<><>A --> []<>A) ....Instance of A15
- ([]<><>A --> []<>A) ....MP 4, 5
- <>A --> []<><>A .... instance of A17
- <>A --> []<>A .... chain rule, 7, 6
- Prove our corollaries of S4 (that means, using just S4
show:)
- []A <--> [][]A
- []A --> [][]A .... axiom A18
- [][]A --> []A .... instance of A16
- [][]A <--> []A .... conditionals to biconditional, 1, 2
- <>A <--> <><>A
- []~A --> [][]~A ....Instance of A18
- ~<>A --> ~<><>A ....1, equivalence, definition
- <><>A --> <>A ....2, contraposition, DN
- [][]~A --> []~A ....Instance of A16
- ~<><>A --> ~<>A ....4, equivalence, definition
- <>A --> <><>A ....5, contraposition, DN
- <>A <--> <><>A .... conditionals to biconditional, 3, 6
- Prove our corollaries of S5 (that means, using just S5 show:)
- []A <--> <>[]A
- <>~A --> []<>~A ....Instance of A19
- ~[]A --> ~<>[]A ....1, equivalence, definition
- <>[]A --> []A .... contraposition, 2
- []<>~A <--> <>~A .... instance of A16
- ~<>[]A --> ~[]A ....4, equivalence, definition
- []A --> <>[]A ....5, contraposition
- []A <--> <>[]A .... conditionals to biconditional, 3, 6
- <>A <--> []<>A
- <>A --> []<>A .... A19
- []<>A --> <>A .... instance of A16
- <>A <--> []<>A .... conditionals to biconditional, 1, 2
- 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.
- 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.