离散数学5_3[2014_11_19].ppt

1、主讲教师：常亮 E-mail: QQ：737059669 办公室电话: 2291071 手机:辅导教师：周小川 答疑时间：星期四 上午 10:20-11:50 答疑地点：5教5楼 软件工程教研室,离散数学,内容回顾,等值演算 基本等值式： 第一组：命题逻辑中的基本等值式 + 代换实例 第二组：量词消去律、量词与否定的交换律、量词辖域收缩与扩张律、量词分配律、双量词交换律 演算规则：置换规则、换名规则、代替规则 前束范式 将谓词逻辑公式化为与之等值的前束范式： (1)消去谓词公式中的联结词“”、“”； (2)运用量词否定律，将移到原子谓词公式的前端； (3)进行换名和代

2、替过程，使每个变元都只以一种方式出现； (4)通过量词辖域收缩与扩张律以及量词分配律将所有量词移到公式的前端。,5.3 谓词逻辑推理,谓词逻辑推理：由已知的谓词公式为前提推出结论的谓词公式的过程。 前提：已知的谓词公式； 结论：由前提出发运用推理规则所推出的谓词公式。 直观例子： 前提：所有实数的平方都是非负的。 是一个实数。 结论：的平方是非负的。,有效推理,定义 5.19 对于谓词公式A和B，如果蕴含式AB是永真式，则称该蕴含式为永真蕴含式或重言蕴含式，记为AB。 注意：AB表示“公式AB为永真式”. 定义 5.20 对于谓词公式A1, A2, , An和B， 如果A1A2AnB是永真蕴含

