Further Reading: Propositional Logic

Annotated pointers for going deeper. Start with the core textbook sections to reinforce the chapter, then branch toward whatever pulls you: the algebra of logic, the hardware connection, or the satisfiability rabbit hole that ends the chapter. All sources below are Tier 1 (canonical, verifiable) or Tier 2 (a real, named result whose exact publication we do not pin down here).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §1.1–1.3 The market-standard treatment of propositions, connectives, truth tables, and logical equivalences, with a large, well-graded exercise bank. If you want more drill problems than this chapter provides — especially translation and equivalence proofs — this is the first place to go.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the propositions chapter Freely available. The most CS-flavored presentation in print: propositions are introduced hand in hand with proofs and with the digital-logic and verification applications that motivate this whole chapter. Its tone — logic as the working grammar of computer science — is the spirit we wrote in.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the logic chapter Freely available. A gentle, well-explained open textbook. Good if you want a second, slower explanation of truth tables, tautologies, and equivalences before tackling the harder exercises here.

Epp, Discrete Mathematics with Applications (5th ed.), Chapter 2 Especially strong on the language side: translating English (including the tricky "only if," "unless," and "necessary/sufficient" phrasings) into symbols, and on the converse/contrapositive distinction that trips up so many readers. Read it alongside §1.2 and §1.4.

On the algebra of logic and Boolean algebra

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), notation and early chapters Less about propositional logic per se and more about the style of manipulating formal expressions by rule, citing a law per line — the habit you practiced when proving equivalences algebraically in §1.4. Denser, but it rewards the effort.

Knuth, The Art of Computer Programming, Volume 1, §1.3 (Boolean basics) and Volume 4A (Boolean functions) The deep reference on Boolean functions, functional completeness (the NAND result from the Deep Dive), and the combinatorics of the $2^{2^n}$ Boolean functions of $n$ variables. Reach for it after you have done Exercises 1.25–1.26 and want to see how far the rabbit hole goes.

On the satisfiability connection (the §1.6 thread)

Sipser, Introduction to the Theory of Computation (3rd ed.), the NP-completeness chapter The clean, standard account of P, NP, and the Cook–Levin theorem that makes SAT the emblem of "easy to check, hard to find." This is the book the chapter is pointing at when it says "we pick the thread back up in Chapter 37." Skim it now for the lay of the land; read it properly later.

Cook, "The Complexity of Theorem-Proving Procedures" (1971) — Tier 2. The original paper introducing NP-completeness and proving SAT is NP-complete (the Cook–Levin theorem). Historically pivotal and surprisingly readable in its framing; consult it once Chapter 37 has given you the vocabulary, for the pleasure of seeing where the idea began.

On logic in real systems

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.) Not a logic text, but the place to see Boolean reasoning put to work inside algorithms and their correctness arguments — the practical destination of the "language of CS" theme. A standard companion for the whole book.

Suggested order

  1. Re-read §§1.2–1.4 here, then work the Rosen §1.1–1.3 exercises for drill (especially translation and equivalence proofs).
  2. Read the MIT 6.042 propositions chapter for the CS framing and the link to verification and circuits.
  3. If the converse/contrapositive or English-translation pitfalls still bite, read Epp Chapter 2.
  4. After the chapter's Deep Dive (Exercises 1.25–1.26 and Case Study 2), skim Sipser's NP-completeness chapter for a preview of where SAT is headed — then return to it in full at Chapter 37.
  5. Save Knuth Vol. 4A (Boolean functions) and the Cook 1971 paper for when your curiosity about functional completeness and SAT outgrows the chapter.