Review: Three Views of Logic: Mathematics, Philosophy, and Computer Science

I read this book largely by accident, because I was attracted by the title. As an academic in (or rather, on the edge of) computer science, I come across logic regularly, both in teaching and research. Mathematics underpins almost everything I do, and I’m certainly interested in whether a mathematician’s view of logic differs significantly from that of a theoretical computer scientist (as a keen reader of mathematics, I’m well aware that standard mathematical practice of proof differs quite strongly from the formal approach studied in computer science, but this isn’t quite the same thing!) I once had a strong interest in philosophy, most significantly in epistemology, which is being rekindled by my involvement in education at the school level, and so combining all these factors, the title was very appealing. What I actually discovered when I started reading wasn’t exactly what I expected. But this book turns out to be an excellent, crystal clear, textbook suitable for undergraduates and those with just a limited level of mathematical maturity. The book is explicitly partitioned into three sections, but in practice I found that the first two sections, proof theory and computability theory (the “maths” and the “computer science”) were very familiar material for any computer scientist, and from my perspective there was no very clear difference in approach taken, just a difference in the range of topics covered.

Part 1, by Loveland, covers propositional and predicate logic, with a particular focus on automated proof by resolution. I found the description of resolution to be very clear, with a particular focus on the difference between resolution for propositional and predicate logic, and with one of the clearest descriptions of completeness results I’ve seen.

Part 2, by Hodel, covers computability theory. Again, the clarity is exemplary. The first chapter discusses concepts informally, the second precisely defines two machine models in a way very accessible to a computer engineer (effectively one supporting general recursion and one supporting only primitive recursion) and discusses their relative computational power. The insistence of an informal discussion first makes these distinctions come to life, and allows Hodel to frame the discussion around the Church-Turing thesis. The focus on compositionality when preserving partial recursiveness, and the emphasis on the ‘minimalisation’ operator (bounded and unbounded) was new to me, and again very clearly presented. Most introductory texts I’ve read only tend to hint at the link between Gödel’s Incompleteness Theorem and Church’s Undecidability Theorem, whereas Hodel makes this link precise and explicit in Section 6.6, Computability and the Incompleteness Theorem.

Part 3, by Sterrett, covers philosophical logic. In particular, Sterrett considers the existence of alternatives to (rather than extensions of) classical logics. She focuses on the logic of entailment aka relevance logic introduced by Anderson and Belnap, into which she goes into depth. This logic comes from rethinking the meaning ascribed to the connective, \rightarrow, logical implication. In classical logic, this is a most confusing connective (or at least was to my students when I taught an introductory undergraduate course in the subject long ago). I would give my students examples of true statements such as “George is the Pope” implies “George is Hindu” to emphasise the difference between the material implication of classical logic and our everyday use of the word. It is exactly this discrepancy addressed by Anderson and Belnap’s logic. I was least familiar with the content of this part of the book, therefore the initial sections came as something of a surprise, as I found them rather drawn out and repetitive for my taste, certainly compared to the crisp presentation in Parts 1 and 2. However, things got exciting and much more fast moving by Chapter 8, Natural Deduction, where there are clear philosophical arguments to be had on both sides. In general, I found the discussion very interesting. Clearly a major issue with the line of reasoning given by my Pope/Hindu example above is that of relevance. Relevance might be a slippery notion to formalise, but it is done so here in a conceptually simple way: “in order to derive an implication, there must be a proof of the consequent in which the antecedent was actually used to prove the consequent.” Actually making this work in practice requires a significant amount of baggage, based on tagging wffs with relevance indices, which get propagated through the rules of deduction, recalling to my mind, my limited reading on the Curry-Howard correspondence. The book finishes with a semantics of Anderson and Belnap’s logic, based on four truth values rather than the two (true/false) of classical logic.

I can’t emphasise enough how easy this book is to read compared to most I’ve read on the subject. For example, I read all of Part 1 on a single plane journey.  I will be recommending this book to any of my research students who need a basic grounding in computability or logic.

9 thoughts on “Review: Three Views of Logic: Mathematics, Philosophy, and Computer Science

  1. Nice!

    Regarding implication I use an alternative explanation to make it more intuitive, an explanation that comes from constructive / intuitionistic logic. The proposition “If George is the Pope then George is is a Hindu” is true because if I manage to construct a proof of ‘George is the Pope’ which is false it means that I am working in an inconsistent logic, in which I can prove everything, including “George is a Hindu” or “1+1=3”.

    Like

  2. Also: the reason people find an implication with a false premise counterintuitive is because they read is counterfactually, i.e. “If George were the Pope then George were a Hindu”, which, according to Kripke, means “In all possible worlds in which George is a Pope, George is a Hindu” which, assuming counterfactuals are sensible, is likely false.

    Like

    1. Thanks, Dan. Your second point – distinguishing a counterfactual reading from the definition of material implication – is the one I’ve made in the past. Though I wouldn’t have called it a counterfactual reading before now; I really wish I had been taught English grammar at school!

      Your first point is intuitively appealing, but how do we show “in an inconsistent logic I can prove anything” without having a definition of implication?

      Like

  3. A small point: the author of the Part 3 is a woman (so you might edit the occurrences of “he” to “she”).

    Like

  4. Dear Prof Constantinides,

    Thanks very much for reading our book so carefully, and for the thoughtful review. I am glad to hear you found it clear and easy to read and, even, interesting.

    I wonder if you might consider putting this review of the book up on amazon.com’s site, as a customer review. I am sure it would help others understand what the book is about and help them decide if it is the right choice for them.

    Thank you,
    S G Sterrett

    Liked by 1 person

    1. Dear Prof Sterrett,

      Thanks for your comment on my review. I very much enjoyed your book. I will put up a review on amazon.

      George

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s