CS616: Pre-Coursework

1 Introduction and motivation

... to the representation and management of knowledge.

References:

• Chapter 2 of Nebel (1990). PostScript (2 pages on one), PostScript

2 Elementary set theory

What is a set, a relation, a function, set operations (intersection, union, etc), properties of binary relations (reflexivity, symmetry, transitivity, etc)?

Suggested literature:

• Chapter 5.2 in Cormen, Leiserson, and Rivest (1990).
• Any book on the mathematical foundations of CS or discrete mathematics.
• Chapter 1.1 and 1.3 of "Interactive Real Analysis" (Website at Seton Hall University).
  This website includes interactive exercises with answers.

3 Propositional logic

What is a theory, language, models, validity and satisfiability, inference rules, soundness and completeness, reasoning methods: truth tables, semantic tableau, proof by contradiction.

Suggested literature:

• Chapters 1, 2 and 4 from Kelly (1997), especially what is necessary for the exercises.
• Chapters 2.1 - 2.6 and 2.10 from Ben-Ari (1993).

4 First-order logic

First order logic formulae, their meaning, validity and satisfiability, translating between natural language and first-order logic.

Suggested literature:

• Chapters 6 from Kelly (1997), especially what is necessary for the exercises.
• Chapter 3.1 - 3.3 from Ben-Ari (1993).

Assignment / Work to be handed in

Please submit your solutions to the following exercises at the first lecture on 30 January 2006.

• Elementary set theory: Exercise 5.2-3 from Chapter 5 (title: "Sets, Etc", title of 5.2: "Relations") of Cormen, Leiserson, and Rivest (1990).
  There might be different editions of Cormen et al. and Exercise 5.2-3 is not the same in all editions. Thus here is the exercise we want you to do.

  Give examples of relations that are a. reflexive and symmetric but not transitive, b. reflexive and transitive but not symmetric, c. symmetric and transitive but not reflexive.

  (The title of Chapter 5 is "Sets, Etc", the title of Section 5.2 is "Relations".)

• Propositional logic: Exercises 1.1(i), (iv), (viii), (x), 1.4 (all page 25), 2.1 (i), (ii), (iii), (v), 2.2 (iv) (all page 41) of Kelly (1997).
• First-order logic: Exercise 4.1 (page 92), 6.1 (page 150-151) of Kelly (1997).

And remember to read

• Chapter 2 of Nebel (1990).

References

• Nebel, B. (1990). Reasoning and Revision in Hybrid Representation Systems. Lecture Notes in Artificial Intelligence, Vol. 422, Springer. The relevant chapter is available online: PostScript (2 pages on one), PostScript
• Cormen, T. H., C. E. Leiserson, and R. L. Rivest (1990). Introduction to Algorithms. MIT Press.
• Kelly, J. (1997). The essence of logic. PHI.
• M. Ben-Ari (1993). Mathematical Logic for Computer Scientists. Prentice Hall International.