MTH 355
Homework 1
Assigned 10 Sept, due 29 Sept

Note:

A lot of the grades on homework 1 were pretty bad. If you'd like to resubmit an improved version of particular problems after reading my comments on the first attempt, you have until Nov. 3 to do it. I'll grade the particular problems that you've rewritten, multiply by 2/3, and record the maximum of that grade and your original grade. Thus if you got 2/3 credit or better the first time around, there's no point resubmitting. If you got, say, half credit the first time around, there's no point resubmitting unless it's going to be nearly perfect the second time. However, if you got something like 10% on a problem, you can improve your grade substantially by re-doing that problem.

Translation

Translate each of the following English sentences into sentential logic. Tell what each sentence symbol stands for; make sure they're true/false statements that can be assessed independently. Point out any difficulties or flaws you see in your translations.

1. I'm not hungry, but thirsty.
2. If you have a cat or a dog, you must not have allergies.
3. If you love books, you've probably run out of bookcases; if not, I'm sorry for you.

Induction proofs about wffs

4. Problem 1.1.3 in the textbook: prove (informally, in English) that the number of sentence symbol occurrences in a wff is exactly 1 more than the number of connective occurrences.
5. Problem 1.1.5 in the textbook: prove (informally, in English) that for any wff that doesn't contain ¬, more than 1/4 of the symbol occurrences in it are sentence symbols.
   Also prove that we couldn't have done without the "that doesn't contain ¬" constraint, by constructing a wff (using ¬) in which fewer than 1/4 of the symbol occurrences are sentence symbols.

Truth tables, tautologies, etc.

6. Problem 1.2.3: is this a tautology? Does this tautologically imply that?
7. Problem 1.2.5: prove or refute each of two claims
8. Problem 1.2.7: the land of liars and truth-tellers
9. Problem 1.2.9: duality
10. Problem 1.2.12: translation and real-world application

Induction proofs about other things

11. Suppose you have a large piece of paper, effectively infinite in all directions. By drawing a straight line, you can cut it into two regions. By drawing another straight line intersecting the first, you can cut it into four regions. What is the largest number of regions you can get with n straight lines? Prove it (informally, in English).
12. Raymond Smullyan, a famous logician, gives the following advice:
    • Always speak the truth, and
    • Every day, say "I will repeat this sentence tomorrow."
    Prove (informally, in English) that if you follow this advice, you will live forever. Then explain why it won't work.
13. Prove (informally, in English) that if n is a natural number, then
    1 + 3 + 5 + ... + (2n+1) = (n+1)²
14. A fnord and its bogosity are defined as follows:
    • The letter a is a fnord of bogosity 0.
    • The letter b is a fnord of bogosity 1.
    • If α and β are fnords of bogosities n and n+1 (in either order), then F(α,β) is a fnord of bogosity n+2.
    • All fnords are constructed by finitely many applications of the above three rules.
15. Prove that all fnords have non-negative-integer bogosity.
16. Prove that every fnord of non-zero bogosity has at least as many F's as a's.
17. Prove that every fnord has a unique construction tree (see p. 17 of the textbook, and the "Unique Readability Theorem" on p. 40), and therefore a unique bogosity. That is, no sequence of symbols can be interpreted both as a fnord of bogosity, say, 7, and also as a fnord of bogosity 8.
18. Prove that any two fnords of the same bogosity (say, n) have the same number of lower-case letters, and that this number is at most 2ⁿ and at least 1.5^n-1.

Formal proofs in the system

Write formal proofs of each of the following arguments, using the proof rules given in class on Sept. 10. If you can't figure one of them out, then for partial credit, give a truth-table proof.

19. From premise (P ∧ Q) prove (Q ∧ P)
20. From premise (P ∨ Q) prove (Q ∨ P)
21. From premise P prove (¬(¬ P)). (Going the opposite direction is a one-liner, using ¬ elimination.)
22. From premise (P → Q) prove (P → (R → Q))
23. From premise (P → Q) prove ((¬ P) ∨ Q).
    Then do the reverse: from premise ((¬ P) ∨ Q), prove (P → Q).
    Thus these two statements are provably equivalent.
24. From premise (¬(P ∧ Q)) prove ((¬P) ∨ (¬Q)).
    Then do the reverse. Thus these two statements are provably equivalent.
25. From premise (P ∧ (Q ∨ R)) prove ((P &and Q) ∨ (P ∧ R)).
    Then do the reverse. Thus these statements are provably equivalent.

---

Last modified: 
Stephen Bloch / bloch@adelphi.edu