Logic and Set Theory (2IT05, 2IT07)

Last update: January 18, 2012

News:

  • (18-Jan-2012) A new version of the examination of January 24, 2011 has been put on the website. (The previous version had a typo in problem 5 of the English version.)
  • (16-Jan-2012) On Tuesday January 17, 2012 (3+4) there will be an extra lab session in MA 1.60. Students of all groups are welcome to join this extra lab session. Roel Bloo will be available to answer your questions and to give you feedback. On Thursday January 19, 2012 (3+4) there will be a tutorial in AUD. 8 in which solutions to a selection of problems from the examinations of January 24, 2011 and June 30, 2010 will be discussed. Do prepare this tutorial by making these old examinations beforehand!
  • (12-Jan-2012) A document with example solutions to selected exercises from Chapter 20 has been added. It contains solutions to exercises 20.4, 20.6, 20.7, 20.13, 20.16, 20.17(a,c). We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (11-Jan-2012) The list of frequently asked questions has been further extended, with some suggestions on how to prepare for the final examination.
  • (10-Jan-2012) On Monday January 16, 2012 (5+6) there will be extra lab session in two locations (MA 1.60 and MA 1.46). Students of all groups may join these lab sessions in either location. There will not be a program for these lab sessions posted on the website; you can work on exercises that have been on the program of one of the previous lab sessions, or work on old examinations. There will be instructors available to answer your questions and to give you feedback. It will then also be discussed with the students present whether it is considered useful to organise one more extra lab session on Tuesday January 17, 2012.
  • (10-Jan-2012) The results for the three tests are listed here. The grade in the 'Result' column is the grade that we will use to compute your final grade for the course (combining it with the grade for the final examination, see the section Examination below). Please check your grades, and contact us if you think they are incorrectly registered. Warning: You will most likely find the final examination at least as challenging as Test 3. So if your grade in the Result column is satisfactory, but your result for Test 3 is not, then we urge you use the remaining two weeks to practice a lot with the material, as a preparation for the final examination.
  • (09-Jan-2012) Solutions to Test 3 can be found here, for those of you who, for some reason, could not attend the tutorial right after the test.
  • (23-Dec-2011) The results for Test 1 and Test 2 are listed here. We urge you to collect your test from your instructor; he can probably give you some valuable feedback.
  • (20-Dec-2011) Solutions to exercise 19.7 have been added to the document with example solutions to selected exercises from Chapter 19 and the collection of Additional Exercises that was posted earlier today.
  • (20-Dec-2011) Important information regarding the test this Thursday December 22, 2011 (10:45-11:30):
    • The test will take place in three lecture halls: AUD 6, 7 and 8.
      • Students in lab session group 1 (instructor: Bloo) should go to AUD 6.
      • Students in lab session group 2 (instructor: Cuijpers) should go to AUD 7.
      • Students in lab session group 3 and 4 (instructors: Hoogerwoord and Cranen) should go to AUD 8.
    • The test will be about the material of Chapters 17, 18, and 19.1-19.5 of the book.
    • Solutions will be presented right after the test, from 11:45-12:30 in AUD 8.
  • (20-Dec-2011) A document with example solutions to selected exercises from Chapter 19 and the collection of Additional Exercises about induction has been added. It contains solutions to exercises 19.7 from the book and exercises 2, 5, 7, 10 and 14 for the collection of Additional Exercises. We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (17-Dec-2011) A document with example solutions to selected exercises from Chapters 17 and 18 has been added. It contains solutions to exercises 17.7, 17.9(c), 17.10, 18.3(c), 18.4(c), 18.7 from the book. We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (06-Dec-2011) Important information regarding the test this Thursday December 8, 2011 (10:45-11:30):
    • The test will take place in three lecture halls (note that this website previously listed wrong locations): AUD 6, 7 and 8.
      • Students in lab session group 1 (instructor: Bloo) should go to AUD 6.
      • Students in lab session group 3 and 4 (instructors: Hoogerwoord and Cranen) should go to AUD 7.
      • Students in lab session group 2 (instructor: Cuijpers) should go to AUD 8.
    • The test will be about the material of Chapters 11-16 of the book, but it will be the case that problems about Chapter 16 can be solved using only the material of 16.1-16.5.
    • Note that when you are asked to prove with a derivation that some formula is a tautology, then you should exclusively use the methods listed in the Tables for Part II on p. 375-380 of book (2nd revised edition of 2011).
    • Solutions will be presented right after the test, from 11:45-12:30 in AUD 8.
  • (03-Dec-2011) The list of frequently asked questions has been extended with two questions and aswers.
  • (02-Dec-2011) A document with example solutions to selected exercises from Chapter 16 has been added. It contains solutions to exercises 16.4(d), 16.7(c,d), 16.8, 16.12(c,d) from the book. We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (01-Dec-2011) A document with example solutions to selected exercises from Chapters 12-15 has been added. It contains solutions to exercises 12.4(d), 13.1(b), 13.2(b), 14.2(a), 14.6, 14.8(b,c), 14.9(b), 14.10(b), 15.5, 15.8 from the book. We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (30-Nov-2011) The major change in the second revised edition of the book, which we are using in the course this year, is that some of the derivation rules discussed in part II of the book have been changed. The available solutions to exams of previous years (see here) have been adapted to use the new rules.
  • (30-Nov-2011) The results for Test 1 are listed here. We urge you to collect your test from your instructor; he can probably give you some valuable feedback.
  • (29-Nov-2011) Because the alternative rules for existential quantification (Sections 15.4 and 15.5) have not yet been introduced properly in the lecture of today, the planning for weeks 4 and 5 has been slightly revised: the exercises involving the alternative rules for existential quantification have been moved to week 5.
  • (26-Nov-2011) For 1st year Software Science and Web Science students participating in the honours star programme: a star examination will be organised in January, including a question about Logic and Set Theory.
  • (18-Nov-2011) A document with example solutions to selected exercises from Chapters 7-11 has been added. It contains solutions to exercises 7.3(b), 7.7(b), 8.2(e), 8.7(c), 8.9(b),(d), 9.5(b), 9.6(b),11.4(c), 11.6 from the book. We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (17-Nov-2011) A document with example solutions to selected exercises from Chapters 1-6 has been added. It contains solutions to exercises 2.4(c),(d), 2.6, 2.8, 3.1, 4.4(e), (f), 5.5 (c), (d), 6.5(b) and 6.6(c) from the book. We strongly advise you to first try these exercises yourself, before looking at all at these solutions.
  • (15-Nov-2011) Room change for lab session group 2 (Pieter Cuijpers): on Mondays 5+6, the lab sessions will, from now on, take place in MA 1.44.
  • (15-Nov-2011) Lab session group 5 has been cancelled.
  • (14-Nov-2011) Group 5 (of Gerard Zwaan) was so small today, that we have decided to merge it with Group 3 (of Rob Hoogerwoord), at least for the lab session of tomorrow, Tuesday November 15, 2011. So there will not be a lab session in MMP room 1; students registered for Group 5 should go to MA 1.44.
  • (10-Nov-2011) If you want to take this course in the second quartile of 2011-2012, then you should register for it at oase.tue.nl, and also subscribe to one of the lab session groups:
    • If you are a Software Science, a Web Science, or a Combined P student and your tutor is Roel Bloo, then you must subscribe (or are automatically subscribed) to lab session Group 1.
    • If you are a Software Science or a Web Science student and your tutor is Pieter Cuijpers, then you must subscribe (or are automatically subscribed) to lab session Group 2.
    • If you are a Software Science or a Web Science student and your tutor is Kees Hemerik, then you are advised to subscribe to Group 3.
    • If you do not belong to any of the abovementioned categories, then you may choose to subscribe either to Group 4 or to Group 5.

