# How can I learn about proofs for computer science?

I study computer science at a university. My school offers several courses where various proofs are expected, but there is no course that introduces the fundamental concepts of proofs and how to write your own proofs. It's possible to "muddle through" some of these courses without really understanding proofs, but I want to spare myself the frustration and actually learn about them.

How can I learn about proofs for computer science?

I want to start at the very basics of proofs. I'm only interested in proofs as they relate to computer science, since I will have to spend my spare time on this. However, if I really do need to learn about mathematical proofs in general first, then so be it.

Note: Just reading the proofs in our course literature is not enough; this is what me and my classmates do right now, and none of us have any deeper understanding of what constitutes an actual proof.

-

Proofs are proofs. The basic logical structures are independent of the mathematical subject area, so there’s no real loss in starting with a general introduction to the subject. You’ll find a list of books on the subject here; it includes the book by Daniel Solow that Gerry Myerson mentioned. It also includes How to Prove It: A Structured Approach, by Daniel J. Velleman, which I think is a significantly better book. (It’s also cheaper and gets some very good reviews at Amazon.) I taught from the first edition of Transition to Advanced Mathematics, by Richard St. Andre, D. Smith, and M. Eggen a good many years ago; if I remember correctly, it was perfectly usable but not so good as the Velleman. I’m not familiar with the others listed.

The discussion and links here are also useful. In particular, the first edition of Bridge to Abstract Mathematics: Mathematical Proof and Structures, by Ronald P. Morash, is available for free download; I also taught from it a number of years ago and remember it as being quite decent.

Finally, some introductory discrete math texts devote significant space to introducing students to reading and writing proofs (and also contain mathematics that students in computer science ought to know). One such is Edward Scheinerman, Mathematics: A Discrete Introduction, which I recommend highly. Another is Susanna S. Epp, Discrete Mathematics with Applications.

-
I read the introduction to Velleman's book, and it seems particularly suitable because it even compares proofs to algorithms. Does the rest of the book relate to computer science somehow, or is it just the introduction? – Jakob Oct 21 '11 at 12:41
@Jakob: There is no difference between proofs in CS and math. The dirty secret that no one likes to admit is that the two fields overlap almost perfectly. – Charles Oct 21 '11 at 14:07

There are some books about it. How to Read and Do Proofs, by Solow, for example.

-