1 Introduction and motivation
... to the representation and management of knowledge.
2 Elementary set theory
What is a set, a
relation, a function, set operations (intersection, union, etc),
properties of binary relations (reflexivity, symmetry,
Chapter 5.2 in Cormen, Leiserson, and Rivest (1990).
Any book on the mathematical foundations of CS or
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.
Chapters 1, 2 and 4 from Kelly (1997), especially what is necessary for
- 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.
Chapters 6 from Kelly (1997), especially what is necessary for
- 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
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
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".)
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).
Exercise 4.1 (page 92), 6.1 (page 150-151) of Kelly (1997).
And remember to read
Chapter 2 of Nebel (1990).
Nebel, B. (1990).
Reasoning and Revision in Hybrid Representation Systems.
Lecture Notes in Artificial Intelligence, Vol. 422,
The relevant chapter is available online:
PostScript (2 pages on one),
Cormen, T. H., C. E. Leiserson, and R. L. Rivest (1990).
Introduction to Algorithms.
Kelly, J. (1997).
The essence of logic.
- M. Ben-Ari (1993). Mathematical Logic for Computer Scientists. Prentice Hall International.
Renate A. Schmidt
FM Group |
Dept Computer Science |
Last modified: 05 Dec 05
Copyright © 2005
Renate A. Schmidt,
School of Computer Science, Man Univ, email@example.com