General information:

Codes: 2IT05 (6 ECTS), 2IT07 (3 ECTS)
Audience: 2IT05:Software Science (bachelor, year 1), Web Science (bachelor, year 1), Combined P Bachelor Mathematics and Computer Science, and Innovation Sciences (ICT) (bachelor, year 2);

2IT07: homologation for BIS, CSE, ES (master, year 1).


Lectures:
 There will be two lectures a week, on Mon 3+4 and Tue 1+2; all lectures will be in AUD 8.

Lecturer: Bas Luttik.

Lectures will be recorded on video (see videocollege.tue.nl).


Lab sessions: There will be two lab sessions a week, on Mon 5+6 and Tue 3+4.

Students:
 Instructor:
 Locations:


Mon 5+6
 Tue 3+4





Group 1
 Roel Bloo MA 1.60
 MA 1.46
Group 2
 Pieter Cuijpers MA 1.44
 MA 1.60
Group 3
 Rob Hoogerwoord/
Gerard Zwaan 		MA 1.43
 MA 1.44
Group 4
 Sjoerd Cranen MA 1.46 AUD 9
 (Exception: on Tue 22 November, 2011 (3+4) this lab session will be in PT 6.05 instead of AUD 9.)



Tutorials:
 There will be one tutorial a week, on Thu 3+4 in AUD 8.

Lecturer: Bas Luttik.


Office hour:
 I'll reserve the midday break (12:30-13:30hrs.) on Tuesdays for answering questions regarding this course; come and see me in my office (HG 6.85)!

Outside this office hour, you can always drop by my office to see if I am available, but chances are that I'm not in my office, or in a meeting. If you want to be sure that I have time to talk to you, first make an appointment by email.

Questions can, of course, also be asked by e-mail; I always try to respond within a day.

See also the list of Frequently Asked Questions!

Course material:

Book (for sale at GEWIS):

Rob Nederpelt, Fairouz Kamareddine:
Logical Reasoning: A First Course
Text in Computing, Vol. 3
King's College Publications, London, 20
Second revised edition, 2011

(The collection of tables appearing at the end of the book, summarizing the most important definitions, axioms and rules, can be downloaded here.)

