140 Logic homepage
Alessandra Russo and Ian Hodkinson (with thanks to Krysia Broda, Robin Hirsch and Dirk Pattinson for
additional material)
Autumn 2016
Coursenotes | top
Here are the slides from an earlier year; this year's will be made
available on cate.
Exercises and solutions are
also available on cate.
Solutions to exercise sheets
will be available (on cate) to students
a week after submission of solutions.
Extra material etc:
Xmas test 2014: Logic questions
| solutions
Xmas test 2009: Logic questions and solutions and markscheme
Xmas test 2005: Logic questions and solutions
Natural deduction advice
Summary of equivalences and natural deduction
rules
Pandora
| top
Pandora
(natural deduction game) --- works fine on Mac Safari 5.1.10 with java enabled (Oct 2015)
New Pandora IV
(natural deduction game) page with new version of Pandora and a free downloadable Java application.
Sample (old-)Pandora session
LOST (LOgic Semantics Tutor)
| top
These Java applications, which probably don't work nowadays,
will let you enter signatures, structures, and sentences, and evaluate them in the structures both directly and in other ways such as
by Hintikka games (not nowadays lectured on, but you should get the hang of them from the software).
They are getting old, and error-free functionality is not guaranteed. There are two versions:
- Windows version (Leon Mouzourakis, 2007): live in the labs, see under programs/lab/LOST, or just type 'lost' at a command prompt (it may no longer be available). Help
and sample files are available in the same directory. You may be able to access the
help system from the Help menu, but it may ask you where the help files are. Alternatively, here is the user manual. For logic-English translation, LOST will ask for a dictionary file. There are some in here.
- Linux version (group project 2006): this may still be live in the labs
at /usr/lib/lost. For help, use the Help menu. Sample files
(and the help files) are in
/usr/lib/lost/plugins/lost_1.0.0 or something like that.
This version doesn't work on 64 bit Linux machines.
It's also using Java 6, which it wasn't tested with, but I had only a few problems and you may find it usable with practice.
I suggest you read the help, and then
try loading the two files about dragons (signature and structure)
and go on from there. I had problems playing Hintikka games
and the make-formula-true game
when the current signature and structure were not saved to disk, so I suggest you do this beforehand.
Extra books/logic
teaching software |
top
Suggested textbooks
- See the reading list on pages 2-3 of the notes.
- Among the books mentioned there, the one available on the
Pandora home page
was written for the course and has long sections on natural deduction,
many examples, etc. It is also good for the courses on
Discrete Maths and Reasoning about Programs.
- You may find
Schaum's
Outline of Logic, by J. Nolt, D. Rohatyn and A. Varzi,
useful. I haven't seen this book, but Schaum books usually have a lot of examples.
- An open access (free) logic book called something like
forall X,
an introduction to formal logic, by P. D. Magnus
(Albany, NY), has a lot of examples of translation of English to logic,
and exercises and solutions.
Discrete Mathematics and Its Applications, by K. Rosen, also has logic chapters
and a full study guide. Thanks to Milen Dzhumerov for these suggestions.
Software
In the US, Jon Barwise and John Etchemendy
have pioneered new approaches to logic
teaching, using software tools. You may be interested in
their work:
- The
language of first-order logic : including the program Tarski's world
Jon Barwise and John Etchemendy, Stanford: CSLI Lecture Notes; New
York: Cambridge University Press; several editions from 1991 onwards.
Several copies in library
- Tarski's
World
Jon Barwise and John Etchemendy, Stanford: CSLI Lecture Notes; New
York: Cambridge University Press; Second edition, 1993.
Classic software; our LoST programs are related to it.
- Hyperproof
Jon Barwise and John Etchemendy; program by Gerard Allwein, Mark
Greaves, and Michael Lenz, with additional programming by Alan Bush ...
[et al.]
University of Chicago Press, 1994.
1 copy in library
- Language,
Proof, and Logic
Dave Barker-Plummer, Jon Barwise, John Etchemendy, CSLI Publications, 2011.
Available here.
Buying this book gets you a lifetime password to a US server called the
grade-grinder. You can submit logic exercises to it, and it marks
them and give you
feedback by email.
There are cheap 2nd-hand copies on Amazon, but they may not have the
CD,
and even if they do, you may not be able to transfer access rights from
the original buyer.
Further reading | top
The course is only an introduction to logic. But we cover the
tips of some bigger topics. For those interested, here is some
more information with links to Wikipedia etc.
- Church's
theorem (1935), that there is no algorithm (computer program) to decide
validity of sentences of predicate logic. This can be proved by
showing that such an algorithm would also be able to solve the halting problem
(the problem of detecting whether a given program halts or runs
forever), which
is impossible. The identification of 'algorithm' with 'computer
program' relies on the Church-Turing
thesis.
- Finding an efficient way of deciding satisfiability
of propositional formulas, or showing that no such method exists,
is
equivalent to solving (positively or negatively, respectively)
the problem 'P = NP'.
This is often called one of the most important unsolved problems in computing, and there is
currently a $1M prize (not from me) going for a correct solution. Here
is more on NP.
- Modus ponens in antiquity
- a study of the ancient development of this form of argument,
from Aristotle to the 2nd century AD, by
Susanne Bobzien, Professor of Philosophy, Yale University.
If you would like to read more on some of
these topics, try the notes
for a past second-year course, or books (try the library), such as:
- Harel, David (2000). Computers Ltd. : what they really
can't
do. Popular book.
- Harel, David (1989). The science of computing : exploring
the
nature and power of algorithms. Accessible textbook.
- Hofstadter, Douglas R (1979). Gödel, Escher, Bach : an
eternal golden braid. Popular book.
- Penrose, Roger (1989). The emperor's new mind : concerning
computers, minds, and the laws of physics. High-powered and
controversial popular
book, with a sequel Shadows of the Mind. See Davis's
and Feferman's
critiques.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001).
Introduction to automata theory, languages, and computation. An
excellent professional-level textbook.
- Wilfrid Hodges (1993).
Model Theory. Another
excellent professional-level textbook, more for mathematicians.
You may prefer A shorter model theory.
- Logicomix -- a graphic novel about logic.