谓词逻辑速成课程

# 谓词逻辑速成课 来源：https://www.hillelwayne.com/post/predicate-logic/ 我开始撰写《程序员的逻辑学》(https://logicforprogrammers.com/)，因为当时没有适合程序员的优质逻辑学资源。如今书籍已经出版，新问题是：程序员的逻辑学仍缺乏优质的*免费*资源。因此，为了解决*这个问题*（顺便为书做点宣传），我将《程序员的逻辑学》第二章改编成了这篇博文。所有脚注均为书中没有的编辑性评论。[1](https://www.hillelwayne.com/post/predicate-logic/#fn:expectations) 请享用！ --- ## 第二章：逻辑学速成课 形式逻辑是一个非常强大的工具，但它也非常简单。在本章中，我们将阐述并解释基本概念和语法。这包括谓词、蕴含运算符、集合和集合量词。你可能已经从编程经验中熟悉了其中大部分内容！ ## 谓词 粗略地说，**谓词**是一个返回布尔值的函数。作为程序员，你可能已经编写过几十个谓词。这些都是谓词： - `Positive(x)` 在 x 大于 0 时为真。 - `IsSum(x, y, z)` 在 x 加 y 等于 z 时为真。 - `RAMAtLeast(c, r)` 在计算机 `c` 拥有至少 `r` 字节物理内存时为真。 我说“粗略地说”，是因为谓词是数学概念，而不是编程构造。程序函数需要附带一种计算答案的方法，而谓词仅仅定义了答案是什么。以 `RAMAtLeast` 为例：其软件实现取决于编程语言、操作系统，甚至可能取决于物理硬件。但谓词本身呢？如果计算机有足够内存则为真，否则为假。仅此而已。 **这意味着谓词可以比编程函数更抽象，** 表达我们甚至无法计算，或者至少尚不知道如何计算的事物。以下也都是有效的谓词： - `CanRunProgram(c)` 在计算机 `c` 有能力运行我们的程序时为真，无论“有能力”最终意味着什么。 - `RainyDayInCa(date)` 在 `date` 当天，加拿大某地下过雨时为真。 - `NotAlone()` 在外星人确实存在时为真。 另一方面，`Positive(x)` 很容易计算：只需检查 `x > 0` 即可。谓词的强大之处在于它们可以跨越抽象的全部范围。因此，让我们引入一些语法来区分**抽象谓词**和**具体谓词**。如果谓词是抽象的，我将用反引号包裹主体： `` # 具体 Positive(x) = x > 0 IsSum(x, y, z) = x + y == z # 抽象 CanRunProgram(c) = `计算机 c 能运行我们的程序` `` 这不是数学家的常见惯例，但就我们的目的而言已经足够清晰。为了将谓词与像 `add_two` 这样的“普通”函数区分开，谓词将始终使用**首字母大写**，而函数将始终使用**蛇形命名法**。 在你编写的程序中找出一些谓词。这些是抽象谓词还是具体谓词？[^exercises] **解答** 谓词通常是不改变程序或世界状态并返回布尔值的函数。我最近写的一个是 `document_has_exactly_one_foo`。无论你找到什么谓词，都应该是具体的，因为实际上不可能编写一个“抽象”谓词。不过，你可能会在设计文档中看到一两个抽象谓词。 由于谓词返回布尔值，现在是时候处理一些布尔运算了。不同的编程语言使用不同的符号表示“与”（AND）、“或”（OR，包含性）和“非”（NOT）。数学家使用 ∧、∨ 和 ¬。我*不会*使用这些，因为它们在键盘上找不到。相反，我将使用 `&&`、`||` 和 `!` 作为我们的符号。因此，`X && !Y` 表示“X 为真且 Y 为假”。[2](https://www.hillelwayne.com/post/predicate-logic/#fn:keyboard) 除了这三个常用的布尔运算符外，数学家还承认第四个：`=>`。但在我们深入其含义之前，让我们先练习一下刚刚学到的知识。 ### 实际示例 **谓词充当了我们人类语言描述系统与编程语言编码系统之间的桥梁。** 让我们回到 `CanRunProgram`。我曾经见过一个程序有如下需求： > 计算机必须有足够内存和快速 CPU，或者有好的显卡（GPU）。 我觉得这令人困惑。这句话在英语中听起来很自然，但我们可以通过逻辑形式化发现问题。我们将首先为每个子需求编写谓词，如下： `` RAM(c) = `计算机 c 有足够内存` CPU(c) = `计算机 c 有快速的 CPU` GPU(c) = `计算机 c 有好的 GPU` `` 这些谓词是抽象的，因为我们不知道它们具体意味着什么。64GB 是“足够内存”吗？32GB 呢？具体细节对我们来说并不重要，因为这些已经足以将 `CanRunProgram` 编写为具体的数学表达式。 `` CanRunProgram(c) = RAM(c) && CPU(c) || GPU(c) `` 现在问题更清楚了：`a && b || c` 应该被理解为 `(a && b) || c` 还是 `a && (b || c)`？这个谓词形式不正确，我们有两种方式使其合理： `` # 方式 1 CanRunProgram(c) = RAM(c) && (CPU(c) || GPU(c)) # 方式 2 CanRunProgram(c) = (RAM(c) && CPU(c)) || GPU(c) `` 这两种解释在英语中都说得通！但对于某些输入，它们的输出是不同的。我们可以通过列出 RAM/CPU/GPU 值的所有可能组合，并查看它们为 `CanRunProgram` 产生的结果来看到这一点。这被称为**真值表**。[3](https://www.hillelwayne.com/post/predicate-logic/#fn:OR) R（内存） C（CPU） G（GPU） **R && (C || G)** **(R && C) || G** T T T T T T T F T T F T T T F F T T **F** **T** F F T **F** **T** F T F F F F F 有两种输入组合，一种解释给出“假”，另一种给出“真”。供应商*可能*在编写需求时*意指*第一种解释，但我*读作*了第二种解释。我敢肯定我的程序在我的计算机上会运行，但它因内存不足而失败了，我认为供应商对我撒了谎。最好用数学方式表达需求！ 用形式逻辑表达属性比用非正式的英语更少歧义。出于教学目的，我们将假设预期的谓词是 `(RAM(c) && CPU(c)) || GPU(c)`。我们将在“决策表”一章中使用真值表进行案例分析。[4](https://www.hillelwayne.com/post/predicate-logic/#fn:references) 如果你在生成真值表时遇到困难，可以尝试使用真值表生成器。我在这里提供了一个简单的工具 (https://logicforprogrammers.com/truthtable)。尝试 `p || !q` 并从那里开始实验。 为 `!P && !Q` 和 `!(P || Q)` 创建真值表。 **解答** P Q **!P && !Q** **!(P || Q)** T T F F T F F F F T F F F F T T 这两者是相同的。这被称为德摩根定律。 ### 条件谓词 现在让我们对谓词做一个变体。以我们的 `CanRunProgram` 示例为例： 有些程序有原生版本和 Web 版本。原生版本使用本地计算机的资源，而 Web 版本在某处的云计算机上进行大部分处理。因此，原生版本需要一台强大的计算机，但*任何*计算机都可以运行 Web 客户端。 > 如果计算机运行的是原生版本，它必须有足够内存和快速 CPU 或好的显卡（GPU）才能使用此程序。但如果它不运行原生版本，就没问题。 为了建模，我们需要一个新的谓词 `Native(p)`。`Native` 是程序的属性，而不是计算机的属性，因此 `CanRunProgram` 则取决于两者： `` CanRunProgram(c, p) = `除非 p 是原生版本，否则为真，如果是原生版本，则为 (RAM(c) && CPU(c)) || GPU(c)` `` 我在这里使用了反引号，因为谓词的一半仍然是非正式英语。事实证明，我们已经拥有了使其具体化所需的工具。每当 `Native(p)` 为假时，`CanRunProgram(c, p)` 应自动为真：我们甚至不需要查看计算机规格。 `` CanRunProgram(c, p) = !Native(p) || ((RAM(c) && CPU(c)) || GPU(c)) `` 这是如何工作的？如果我们将右侧提取到一个新谓词中，比如 `Beefy(c)`，就更容易理解了，这样我们得到 `!Native(p) || Beefy(c)`。这是该表达式的真值表（使用 `N(p)` 表示 `Native(p)`，`B(c)` 表示 `Beefy(c)`）： N(p) B(c) **!N(p) || B(c)** T T T T F T F T T F F F 当 `Native(p)` 为假时，`!Native(p) || Beefy(c)` 为真，无论 `Beefy(c)` 的值如何。当 `Native(p)` 为真时，则表达式的值等于 `Beefy(c)` 的值。因此，我们只有在运行原生版本时才检查计算机规格，否则忽略它。 编写 `!P || Q` 来表示“仅当 `P` 为真时才检查 `Q`”的技巧在数学中极其常见。常见到数学家使用一个特殊的运算符：`=>`，或**蕴含运算符**。`P => Q`（“P 蕴含 Q”）等同于编写 `!P || Q`。以此方式表达，我们的谓词是： `` CanRunProgram(c, p) = Native(p) => (RAM(c) && CPU(c)) || GPU(c) `` `=>` 的绑定优先级低于 `&&` 和 `||`：`A && B => C` 是 `(A && B) => C`，而不是 `A && (B => C)`。 蕴含运算符非常强大，在许多不同地方都很有用，例如编写规范或建立系统模型。除此之外，我们可以用它来表示一个布尔陈述比另一个“更强”。[5](https://www.hillelwayne.com/post/predicate-logic/#fn:stronger) 例如，“此代码在传入 0 时崩溃”是比“此代码包含错误”更强的陈述。如果它在某些输入上崩溃，它肯定包含错误！但即使程序不崩溃，它也可能有错误，比如差一错误。或者，用数学方式编写： `` CrashesOnInput(code, 0) => HasBug(code) `` 蕴含也很有用，因为它是**可传递的**。如果 `P => Q` 且 `Q => R`，那么我们知道 `P => R`，无论 P、Q 和 R 实际是什么。如果 `CanRenderVideo(c) => CPU(c) && RAM(c)`，那么 `CanRenderVideo(c) => CanRunProgram(c)`。 假设我们添加两个条件，使 `CanRunProgram` 变成： `` CanRunProgram(c, p) = `除非 p 是原生版本且 Q(p) 或 R(p)，否则为真，如果是原生版本，则为 (RAM(c) && CPU(c)) || GPU(c)` `` 使用 `=>` 编写这个表达式。然后不使用 `=>` 编写这个表达式。哪个更容易阅读？ **解答** 1. `Native(p) && (Q(p) || R(p)) => (RAM(c) && CPU(c)) || GPU(c)` 2. `!(Native(p) && (Q(p) || R(p))) || ((RAM(c) && CPU(c)) || GPU(c))` 我个人发现 (1) 更容易阅读，因为我们的嵌套表达式没有那么多。 `RAM(c)` 表示“计算机 `c` 有足够内存”。将其修改为“计算机 `c` 有足够内存来运行程序 `p`”。对我们其他的谓词进行类似的更改，并编写 `CanRunProgram`。 **解答** `` CanRunProgram(c, p) = Native(p) => (RAM(c, p) && CPU(c, p)) || GPU(c, p) `` 1. 使用 `=>`，编写表达式“如果 `Native(p)` 为真则 `Web(p)` 为假，并且如果 `Web(p)` 为真则 `Native(p)` 为假”。 2. 使用 `&&`，编写表达式“`Native(p)` 和 `Web(p)` 不同时为真”。 3. 使用 `||`，编写表达式“`Native(p)` 为假或 `Web(p)` 为假”。 **解答** 1. `(Native(p) => !Web(p)) && (Web(p) => !Native(p))` 2. `!(Web(p) && Native(p))` 3. `!Native(p) || !Web(p)` 取谓词： `` IfElse(c, x, y) = (c => x) && (!c => y) `` 假设 c、x 和 y 都是布尔值。 1. `IfElse` 何时为真？何时为假？ 2. 这看起来像什么常见的代码构造？ **解答** 1. `(c => x) && (!c => y)` 等同于 `(!c || x) && (c || y)`。如果你推导各种情况，你会发现当 `c` 为真且 `x` 为真时，或者当 `c` 为假且 `y` 为真时，`IfElse` 为真。 2. 如名称所暗示，`IfElse` 在模拟一个条件语句。 ## 集合 谓词默认具有无类型的输入。在 `CanRunProgram(c)` 中，`c` 可以是一台计算机，但 `c` 也可以是一个机器人、数字 26 或字符串“数字 26”。在编程中，我们会希望给它一个类型，以明确说明只应传入计算机。像这样： `` CanRunProgram(c) = `c 是计算机` && ((RAM(c) && CPU(c)) || GPU(c)) `` 现在，即使我们将一个好显卡粘在贵宾犬身上，`CanRunProgram(poodle)` 仍然为假。 为了使“c 是计算机”这个概念在数学上可表示，数学家使用**集合**。集合是唯一值的无序集合，例如“所有计算机”、“所有小于 500KB 的网页”或“所有有效的 Java 程序字符串”。通常，我们这样书写集合的元素： `` Computer = {my_laptop, your_laptop, your_other_laptop, ... } `` 那么，“c 是计算机”等同于说“c 是集合 `Computer` 的元素”。我们将写作 `c in Computer`。 `` CanRunProgram(c) = c in Computer && ((RAM(c) && CPU(c)) || GPU(c)) `` 为了使我们的谓词定义更简洁，我将借用一种常见的编程语法，编写 `CanRunProgram(c: Computer)` 来表示“`c` 必须是 `Computer` 的一个元素”，像这样： `` CanRunProgram(c: Computer) = (RAM(c) && CPU(c)) || GPU(c) `` 这将使编写具有多个受约束参数的谓词变得更容易。 **数学家将集合视为他们可以用来构建更复杂数学概念的基石。**例如，他们可能通过将 `(a, b)` 写为 `{a, {b}}` 来用集合定义**对**，[6](https://www.hillelwayne.com/post/predicate-logic/#fn:error) 然后将**列表** `[a, b, c]` 定义为对的集合 `{(0, a), (1, b), (2, c)}`。[7](https://www.hillelwayne.com/post/predicate-logic/#fn:lists) 然后，有了基于集合的列表“抽象”实现，他们可以丢弃集合，直接使用列表。 作为程序员，我们不需要在使用列表之前编写它们的形式定义，并且更愿意使用那个更复杂的抽象。即便如此，集合仍然是一种有用的编程数据类型。我们将在下一章看到这一点。 ### 集合运算 **就像我们有数字算术和布尔算术一样，我们也有集合的算术。** 给定集合 `{A, B}` 和 `{B, C}`，我们可以做的基本操作是： 1. **合并**它们，或将它们挤压成一个大集合：`{A, B} | {B, C} == {A, B, C}` 2. **求交集**，或找到共同元素：`{A, B} & {B, C} == {B}` 3. 取**集合差**，或从一个集合中减去另一个集合：`{A, B} - {B, C} == {A}` 我们还可以测试一个集合是否是另一个集合的**子集**。`EvenIntegers` 是 `Integers` 的子集，因为 `EvenIntegers` 的每个元素也是 `Integers` 的元素。值 `2` 不是 `Integers` 的子集，但集合 `{2}` 是。子集类似于编程语言中的**子类型**。[8](https://www.hillelwayne.com/post/predicate-logic/#fn:types) 如果一种语言说“`Rectangle` 是 `Shape` 的子类型”，这意味着所有矩形的集合是所有形状的集合的子集。我们将在更广泛的契约主题中更详细地探讨子类型。 1. 使用集合 `ram`、`cpu` 和 `gpu` 来构造集合 `can_run_program`，即所有通过 `CanRunProgram(c)` 的计算机的集合。 2. 给定集合 `Child` 和 `Adult`，通过说这两个集合不重叠来表达“没有人既是儿童又是成人”的陈述。你可以使用 `{}` 表示空集。 3. 两个集合的**对称差**是恰好属于其中一个集合的所有元素的集合。例如，`{A, B}` 和 `{B, C}` 的对称差是 `{A, C}`。仅使用基本的集合运算，找出任意集合 `S` 和 `T` 的对称差。 **解答** 1. `can_run_program = (ram & cpu) | gpu` 2. `Child & Adult == {}`。另一种方式是 `Child - Adult == Child && Adult - Child == Adult`。 3. 一种方式是 `(S - T) | (T - S)`；另一种是 `(S | T) - (S & T)`。 映射和过滤集合也很有用。标准数学符号是 `{f(x) | P(x)}`，但我发现初学者会混淆哪一边是映射，哪一边是过滤。因此，在本书中，我将使用更明确的语法： 名称 语法 映射 `{x^2 for x in set}` 过滤 `{x in set where condition}`