Slides used in lectures:

  • (14-Nov-2011) Organisation, Introduction, Propositional logic 1
  • (15-Nov-2011) Organisation, Propositional logic 2
  • (21-Nov-2011) Propositional logic 3, Predicate logic 1
  • (22-Nov-2011) Predicate logic 2, Binders
  • (28-Nov-2011) Reasoning 1
  • (29-Nov-2011) Reasoning 2
  • (05-Dec-2011) Reasoning 3, Sets 1
  • (06-Dec-2011) Sets 2
  • (12-Dec-2011) Sets 3, Relations
  • (13-Dec-2011) Mappings
  • (19-Dec-2011) Induction 1
  • (20-Dec-2011) Induction 2, Cardinality
  • (09-Jan-2012) Organisation, Orderings 1
  • (10-Jan-2012) Organisation, Orderings 2

    • Solutions to selected exercises:

  • Solutions to selected exercises from Chapters 1-6 from the book.
  • Solutions to selected exercises from Chapters 7-11 from the book.
  • Solutions to selected exercises from Chapters 12-15 from the book.
  • Solutions to selected exercises from Chapter 16  from the book.
  • Solutions to selected exercises from Chapters 17 and 18 from the book.
  • Solutions to selected exercises from Chapter 19 from the book and some Additional exercises.
  • Solutions to selected exercises from Chapter 20 from the book.

    • Additional material:

  • Additional exercises
  • A handout entitled What is (in) a proof? about the correspondence between derivations and proofs in natural language.

    • Old examinations:

    An extensive list of examinations of previous installments of this course is maintained on a separate page.

    Syllabus and schedule:

    A detailed syllabus with a week-by-week listing of topics, slides used in the lectures, programmes for lab sessions and tutorials, etc. can be found here.

    This week's schedule:


    (09-Jan-2012)
        Lecture 7:
    		Chapter 20 of the book; slides: Organisation, Orderings 1
        Lab 5:
    		 20.1, 20.3, 20.5, 20.8
    (10-Jan-2012)
        Lecture 6:
    		 Chapter 20 of the book; slides: Organisation, Orderings 2
        Lab 6:
    		 20.10, 20.11, 20.14, 20.15
    (12-Jan-2012)
        Tutorial 7:
    		 20.2, 20.4, Problem 8 of Examination of Jun-30-2010, 20.9, 20.12, 20.16

    Examination:

    There will be three tests during the course, and a final examination at the end of the course.

    The first test is about Chapters 1-10 of the book; it will take place on Thursday November 24, 2011 (10:45-11:30) in HG 10.01.

    The second test is about Chapters 11-16 of the book; it will take place on Thursday December 8, 2011 (10:45-11:30) in AUD 6, 7 and 8.

    The third test is about Chapters 17-19 of the book; it will take place on Thursday December 22, 2011 (10:45-11:30) in AUD 6, 7, and 8.

    The final examination is about all course material (book, slides, additional material); it will take place on Tuesday January 24, 2012 (9:00-12:00).
    Although we strongly advise students to read Sections 19.6-19.10 of the book (structural induction, cardinality, denumerability and uncountability),  and Section 20.8 of the book (well-ordering and well-foundedness), there will not be questions about these topics in the regular examinations for the academic year 2011-2012. There may, however, be questions pertaining to these topics in the special honours-star program exam.

    The grade G for the course Logic and Set Theory (2IT05 and 2IT07) is computed as follows:
    1. Let T1 and T2 be the two highest grades obtained for the three tests during the course.
    2. Let F be the grade obtained for the final examination.
    3. Then G=round[(T1+T2+4*F)/6].
    (Thus, the lowest grade obtained for the tests during the course will be discarded when computing the final grade.)

    The course Logic and Set Theory (2IT05 and 2IT07) has been passed if G >= 6.

    NB: It is not allowed to use any course material (books, notes, tables with formulas, etc.)  at the test or the examinations!

    There is a resit examination on Monday April 16, 2012 (9:00-12:00). The results for the tests are not taken into account when determining the grade for the resit examination: the grade for the resit examination, rounded off to the nearest integer, is directly a grade for the course Logic and Set Theory (2IT05 and 2IT07).

    NB: It is not allowed to use any course material (books, notes, tables with formulas, etc.)  at the resit examination!

    Miscellaneous:

    There is a LaTeX package to typeset flag style derivation.
    It is made by Paul van Tilburg and it can be downloaded from http://www.ctan.org/tex-archive/help/Catalogue/entries/flagderiv.html.
    (The package flagderiv.sty is obtained by downloading all files and executing  'latex flagderiv.ins'.)

    PROP is a computer program to do logical calculations with abstract propositions, according to the methods described in part I, Chapter 6.
    The program is written by Hans Zantema and it can be downloaded from http://www.win.tue.nl/~luttik/Courses/LV/prop.zip. After unpacking, run prop.exe.

    At http://www3.amherst.edu/~nstarr/puzzle.html there is information about the tromino puzzle