谓词逻辑初步 与推理规则.

Presentation on theme: "谓词逻辑初步 与推理规则."— Presentation transcript:

1 谓词逻辑初步 与推理规则

2 回顾 问题1：什么是命题逻辑？ 问题2：如何判断命题表达式的真假？ 问题3：如何判定命题可满足？ 与命题真假有关的判断
真值表 与 常用逻辑等价 问题3：如何判定命题可满足？ 范式 与 主范式 命题包括原子和复合，统称为命题(表达式)

3 本节提要 问题1：什么是(一阶)谓词逻辑？ 问题2：如何进行推理？

4 引例 人都要死的，苏格拉底是人，所以苏格拉底要 死的
father(x, y)  father(y, z)  grandfather(x, z) 命题逻辑无法处理上述推理！

5 谓词（Predicate） 如果 x 是整数，“x 大于2” 不是命题，它的真值 依赖于 x 的取值
可以将“x 大于2”表示为 P(x)。 谓词：P(x)可以视同关于x的一个属性的取值(一 个函数） P 的定义域是整数集，其值域是 { T, F } P(3)是一个取值为 T 的命题 “for all x, P(x)”是一个取值为 F 的命题 “存在一个x，P(x)”是一个真值为 T 的命题 谓词：表示语句的主语具有某个性质

6 量词（Quantifier） 若P(x) 是谓词, xP(x)表示 “对所有的x, P(x)”  称为 全称量词
例：P(x)表示x>2 ，xP(x)为假， xP(x)为真 注1：量词必须指定论域（默认为实数域） 注2：当论域元素可以一一列出时，量词（谓词公式） 可以转化成命题公式的合取、析取范式 注3：量词的优先级高于其它逻辑运算符 量词：表示在何种程度上谓词成立；例如自然语言中的所有、没有、某些

7 量词的论域 符号化以下语句： P(x)表示x2>0，xP(x)的真值？ 有的政治家诚实 所有美国人都喜欢汉堡包

8 量词的作用域 观察量化表达式： x(P(x)Q(x)) xP(x)Q(x) x(P(x,y)Q(x,y))
xP(x)xQ(x) xP(x)yQ(y) 量化表达式中的变元：绑定、自由、作用域、替换 命题逻辑的可满足性问题是NP-Complete的,一阶谓词逻辑的可满足性问题不可判定的

9 量化表达式的逻辑等价 逻辑表达式的逻辑等价： 都有相同的真值，无论变量设定在哪个论域上， 无论什么谓词代入。 例：
逻辑表达式的逻辑等价： 都有相同的真值，无论变量设定在哪个论域上， 无论什么谓词代入。 例： x(P(x)  Q(x))  xP(x)  xQ(x) x(P(x)  Q(x))  xP(x)  xQ(x) 设P和Q采用同一个论域，逻辑等价即两边永远有相同的真值

10 量化表达式的否定式 xP(x)  xP(x) xP(x)  xP(x) 对所有的x, x的平方是正数
xy(xy1) 练习：表达语句xy(xy=1)的否定

11 嵌套量词 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” 。

12 将自然语言翻译成逻辑表达式 这个班上的每个学生都学过微积分课程. S(x): x是这个班上的，C(x): x学过微积分课程
x (S(x) C(x)) 这个班上某些人去过墨西哥；这个班上每个学生都或去过加拿 大，或去过墨西哥. ∃x(S(x) → M(x)) or ∃x(S(x)  M(x))? x (S(x) V(x, 加拿大) V(x, 墨西哥) ) 练习：所有狮子都是凶猛的，有些狮子不喝咖啡。 例子中的x的论域是所有人，如果设定论域为这个班级的学生则可以简化 用双变量V(x, 加拿大)，也可以用两个单变量 存在量词不用蕴含用合取 有些凶猛的动物不喝咖啡

13 将自然语言翻译成逻辑表达式 如果一个人是女性且是家长，则她是某人的母亲 x((F(x)P(x))  yM(x,y))
xy((F(x)P(x))  M(x,y))

14 将自然语言翻译成逻辑表达式 n(N(n)  x(N(x)(xn)  (x2n)  y(y|x (y=1y=x))))
y|x: y 整除 x 在 n 与 2n 之间存在素数 (Tschebyscheff定理): 对任意素数x，存在素数y使得y>x x(G(x)  y(G(y)D(y,x))) 练习: “不存在最大的素数。”

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

16 本节提要 问题1：什么是(一阶)谓词逻辑？ 命题逻辑+谓词+量词；量化表达式 问题2：如何进行推理？

17 引例：老钱该不该来？ 推理的样例 老张请小刘和老钱吃饭。 他和老钱先到饭店，等了 好久小刘还没有到。老张自言自语说：“哎，该来的 还没来。”老钱听了不高兴了：“哦，原来我是不该来 的？那我走吧。” 问题： 如果你是老钱，你会不高兴吗？你的不高兴，有道理吗？ 证明是建立数学命题真实性的有效论证；推理从已知命题推出新命题

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

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

20 引例：老钱可以来 前提： 推理过程 结论： “该来的还没有来”改成“还有一个该来的还没有来” 老钱来了
（1） 老钱来了 Q(老钱) （2） 推理过程 (1) ==> P(小刘)  ¬Q(小刘) 结论： 老钱可以来！

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

22 论证 An argument in propositional logic is a sequence of propositions. All but the final proposition in the argument are called premises and the final proposition is called the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true. “如果我是马云，那么我给各位每人发一辆法拉利。” “我是马云。” ∴“我给各位每人发一辆法拉利。” “如果我是教师，那么我要上课。” “我是教师。” ∴“我要上课。” 要证明一个论证合理，关键是证明论证形式合理

23 论证形式 An argument form in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true. 其实，只要证明相应的蕴含式是永真式 𝑝→𝑞 𝑝 ∴ 𝑞

24 推理规则 前提：一组命题公式A1, A2, …, Ak 结论：一个命题公式B 所谓“推理正确”指：
对诸Ai和B中出现的命题变元的任一指派，若前提的 合取式为真，则结论必为真 即“推理为正确的”当且仅当 （A1  A2  …  Ak)B是永真式

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

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

