L03b-2 可满足、有效与等价:数真值表里有几行为真
从零讲可满足、不可满足、有效三类句子,用岛民另外两句话演示 3 个模型和 0 个模型,再用整列对比讲等价、逆否和转 CNF 要用的等价律。
一句话版
把一个句子的真值表列完,数一数有几行为真:一行都没有叫不可满足,至少一行叫可满足,每行都真叫有效。两个句子的真值列逐行相同,就叫等价。
上一页 L03b-1 教了怎么一行一行算真值。这一页只多做一个动作:算完以后数行,再拿两列对比。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 可满足 | satisfiable | 至少有一个解释让它为真 |
| 不可满足 | unsatisfiable | 没有任何解释能让它为真,永远为假 |
| 有效 / 重言式 | valid / tautology | 每个解释下都为真,永远为真 |
| 等价 ≡ | equivalence | 两个句子在每个解释下真值都一样 |
| 逆否 | contraposition | α ⇒ β 改写成 ¬β ⇒ ¬α,和原句等价 |
| 蕴含 ⊨ | entailment,读「推出」 | KB ⊨ Q:KB 为真的每一行,Q 也为真 |
一个类比:同一份问卷,看有几种答法能过关
把一个句子想成一道门禁规则,把每个解释想成一位来访者手里的一组答案。真值表就是让所有可能的来访者轮流试一遍。
有的规则谁来都放行,比如「你今天下雨或者没下雨」,这是有效。有的规则谁来都拒绝,比如「你今天既下雨又没下雨」,这是不可满足。大多数规则只放行一部分人,这些都是可满足。
两条规则是否等价,也不看它们的措辞,看放行名单:每一位来访者在两条规则下的结果都一样,两条规则就等价。只要有一个人在一条规则下过、在另一条下不过,就不等价。
类比在哪里失效:
- 真实门禁可以改规则、可以通融,逻辑句子的真值表一旦定了就不会变。
- 来访者的数量是固定的 2ⁿ 个,n 个原子就有这么多组答案,一个都不能漏。
从零讲起
1. 可满足、不可满足、有效:按模型个数分三类
它解决什么问题
上一页的岛民第一句只剩一个模型,结论唯一。可另外两句话列完表,一句剩三行,一句一行都不剩。需要几个词把这几种情况说清楚,后面的归结法也要靠其中一个词来判定证明成功。
从哪来(补充)
「我是骗子」这类句子有很长的历史。最早的版本一般归于公元前 4 世纪的希腊哲学家 Eubulides of Miletus,叫说谎者悖论:如果说话的人在说真话,那他是骗子;如果他在说假话,那他又说对了。岛民规则下这句话为什么说不出口,下面的第四行会算给你看。
直觉
模型就是真值表里整句为 T 的那些行。数行数,就能分类:
- 不可满足:0 行为真。
- 可满足:至少 1 行为真。
- 有效:全部 2ⁿ 行都为真。
有效句一定可满足,所以有效是可满足里面的一个小圈;不可满足是可满足的补集。三者不是并列的三类,是「两分加一个子集」:任何句子要么可满足要么不可满足,可满足的里面再挑出永远为真的那些。
一步一步看
目标:在同一张两原子真值表上数四个句子为真的行,看模型个数怎样把它们分成有效、可满足、不可满足。
把四个句子放在同一张两原子真值表上,逐个数为 T 的行。第一个是 AL ∨ ¬AL,后三个是岛民 A 可能说的三句话,按上一页的方法写成两条蕴含:
-
AL ∨ ¬AL:AL 不管真假,两边总有一边为真,四行全 T,有效。
-
「At least one of us is a liar」:只有 AL=F、BL=T 那行为真,1 个模型,可满足且结论唯一。
-
「None of us is a liar」:只有 AL=F、BL=T 那行为假,3 个模型,可满足但结论很弱。
-
「I’m a liar」:四行全 F,0 个模型,不可满足。
怎么判断
拿到一个句子,先数原子个数 n,再列 2ⁿ 行,逐行算整句,最后数 T 的个数。
意思是:分类只看模型数,和句子长短、符号多少都无关。0 个是不可满足,等于 2ⁿ 是有效,其余都只是可满足。
岛民三句话正好落在三个位置。第一句 1 个模型,信息量最大;第二句 3 个模型,只排除了一种情况;第三句 0 个模型,在岛规下根本不可能被说出来。
常见误解
以为可满足和有效是并列的两类
有效句每一行都为真,当然至少有一行为真,所以有效句全部属于可满足。可满足和不可满足才是互补的两类。
以为「I'm a liar」是「无法判断」
它在这个形式化下 0 个模型,是确定的不可满足。含义是岛上的人不可能说出这句话,如果你真听到了,说明「每人要么全真要么全假」这条前提有问题。
试一下
P ∧ ¬P、P ∨ ¬P、P ⇒ P 分别是哪一类?
P ∧ ¬P:P 真时 ¬P 假,P 假时 P 假,两行都 F,不可满足。P ∨ ¬P:两行都 T,有效。P ⇒ P:P 真时 T ⇒ T,P 假时空真,两行都 T,有效。
2. 等价:两列真值逐行相同
它解决什么问题
同一个意思可以写成很多种式子。后面转 CNF 时要把式子一步步改写,每一步都必须保证意思不变。等价就是「意思不变」的精确说法,等价律就是一张允许使用的改写清单。
从哪来(补充)
清单里最常用的两条叫 de Morgan 律,名字来自英国数学家 Augustus De Morgan(1806–1871),他把这两条写进了形式逻辑。规律本身更早,Aristotle 已经知道,14 世纪的 William of Ockham 也用文字写过。
出处:Wikipedia: De Morgan’s laws
直觉
两个句子等价,要求在每一个解释下真值都相同。只看一两行对得上不算,必须整列对齐。
判断方法很机械:把两个句子放在同一张真值表里,各算一列,逐行比。全对上就等价;有一行不同就不等价,那一行就是反例。
一步一步看
目标:把 α ⇒ β 和四个候选句逐列对照,看逆否和 ¬α ∨ β 与原句等价,逆命题和否命题不等价。
拿 α ⇒ β 当原句,和四个候选句逐列对比:
-
列出 α、β 的四种组合,算出 α ⇒ β:只有 α=T、β=F 那行为 F。
-
¬α ∨ β:同样只在 α=T、β=F 那行为 F,四行全对上,等价。
-
逆否 ¬β ⇒ ¬α:前真后假只发生在 ¬β=T、¬α=F,也就是 α=T、β=F,四行全对上,等价。
-
逆命题 β ⇒ α:在 α=F、β=T 那行为 F,和原句不同,不等价。
-
否命题 ¬α ⇒ ¬β:同样在 α=F、β=T 那行为 F,不等价。
怎么判断
后面真正要用的等价律只有下面几条,课件用红框圈出:
| 等价式 | 名称 | 后面用在哪 |
|---|---|---|
| (α ⇒ β) ≡ (¬β ⇒ ¬α) | contraposition(逆否) | 选择题干扰项 |
| (α ⇒ β) ≡ (¬α ∨ β) | implication elimination | 转 CNF 第二步 |
| (α ⇔ β) ≡ ((α ⇒ β) ∧ (β ⇒ α)) | biconditional elimination | 转 CNF 第一步 |
| ¬(α ∧ β) ≡ (¬α ∨ ¬β) | de Morgan | 转 CNF 第三步 |
| ¬(α ∨ β) ≡ (¬α ∧ ¬β) | de Morgan | 转 CNF 第三步 |
| (α ∨ (β ∧ γ)) ≡ ((α ∨ β) ∧ (α ∨ γ)) | distributivity of ∨ over ∧ | 转 CNF 第四步 |
| (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) | distributivity of ∧ over ∨ | 转 DNF,本讲不用 |
| α ∨ (α ∧ β) ≡ α | absorption(吸收律) | 化简 |
意思是:每一条都能用上面的整列对比法自己验证,背不下来时现场列表比一比就行。两条分配律方向相反,转 CNF 要的是把 ∨ 分配进 ∧ 的那条,目标是「合取套析取」。
常见误解
以为逆命题和原命题等价
「下雨 ⇒ 地湿」为真,不代表「地湿 ⇒ 下雨」为真,洒水车也能让地湿。只有逆否「地不湿 ⇒ 没下雨」和原句等价。
以为 ¬(α ∧ β) 等于 ¬α ∧ ¬β
把 ¬ 推进括号时,∧ 要换成 ∨。¬(α ∧ β) 说的是「两个不全真」,¬α ∧ ¬β 说的是「两个全假」,前者在 α=T、β=F 时为真,后者为假。
试一下
用整列对比判断:¬(P ∨ Q) 和 ¬P ∧ ¬Q 等价吗?
四行逐个算。P、Q 全真:左边 ¬T = F,右边 F ∧ F = F。P 真 Q 假:左 F,右 F ∧ T = F。P 假 Q 真:左 F,右 T ∧ F = F。全假:左 ¬F = T,右 T ∧ T = T。四行全对上,等价,这就是第二条 de Morgan 律。
3. 有效和不可满足可以互换:归结法的底层依据
它解决什么问题
后半讲的归结法只会做一件事:证明某个集合不可满足。可我们想证的是「KB 能推出 Q」。需要一座桥,把「推出」换成「不可满足」。
直觉
α 永远为真,等于 ¬α 永远为假。所以 α 有效 ⟺ ¬α 不可满足,两个说法是同一件事从两头看。
「KB 推出 Q」的意思是:真值表里 KB 为真的每一行,Q 也为真。换个说法,找不到一行让 KB 为真而 Q 为假。「KB 为真而 Q 为假」写成式子就是 KB ∧ ¬Q,找不到这样的行就是它不可满足。
一步一步看
目标:用 KB = (P ⇒ Q) ∧ P 列一张表,看「KB 推出 Q」和「KB ∧ ¬Q 不可满足」怎样给出同一个结论。
用一个最小的 KB 走一遍:KB = (P ⇒ Q) ∧ P,要证 KB ⊨ Q。
- 列出 P、Q 的四种组合。
- 逐行算 KB:只有 P=T、Q=T 那行为 T。
- 看 KB 为真的行里 Q 是否都为真:唯一那行 Q=T,所以 KB ⊨ Q。
- 换成另一个说法:逐行算 KB ∧ ¬Q,四行全 F,不可满足。
| P | Q | P ⇒ Q | KB = (P ⇒ Q) ∧ P | ¬Q | KB ∧ ¬Q |
|---|---|---|---|---|---|
| T | T | T | T | F | F |
| T | F | F | F | T | F |
| F | T | T | F | F | F |
| F | F | T | F | T | F |
两种看法给出同一个结论。第 3 步要盯着 KB 为真的行看,第 4 步只要看最后一列是不是全 F。
怎么判断
想证 KB ⊨ Q,有两条路:枚举真值表,或者证明 KB ∧ ¬Q 不可满足。
意思是:后半讲的归结法走的是第二条路,先把目标取反放进集合,再想办法推出矛盾。推出矛盾,就说明 KB ∧ ¬Q 一行模型都没有,Q 得证。
常见误解
以为证 KB ⊨ Q 要证 KB ∧ Q 可满足
KB ∧ Q 可满足只说明「KB 和 Q 可以同时为真」,不排除还有 KB 为真而 Q 为假的行。要的是后者一行都没有,所以看的是 KB ∧ ¬Q。
试一下
KB = P ∨ Q,KB ⊨ P 成立吗?用 KB ∧ ¬P 判断。
KB ∧ ¬P 在 P=F、Q=T 时为 (F ∨ T) ∧ T = T,有模型,可满足。所以 KB ⊭ P:只知道 P 或 Q 至少一个为真,推不出 P 一定为真。
把它们串起来
这一页所有判断都建立在同一个动作上:把真值表列完,再数行或比列。
数行得到三类句子。0 行为真是不可满足,全部为真是有效,其余是可满足。岛民的三句话把三种情况各演示了一遍:第一句锁定答案,第二句只排除一种组合,第三句根本说不出口。
比列得到等价。两个句子每一行都对上才算等价,一行不对就有反例。逆否能过,逆命题和否命题过不了。红框里那几条等价律,是后面转 CNF 时允许做的改写。
两件事最后在一个地方汇合。α 有效等于 ¬α 不可满足,于是「KB 推出 Q」可以换成「KB ∧ ¬Q 不可满足」。这条换法就是归结法的出发点。
问题在于真值表的行数是 2ⁿ。原子一多,数行和比列都做不动。下一页开始换路线,用推理规则只碰和目标有关的句子。
课件里的坑
- [课件留白] 岛民另外两句话课件只出题不给答案;答案是「None of us is a liar」3 个模型、「I’m a liar」0 个模型(p.16)
- [课件没写] 「α 有效 ⟺ ¬α 不可满足」课件这里没写,后面归结法却直接拿它当依据(p.17、p.39)
- [易混] 两条分配律方向相反,转 CNF 用的是 ∨ 对 ∧ 的那条;∧ 对 ∨ 的那条是转 DNF 用的(p.18)
- [易错] 逆否才等价,逆命题和否命题都是标准干扰项(p.18)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写三类句子的模型数和文氏图的嵌套关系;再把「None of us is a liar」从翻译到数模型完整做一遍;最后默写红框里的等价律,挑两条用真值表验证。
必背
- satisfiable 至少 1 个模型,unsatisfiable 0 个模型,valid 全部 2ⁿ 个解释都是模型;Valid ⊂ Satisfiable
- α 有效 ⟺ ¬α 不可满足;归结法证 KB ⊨ Q,就是证 KB ∧ ¬Q 不可满足
- 两个句子等价 = 在每一个解释下真值都相同,只要有一行不同就不等价
- α ⇒ β 只和逆否 ¬β ⇒ ¬α 等价;逆命题 β ⇒ α 和否命题 ¬α ⇒ ¬β 都不等价于原命题
- 岛民三句话的模型数是 1 / 3 / 0:「None of us is a liar」只能推出 AL ∨ ¬BL,「I’m a liar」不可满足
- 转 CNF 用到的等价律:biconditional elimination、implication elimination、两条 de Morgan、双重否定、∨ 对 ∧ 的分配律
课件例题
例 1(课件 p.16):岛民 A 说「None of us is a liar」,几个模型?结论是什么?
见下方完整例题。
例 2(课件 p.16):岛民 A 说「I’m a liar」,几个模型?
题面:岛规不变,A 说「I’m a liar」。形式化,判断模型个数。
提示
A 的话就是 AL。BL 不出现,只需看 AL 的两种取值。
解答
整句 (AL ⇒ ¬AL) ∧ (¬AL ⇒ AL)。AL=T:第一项 T ⇒ F = F,整句 F。AL=F:第二项 T ⇒ F = F,整句 F。
0 个模型,不可满足,这就是说谎者悖论。岛上的人不可能说出这句话。BL 在式子里不出现,取值无关。
例 3(课件 p.18):下面哪个和 α ⇒ β 等价:β ⇒ α、¬α ⇒ ¬β、¬β ⇒ ¬α?
题面:从三个候选里选出和原句等价的那个,并说明另外两个为什么不等价。
提示
只看 α=F、β=T 这一行就够分辨。
解答
只有逆否 ¬β ⇒ ¬α 等价。α=F、β=T 时原句空真为 T;逆命题 β ⇒ α 是 T ⇒ F = F;否命题 ¬α ⇒ ¬β 也是 T ⇒ F = F。逆否在这一行是 F ⇒ T = T,其余三行也和原句一致。
完整例题
题面(课件 p.6、p.16):岛上每个人要么永远说真话,要么永远说假话。A 说「None of us is a liar」。有几个模型?结论怎么描述?
约定:AL = A is a liar,BL = B is a liar。
解法:
- 翻译 A 的话。我们都不是骗子 = ¬AL ∧ ¬BL。
- 套岛规,写两条蕴含。A 是骗子则话为假:AL ⇒ ¬(¬AL ∧ ¬BL);A 不是骗子则话为真:¬AL ⇒ (¬AL ∧ ¬BL)。
- 合起来:(AL ⇒ ¬(¬AL ∧ ¬BL)) ∧ (¬AL ⇒ (¬AL ∧ ¬BL))。
- 列真值表:
| AL | BL | 第一项 | 第二项 | 整句 |
|---|---|---|---|---|
| T | T | T ⇒ ¬(F∧F) = T ⇒ T = T | 前件 F,空真 T | T |
| T | F | T ⇒ ¬(F∧T) = T ⇒ T = T | 前件 F,空真 T | T |
| F | T | 前件 F,空真 T | T ⇒ (T∧F) = T ⇒ F = F | F |
| F | F | 前件 F,空真 T | T ⇒ (T∧T) = T ⇒ T = T | T |
- 数模型。三行为真,3 个模型,可满足。
- 描述结论。只有被排除的那一行能确定:不可能是「A 说真话而 B 是骗子」,即 ¬(¬AL ∧ BL),等价于 AL ∨ ¬BL。
- 直觉验算。A 说真话,则两人都不是骗子,对应 F,F 行;A 是骗子,则他的话为假,至少一人是骗子,AL=T 已满足,B 任意,对应 T,T 和 T,F 两行。
要点:模型越多,结论越弱。三个模型时只能写出「被排除的那种情况不成立」。
答题格式:原子定义 → 整句式子 → 四行真值表(每项写出计算)→ 模型数 → 结论写成一个式子并附一句白话。
变式题(先自己做)
(1) 改编自课件 p.18:用真值表证明 (P ⇒ Q) ≡ (¬Q ⇒ ¬P),并给出说明 (Q ⇒ P) 不与之等价的那一行。 (2) 改编自课件 p.17:判断 P ⇒ (Q ⇒ P) 属于哪一类,写出模型数。 (3) 改编自课件 p.16:岛民 A 说「B is not a liar」(B 不是骗子)。写出整句并数模型。
提示
(1) 四行各算三列。(2) 只有 P=T 且 Q ⇒ P 为假时整句才为假,看这种情况能不能发生。(3) A 的话是 ¬BL,照样写两条蕴含。
判分点与答案(非官方评分标准)
判分点:① (1) 四行都要列,指出反例行;② (2) 分类和模型数都要写;③ (3) 两条蕴含都要写,结论写成式子。
(1)
| P | Q | P ⇒ Q | ¬Q ⇒ ¬P | Q ⇒ P |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | T | T |
前两列四行相同,等价。P=F、Q=T 那行 Q ⇒ P 为 F,和原句不同,不等价。
(2) 整句为假需要 P=T 且 Q ⇒ P 为假,而 Q ⇒ P 为假需要 P=F,矛盾。所以四行全 T,有效,4 个模型。
(3) 整句 (AL ⇒ BL) ∧ (¬AL ⇒ ¬BL),等价于 AL ⇔ BL。T,T 行与 F,F 行为真,其余为假,2 个模型。结论:A、B 同类,要么都是骗子要么都说真话,分不出是哪种。
闪卡自测
1. 三类句子各对应几个模型?
satisfiable 至少 1 个,unsatisfiable 0 个,valid 全部 2ⁿ 个(p.17)。
2. 文氏图里三者是什么关系?
Valid ⊂ Satisfiable;Unsatisfiable 是 Satisfiable 的补集,在它的圈外(p.17)。
3. 岛民三句话分别有几个模型?
「At least one of us is a liar」1 个,「None of us is a liar」3 个,「I’m a liar」0 个(p.15、p.16)。
4. 等价的定义是什么?
两个句子在每一个解释下真值都相同(p.18)。
5. α ⇒ β 的逆否、逆命题、否命题,哪个等价?
只有逆否 ¬β ⇒ ¬α 等价;逆命题 β ⇒ α、否命题 ¬α ⇒ ¬β 都不等价(p.18)。
6. 为什么说「α 有效 ⟺ ¬α 不可满足」是归结法的依据?
KB ⊨ Q 等价于 KB ∧ ¬Q 不可满足,归结法就是把 ¬Q 放进集合、推出空子句来证明这一点(p.17、p.39)。
下一讲
真值表的行数随原子个数翻倍,下一页换成推理规则路线,先讲 Horn 子句和数据驱动的前向链接。见 L03b-3。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。