3、式， 则称公式A1, A2, , An到公式B是一个有效推理， 或者称公式A1, A2, , An到公式B的推理是有效的。 并称公式A1, A2, , An是推理的前提， 公式B是以A1, A2, , An为前提的有效结论。 记为A1, A2, , An B。,重要的重言蕴涵式,第一组：命题逻辑中推理定律的代换实例 (p129) 附加律 A(AB) (x)A(x) (x)A(x)(y)B(y) 化简律 (AB)A 假言推理 A(AB) B (x)A(x)( (x)A(x)(y)B(y) (y)B(y) 拒取式 (AB)BA (y)B(y)(x)A(x) (y)B(y) (x)A(x) 析取三段

4、论 (AB)BA 假言三段论 (AB)(BC)(AC) 等价三段论 (AB)(BC)(AC) 构造性二难推理 (AB)(CD)(AC)(BD),重要的重言蕴涵式,第二组：由基本等值式生成的推理定律 （2） 命题逻辑中等值式的推广 (16组24个) (P109,159) 消去量词等值式 (2个) 量词与否定的交换等值式 (2个) 量词辖域收缩与扩张等值式 (8个) 量词分配等值式 (5个) 双量词交换等值式(2个),重要的重言蕴涵式,第三组：几条重要的关于量词分配的常用永真蕴含式 (p169) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)(A(x)B(x) (x)A(x)(x)

5、B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) (x)(y)A(x,y) (x)A(x,x) (x)A(x,x) (x)(y)A(x,y) (x)(y)A(x,y) (y)(x)A(x,y) 注意： (1) x (A(x) B(x) x A(x) x B(x) (2) x (A(x) B(x) x A(x) x B(x) (1) x (A(x)B(x) x (A(x)B(x) (2) x (A(x)B(x) x (A(x)B(x),重要的重言蕴涵式,三组重言蕴涵式的作用：用来证明推理的正确性； 证明简单的推理形式 对于复

6、杂的情况使用起来不方便,引入：构造证明法,构造证明推理,待判断的推理为：A1, A2, , Ak B 什么是“证明”： 由公式组成的序列； 其中的每个公式 要么是已知的前提 （即集合A1, A2, , Ak中的元素）， 要么是由某些前提应用推理规则得到的结论； 该序列的最后一个公式为B。 推理规则 命题逻辑中的11条推理规则 (p129) 4条针对量词的推理规则,11条推理规则 (p129-130),(1)前提引入规则： 在证明的任何步骤上，都可以引入前提。 (2)结论引入规则： 在证明的任何步骤上，所得中间结果都可以作为后继证明的前提。 (3)置换规则： 在证明的任何步骤上，公式中的子公式均

7、可用与之等值的公式置换。,11条推理规则 (p129-130),(4) 化简规则 AB A 或 AB B (5) 合取引入规则 A B A B (6) 附加规则 A AB 注意：A、B、C代表任意公式；推理模式。,11条推理规则 (p129-130),(7) 假言推理规则(分离规则) AB A B (8) 拒取式规则 AB B A (9) 析取三段论规则 AB A B,11条推理规则 (p129-130),(10) 条件三段论规则 AB BC AC (11) 析取构造性二难推理规则 AB CD AC BD,4条关于量词的推理规则 (p170-171),全称量词消去规则 (US规则: Unive

8、rsal Specification) x A(x) A(y) 要求：x是A(x)中自由出现的个体变项； y是不在A(x)中出现的个体变项； c可以是任何一个个体常项。 存在量词消去规则 (ES规则: Existential Specification) x A(x) A(c) 要求： x是A(x)中自由出现的个体变项； A(x)中除x之外不含有其他自由出现的个体变项； c是新引入的(即不在A(x)中出现的)某个特定的个体常项。,或者 x A(x) A(c),4条关于量词的推理规则 (p170-171),全称量词引入规则 (UG规则: Universal Generalization) A(y

9、) x A(x) 要求：y在A(y)中为自由出现的个体变项，是一个任意的个体变项； 取代y的x不能在A(y)中出现过。 存在量词引入规则 (EG规则: Existential Generalization) A(c) x A(x) 要求：c是特定的个体常项。 取代c的x不能在A(c)中出现过。,判断推理是否正确(构造证明法),待判断的推理为：A1, A2, , Ak B 什么是“证明”： 由公式组成的序列； 其中的每个公式 要么是已知的前提 （即集合A1, A2, , Ak中的元素）， 要么是由某些前提应用推理规则得到的结论； 该序列的最后一个公式为B。 推理规则 命题逻辑中的11条推理规则

10、(p129) 4条针对量词的推理规则,例子,构造下面推理的证明： 前提：x (F(x)G(x)，x (F(x) H(x) 结论： x (G(x)H(x) 证明： (1) x (F(x)G(x) 前提引入 (2) x (F(x) H(x) 前提引入 (3) F(c) H(c) (2) ES规则 (4) F(c) G(c) (1) US规则 (5) F(c) (3) 化简式 (6) G(c) (4)(5)假言推论 (7) H(c) (3) 化简式 (8) G(c) H(c) (6)(7) 合取引入 (9) x(G(x) H(x) ) (8) EG规则,同时出现全称量词和存在量词时，先消去存在量词。

11、,例子,构造下面推理的证明： 前提：所有实数的平方都是非负的。 是一个实数。 结论：的平方是非负的。 解：令F(x)：x是实数， G(x)：x是非负； 函词D(x)：x的平方，个体常项a： 。 符号化为： 前提：(x) (F(x)G(D(x)，F(a) 结论：G(D (a) 对其证明如下： (1) (x)(F(x)G(D(x) 前提引入 (2) F(a)G(D(a) (1) US规则 (3) F(a) 前提引入 (4) G(D(a) (2)(3) 假言推理,例子,将推理“鸟会飞，鸭子不会飞，所以鸭子不是鸟”符号化并给出形式证明。 解：令P(x)表示x是鸟，Q(x)表示x是鸭子，R(x)表示x会

12、飞，则将上述推理符号化为： 前提：x(P(x)R(x), x(Q(x) R(x) 结论：x(Q(x) P(x) 对其证明如下： (1) x(P(x)R(x) 前提引入 (2) x(Q(x) R(x) 前提引入 (3) P(c)R(c) (1) US规则 (4) Q(c) R(c) (2) US规则 (5) R(c) P(c) (3) 等值置换 (6) Q(c) P(c) (4)(5)条件三段论 (7) x(Q(x) P(x) (6) UG规则,构造证明法间接构造证明推理,若待判断的推理形如 A1, A2, , Ak CB 则转换为判断 A1, A2, , Ak, C B 欲证明 前提：A1,A

13、2,Ak 结论：CB 等价地证明 前提：A1,A2,Ak,C 结论：B 理由： (A1A2Ak)(CB) (A1A2AkC)B 附加前提引入规则,构造证明法归谬法(间接构造证明推理的另一方式),若待判断的推理形如 A1, A2, , Ak B 则转换为判断 A1, A2, , Ak, B 矛盾 欲证明 前提：A1,A2,Ak 结论：B 等价地证明 前提：A1,A2,Ak, B 结论：矛盾 理由： A1A2AkB ( A1A2AkB) A1A2AkB为永真式 iff A1A2AkB为矛盾式 结论的否定引入规则,反证法,例子,构造下面推理的证明： 前提：(x)(F(x)(G(a)R(x), (x)

14、F(x) 结论: (x)(F(x)R(x) 证明： (1) (x)F(x) 前提引入 (2) F(c) (1) ES规则 (3) (x)(F(x)(G(a)R(x) 前提引入 (4) F(c)(G(a)R(c) (3)US规则 (5) G(a)R(c) (2)(4)假言推论 (6) R(c) (5)化简式 (7) F(c)R(c) (2)(6)合取引入 (8) (x)(F(x)R(x) (7)EG规则,此处，用ES时，能用个体常项 a 吗？,练习,构造下面推理的证明： 人都喜欢吃蔬菜，但不是所有的人都喜欢吃鱼。所以，存在喜欢吃蔬菜而不喜欢吃鱼的人。 证明： 令F(x)：x是人， G(x)：x喜

15、欢吃蔬菜， H(x)：x喜欢吃鱼。 前提：x (F(x) G(x)， x (F(x) H(x) 结论：x (F(x)G(x)H(x) ,练习,构造下面推理的证明： 火车都比汽车快，汽车都比轮船快，a是火车，b是汽车，c是轮船。所以，a比b快，b比c快。 证明： 令 F(x)：x是火车， G(x)：x是汽车， H(x)：x是轮船，L (x，y)：x比y快。 前提：x y (F(x) G(y) L (x，y) ， x y (G(x) H(y) L (x，y) ， F(a) ，G(b)，H(c) 结论：L (a，b) L (b，c),几个错误推理的例子,下列推导有何错误？ (1) y(P(y) Q(

16、y) 前提引入 P(a) P(b) US规则 (2) xP(x) Q(x) 前提引入 P(x) Q(x) US规则,谓词逻辑的归结推理方法,归结推理方法 (Resolution method) 归谬法 若待判断的推理形如 A1, A2, , Ak B 则转换为判断 A1, A2, , Ak, B 矛盾 基于归结原理/消解原理 (resolution principle) 机械化，可以在计算机上实现 命题逻辑的归结推理方法 谓词逻辑带来的问题 量词 利用Skolem标准形消去存在量词 消去全称量词 个体变元 合一/置换,不作要求！,作业,P185 41 42 44 45,第4到5章总结,基本思路

17、：首先引进一套符号体系，规定一些规则，然后借助这些符号和规则，将逻辑推理过程在形式上变得像代数演算一样。,对命题形式化/符号化,推理,谓词逻辑,命题逻辑,真值表法 主析取范式法/主合取范式法 等值演算法 构造证明法(形式证明系统) 归结推理方法(消解法),命题符号、联结词,等值演算法 构造证明法(形式证明系统) 归结推理方法(消解法),命题符号、联结词 谓词、量词、个体词 函词,课堂小测试(第二次),(1)构造下面推理的证明： 前提：x (F(x)G(x)，x (F(x) H(x) 结论： x (G(x)H(x) (2)构造下面推理的证明： 前提：所有实数的平方都是非负的。 是一个实数。 结论：的平方是非负的。 (3)将推理“所有乌鸦都是黑色的，有些鸟是乌鸦，所以有些鸟是黑色的”符号化并给出形式证明。 提示：令P(x)表示x是乌鸦，Q(x)表示x是黑色的，R(x)表示x是鸟，则将上述推理符号化为： 前提：x(P(x)Q(x), x(R(x)P(x) 结论：x(R(x)Q(x)