27 例 课本61页表1：推理规则

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

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

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

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

32 量化表达式的推理规则 全称例示: xP(x)  P(c) 全称生成: P(c),任意c  xP(x)
存在例示: xP(x)  对某个c, P(c) 存在生成: 对某个c, P(c)  xP(x)

33 用推理规则建立论证 “在这个班上的某个学生没有读过这本书”，“班上的每个人都通过了第一门考试”，结论“通过第一门考试的某个人没有读过这本书”。 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)) 存在生成

34 例 以下推论正确吗？ 令：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

35 练习 用命题逻辑，将下列推理形式化，并对正确的推理 给出推理过程，要指明所假设命题的含义
若小张喜欢数学，则小赵或小李也喜欢数学。若小李喜 欢数学，他也喜欢物理。小张确实喜欢数学，可小李不 喜欢物理。所以小赵喜欢数学 用谓词逻辑，将下列推理形式化，并对正确的推理 给出推理过程，要指明所假设命题或谓词的含义 人都喜欢吃蔬菜，但说所有人都喜欢吃鱼是不对的，所 以存在只喜欢吃蔬菜而不喜欢吃鱼的人 拒取式、假言推理、析取三段论

36 本节小结 问题1：什么是(一阶)谓词逻辑？ 问题2：如何进行推理？ 命题逻辑+谓词+量词；量化表达式 前提正确+过程正确=>结论正确
以永真式作为推理过程

37 作业 见课程主页

38 附录

39 命题逻辑的可判定性 自然演绎规则就是前面的推理规则；根据语法进行的推导是等价于基于语义的真值检查的。 正确-》可靠

40 自然演绎规则（含量词相关的）是可靠的、完备的
一阶谓词逻辑的可判定性 自然演绎规则（含量词相关的）是可靠的、完备的 不可判定的（undecidable） 自然演绎规则是完备的，一阶谓词逻辑是不完备的

41 停机问题 停机问题就是判断任意一个程序是否能在有限的 时间之内结束运行的问题
该问题等价于如下的判定问题：是否存在一个程序P，对 于任意输入的程序w，能够判断w会在有限时间内结束 或者死循环。 反证法：假设存在这样的判定程序halt()，定义g如下， def g(): if halt(g): loop_forever() 如果halt(g)停止则g死循环；如果halt(g)死循环则g停止；导 出矛盾。

42 哥德尔不完备性定理 逻辑系统可具有下列性质： 1, 有效性(validity):依系统的推理规则，若所有前提皆为真则结论必为 真（保真）。 2, 相容性(consistency):系统中任一定理都不与其他定理相矛盾。不存在 命题P，P和非P皆可在系统中证明。 3, 可靠性(soundness):系统中所有定理（有效且可证明的命题）皆为真。 可靠性与完备性互为逆命题。  4, 完备性(completeness):系统中不存在无法证明或证否的有效命题。系 统中真命题皆可证明（真命题皆为定理）且假命题皆可证否。 哥德尔证明了没有标准的算术形式系统可以同时满足相容性和完备性 哥德尔不完备性第一定理：任意一个包含一阶谓词逻辑与初等数论的形 式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被 证明为否。