I am looking for a book that deals with advanced topics in propositional logic.

Question

Many logic books deal only a little with propositional logic. However I think that some advanced topics, such as definability, decidability and so on, can be discussed in the propositional logic. Please let me know if there is any book or reference that deals with advanced topics in propositional logic.

Answer 1

I can't resist opening with a reference to the veritable tome which is Lloyd Humberstone's The connectives. It's $1512$ pages long and doubles as submarine ballast.

It's a truly wonderful book; see this review.

---

OK, now let's be a bit more realistic. Classical propositional logic is indeed quite simple (e.g. decidable) and limited in expressive scope. It becomes interesting when we change our perspective, or refine our analysis, in some way. Here are a few ways that might happen:

• Varieties of propositional logic. Classical propositional logic isn't the only propositional game in town. There are many-valued, intuitionistic, relevant (or relevance), modal, linear, and many other kinds of propositional logics as well. For the intuitionistic and modal sides I strongly recommend the book Modal logic by Chagrov and Zakharyaschev as an advanced text (despite the name it also treats intuitionistic logics); at a more elementary level, I recommend van Benthem's Modal logic for open minds for modal logic (I don't know a good elementary introductory intuitionism text off-hand, my favorites are a bit technical). For many-valued logic I recommend Malinowski's book. I also recommend Mints on intuitionistic logic, but again that's a bit advanced.

  • Incidentally, this is also the context where Humber.'s Stone lives.

• Complexity considerations. Decidability/undecidability is a very coarse dividing line. When something's decidable that's not the end of the story: we can also talk about efficient decidability, that is, complexity theory. For example, telling whether a propositional sentence is a tautology is the standard example of an NP-complete problem. So there's a lot of interesting work on how difficult it is to tell whether a propositional sentence has a given property. Relatedly, there's a lot of interesting work on the lengths of propositional proofs.

As for definability, here we have to stretch a bit. Propositional logic talks only about "black-box properties," and can't refer to objects within a system; thus, it has no real notion of "definability" in the sense of e.g. first-order logic. In the context of modal propositional logic, we can talk about the definability of properties of frames; in many-valued contexts we can talk about what operations on truth values are expressible in a given system. But I'm not familiar enough with this side of things to give a good reference.

---

EDIT: I forgot to mention this, but the "varieties" bulletpoint above has another aspect: the study of "general propositional logics." A large (the vast majority?) of this consists of algebraic logic (which also studies non-propositional logics); this builds on the "propositional logic = Boolean algebra" observation. A wonderfully lucid text on the general study of propositional logics is Blok and Pigozzi's Algebraizable logics; the later text Protoalgebraic logics by Czelakowski is significantly more difficult, but also quite interesting.