Mathematical LOGIC
Spring 2012
Homework Assignments
January 17
Covered slides: 0.a - 2.5
Electronic submissions: Exercises 1.1, 1.2, 1.3, 2.15, 2.24, 2.25.
Expected quiz questions: Exercise 2.4.
January 24
Covered slides: 3.0 - 6.6
Electronic submissions: Exercises 3.23, 3.22, 4.1, 4.17, 6.5, 6.9, 6.33.
Expected quiz questions:
Definitions of "logically possible", "logically necessary", "tautology", "logically equivalent", "tautologically equivalent", "logical consequence", "tautological consequence", "negation normal form", "disjunctive normal form", "conjunctive normal form".
You should be able to construct a truth table for any given sentence and tell if it is a tautology.
Using truth tables, you should be able to tell, for any given sentence, if it is a tautology; or, for any two sentences, tell whether one is a tautological consequence of the other, or whether the two sentences are tautologically equivalent.
You should remember the Distributivity and DeMorgan laws.
Give an informal proof of the following fact: There are irrational numbers b,c such that b^{c} is rational (pages 132-133).
Give an informal proof of the fact that Ö2 is irrational (page 138).
January 31
Covered slides: 7.1 - 9.6
Electronic submissions: Exercises 7.4, 7.6, 7.25, 8.19, 8.30, 9.13, 9.15.
Expected quiz questions:
Applying the method explained in Section 7.4, you should be able to express any truth function using only negation, disjunction and conjunction. Specifically, a truth function (a new connective, that is) will be given to you through a truth table, and you should write an equivalent formula only containing negation, disjunction and conjunction.
Remember that F_{T} is the version of F (or Fitch) that only includes the rules for introducing and eliminating Boolean connectives (including contradiction), plus reiteration. Section 8.3 of our textbook rightfully claims that this system is sound and complete with respect to tautological consequence.
What does the soundness of F_{T} exactly mean here? Provide a clear, definition-style answer. It should be short and to the point.
What does the completeness of F_{T} exactly mean here?
If we arbitrarily delete (i.e. disallow, forbid) some --- perhaps critically important --- rules from F_{T}, which of the above two properties could be lost? (underline)
soundness completeness both neither
If we arbitrarily add some --- perhaps wrong --- new rules to F_{T}, which of the above two properties could be lost?
soundness completeness both neither
Assume we add to F_{T} the rule "From A®B and ØB, infer ØA" (this rule, called Modus Tollens, is dealt with in your homework Exercise 8.19).Which of the above two properties could be lost?
soundness completeness both neither
February 7
Covered slides: 10.0 - 11.5
Electronic submissions: Exercises 10.8, 10.22, 10.27, 11.1, 11.4, 11.13, 11.17
Expected quiz questions:
February 14
Covered slides: 12.1 - 13.4
Electronic submissions: Exercises 13.3, 13.4, 13.10, 13.11, 13.46, 13.48, 13.50
Expected quiz questions:
February 21
Covered slides: 15.1.a - 15.5.b
Electronic submissions: Exercises 15.2, 15.13, 15.14, 15.15, 15.16, 15.18, 15.21
Expected quiz questions:
February 28
Covered slides: 15.6.a - 15.10.c
Electronic submissions: Exercises 15.34, 15.35, 15.36, 15.37, 15.38, 15.39, 15.66
Expected quiz questions:
March 13
Covered slides: 16.0 - 16.7
Electronic submissions: Exercises 16.29, 16.30, 16.33, 16.39, 16.40, 16.42
Expected quiz questions:
March 20
Covered slides: 17.1.a - 17.2.c
Electronic submissions: Exercises 16.31, 16.32, 16.34, 16.35, 16.36
Expected quiz questions:
March 27
Covered slides: 17.2.d - 17.2.g
Electronic submissions: Exercises 16.37, 16.38, 16.41, 16.43, 17.7.
Expected quiz questions:
April 3
Covered slides: 17.3.a - 17.4.i
Electronic submissions: Exercises 16.44, 16.45, 16.46, 16.47, 17.25, 17.26.
Expected quiz questions:
April 10
Covered slides: 18.1 - 18.2.c
Electronic submissions: Exercise 18.2.
Expected quiz questions:
All definitions from Slides 18.1 - 18.2.c.
Exercises 18.1, 18.3, 18.4, 18.7, 18.8.
April 17
Covered slides: 18.2.d - 18.3.c
Electronic submissions: None
Expected quiz questions:
The proofs from slides 18.3.b and 18.3.c
Exercises 18.14, 18.15, 18.16
April 24
Note: Examination on May1. Usual time and place. Comprehensive. No books/notes/computers.
Covered slides: 18.5.a - 18.7.d
Electronic submissions: None
Expected quiz questions:
Exercises 18.20, 18.22, 18.23, 18.24, 18.25, 18.26, 18.30.