6
$\begingroup$

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

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.

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

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Every algorithms textbook? $\endgroup$
    – JeffE
    Commented Jul 31, 2012 at 15:33
  • $\begingroup$ @JeffE I am more interested in how to understand theorems by learning how to construct them from the syntax and fundamentals of logic up and then use that to understand other theorems. The books purely on learning theorems that don't rely on an advanced math background are better for me, e.g. "How to Prove It – A Structured Approach", but if they were then targeted toward computer science and added extra chapters related to theorems typically used in computer science, that would be great. This is what the example books on logic tend to do. I don't know if such a book exists, so I am asking. $\endgroup$
    – Guy Coder
    Commented Jul 31, 2012 at 15:50
  • 1
    $\begingroup$ I am not sure you are looking for something feasible. In order to deal with formal stuff you need mathematical background. Notation-knowledge will grow with the amount of material you read. Do you have access to a (university) library? $\endgroup$
    – Raphael
    Commented Jul 31, 2012 at 16:35
  • $\begingroup$ @Raphael Oh how I wish I did have access to a university quality library. $\endgroup$
    – Guy Coder
    Commented Jul 31, 2012 at 17:01
  • $\begingroup$ @GuyCoder: Usually they allow externals to visit and lend books (at least over here in Germany). That would, of course, only work if you live near a university. $\endgroup$
    – Raphael
    Commented Aug 4, 2012 at 8:38

6 Answers 6

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ In fact, many algorithms textbooks do not explain the logics/maths behind the proof syntax they use (point in case: Landau notation abuse). If you really want to get the formal object "proof", you have to study (mathematical) logics. $\endgroup$
    – Raphael
    Commented Jul 31, 2012 at 16:37
  • 2
    $\begingroup$ "Everyone seems to take it for granted that if you do math you know theorems" -- yes, because it's true! $\endgroup$
    – Sasho Nikolov
    Commented Jul 31, 2012 at 18:38
  • 3
    $\begingroup$ Careful, @SashoNikolov! $\endgroup$
    – JeffE
    Commented Jul 31, 2012 at 20:52
  • 3
    $\begingroup$ @SashoNikolov In my experience, many mathematicians do not understand the formal concept of a proof, because they never see it. Proofs in mathematics are usually fairly high-level with liberal user of "clearly", "obviously", "by simple application of [thing]" and so on. The same is true for many "track A" TCSists. "Track B" TCSists tend to have better grasp on logics. Lamport's How to Write a Proof is an interesting read in that regard. $\endgroup$
    – Raphael
    Commented Aug 1, 2012 at 10:15
  • 1
    $\begingroup$ Really? Anyone I've met has had the minimum exposure to formal logic to know that human proofs are not formal proofs. The way I parse OP's questions is that he would like to work in formal verification or some such endeavor but cannot understand basic proof techniques. Notice he references "How to prove it", which is an intro to basic mathematical reasoning, as an example of the kind of book he'd like to have $\endgroup$
    – Sasho Nikolov
    Commented Aug 2, 2012 at 2:52
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I took a look at "Algorithm Design" using Amazon's Look Inside feature and could not find a mention of theorems. Sorry, this is not what I seek. Thanks for the effort. $\endgroup$
    – Guy Coder
    Commented Jul 31, 2012 at 16:53
  • 5
    $\begingroup$ There's at least one theorem (and at least one proof) on every other page of Kleinberg and Tardos. Theorems are not an explicit chapter topic for precisely the same reason that English grammar is not a chapter topic. $\endgroup$
    – JeffE
    Commented Jul 31, 2012 at 20:54
4
$\begingroup$

(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"

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the response. I own, and have been reading "How To Prove It"; it is a great book (see comments above). I don't have "How to Think Like a Mathematician" but it is on my huge Amazon wish list. $\endgroup$
    – Guy Coder
    Commented Aug 8, 2012 at 12:37
  • 2
    $\begingroup$ In his book “How to solve It” George Pólya explains his approach for solving mathematical problems. He describes how to attack a problem and arrive at an answer that will then become a proof. $\endgroup$
    – uli
    Commented Aug 8, 2012 at 15:50
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Maybe Concrete Mathematics is a good choice; it teaches you maths useful for CS along the way. $\endgroup$
    – Raphael
    Commented Aug 1, 2012 at 10:11
  • $\begingroup$ Concrete Mathematics is an interesting choice because of its highly unusual style. It may be more valuable because it presents formal mathematics using intuition and examples, but it also may be less useful because it doesn't have as much formalism. I personally found the presentation method confusing, but that's because I'm used to a formal presentation. Someone with a different background might find it more useful for exactly that reason. In any case it's certainly a math book with a great deal of CS application. $\endgroup$
    – SamM
    Commented Aug 3, 2012 at 16:02
  • $\begingroup$ I opened a random page in Concrete Mathematics and was drowned in formulae. What do you mean exactly by "[not much] formalism"? I would agree that GKP present the material conversationally, but I have always perceived them as quite rigorous. $\endgroup$
    – Raphael
    Commented Aug 4, 2012 at 9:48
  • $\begingroup$ Well of course it's a matter of opinion, but the book seems more willing to present ideas on a large scale and then talk some about the formalism later, rather than follow Theorem(lemma lemma)->Theorem(lemma)->Theorem, etc, the truth of each necessary for the next, as a book on (say) analysis might. I recall in particular that they presented their method of solving recurrences in a "top-down approach" where they showed several specific examples, then talked about why it works and how to generalize it to other cases. It's not hand-wavy but it's not rigidly structured either. $\endgroup$
    – SamM
    Commented Aug 4, 2012 at 17:38
  • 1
    $\begingroup$ I see what you mean now. The (Definition-Theorem-Proof)+ scheme has its use, but it is imho often inaccessible, especially for beginners -- ideas are more important (because they stick!), as long as the formal detail is there. It's a different philosophy, really: teaching vs telling. $\endgroup$
    – Raphael
    Commented Aug 5, 2012 at 0:38
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Link seems dead. $\endgroup$
    – zkutch
    Commented Aug 6, 2022 at 13:17
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ First link answers forbidden. $\endgroup$
    – zkutch
    Commented Aug 6, 2022 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.