nculwell.github.io

Logic and Discrete Math

Logic

A nice guide to studying logic: http://www.logicmatters.net/tyl/

Philosophical logic

• Gensler, Introduction to Logic (2e, 1e)

  This is a really nice first course in logic, which covers all the core material that you’d want to see in a first course, gives a tour of major philosophical applications of logic, and also has a nice overview of less mainstream types of logics.

• Copi and Cohen. Introduction to Logic (12e, 11e)
• Hurley. A Concise Introduction to Logic (10e, 9e)

Mathematical logic

• Keisler, Kunen, Millar, Miller, Robbin, Mathematical Logic and Computability

  Free online here: https://www.math.wisc.edu/~miller/res/book.pdf.

• Enderton, A Mathematical Introduction to Logic (2e, 1e at AbeBooks)
• Chiswell and Hodges. Mathematical Logic (1e)
• Goldrei. Propositional and Predicate Calculus: A Model of Argument (1e)
• Lover. Elementary Logic: For Software Development (1e)
• Smullyan. First-order logic (Dover)
• Tarski. Introduction to logic (Dover 2e revised, 4e [with Jan Tarski])
• van Dalen, Logic and Structure (5e, 4e, 3e)
• Manin and Zilber, tr. Koblitz. A Course in Mathematical Logic for Mathematicians (2e/2010)
• Kleene. Mathematical Logic (1e)
• Kleene. Introduction to Metamathematics (1e)
• Schöning. Logic for Computer Scientists
• Robbin. Mathematical Logic: A First Course (Dover)
• Boolos, Burgess, Jeffrey. Computability and Logic (5e)
• Shapiro. Foundations without Foundationalism: A Case for Second-Order Logic (1e)
• Hedman. A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity (1e)

Modal Logic

• Girle. Modal Logics and Philosophy (2e)
• Blackburn, de Rijke, and Venema. Modal Logic (1e)
• van Benthem. Modal Logic for Open Minds (1e)
• Cocchiarella, Freund. Modal Logic: An Introduction to its Syntax and Semantics (1e)

Model Theory

• Manzano. Model Theory (1e)
• Chang and Keisler. Model Theory (3e Dover)
• Hodges. A Shorter Model Theory (1e)
• Hodges. Model Theory (1e)
• Marker. Model Theory: An Introduction (1e)

Proof Theory

• Takeuti. Proof Theory (2e Dover)

Topos Theory

• Johnstone. Topos Theory (Dover)
• Goldblatt. Topoi: The Categorial Analysis of Logic (Dover)

Type Theory

• Nederpelt and Geuvers. Type Theory and Formal Proof: An Introduction (1e)
• Hindley. Basic Simple Type Theory (1e)

Misc logic

• Goldblatt, Logics of Time and Computation (1e)
• Baier and Katoen, Principles of Model Checking (1e)
• Harel, Kozen, Tiuryn, Dynamic Logic (1e)
• Franzén, Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse (1e)

Logic course notes

• Simpson: http://www.personal.psu.edu/t20/notes/

  Mathematical Logic; Incompleteness and Undecidability; Foundations of Mathematics; Model Theory; Computability, Unsolvability, and Randomness; some “topics” courses.

• Simmons and Schalk. An introduction to lambda-calculi and arithmetic http://www.cs.man.ac.uk/~hsimmons/BOOKS/lcalculus.pdf
• Simmons. An introduction to Good old fashioned model theory (incomplete) http://www.cs.man.ac.uk/~hsimmons/BOOKS/ModelTheory.pdf
• Simmons. Basic Model Theory http://www.cs.man.ac.uk/~hsimmons/MODEL-THEORY/model-theory.html

Set Theory

