CS616: PreCoursework
1 Introduction and motivation
... to the representation and management of knowledge.
References:
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 BenAri (1993).
4 Firstorder logic
First order logic formulae, their meaning, validity and satisfiability,
translating between natural language and firstorder logic.
Suggested literature:

Chapters 6 from Kelly (1997), especially what is necessary for
the exercises.
 Chapter 3.1  3.3 from BenAri (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.23 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.23 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).

Firstorder logic:
Exercise 4.1 (page 92), 6.1 (page 150151) 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. BenAri (1993). Mathematical Logic for Computer Scientists. Prentice Hall International.
Renate A. Schmidt
Home 
Publications 
FM Group 
Dept Computer Science 
Man Univ
Last modified: 05 Dec 05
Copyright © 2005
Renate A. Schmidt,
School of Computer Science, Man Univ, schmidt@cs.man.ac.uk