逻辑与证明(3) 南京大学计算机系离散数学教学组

回顾 命题逻辑 逻辑等价 命题；命题变量；逻辑连接词；复合命题； 自然语言事实和推理的命题逻辑形式表达 真值；指派； 重言式（永真式），矛盾式（永假式），可能式 范式 逻辑等价 真值表证明；双蕴含永真；等价替换；

提要 谓词逻辑 谓词，量词，论域 谓词的否定与嵌套 逻辑等价 推理 有效论证形式 推理规则与及用推理规则来论证 有关谓词逻辑的论证

谓词逻辑 例： 人都要死的 苏格拉底是人 苏格拉底要死的 命题逻辑对此推理毫无办法！

谓词逻辑 知识表示 brother(x, y) father(y, z)  uncle(x, z) father(x, y) father(y, z)  grandfather(x, z) 命题逻辑无法表达！

谓词 如果 x 是整数，“x 大于2” 不是命题，它的真值依赖于 x 的取值 谓词：P(x)陈述可以视同关于x的一个P属性取值(一个函数） P 的定义域是整数集，其值域是 { T, F } P(3)是一个取值为 T 的命题 “for all x, P(x)”是一个取值为 F 的命题 “存在一个x，P(x)”是一个真值为 T 的命题

量词 若P(x) 是谓词, xP(x)表示 “对所有的x, P(x)”  称为 全称量词 例： P(x)表示x>2 ，xP(x)为假， xP(x)为真

关于论域/作用域的讨论 符号化以下语句： P(x)表示x2>0，xP(x)的真值？ 有的政治家诚实 所有美国人都喜欢汉堡包 不同的论域，真值不一 不同的谓词，符号化表达式不一 特别注意：不同论域下，不同量词的符号化

关于论域/作用域的讨论 观察量化表达式： x(P(x)  Q(x)) x(P(x,y)  Q(x,y)) xP(x) xQ(x) xP(x) yQ(y) 量化表达式中的变元：绑定、自由、作用域、替换

逻辑等价 逻辑表达式的逻辑等价： 都有相同的真值，无论变量设定在哪个论域上，无论什么谓词代入。

带量词的公式的否定式 xP(x)  xP(x) xP(x)  xP(x) 对所有的x, x的平方是正数

多个量词并用 xyP(x,y)  yxP(x,y) xyP(x,y)  yxP(x,y) 举例：P(x,y) 表示 x+y=y+x。论域为实数集 xyP(x,y)  yxP(x,y) 举例： P(x,y) 表示x=y+1。 xyP(x,y) 与 yxP(x,y) 不一定等价 举例：P(x,y) 表示“y>x” 。

多个量词并用 考虑实数集： xyP(x,y) 与 yxP(x,y) 总是有相同的真值。若P(x,y) 表示 x+y=y+x，则yxP(x,y)为真。 xyP(x,y) 与 yxP(x,y)总是有相同的真值。若P(x,y) 表示x=y+1，则yxP(x,y)为真。 若P(x,y) 表示“y>x” 则xyP(x,y) 为真，但 yxP(x,y) 为假。

将自然语言翻译成逻辑表达式 这个班上的每个学生都学过微积分课程. S(x): x是这个班上的 C(x): x学过微积分课程 x (S(x) C(x)) 这个班上的每个学生都或去过加拿大，或去过墨西哥. x (S(x) V(x, 加拿大) V(x, 墨西哥) ) 练习：所有狮子都是凶猛的，有些狮子不喝咖啡。

一个关于素数的命题 n(N(n)  x(N(x)(xn)  (x2n)  y(y|x (y=1y=x)))) y|x: y 整除 x 在 n 与 2n 之间存在素数 (Tschebyscheff定理): 练习: “不存在最大的素数。”

为阅读和构造证明而必须掌握的若干基本逻辑要素：推理规则 推理的样例 老张请小刘和老钱吃饭。 他和老钱先到饭店，等了好久小刘还没有到。老张自言自语说：“哎，该来的还没来。”老钱听了不高兴了：“哦，原来我是不该来的？那我走吧。” 问题： 如果你是老钱，你会不高兴吗？你的不高兴，有道理吗？

推理的一般解释： 从“前提”A1, A2, …, Ak为真出发，推出“结论”B为真的推理（证明）过程。 其中我们关心的是： 前提：该来的还没有来；老钱来了 结论：老钱不该来 其中我们关心的是： 结论是否正确 其实，我们更关心的是： 推理（证明）过程是否正确！ 当前提都正确的时候， 如果推理过程正确， 那么，结论一定正确！

老钱该不该来？ 前提： 推理过程 结论： 该来的还没有来 老钱来了 (1)  P(老钱)→¬Q(老钱) ------(3) 定义谓词： P(x):x该来；Q(x):x来了 ：全称量词，表示“对所有的” 前提： 该来的还没有来 -------（1） 老钱来了 Q(老钱) -------（2） 推理过程 (1)  P(老钱)→¬Q(老钱) ------(3) (3)+(2)  ¬ P(老钱) 结论： 老钱不该来！ 老钱其实完全可以来！ 问题出在哪里？ 推理过程？正确！ 前提？前提有误！

再一例 如果税收下降，收入一定上升。现在我的收入上升了，所以，一定是税收下降了！ 定义命题P：税收下降；命题Q：收入上升 前提： 结论： P  Q；Q 结论： P 推理过程: ? 推理过程的不正确， 不能保证任何结果的正确性

推理过程正确性保障 推理过程正确性的保障需要 数学(具体而言是数理逻辑)的支持！ 数理逻辑基础包括： 命题逻辑和谓词逻辑

推理的结构-重言式 前提：一组命题公式A1, A2, …, Ak 结论：一个命题公式B 所谓“推理正确”指： 对诸Ai和B中出现的命题变元的任一指派，若前提的合取式为真，则结论必为真

推理的结构-重言式 即“推理为正确的”当且仅当 （A1  A2  …  Ak)B是重言式 说明：  若推理正确，则或者A1  A2  …  Ak ≡ F，或者（A1  A2  …  Ak ≡ T，且B ≡ T)，无论何种情况，上式为真，蕴涵式永真。  若上述蕴涵式为重言式，且A1  A2  …  Ak为真，B也必为真，因此推理正确。 注意：若前提的合取式为假，推理总是正确，或者说，推理正确并不保证结论正确

