These will be published progressively here during the course of the semester.
Practical work for this unit (tutorials) will be done during the Lecture Workshops. See below for assessment details.
See the Asssessment page.
I recommend you use the book “Mathematics for Computer Science” by Lehman, Leighton and Meyer, as the first place to turn to after the lectures. This is a 908-page behemoth that covers all we need and lots more. It is also freely available to download as a PDF, though I wouldn’t advise printing it! The direct link is: courses.csail.mit.edu/6.042/spring17/mcs.pdf
For the final part of the course, on automata and languages, I recommend the book Introduction to the Theory of Computation by Michael Sipser. This can be an expensive book, but copies are available to buy online from $15 from e.g. www.bookfinder.com. The 3rd edition is the most recent, but earlier editions would be fine too. It is a classic text, so well worth having on your bookshelf for Computer Scientists.
It’s important to find and use a textbook that works well for you, though, and the two recommended textbooks can move quite briskly. As an alternative, you might wish to investigate some of the textbooks listed under Supplementary texts, below.
Additional suggestions for this list are welcome. Post your suggestions to help2211.
In addition to the recommended reading for weeks 1 through 3, you might find helpful several chapters from the “Book of Proof” by Richard Hammack. For some topics, it moves at a gentler pace than does the Lehman, Leighton and Meyer textbook (plus it also contains more sample exercises you can try). Relevant chapters are chapter 2, on propositional and predicate logic, and chapters 4 through 10, on methods of proving things.
Chapter 1 of Foundations of Computation by Carol Critchlow and David Eck covers similar material.
If you would like more practice on using truth tables – and instant, web-based feedback on whether you are right or not – you might want to try some of the online exercises from Chapter 10 of the Carnap online logic course.
Extra exercises for weeks 1-3:
Here are some additional logic resources:
Propositional logic quizzes. For practice, try your hand at the following quiz exercises:
Some classes of assertion automatically proved or disproved by computer. For example, the following websites are all capable of proving (or disproving) particular classes of statements:
Try some of these out. What sort of theorems can they prove? From lectures and the textbook, are these all theorems which you know can be mechanically proved? If not, then can you work out how the program is tackling them?
Even when a theorem cannot be automatically proved, computers can still check (or assist in the writing of) a human-produced proof. Some examples of so-called “proof assistants” are:
Advice on writing proofs:
Besides the tips in the Lehmann textbook, there are several other resources you may find useful:
Two books are available which provide extensive advice on reading and writing proofs:
You may find useful the videos listed under the “Set Theory” and “Relations and Functions” sections of the Trevtutor.com “Discrete Math 1” page, part of the Discrete Math 1 YouTube playlist. The first video is Introduction to Sets.
We look at three classes of language – regular languages, context-free languages, and Turing-recognizable languages – which are recognized by three corresponding sorts of automata (Finite State Machines, Push-Down Automata, and Turing machines, respectively).
There is another class of language we do not cover in CITS2211, the class of context-sensitive languages. Context-sensitive languages are generated by context-sensitive grammars and recognized by linear-bounded automata; context-sensitive grammars are similar to context-free grammars, but loosen the requirement that, for any production rule, there may be only one non-terminal on the left-hand side of the rule.
For an explanation of context-sensitive languages, and formal languages and automata in general, a good reference is the book Introduction to Formal Languages by György E. Révész (Dover publications, 1983, reprinted 2015, ISBN 9780486666976).
You may find useful the videos listed under the “Number Theory and Formal Languages” section of the Trevtutor.com “Discrete Math 1” page, part of the Discrete Math 1 YouTube playlist. The first relevant video is Formal Languages.
These may be a useful addition to the texts we follow in class.
The Open Logic project provides a number of open-source texts on logic, set theory, and computation.
The Open Logic project wiki also provides a list of links to other freely available logic texts
The University of Minnesota Open Textbook Library links to a number of freely available texts that may be of interest: Foundations of Computation, the Book of Proof, Mathematical Reasoning, and Proofs and Concepts.
The Book of Proof has solutions available on its website, and the Mathematical Reasoning text has solutions to selected exercises available in an appendix.