Looking for books on creating and understanding theorems targeted at Computer Science

Question

In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g.

• Logic in Computer Science: Modelling and Reasoning about Systems
• Mathematical Logic for Computer Science
• Computability and Logic
• Handbook of Practical Logic and Automated Reasoning

With regards to books on understating theorems targeted at Computer Science I find only one that may fit. As I don't have the book I can't say for sure.

• Handbook of Logic and Proof Techniques for Computer Science

Are there any books for understating theorems targeted at Computer Science? In other words are there books for understating syntax, semantics and construction of theorems that don't rely on a heavy math background and that give examples more from the world of computer science and explain in a style more natural to a person in computer science.

EDIT

After seeking more on this topic I have come upon the phrases "informal mathematics" and "mathematical discourse" which are starting to turn up useful info from Google. In particular the following: Understanding Informal Mathematical Discourse found at Understanding Informal Mathematical Proofs

Answer 1

What do you expect from such a book? The comment by JeffE is a good one: sensible textbooks do this. Sorry for this is not a book recommendation, but merely a different way of thinking. Coming up with just the right properties, invariants and theorems is hard. It requires time, insight and experience. Not everything can be learned from a book.

Why not start with something simple and try to discover those useful theorems yourself? Math is a necessary tool for expressing yourself accurately. You don't necessarily need it right away though. Start with something simple, say your favorite sorting algorithm. Without writing any math if you don't want to, think about why and how the algorithm works.

Maybe with some thinking you'll convince yourself why it works and what the right invariant and properties could look like. If you already have some experience with program verification as you say, try to prove the program is correct. If you get totally stuck, then go to a textbook or a paper and see how it can be done. In some cases, you might even discover something new and exciting the author of the algorithm hasn't considered.

Answer 2

Algorithm Design, by John Kleinberg and Eva Tardos looks like it may be what you want. Here's the description on Amazon:

Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

However, since the fields of computer science and mathematics are so closely related, you really should take the time to understand the math side of things. This looks like it could be a good starting point though

Answer 3

(in addition to all the great books that others have recommended)

For proofs, hands down:

How to Prove it: A Structured Approach by Daniel Velleman.

It has the best paced and detailed introduction into proving techniques. I read many books on the subject of proofs, but this one helped me really get the hang of it.

More introductory reading would be "How to think like Mathematician"

Answer 4

I personally didn't understand how to construct theorems and proofs at all until I took a proof-based calculus course my first year of college. I don't think much of it applies directly to computer science but the method of thinking has helped me along greatly.

You may have more success looking at math books rather than computer science books. Most theoretical computer science books I've seen are either fairly informal or highly technical. Someone without a good math background won't learn much about formal proofs from either. There may be some good options for you in CS, but if you're still unsatisfied, see if there are math books that are known to be particularly good at showing how to state theorems and proofs. Especially if you can get one in something like Discrete Math or Number Theory, which you'll find at least some applications for in CS. (Some Discrete Math books have chapters on theorems and proofs which you may find useful).

The other answers allude to it a bit, but to be clear: there is absolutely no substitute for experience when it comes to clearly and formally writing theorems and proofs. Whether you get it from a class, a math book, a CS book, or a book about theorems in particular is up to you, but at the end of the day reading and writing them is the only way to learn.

Answer 5

The more advanced an algorithm is, the heavier the required math will be. The field of (designing and analyzing) algorithms is a mathematical field. The algorithms are based on mathematical theorems and concepts, you cannot understand an algorithm without understanding the mathematical bases of the algorithm.

If you are looking for books on informal reasoning there are quite a few, I don't have any favorite ones so I will leave the book recommendation part of our question to others. You can also have a look at the lecture notes from our CSC165: Mathematical Expression and Reasoning for Computer Science.

Answer 6

try this comprehensive/outstanding new free online ref of over 875 pgs. Mathematics for Computer Science by Lehman, Leighton, Meyer based on MIT class 6.042