推理过程 从前提A1, A2, …, Ak为真出发，推出结论B为真的推理过程是一个表达式序列，该序列最后一个表达式应是要证明的结论，而其它任一表达式满足如下的条件,： 它可以是任意一个重言式； 它可以是{A1, A2, …, Ak}中的任何一个表达式； 可以是序列中前面的任一表达式通过应用“替换规则”得到的表达式； 可以是对序列中前面任意一个或若干个表达式应用推理规则得到的新表达式 A, (AB)得到B

例 以下推论合理吗？ 再一例： 晚上编程序就没法早早睡觉； 睡得早，起床早，上课不迟到； 所以，要想不迟到，晚上千万不能编程序！ 不合理 再一例： 如果税收下降，收入一定上升。现在我的收入上升了，所以，一定是税收下降了！

命题逻辑的推理规则

用推理规则建立论证 “今天下午不出太阳并且比昨天冷”,“只有今天下午出 太阳,我们才去游泳”,“若我们不去游泳,则我们将乘 独木舟游览”,“若我们乘独木舟游览,则我们将在黄昏时 回家”,结论“我们将在黄昏时回家”。

用推理规则建立论证 已知 (p∧q)∨r 和 r → s ，那么 p∨s 是否为真?

常用的蕴涵重言式 蕴含重言式在逻辑推理 中相当重要

蕴涵重言式与导出的推理规则 附加律 化简律 假言推理 取拒式 析取三段论 假言三段论 等价三段论 构造性二难 破坏性二难

与量词有关的基本推理规则 全称例示 UI: xP(x)  P(c) 全称生成 UG: P(c),任意c  xP(x) 存在例示 EI: xP(x)  对某个c, P(c) 存在生成 EG: 对某个c, P(c)  xP(x)

苏格拉底到底死不死？ P(x): x是人；Q(x)： x要死 符号化及推理过程： 人都是要死的：x(P(x)  Q(x)) P(苏格拉底)  Q(苏格拉底) 苏格拉底是人：P(苏格拉底) Q(苏格拉底)

谓词逻辑中的推理（举例） “在这个班上的某个学生没有读过这本书”，“班上的每个人都通过了第一门考试”，结论“通过第一门考试的某个人没有读过这本书”。 C(x): x在这个班上 B(x): x读过书了 P(x): x通过了第一门考试 x(C(x) ¬B(x)) x(C(x) P(x)) x(P(x) ¬B(x)) C(a) ¬B(a) 存在例示 C(a) 化简 C(a) P(a) 全称例示 P(a) 假言推理 ¬B(a) 化简 x(P(x) ¬B(x)) 存在生成

老钱真的可以来 前提： 推理过程 结论： “该来的还没有来”改成“还有一个该来的还没有来” 老钱来了 -------（1） 老钱来了 Q(老钱) -------（2） 推理过程 (1) ==> P(小刘)  ¬Q(小刘) 结论： 老钱真的可以来！ 定义谓词： P(x):x该来； Q(x):x来了

再一例 以下推论正确吗？ 令：A(x)：x喜欢喝茶；B(x)：x喜欢喝酒 推理如下： 1. xA(x)xB(x) Premise 有人喜欢喝茶，有人喜欢喝酒 因此，有人既喜欢喝茶又喜欢喝酒 令：A(x)：x喜欢喝茶；B(x)：x喜欢喝酒 推理如下： 1. xA(x)xB(x) Premise 2. xA(x) 化简，1 3. xB(x) 化简, 1 4. A(c) 例示, 2 5. B(c) 例示, 3 6. A(c)B(c) 合取. 4,5 7. x(A(x)B(x)) 生成, 6

再一例 请根据下面事实，找出凶手： a. 清洁工或者秘书谋害了经理。 b. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 c. 如果秘书的证词是正确的，则谋害发生在午夜前。 d. 如果秘书的证词不正确，则午夜时屋里灯光未灭。 e. 如果清洁工富裕，则他不会谋害经理。 f. 经理有钱且清洁工不富裕。 g. 午夜时屋里灯灭了。

再一例 用谓词逻辑，将下列推理形式化，并对正确的推理给出推理过程，要指明所假设命题或谓词的含义 人都喜欢吃蔬菜，但说所有人都喜欢吃鱼是不对的，所以存在只喜欢吃蔬菜而不喜欢吃鱼的人

再一例 用命题逻辑，将下列推理形式化，并对正确的推理给出推理过程，要指明所假设命题的含义 若小张喜欢数学，则小赵或小李也喜欢数学。若小李喜欢数学，他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以小赵喜欢数学

小结 谓词逻辑 在命题逻辑基础上引入谓词和量词， 推理 严格的基于命题逻辑和谓词逻辑的形式推理

作业 教材内容：[Rosen] 1.3—1.5节 课后习题： pp.34—37（英文教材pp.47—49）: 10,14(任选3小题), 34,42 pp.43—47 （英文教材pp.58—62）: 6 (任选3小题), 16, 44 p.56 （英文教材p.74）: 19, 21, 24, 29