Specification and Analysis of Discrete Systems: A Programmer's Perspective

This class-tested textbook provides a comprehensive and accessible introduction to discrete systems. The author uses illustrations, engaging examples, and historical remarks to make the material interesting and relevant for students. The book uses multiple notations to convey each idea, and also multiple automated tools. It also adopts a programmer's perspective, using a declarative subset of Python to emphasize the "what" and not the "how." A Jupyter notebook will accompany the book to feature code, YouTube videos, and other supplements to assist instructors and students.

Introduction. A Simple Assertion Whose Proof Isn't. Hardware and Software: Trust but Verify. Boolean Logic and Many Others that Followed. Basics of Boolean Logic. Notations used to Present Discrete Structures. Logic: Central Workhorse of Programming, Puzzles. Functional Programming in Python. Boolean Reasoning: Personality, Universality. Boolean Reasoning: Identity, Non-Universality. Efficient Boolean Function Representation through BDD. Proofs and Truths. Sets: Fundamental Data Structure of Mathematics. Predicate Logic: Universal Language for Expressing Infinite Truths. Z3Py: Verified Fun. Combinatorics: A Cornucopia of Counting. Playing Mastermind Using Z3Py. Probability: Measured Uncertainty. Conditional Probability: When “it depends”. Functions: One-to-one, Onto, and Gödel Hashes. (Binary) Relations: Partial Orders and Equivalences. 4-Color the US Map: Explicit and Implicit (BDD/SMT). Infinite Sets: Proofs via Barter and Diagonalization. Induction: Dominos tripped through Implication.