Logic for Mathematics and Computer Science
The Flow of Topics
|
Chapter
|
Traditional Logic
|
Universal Algebra
|
Computational Logic
|
| 1 |
syllogisms (1.1-1.2)
|
™
|
algebra of logic (1.3-1.4)
|
| 2 |
basics (2.1-2.9)
|
™
|
resolution (2.10-2.13)
|
| 3 |
algebras, terms (3.1-3.3)
|
equational
logic (3.4-3.11)
|
unification (3.12)
TRSs (3.13-3.15)
|
| 4 |
structures,
formulas (4.1-4.2)
|
™
|
resolution (4.3-4.9)
ground clauses (4.10)
|
| 5 |
semantics (5.1-5.14)
|
™
|
skolemization (5.12-5.3)
|
| 6 |
completeness (6.1-6.10)
|
™
|
™
|
The preceding diagram indicates the basic structure
of the text, showing the topics that are normally covered in
a logic course, topics from universal algebra,
and topics from computer science.
Two fundamental aspects of logic, the foundational and the computational,
are presented here. Traditional logic topics can be taught without going
into computational aspects by staying with the first column of the
diagram, and one can work through the algorithms of the computational side
without being too concerned about the traditional theory. One can
see possible ways of designing a course by considering the following
dependency diagram, where a bold line from a higher topic to
a lower topic means that the lower topic depends on the higher
topic.
Dependency of topics
Thus one can design a traditional course based on the
shaded portion. Note that the topic in Sec. 2.9
is not required
for other topics. Thus one can, if desired, completely omit
the study of propositional proof systems, with the idea that
the interesting proof system to be covered will be the first-order
case. Or one can replace Sec. 2.9 with any of a number of
different proofs systems available. One particularly elegant
choice is given in Appendix D. Likewise, one can omit the leisurely
introduction to the first-order logic given in Secs. 5.1-5.6.
One can design a very computational course by
choosing the topics in the loop. Note that Chapter 1 and
Secs. 3.4-3.15 are not requisite for other topics, and thus
could be optional,
but all the other computational topics have important
interdependencies.
Personally
I prefer a mix of the two, with some variation from year to year.
The University of Waterloo has a one-semester elective course in
logic that is intended for third- and fourth-year students in
all areas of
the mathematical sciences.
A substantial portion of the students in mathematics and computer
science take this course.
Most recently I have taught the following topics in this course:
Chapter
1 Secs. 1.1-1.2,
Chapter
2 Secs. 2.1-2.13,
Chapter
3 Secs. 3.1-3.11,
Chapter
4 Secs. 4.1-4.2,
and
Chapter
5 Secs. 5.1-5.11.
