Logic for Programmers

Logic for Programmers A book about math, software, and using one to fix the other. Written for the working programmer. No math background required. 这是一本关于数学、软件以及如何利用前者来优化后者的书。专为在职程序员编写，无需数学背景。

What’s this book? This is a book about designing, verifying, and reasoning about software better. And it’s about how learning a little bit of logic, the mathematics of Booleans, unlocks all sorts of cool techniques in our field. If you want to get a feel for what it’s like, try reading a sample chapter! 这本书讲什么？ 这是一本关于如何更好地设计、验证和推导软件的书。它探讨了学习一点逻辑学（布尔数学）如何能为我们这一领域解锁各种酷炫的技术。如果你想了解它的风格，可以试读一下样章！

Is this mostly theoretical or does it have practical applications, too? Everything in the book is meant to be practical. Early chapters are on topics like “simplifying conditionals” and “ensuring an API change won’t break clients”. Later chapters are on slightly more esoteric subjects, like “finding race conditions in hypothetical software designs” and “minimizing the wall clock time of a distributed task”. Not everything will be useful to everyone, but I hope everyone finds something useful! 它是纯理论的，还是有实际应用？ 书中的一切内容都旨在实用。早期章节涵盖了“简化条件判断”和“确保 API 变更不会破坏客户端”等主题。后续章节则涉及一些稍显深奥的主题，例如“在假设的软件设计中发现竞态条件”以及“最小化分布式任务的挂钟时间”。并非所有内容对每个人都有用，但我希望每个人都能从中找到有价值的东西！

Do I need to know math? Nope! You don’t need to know math besides the Boolean AND, OR, and NOT that programmers pick up through daily experience. The book covers the rest of the math you need. That said, you do need to know some programming! This book is meant for intermediate-to-advanced programmers and I assume the reader knows universal topics like loops, version control, testing, etc. Some chapters expect more specific knowledge like SQL or API design. Chapters are independent, though, so if something doesn’t fit your needs, go ahead and skip it. 我需要懂数学吗？ 不需要！除了程序员在日常工作中积累的布尔逻辑（与、或、非）之外，你不需要任何额外的数学知识。书中涵盖了你所需的其余数学内容。话虽如此，你确实需要具备一定的编程基础！本书面向中高级程序员，我假设读者已经掌握了循环、版本控制、测试等通用知识。部分章节可能需要 SQL 或 API 设计等特定知识。不过，各章节是相互独立的，如果某部分不符合你的需求，直接跳过即可。

What’s with the weird A and E in the title? Logicians use the symbols ∀ and ∃ to mean “for all” and “there exists”, respectively. For example, we could write the sentence “everybody has a favorite color” as ∀p ∈ Person: ∃c ∈ Color: IsFavoriteColor(p, c). To make learning the topics (and searching the book) easier, I use English words instead of math symbols. So the same expression would be all p in People: (some c in Color: IsFavoriteColor(p, c)). 标题中奇怪的 A 和 E 是什么意思？ 逻辑学家使用符号 ∀ 和 ∃ 分别表示“对于所有”和“存在”。例如，我们可以将“每个人都有一个最喜欢的颜色”这句话写成 ∀p ∈ Person: ∃c ∈ Color: IsFavoriteColor(p, c)。为了让学习（以及在书中搜索）更轻松，我使用英语单词代替了数学符号。因此，同样的表达式会写成 all p in People: (some c in Color: IsFavoriteColor(p, c))。

What’s in the book? Here’s a table of contents and corresponding techniques:

• A Crash Course in Logic: predicates, booleans, sets, and quantifiers
• Refactoring Code: rewrite rules
• Writing Better Tests: property testing
• Composing Code Correctly: contracts, subtyping
• Proving Code Correct: formal verification, Dafny
• Working with Data: database theory
• Decoding Decisions: decision tables
• Modeling Domains: formal specification, Alloy
• Designing Systems: temporal logic, TLA+
• Solving Math Problems: constraint and SMT solving
• Logic Programming: Prolog and answer set programming Plus some appendices on math notation, useful rewrite rules, and advanced topics in logic. All code samples are available on GitHub, along with a bunch of extra samples on the same topics that are not used in the book. 书中包含什么？ 以下是目录及对应的技术：
• 逻辑速成：谓词、布尔值、集合和量词
• 代码重构：重写规则
• 编写更好的测试：属性测试
• 正确组合代码：契约、子类型
• 证明代码正确性：形式化验证、Dafny
• 处理数据：数据库理论
• 解码决策：决策表
• 建模领域：形式化规范、Alloy
• 设计系统：时序逻辑、TLA+
• 解决数学问题：约束求解和 SMT 求解
• 逻辑编程：Prolog 和答案集编程 此外还有关于数学符号、实用重写规则以及逻辑学高级主题的附录。所有代码示例均可在 GitHub 上获取，同时还有大量书中未使用的相关主题额外示例。

How come in Python all([]) == True? That always bugged me. Python’s all function is equivalent to this: all(l) = l[0] && l[1] && l[2] ... This has a particular property: given any two lists xs and ys, we know: all(xs . ys) == all(xs) && all(ys). But that’s for any two lists, and that includes empty lists! What happens if we pick ys = []? Then xs . [] == xs, meaning: all(xs) && all([]) == all(xs . []) -> all(xs) && all([]) == all(xs). If all([]) = True, then this equation becomes all(xs) && True == all(xs), aka all(xs) == all(xs). If all([]) = False, then this becomes all(xs) && False == all(xs), which means all(xs) == False no matter what xs is. So it makes more sense for all(xs) = True, to preserve the property. We say that True is the identity of &&: p && True == p regardless of what p is. The same argument, incidentally, also explains why the sum of an empty list is 0 and the any of an empty list is False. 为什么在 Python 中 all([]) == True？ 这总是让我感到困惑。Python 的 all 函数等同于：all(l) = l[0] && l[1] && l[2] ... 它具有一个特定属性：对于任意两个列表 xs 和 ys，我们知道：all(xs . ys) == all(xs) && all(ys)。但这适用于任何两个列表，包括空列表！如果我们取 ys = [] 会怎样？那么 xs . [] == xs，意味着：all(xs) && all([]) == all(xs . []) -> all(xs) && all([]) == all(xs)。如果 all([]) = True，则该等式变为 all(xs) && True == all(xs)，即 all(xs) == all(xs)。如果 all([]) = False，则变为 all(xs) && False == all(xs)，这意味着无论 xs 是什么，all(xs) 都等于 False。因此，为了保持该属性，all([]) = True 更合理。我们称 True 为 && 的单位元：无论 p 是什么，p && True == p。顺便提一下，同样的逻辑也解释了为什么空列表的和是 0，而空列表的 any 是 False。

Who’s the author? I’m a software engineer specializing in formal methods, distributed systems, and software history. Some of my past works include Practical TLA+ and The Crossover Project. I’ve done formal verification and training for clients like NASA, Meta, Giesecke+Devrient, McKinsey & Company, Siemens AG, and Western Digital. I usually bring homemade chocolate when I speak at conferences. I also have a blog and a weekly newsletter. 作者是谁？ 我是一名专注于形式化方法、分布式系统和软件历史的软件工程师。我过去的作品包括《Practical TLA+》和《The Crossover Project》。我曾为 NASA、Meta、Giesecke+Devrient、麦肯锡、西门子和西部数据等客户提供形式化验证和培训。在会议上演讲时，我通常会带上自制的巧克力。我还有一个博客和一份每周通讯。