CS 1155B - Understanding and Constructing Proofs

CS 1155 (Understanding and Constructing Proofs) is the first course in the computer science department on the formal mathematical foundation of computer science. The material in this course is required and further developed in courses such as CS 3156 (In troduction to Automata Theory) and CS 3158 (Design and Analysis of Algorithms). All CS majors should take this course as early as possible, preferably in their freshman year.

As described above, the primary purpose of this course is for you to develop skill in the technique of proving things. Like any skill, development takes practice --- lots of practice. I will present many examples of proofs in class; these should serve as useful models, but are no substitute for working out problems yourself. The homework assignments will give you the opportunity to practice your technique. You should try to work out the homework problems on your own, seeking help from the TA's or mys elf after you have given the problem some thought.

Goals for this course are :

1. To take an informal problem statement and express it using unambiguous and rigorous mathematics.
2. To correctly use mathematical definitions, and to recognize that the precision of definitions complements (and sometimes contradicts) intuition.
3. To apply understanding of proofs and proof techniques to write correct proofs, starting with the hypothesis and known facts and ending with the conclusion.
4. To understand what constitutes a proof, and be able to recognize flaws in candidate proofs.
5. To select an appropriate proof method.
6. To understand the relationship between mathematical foundations and the rest of computer science.
7. To appreciate a part of the history of mathematics and computer science.

The required textbook is by K. Rosen, "Discrete Mathematics and Its Applications (Third Edition)", McGraw Hill, 1995.

Several other books cover proofs and proof techniques with a more "conversational" tone. These books should be available at the library. None are required, but they are all fun to read and are likely to reinforce the notion of what constitutes an elegant proof and how proofs can be useful in a variety of contexts.

• J. Woodcock & M. Loomes, "Software Engineering Mathematics", Addison-Wesley, 1988.
• D. Velleman, "How to Prove It: A Structured Approach", Cambridge University, 1994.
• G. Polya, "How to Solve It: A New Aspect of Mathematical Method", Princeton University Press, 1945.
• D. Solow, "How to Read and Do Proofs: An Introduction to Mathematical Thought Processes", John Wiley and Sons, 1990.

There are two teaching assistants for this course.

Michael Smith
Email: TBA Office: Picnic Area
Office Hours: TBA