2007/2008; 1st Semester
Institute for Logic, Language & Computation
Universiteit van Amsterdam
|
Basic Logic 2007/2008; 1st Semester Institute for Logic, Language & Computation Universiteit van Amsterdam |
N.B.: Next Homework, DIFFERENT DEADLINE, DIFFERENT PERSON. The deadline is 10 am on December 17th (Monday). Since Daisuke is going home from Thursday, Benedikt will grade the homework. So please hand in your homework to Benedikt in person, in Benedikt's mail box or by sending an e-mail to him.
N.B.: We modified the homework this week by adding some instructions. For the details, see below in red.
Instructor:
Prof Dr Dick de Jongh,
Dr Benedikt Löwe
ECTS: 4
Time & Place: Tuesday 17-18 P.016; Friday sometimes 13-15,
sometimes 14-16, in varying rooms (see below)
Course language: English
Teaching Assistant: Daisuke Ikegami (e-mail: ikegami@science.uva.nl)
Organization. The course will be organized in Lectures and Exercise sessions. The lectures will be on Fridays, the exercise will be sessions on Tuesdays. There are weekly exercises to be handed in on Friday before the lecture, either in person, or to Daisuke Ikegami (e-mail: ikegami@science.uva.nl), his office is at Room B.85 in J/K building.
The course follows the book Dirk van Dalen, Logic and Structure, 4th Edition, Springer 2004 (not 3rd) which can be bought at the book store Scheltema. There is a copy of the book on reserve in the library in the Euclides building.
The grade will be determined by weekly homework. At the end of the course, we shall offer a take-home exam for those of you who wish to improve their grade (not mandatory).
N.B.: The Friday lectures will change time and place during the semester. Please make sure that you write down where and when the Friday lectures are.
N.B.: The Tuesday problem sessions will be at P.016 unless any special notice.
N.B.: The deadline of homework is at 5pm on Fridays. You can either hand in at Friday lectures, put it in Daisuke's mailbox at Euclides Building (the name tag says "I.Ikegami" not "D.Ikegami"), or send it to Daisuke via e-mail.
N.B.: For a texbook, please use 4th edition because the exercises are different from those in previous editions.
N.B.: The homework last weeks will be returned in the problem sessions on Tuesdays in person. For those who do not attend the problem session, Daisuke will put them in his mail box after the problem session.
N.B.: For exercises: starred (*) exercises are more difficult and are intended in first instance only for students who want a high grade for the course.
N.B.: If you prefer to use latex to write derivations, here is the website for you.
N.B.: We modified Definition 2.3.12 on page 66 in the book as follows.
Preliminary course syllabus.
| Day | Material covered | Homework | |
|---|---|---|---|
| Tuesday, 4 Sep 2007 17-18 B.341 |
Introductory Lecture Dick de Jongh | ||
| Friday, 7 Sep 2007 13-15 I.401 |
Lecture Dick de Jongh | Section 1.1. until p.11 |
Total (17 points) A. (6 points) (1) Give definitions by recursion [as I did in class for the number of brackes, etc.] for (a) the number of 2-place connectives in a formula, (b) the number of atomic formulas (atoms), including \bottom in a formula [different occurrences count as different atomic formulas], (c) the leftmost atom in a formula, (d) the total number of symbols in a formula. (2) Prove that the number of atomic formulas is the number of 2-place connectives plus 1. (3) Prove that for formulas without negations the total number of symbols is 4 times the number of atoms minus 3. B. (2 points) P.14 (book), Exercise 1 (Only the first two questions). C. (5 points) P.14 (book), Exercise 7 (for (a) only for the first two quesions in Exercise 1). D. (4 points) P.14 (book), Exercise 2. |
| Tuesday, 11 Sep 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 14 Sep 2007 13-15 I.401 |
Lecture Benedikt Löwe | Section 1.2. until p.20 except substitution (Definition 1.2.5, Theorem 1.2.6, and Lemma 1.2.7). |
Total (16 points) E.(*) (3 points), F. (4 points): go to this page. G. (3 points) P.15 (book), Exercise 1.1.9. H. (3 points) p.21 (book), Exercise 1.2.2. I. (3 points) p.21 (book), Exercise 1.2.6. |
| Tuesday, 18 Sep 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 21 Sep 2007 13-15 P.227 |
Lecture Dick de Jongh | Section 1.3. until Lemma 1.3.5. (p.23) |
Total (17 points) J. (4 points) p. 21 (book), Exercise 1.2.5. K. (3 points) p. 27 (book), Exercise 1.3.1. only the first, second and fifth ones. L. (3 points) p. 27 (book), Exercise 1.3.2. only (a), (c), (e). M. (3 points) In class we showed: If \psi is an element of Sub(\phi), then \psi (occurs) in T(\phi). Show the opposite direction. N. (4 points) (a) Prove that if V'(p) = V(\psi), V'(q) = V(q) for all q other than p, then V'(\phi) = V(\phi[\psi/p]). (b) (*) Show that, if |= \phi (i.e. \phi is a tautology), then |= \phi[\psi/p] for all \psi. Hint: use (a) and reason by contradiction (more precisely, contrapositive): i.e. to prove A implies B, assume not B and try to prove not A. |
| Tuesday, 25 Sep 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 28 Sep 2007 13-15 I.401 |
Lecture Dick de Jongh | Section 1.3. (except Duality), Section 1.4. (only derivation rules) (p.36) | Go to this page. |
| Tuesday, 2 Oct 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 5 Oct 2007 13-15 I.401 |
Lecture Daisuke Ikegami | Section 1.4, 1.6 (But we have ignored Definition 1.6.1), not 1.5 (next week). |
Total (15 points) R. (8 points) Go to this page. S. (2 points) P. 39 (book), Exercise 1.4.4 T. (5 points) P. 39 (book), Exercise 1.4.8 (only for "and" and "negation" as inductive steps) (Hint): Go to this page. |
| Tuesday, 9 Oct 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 12 Oct 2007 13-15 P.227 |
Lecture Benedikt Löwe | Section 1.5 (until Definition 1.5.6, p. 47) |
Total (18 points) U. (4 points). In class, we proved the soundness of the rules of conjunction-introduction and contradiction. Prove the soundness of implication-elimination in the style of the book (see p.40-42 of the book). V. (6 points). Exercise 1.5.1 (p.47 of the book). (If you want to prove something is inconsistent, you should make a derivation witnessing it derives the falsum. You should not use Completeness Theorem instead.) W. (4 points). Exercise 1.5.2 (p.47 of the book). (You are not allowed to use Soundness and Completeness Theorems) X. (*) (4 points). Exercise 1.5.6 (p.48 of the book). |
| Tuesday, 16 Oct 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 19 Oct 2007 13-15 I.401 |
Lecture Dick de Jongh | Section 1.5 in the book. |
Total points (17 points) Y. (5 points) State and prove the corresponding result for disjunction in lemma 1.5.9.(p.45) Z. (4 points) Exercise 3 of p. 47 27. (*) (5 points) Show that, if \phi is independent of \Gamma, then there is a maximal \Delta containing \Gamma such that \phi is independent of \Delta, i.e. \phi is independent of \Delta but \phi is not independent of any set that properly contains \Delta. 28. (3 points) Show that if \Gamma is a consistent theory which is not maximally consistent, then there is a \phi independent of \Gamma. |
| Oct 22-26 EXAM WEEK No classes | |||
| Tuesday, 30 Oct 2007 17-18 P.016 |
Exercise Session |
| |
| Friday, 2 Nov 2007 13-15 I.401 |
Lecture Dick de Jongh | 2.1-2.3 until before freeness for a variable. |
Total (17 points) 29. (3 points) 2.2 Exercise 1, p. 60 (i), (ii), (iii), (vii), (viii) 30. (5 points) 2.3 Exercise 1, p.67 for (i), (ii), (iii), (vii), (viii) Work strictly according to the definition at least in the first three cases. Write down two terms and two atomic formulas in each case (try to vary a little). 31. (5 points) (a) Give a definition by recursion of BV(\phi) (2 points) (b) Give a definition by recursion of "nice formula", a formula in any whose subformula no variable occurs both free and bound. (2 points) (*) remark on the role of the definiton of FV and BV in this definition. (1 point) 32. (4 points) Go to this page. |
| Tuesday, 6 Nov 2007 17-18 P.016 |
Exercise Session, Canceled | ||
| Friday, 9 Nov 2007 14-16 P.014 |
No lecture | ||
| Tuesday, 13 Nov 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 16 Nov 2007 14-16 P.014 |
Lecture Benedikt Löwe | p.65-70 (up to and including Def 2.4.1) |
Total (19 points) 33. (5 points) On p.65, van Dalen gives an intuitive definition of "simultaneous substitution" and gives an example of how it differs from iterated substitution. Give a precise definition of simultaneous substitution along the lines of Definition 2.3.10. 34. (8 points) Exercise 2.3.4 (p.67) Modify the sentence as follows: Check which of the indicated terms are free for the variables for which they are to be substituted. Carry out the substitution in any case: 35. (6 points) Exercise 2.4.1 (p.72) |
| Tuesday, 20 Nov 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 23 Nov 2007 14-16 P.014 |
Lecture Benedikt Löwe |
p.70-74 from the definition of interpretation of
sentences (2.4.2) to Thm 2.5.1-2.5.2-2.5.3 (the theorems of section 2.5
without proof). In addition, the notion of assignment and the alternative definition of semantics via assignments and their induced interpretations. |
Total (19 points) 36. (4 points) The definition of Cl (phi) seems to depend on a choice of the order of free variables. Show that it does not really depend on the order, i.e., prove that if FV(phi) = {v_1,...,v_n} = {w_1,...,w_n}, then A models forall v_1 ... forall v_n phi if and only if A models forall w_1 ... forall w_n phi. 37. (6 points) Exercise 2.4.5 (p.72) 38. (6 points) Exercise 2.4.7 (p.72) 39. (3 points) Consider the 'WARNING' on p.74 and find an example of a structure A such that A models forall x (phi(x) vee psi(x)) but not A models forall x (phi(x)) vee forall x (psi(x)). Be precise about the definition of the semantics. |
| Tuesday, 27 Nov 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 30 Nov 2007 14-16 P.014 |
Lecture Benedikt Löwe |
Lemma 2.5.4, Substitution Theorem (2.5.8), a little bit about examples
(Def 2.7.4; and a bit about partial orders). A motivation for the completeness theorem, discussing compactness and an application (non-definability of 'finiteness' in the language of partial orders), and the deduction system pp. 91-92. |
Total (25 points) 40. (9 points) Exercise 2.5.4 (3 points) Exercise 2.5.12 (3 points) Exercise 2.5.13. (i) (3 points) 41. (*) (6 points) Exercise 2.5.11 42. (4 points) Exercise 2.5.15 43. (6 points) Read Section 2.7 (pp. 83-90) carefully. Do exercises 2, 4 and 5 (p.90; two points each). |
| Tuesday, 4 Dec 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 7 Dec 2007 13-15 E.020 |
Lecture Dick de Jongh | 2.8 and 2.9 (natural deduction). |
Total (24 points) 44. (6 points) Exercise 2.8.1 (ii), (v), (vii). For (vii), Say at which step "x notin FV(phi)" is used. 45. (10 points) Exercise 2.9. 1,3,5,7(one direction *), 9. For 7 and 9, Say at which step "x notin FV(phi)" is used. 46. (*) (8 points) Prove soundness for the elimination of existentence rule of page 98. Don't forget to note where the restrictions on the rule are used (p. 97). |
| Tuesday, 11 Dec 2007 17-18 P.016 |
Exercise Session | ||
| Friday, 14 Dec 2007 13-15 I.301 |
Lecture Benedikt Löwe | ||
| Dec 17-21 EXAM WEEK No classes | |||
Last update: November 17th, 2007