• Halmos. Naive Set Theory (Martino, Springer HC [OOP])
• Pinter. Set Theory (Dover)
• Suppes. Axiomatic Set Theory (Dover)
• Enderton. Elements of Set Theory (1e)
• Goldrei. Classic Set Theory: For Guided Independent Study (1e)
• Kunen. Set Theory (1e)
• Jech. Set Theory (3e)
• Moore. Zermelo’s Axiom of Choice: Its Origins, Development, and Influence (Dover
• Jech. The Axiom of Choice (Dover)
• Cohen. Set Theory and the Continuum Hypothesis (Dover)

Category Theory

• Mac Lane. Categories for the Working Mathematician (2e)

  The classic introduction by one of the creators of category theory.

• Awodey. Category Theory (2e)

• Spivak. Category Theory for the Sciences (1e)

  Note that this is by David Spivak, not Michael Spivak of Calculus fame. A pre-publication version, before final editing and without solutions, is available online here:

  http://ocw.mit.edu/courses/mathematics/18-s996-category-theory-for-scientists-spring-2013/textbook/

• Pierce. Basic Category Theory for Computer Scientists (1e)

• Lawvere and Schanuel. Conceptual Mathematics: A First Introduction to Categories (2e)

• Simmons. An Introduction to Category Theory (1e)

Course notes

• Simmons and Schalk. Category theory in four easy movements http://www.cs.man.ac.uk/~hsimmons/BOOKS/CatTheory.pdf
• Simmons. Category Theory by Magic http://www.cs.man.ac.uk/~hsimmons/MAGIC-CATS/CourseNotes-Nov-29.pdf

Discrete Math

Introductions

Discrete math for computer science

These are generally grab-bags of topics relevant for beginning CS students: logic, proofs, number theory, boolean algebra, combinatorics, graph theory. I only list older, cheap editions. These books tend to be relatively elementary and shallow, because they are devoted to brief coverage of a large variety of topics, but on the other hand they are widely available, polished in their presentation and they have lots of exercises.

Typical topics are: logic and proof, set theory, functions, introduction to algorithms, basic number theory, mathematical induction, counting and discrete probability, other topics in combinatorics, graphs and trees, basic automata theory.

• Lehman, Leighton, Meyer. Mathematics for Computer Science (FREE Harvard CS 20 notes)
• Rosen. Discrete Mathematics and its Applications (6e, 5e, 5e solns [odd problems only]) - Probably the most popular book of this type.
• Epp. Discrete Mathematics with Applications (3e, 3e solns, 2e, ERRATA) - Noted for its clarity. Seems to be well-liked by struggling students.
• Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction (4e, 3e, 2e) - Older. Concludes with an introduction to abstract algebra with applications including cryptography.
• Hunter. Essentials Of Discrete Mathematics (2e) - Has some interesting applications outside of computer science (DNA, social networks, language, music).
• Bender and Williamson. Mathematics for Algorithm and Systems Analysis (Dover) - A somewhat less-flashy DM for computer science.

Discrete math with a different focus

• Scheinerman. Mathematics: A Discrete Introduction (3e, 2e) - Covers a similar range of topics, but is aimed more at math majors.
• Ross. Topics in Finite and Discrete Mathematics (1e Dover) - Unusual topics include finance, linear programming and statistical inference. No coverage of logic or proofs.

More advanced approaches to discrete math for computer science

• Aho and Ullman, 1994. Foundations of Computer Science: C Edition (FREE ONLINE, 1e) - Combines discrete math with programming.

• Graham, Knuth, Patashnik. Concrete Mathematics: A Foundation for Computer Science (2e) - One of the most well-loved books in math and computer science.

Combinatorics

Beginning

• Lovász, Pelikán, Vesztergombi. Discrete Mathematics: Elementary and Beyond (1e)
• Brualdi. Introductory Combinatorics (4e, 3e; 4e errata)
• Niven. The Mathematics of Choice: How to Count Without Counting (MAA 1e)
• Martin. Counting: The Art of Enumerative Combinatorics (1e)
• Chen and Koh. Principles and Techniques in Combinatorics (1e)
• Bogart. Combinatorics Through Guided Discovery
• Wilf. generatingfunctionology (2e FREE ONLINE 3e)
• Stanley. Enumerative Combinatorics (Vol I, 2e, Vol II, 1e)
• Cameron. Combinatorics: Topics, Techniques, Algorithms (1e)
• Bona. Combinatorics of Permutations (2e)
• Bona. A Walk through Combinatorics: An Introduction to Enumeration and Graph Theory (3e)
• Bona. Introduction to Enumerative and Analytic Combinatorics (2e)
• Bona. Handbook of Enumerative Combinatorics (1e)
• Lovász. Combinatorial Problems and Exercises (AMS Chelsea)
• Flajolet and Sedgewick. Analytic Combinatorics (1e)
• Stanley. Algebraic Combinatorics: Walks, Trees, Tableaux, and More (1e)
• Stanley. Catalan Numbers (1e)
• Aigner. A Course in Enumeration (1e)
• Jukna. Extremal Combinatorics: With Applications in Computer Science (2e)
• Mansour. Combinatorics of Set Partitions (1e)
• Bollobás. Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability (1e)
• Anderson. Combinatorics of Finite Sets (Dover)
• Matousek, Nešetřil, Pellegrini, eds. Geometry, Structure and Randomness in Combinatorics (1e)

Graph Theory

Introductions

• Trudeau. Introduction to Graph Theory (Dover)

• Chartrand, 1984. Introductory Graph Theory (Dover)

• Chartrand, Zhang, 2012. A First Course in Graph Theory (Dover)

  More in-depth than Chartrand’s other intro book. Includes solutions to odd-numbered exercises.

• Hartsfield and Ringel. Pearls in Graph Theory: A Comprehensive Introduction (Dover ed)

Beyond

• Diestel. Graph Theory (4e, 3e)

  Can be previewed free online. See: http://diestel-graph-theory.com/

• Bollobás. Modern Graph Theory (1e)
• Bollobás. Extremal Graph Theory (Dover)
• Bondy and Murty. Graph Theory (1e)
• Bollobás. *Random Graphs(2e)

See also: random matrix theory