离散数学第二章

1、离散数学第二章第1页，共117页，2022年，5月20日，1点52分，星期六用命题逻辑处理苏格拉底三段论：谓词逻辑又例: 张华是大学生,李明也是大学生。所有的自然数都等于1.(F); 存在着自然数等于1.(T)PQR人总是要死的,苏格拉底是人,苏格拉底是要死的。若论证有效则有: PQR,即 PQR 永真.第2页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑对简单命题作进一步分析,分离出个体和谓词,并考虑到泛指和特指 (全称和存在),在此基础上,研究命题的逻辑结构及命题间的推理关系。Predicate Logic第二章第3页，共117页，2022年，5月20日，1点52分，星期

2、六-1 谓词的概念与表示-2 量词-3 谓词公式-5 等价式与重言式 -7 谓词演算的推理理论26 前束范式谓词逻辑 -4 谓词公式的解释第4页，共117页，2022年，5月20日，1点52分，星期六命题是具有确定真值的陈述句。2-1谓词的概念和表示如 “电子计算机是科学技术的工具。”个体:思维的对象,可以是具体的事物或抽象的概念谓词:刻画个体性质或个体之间关系的词。1. 个体和谓词 陈述句由主语和谓语两部分构成，主语谓语个体谓词一元谓词: 与一个个体相关联的谓词.(描述个体性质)N元谓词: 与N个个体相关联的谓词.(描述个体间的关系)谓词逻辑 谓词的概念和表示第5页，共117页，2022年，

3、5月20日，1点52分，星期六(a).他是三好学生。(b).7 是质数。(c).每天作广播操是好习惯。(d).5 大于 3.(e).地球绕着太阳转。一元谓词。谓词刻画个体性质(f).张明和张亮是兄弟。(e).上海位于南京和杭州之间。谓词刻画个体间关系。在谓词逻辑中,命题是由一个谓词和若干有序个体组成的。谓词逻辑 谓词的概念和表示二元谓词二元谓词二元谓词三元谓词第6页，共117页，2022年，5月20日，1点52分，星期六2.个体和谓词的表示 命题由一个谓词和若干个体组成谓词逻辑 谓词的概念和表示用大写字母 A, B , C, D,. 代表谓词。用小写字母代表个体 ： 用小写字母 a , b,

4、c. 表示特定个体: 个体常元 用小写字母 x,y,z.表示任意个体：个体变元. 一个 n 元谓词记作: A ( x1 , x2, xn)其中 x1 , x2,xn 为个体变元.当A ( x1 , xn)中个体变元用个体常元: a1,an 代入后, A(a1an) 就成为一个命题。则 A (a) 表示命题: 张华是大学生, A (b) 表示命题: 李明是大学生。例: 令 A(x) : x 是大学生; a:张华 , b:李明第7页，共117页，2022年，5月20日，1点52分，星期六命题由一个谓词和若干个体组成，但并非任意个体都和任意谓词都能构成命题。如 2 是偶数,(T)个体域:个体的取值范

5、围,用D表示 如谓词 “. 是偶数” 的个体域 D: 全体整数。 “.是要死的” D:全体生物 或 D: 人类全总个体域:所有个体的集合称之。谓词逻辑 谓词的概念和表示3 是偶数,(F)x 是偶数 (不是命题)当谓词确定后,其允许的个体取值范围称为个体域。则 A (a) 表示命题: 张华是大学生, A (b) 表示命题: 李明是大学生。例: 令 A(x) : x 是大学生; D:人类 a:张华 ,b:李明第8页，共117页，2022年，5月20日，1点52分，星期六又例: 上海位于南京和杭州之间。 令 L (x ,y,z) : x 位于 y 和 z 之间, D: 城市则命题符号化为: L(a,

6、b,c)谓词逻辑 谓词的概念和表示 则 L(2,3) 表示命题: 23. (真)又例: 设 L (x,y) : x 小于 y, D: 实数集合 则 L(5,1):表示命题: 5谓词的概念和表示3.复合命题第10页，共117页，2022年，5月20日，1点52分，星期六例如: 张华的母亲爱张华. 设 P(x,y):x爱y; D:人; f(x): x的母亲; a:张华命题符号化: P ( f (a), a )例如: 2与3之和小于2与3之积. 设 P(x,y):x小于y; D:整数; f(x,y): x与 y之和 g(x,y): x与 y之积 ; a:2 ; b:3命题符号化: P( f(a,b)

7、, g(a,b) ) 或 P( 2+3, 23 ) 自变量和函数值均为个体域中的个体.用小写字母f,g.表示.谓词逻辑 量词4.个体函数例如: 张华的母亲爱张华.第11页，共117页，2022年，5月20日，1点52分，星期六-1 谓词的概念与表示-2 量词-3 谓词公式-5 等价式与蕴含式 -7 谓词演算的推理理论26 前束范式谓词逻辑 -4 谓词公式的解释第12页，共117页，2022年，5月20日，1点52分，星期六例如: 任何人都是要死的.(T)有些人是聪明的.(T)所有的自然数都等于1.(F)存在着自然数等于1.(T)对个体域中的所有个体成立对个体域中的某些个体成立当命题的主语是泛指

8、时,命题的真值还取决于谓词与个体域中个体的数量关系.谓词逻辑 量词2-2量词1.全称量词与存在量词第13页，共117页，2022年，5月20日，1点52分，星期六两种量词:命题中表示个体数量的词。全称量词(Universal Quantifier):表示个体域中全体个体的词，记作 相当于 “任意”,“凡是”,“所有”.若个体域中所有个体x,均使A(x)为真,记作(x)A(x)存在量词(Existential Quantifier):表示个体域中部分个体的词， 记作 相当于 “存在”,“至少有一个”,“有些”.若个体域中存在某些个体x,使A(x)为真,记作(x)A(x)谓词逻辑 量词第14页，共

9、117页，2022年，5月20日，1点52分，星期六设H(x): x 是要死的, 任何人都是要死的。例如:则命题表示为: (x)H(x) 个体域D: 人类 又例如: 有些人是聪明的.设A(x): x是聪明的, 个体域 D:人类则命题表示为: (x)A(x)谓词逻辑 量词第15页，共117页，2022年，5月20日，1点52分，星期六当在全总个体域中讨论命题时,需在命题表示中增加一个特性谓词,以给出个体变元的个体域。2.特性谓词(1)带全称量词的命题,特性谓词作为 加入. 任何人都是要死的例如:M(x):x是人则命题表示为：(x)(M(x)H(x)改为:谓词逻辑 量词设 H(x):x是要死的 个

10、体域D: 全人类 则命题表示为：(x)H(x)。H(x):x是要死的条件式的前件第16页，共117页，2022年，5月20日，1点52分，星期六例如:有些人是聪明的.个体域 D：人设A(x)：x是聪明的,则命题表示为: (x)A(x)改为:A(x)：x是聪明的,则命题表示为: (x)(M(x)A(x)(2)带存在量词的命题,特性谓词作为合取项加入。为何特性谓词以前件加在全称量词后,而以合取项加在存在量词后? 能否改为:(x)(H(x) M(x) 和 (x)(M(x) A(x) ?谓词逻辑 量词M(x):x是人第17页，共117页，2022年，5月20日，1点52分，星期六3.命题符号化谓词逻辑

11、 量词日常用语翻译第18页，共117页，2022年，5月20日，1点52分，星期六用谓词逻辑处理苏格拉底三段论：人总是要死的,苏格拉底是人,所以,苏格拉底是要死的。a: 苏格拉底 M(x): x是人,(x) (M(x) P(x),M(a),P(a).令谓词逻辑 量词例题P(x): x是要死的,推理形式为: (x) (M(x) P(x), M(a) P(a).1.判断是否复合命题(看有几个主谓结构或连接词).2.对复合命题找出每个原子命题.3.对每个原子命题分出主语和谓语,主语若是泛指需加量 词和特性谓词.并用符号表示.4.分析各原子命题的关系,确定连接词.第19页，共117页，2022年，5月

12、20日，1点52分，星期六存在着最小的自然数.谓词逻辑 量词P61 例题补例 兔子比乌龟跑的快例题3 尽管有人聪明, 但未必一切人都聪明.例题1 并非每个实数都是有理数.每个人都有自己喜欢的职业.R(x): x是实数设 Q(x): x是有理数,故符号化为: (x) (R(x) Q(x) M(x): x是人设 P(x): x是聪明的,(x)(P(x) M(x) ) (x)(M(x)P(x)第20页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词作 业2-1， 2-2 （1）（e）,（f）,（g）,（h）2-3 （3） 本节重点掌握的概念: 个体，谓词, 量词, 个体域

13、。 本节重点掌握的方法: 命题符号化。特别注意特 性谓词的两种使用方法。第21页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 谓词公式1.个体和谓词2.谓词的表示: P(x1,x2,.xn) 每个命题有一个谓词和若干个体组成.当谓词确定后,命题的真值依赖个体,因此采用函数的记法表示谓词,自变量的取值范围称为个体域 D3.量词:当句子的主语是泛指的时候,必须引入量词符号4.特性谓词: 若在全总个体域讨论问题,还需在命题表达中增加特性谓词,以说明命题中个体的取值范围.5.命题符号化 “每个计算机系的学生都学离散数学“ “存在着偶素数”第22页，共117页，2022年，5月20日

14、，1点52分，星期六谓词逻辑 谓词公式北京是中国的首都甲是乙的父亲3介于2与4之间3大于2仅当3大于4。张三和李四是同班同学天下乌鸦一般黑火车都比汽车跑得快有的火车比所有汽车快。 课堂练习在谓词逻辑中符号化：第23页，共117页，2022年，5月20日，1点52分，星期六-1 谓词的概念与表示-2 量词-3 谓词公式-5 等价式与蕴含式 -7 谓词演算的推理理论26 前束范式谓词逻辑 -4 谓词公式的解释第24页，共117页，2022年，5月20日，1点52分，星期六2-3谓词公式如 P, P(x), P(x,y), P( f(x), y ), P(a, y) 均原子公式。1. 谓词公式 补充

15、定义(项)1).个体常元和个体变元是项. 2).若f 是n元个体函数,t1,.,tn是项,则 f(t1,.tn)是项.3).只有有限次运用1),2)规则得到的符号串是项.如 x, a, f(x), g(x,y), g( f (x),a).谓词逻辑 谓词公式项代表公式中以各种形式出现的个体.原子公式: 把A(t1, t2, tn)称为谓词演算的原子公式,其中, t1, t2, tn是项.不含个体变元的原子公式是原子命题.第25页，共117页，2022年，5月20日，1点52分，星期六定义 2-3.1 谓词演算的合式公式wff,由下述各条组成：(1)原子谓词公式是合式公式。(2)若A是合式公式,则

16、A是合式公式。(3)若A和B都是合式公式,则(AB),(AB), (AB)和(AB) 是合式公式。(4)如果A是合式公式,x是A中出现的任何变元, 则 (x)A和 (x)A都是合式公式。(5)只有经过有限次的应用规则(1),(2),(3),(4) 所得到的公式是合式公式。简称谓词公式如 xy P( x, y), x P( f(x), y),谓词逻辑 谓词公式P(a,y) Q 第26页，共117页，2022年，5月20日，1点52分，星期六2.变元的约束 若给定为一谓词公式,它可带有如下子公式: ( x) A( x ) 或 ( x) A( x )指导变元辖域约束变元其中,、 后的 x 称为该量词

17、的指导变元; A(x)称为量词的作用域或辖域(scope);在辖域中 x 的一切出现称为x在中的约束出现,x称为约束变元;在中除约束变元以外所出现的变元称为自由变元。P63例题1如x(M(x)R(x) , yP(x, y)R(y) 谓词逻辑 谓词公式第27页，共117页，2022年，5月20日，1点52分，星期六 闭式:不含自由变元的公式. 开式:含有自由变元的公式. 其中,含有k个自由变元 x1, x2,.xk的公式称为 k元谓词,记作A(x1,x2,.xk ),0元谓词为闭式.例如 ( x) P( x,y,z ) x是小于100的质数: L(x,100)又如 任意的实数x,都存在着实数y,

18、使得xy.（不存在最大实数） 令 P(x,y): x谓词公式 闭式 (T) 二元谓词一元谓词由命题符号化得到的公式是闭式.第28页，共117页，2022年，5月20日，1点52分，星期六-1 谓词的概念与表示-2 量词-3 谓词公式 -4 谓词公式的解释-5 等价式与蕴含式 -7 谓词演算的推理理论26 前束范式谓词逻辑第29页，共117页，2022年，5月20日，1点52分，星期六谓词公式的真值与那些因素有关?谓词公式的真值能否像命题逻辑那样总可由真值表给出?例xy (P(x) Q( f(x,a), y ,z )R) 的真值给出个体域指定谓词2-4.谓词公式的解释指定个体函数和个体指定自由变

19、元谓词逻辑 谓词公式的解释令 P(x,y): xy , D:自然数x y P( x, y )(闭命题) (F) 例(T);令 P(x,y): x+y=0 ,D:自然数Q(x,y)P( x, y )(开命题)例令D: 自然数; P(x,y): x谓词公式的解释第31页，共117页，2022年，5月20日，1点52分，星期六 给定解释I和I 中的赋值如下: DI:自然数集,L(x,y):xy, E(x,y):x=y, h(x,y):xy, v1: x=0, v2: x=1求公式在解释I下的真值.(1) y (E(x,y) L(x, y )(2) yz E( h( y,z ), x ) 解 在解释I

20、下 E(x,y)为 x=y; L(x, y )为x谓词公式的解释补例第32页，共117页，2022年，5月20日，1点52分，星期六补例 设解释I的个体域为 a1, a2, an , 则在解释I下, xA(x) A(a1)A(a1).A(an)xA(x) A(a1)A(a1).A(an)当个体域DI中的元素个数有限时,可将变元的所有可能取值一一列举出来,此时量词可消除.谓词逻辑 谓词公式的解释第33页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 谓词公式的解释求下列闭式在解释I下的真值 给定解释I如下:D= 2, 3 , f (2)=3, f (3)=2, P(2)=T P

21、(3)=F, Q(2, 2)=T, Q(3, 3)=T,Q(2, 3)=F, Q(3, 2)=F. 解1) x(Q( f(x), x)P(x) 2) x( y)Q( x, y) 1). 原式=(Q( f (2), 2)P(2) ) (Q( f (3), 3)P(3) ) =(Q(3, 2)P(2) )( Q(2, 3)P(3) ) =(FT) (FF) =T 2). 原式= x (Q(x, 2) Q( x, 3 ) = (Q(2, 2) Q( 2, 3)(Q(3, 2) Q(3, 3) = (T F) (F T) =T yx Q( x, y)的真值?补例第34页，共117页，2022年，5月2

22、0日，1点52分，星期六谓词逻辑 谓词公式的解释 求(x)(y)(P(x)Q(x, y) 在解释I的真值 DI=1,2, P(1)=F, P(2)=T, Q(1,1)=T, Q(2,2)=T; Q(1,2)=F, Q(2,1)=F.原式= (x)(P(x) Q(x,1)(P(x) Q( x, 2) ) = (P(1) Q(1,1)(P(1) Q( 1, 2 ) (P(2) Q(2,1)(P(2) Q( 2,2 )= (FT) (F T) (F F) ( T T) )= F补例第35页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 谓词公式的解释课堂练习1.“并非一切推理都能用

23、计算机完成”符号化为( )2.设R(x):x是实数, P(x,y): x=y, 则命题“对任意的实数 x, y, 有x+y= y+ x”符号化为( ) 3.不含有自由变元的谓词公式是命题. ( ) 4. y E(x,y) L(x, y, z )是二元谓词( )5.使一阶逻辑公式 y x F(y ,x) 为真的解释是 ( )A.个体域为自然数集合，F(x,y)为 xy B.个体域为自然数集合，F(x,y)为 y谓词公式的解释 本节重点掌握的概念: 谓词公式, 自由变元,约束变元, 开式, 闭式。本节重点掌握的方法: 求谓词公式的真值第37页，共117页，2022年，5月20日，1点52分，星期六

24、要点回顾谓词逻辑 等价与蕴含式1.个体和谓词2.谓词的表示: P(x1,x2,.xn)3.量词4.特性谓词5.谓词公式6.谓词公式的赋值: 对谓词公式一个赋值称为一个解释。闭式在一组解释下会求得一个真值；开式还需在此基础上对自由变元赋值，才能求出一个真值。 例: 对任意的自然数x存在着自然数y ,使得 p(x,y) 成立. 解释1：p(x,y) :x等价与蕴含式第40页，共117页，2022年，5月20日，1点52分，星期六命题逻辑永真式（永假式）的代换实例是谓词逻辑的永真式（永假式）。设A是包含命题变元 P1, P2,.Pn的命题公式, B1,B2,.Bn是谓词公式, 用 B1,B2,.Bn

25、 分别代替P1,P2,.Pn 在A中的所有出现,得到的谓词公式B称A的代换实例,命题逻辑永真式的代换实例称为重言式.谓词逻辑 等价与蕴含式命题逻辑的代入定理:一个重言式,对同一分量都用任何合式公式置换,结果仍重言.第41页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 等价与蕴含式上式可看作命题公式PP的代入实例1) (x)P(x) (x)P(x) 2 ) (xP(x)(xQ(x)xP(x) ) 上式可看作命题公式 ( P(Q P) )的代入实例 而(P(Q P)(P (QP)F 所以, (xP(x)(xQ(x)x P(x) )为永假式而PP T,所以, (x)P(x) (x

26、)P(x)为重言式 判定公式的类型重言式是永真式 ,但永真未必重言. 例如 xP( x ) xP( x ) 是永真式，但不是重言式.补例第42页，共117页，2022年，5月20日，1点52分，星期六2.等价与蕴含定义 2-5.1 设A,B是公式,若AB是永真式,则称A,B等价.记作AB.等价式的判定等价演算:利用基本公式、等价的性质 和 置换 定理，推演出其他等价式.定义 2-5.2 设A,B是公式,若AB是永真式,则称A蕴含B.记作AB.谓词逻辑 等价与蕴含式AB 当且仅当 A B且B A第43页，共117页，2022年，5月20日，1点52分，星期六(1) 命题公式的推广例如 PQPQ

27、用 xP(x) 代替 P; (x)P(x)(x)Q(x)(x)P(x)(x)Q(x) xQ(x) 代替 Q 得到:(x)(P(x)Q(x)(x)R(x)(x(P(x)Q(x) ) (x)R(x) 同理 P(x)Q(x)P(x)Q(x) 利用代入定理,将命题逻辑的所有等价式推广到谓词逻辑.谓词逻辑 等价与蕴含式第44页，共117页，2022年，5月20日，1点52分，星期六(2) 量词与联结词的关系例 设 P(x) : x今天来校上课, D:学生 则 P(x)表示: x今天没来校上课 “并非所有人今天来校上课” (x)P(x) 等价 “有人今天没来校上课” (x)P(x) (x)P(x) (x)

28、P(x) “ 没有人今天来校上课” (x) P(x) 等价 “所有人今天都没来校上课” (x)P(x) (x) P(x) (x)P(x)谓词逻辑 等价与蕴含式第45页，共117页，2022年，5月20日，1点52分，星期六(3) 量词作用域的扩张与收缩(x)(A(x) B) (x)A(x)BB(x)A(x) ( x)(A(x)B) ( x)A(x)BB (x)A(x)(x) A(x)B ( x) (A(x) B)(x) A(x) B (x)A(x) B)B (x) A(x) (B (x)A(x)B (x)A(x) (B (x)A(x)由上式可推出谓词逻辑 等价与蕴含式第46页，共117页，20

29、22年，5月20日，1点52分，星期六(4) 量词与联结词之间的一些等价式例第一式中用 A代A ,用 B代B：(x)(A(x) B(x) (x)A(x) (x)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)(A(x)B(x) (x)A(x)(x)B(x)(x)(A(x)B(x) (x)A(x)(x)B(x)对满足分配律对满足分配律“联欢会上所有人即唱歌又跳舞. ” 谓词逻辑 等价与蕴含式(x)(A(x)B(x) (x)A(x)(x)B(x)第47页，共117页，2022年

30、，5月20日，1点52分，星期六 (x)(A(x)B(x) (x)A(x) (x)B(x) ? (x)(A(x)B(x) (x)A(x) (x)B(x) ?(x)(A(x)B(x): 对所有的x, 有A(x)或B(x)成立. (x)(A(x)B(x): 存在着x ,使A(x)和B(x)同时成立. 例 D:整数集合, A(x): x是偶数, B(x): x是奇数(x)A(x)(x)B(x) (T) (x)(A(x)B(x) (F) 谓词逻辑 等价与蕴含式(x)A(x) (x)B(x): 对所有的x , A(x)成立; 或对所有的x, B(x)成立. (x)A(x)(x)B(x):存在着x,使A(

31、x)成立, 且存在x, 使B(x)成立. 第48页，共117页，2022年，5月20日，1点52分，星期六(5) 量词与联结词之间的一些蕴含式(x)A(x) (x)B(x) (x)(A(x)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)(A(x) B(x) (x)A(x) (x)B(x)常见的等价式与蕴含式见表2-5.1同理可得谓词逻辑 等价与蕴含式第49页，共117页，2022年，5月20日，1点52分，星期六(6) 多个量词的使用公式中多个量词的出现次序关系到命题的含义,不能随意交换.例如 xy A(x,y):

32、 对任意x ,都存在y, 使得A成立.例 (x) (y)(x+y=0) 为真命题 , y = -x yxA (x,y) : 存在着y, 对所有的x 都有A成立. (y) (x)(x+y=0) 为假命题谓词逻辑 等价与蕴含式 y 的值独立于x .y 的值依赖于x .第50页，共117页，2022年，5月20日，1点52分，星期六特殊情况:全称量词之间可交换,存在量词之间可交换.全称与存在之间存在如下关系:I18 (x) (y)A(x,y) ( y)(x)A(x,y)I19 (x) (y)A(x,y) ( x)(y)A(x,y)I20 (y) (x)A(x,y) ( x)(y)A(x,y)I21

33、(x) (y)A(x,y) ( y)(x)A(x,y)I22 (x) (y)A(x,y) ( y)(x)A(x,y)I23 (y) (x)A(x,y) ( x)(y)A(x,y)谓词逻辑 等价与蕴含式xyy xyxy xyxxy xyyx第51页，共117页，2022年，5月20日，1点52分，星期六例题谓词逻辑 等价与蕴含式右式验证 (x)(A(x)B(x) (x)A(x)(x)B(x) (x)A(x) (x) B(x) (x)A(x) (x) B(x) (x)(A(x) B(x) )(x)(A(x) B(x) )证明 (x)P(x)(x)P(x)为永真式。 证明 (P(x)(Q(x) P(

34、x) 为永假式。 第52页，共117页，2022年，5月20日，1点52分，星期六例题谓词逻辑 等价与蕴含式 (x)P(x) (x)P(x) 分析真值法:左右 且 右左. 给定公式(x)P(x)(x)P(x) 一组解释I,若 (x)P(x) 在 I下为真,则(x)P(x)为假,即存在 aD,使P(a)为假,即P(a) 为真,即(x)P(x)为真. 给定(x)P(x) (x)P(x) 一组解释I,若(x) P(x)在I下为真,则存在 aD,使 P(a)为真,即P(a)为假,即(x)P(x)为真.则(x)P(x)为假,第53页，共117页，2022年，5月20日，1点52分，星期六-1 谓词的概念

35、与表示-2 量词-3 谓词公式-5 等价式与蕴含式 -7 谓词演算的推理理论26 前束范式谓词逻辑 -4 谓词公式的解释第54页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 前束范式2-6前束范式定义 2-6.1 一个公式,如果量词均在全式的开头,它们的作用域,延伸到整个公式的末尾,则该公式叫做前束范式。前束范式简记为:(v1)(v2).(vn) A或指导变元母式(不含量词)例如 (x) (y) (z)( Q(x,y) R(z) (x)P(x) ( x)Q(x) ? Q(x,y) R(z)定理2-6.1 任一谓词公式,均和一个前束范式等价.第55页，共117页，2022年，

36、5月20日，1点52分，星期六化前束范式的方法 (1).将公式中的连接词化为,.(非必须) (2).利用否定律,德.摩根律,及量词转化律,将否 定深入到谓词字母前. (3).利用换名规则或代入规则使所有约束变元均 不相同且使所有的自由变元与约束变元不同. (4).利用量词的的扩张与收缩,扩大量词的辖域 至整个公式.谓词逻辑 前束范式例如 (x) P(x,y)Q(x)(x)P(x) (x)Q(x) 第56页，共117页，2022年，5月20日，1点52分，星期六因为 (x)P(x) (y)P(y), (x)P(x) (y)P(y),所以,若谓词公式中有变元既约束出现,又自由出现,为避免混淆,可对

37、约束变元进行换名或对自由变元代入,使得一个变元在公式中只呈一种出现. (1)对约束变元换名,其更改的变元名称范围是:量词 中的指导变元及该量词辖域中出现的该变元,而 公式中其余变元不变.(2)对约束变元换名时一定要更改为辖域中未出现 的变元名.换名规则 例如 (x)P(x) (x)Q(x) (x)P(x) (y)Q(y) 谓词逻辑 前束范式 (x) (y) (P(x) Q(y) ) (x) (P(x)R(x, y) Q(x,y)=?第57页，共117页，2022年，5月20日，1点52分，星期六代入规则(1).代入须对公式中该自由变元的所有出现同 时进行.(2).代入的变元不能与公式中其它变元

38、同名. 例如 (x)P(x) Q(x,y) (x)P(x) Q(r, y) (x)(y)P(x,y) R(x,y,z) (x)(y)P(x,y) R(u,v,z) (x)(y)(P(x,y) R(u,v,z) 谓词逻辑 前束范式第58页，共117页，2022年，5月20日，1点52分，星期六(v1) (v2) (vn)(其中可能是量词或,vi (i=1,2,n)是指导变元, Aij是原子公式或其否定。定义2-6.2 一个wff A如果具有如下形式称为前束合取范式例如 (x) (z) (y)( P(x ,y) (z=b) (Q(y)(a=b)定理2-6.2 每一个wff A都可以转换为与它等价的

39、前束合取范式。谓词逻辑 前束范式第59页，共117页，2022年，5月20日，1点52分，星期六其中可能是量词或,vi (i=1,2,n)是客体变元,Aij是原子公式或其否定。定义2-6.3 一个wff A如果具有如下形式称为前束析取范式例如 (x) (z) (y)( P(x, y) (z=b) (Q(y) (a=b)定理2-6.3 每一个wff A都可以转换为与它等价的前束析取范式。(v1) (v2) (vn)(谓词逻辑 前束范式第60页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 前束范式化前束范式的方法 (1).将公式中的连接词化为,.(非必须) (2).利用否定律,

40、德.摩根律,及量词转化律,将否 定深入到谓词字母前. (3).利用换名规则或代入规则使所有约束变元均 不相同且使所有的自由变元与约束变元不同. (4).利用量词的的扩张与收缩,扩大量词的辖域 至整个公式.前束范式：(v1)(v2).(vn) A第61页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 前束范式例题 xyz(P(x,z)P(y,z)uQ(x,y,u) 化为前束析取范式 .第62页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 前束范式例题 x yP(x) zQ(z, y) yR(x, y)的前束合取范式原式消去多余xP(x)zQ(z, y)y R

41、(x, y)换名xP(x)zQ(z, y)wR(x, w)自由w消去其它x(P(x)zQ(z, y)wR(x, w)否定深入x(P(x)zQ(z,y)wR(x,w)量词提出x zw(P(x)Q(z,y)R(x, w)分配律 xz w(P(x) R(x, w) (Q(z,y) R(x,w)量词w联结词前束析取范式第63页，共117页，2022年，5月20日，1点52分，星期六作 业2-5 （4）, （6） 2-6 (1) (a) (2) (a), (b)谓词逻辑 前束范式本节重点掌握的概念: 谓词演算的永真式，重言式，等价式, 蕴含式; 前束范式.本节重点掌握的方法: 证明永真式，等价式, 求前

42、束合取范式, 析取范式.第64页，共117页，2022年，5月20日，1点52分，星期六-1 谓词的概念与表示-2 量词-3 谓词公式-5 等价式与蕴含式 26 前束范式谓词逻辑 -4 谓词公式的解释 -7 谓词演算的推理理论第65页，共117页，2022年，5月20日，1点52分，星期六2-7 谓词演算的推理理论 设H1,H2Hn和C是谓词公式, 当且仅当 H1H2,HnC称C是一组前提H1,H2Hn的有效结论.等价演算、 分析真值、 证明法。判定谓词公式永真的各种方法都可用于判断推理正确性谓词逻辑 谓词演算的推理. 等价演算：AB 即 A B T例： xP(x) xQ(x) x（P(x)

43、Q(x) ） 分析真值：设前件在一组解释下为真,推出后件也真； 或证明后件在一组解释下为假时，前件也为假。第66页，共117页，2022年，5月20日，1点52分，星期六要证C是一组前提H1,H2Hn的有效结论, 需证 : H1H2,HnC 是重言式 即证: H1,H2Hn 均为真时, C必为真. 为描述这样一个推理过程,可构造一个命题公式序列: 其中每个公式或是前提,或是由某些前提利用推理规则推出的.序列的最后一个命题公式就是所要结论.这样一个描述推理过程的命题公式序列称为形式论证 (证明或演绎法).证明法谓词逻辑 谓词演算的推理.第67页，共117页，2022年，5月20日，1点52分，星

44、期六P规则(前提引入规则):前提在推理过程中的任何时候均可引用.T规则(结论引入规则):在推理过程中,如有一个或多个公式蕴含公式 S,则 S可引入推导过程.推理规则命题逻辑 推理理论 由于谓词公式中包含量词,还需增加一组处理量词的推理规则. 首先命题逻辑中的推理规则都可应用于谓词逻辑的推理中:第68页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑 谓词演算的推理.(1)全称指定规则 US含义:若D中所有个体使A真,则 D中任一个体t也使A真.例 (x) (y) (x y) P (不存在最大实数) 例 (x) P(x) : 所有的人都是要死的 P P(a) : 苏格拉底是要死的

45、. US (y) (a y) US 或 (y) (x y) US (y) (y谓词演算的推理.第70页，共117页，2022年，5月20日，1点52分，星期六(3)存在指定规则 ES含义:若D中存在个体使A真,则D中必有某个体c使A真. 使用限制:(x)A(x)为闭式,c为一个新常元(歧义名称).(4)存在推广规则 EG含义: 若项t使A真,则D中存在个体使A为真.谓词逻辑 谓词演算的推理. 使用限制: x 不能与A(t)中的自由变元或指导变元同名第71页，共117页，2022年，5月20日，1点52分，星期六例 (2) (y) (x y) US (3) x a ES(1) (x) (y) (

46、x y) P取 D:有理数(4) (x) (x a) UG(5) (y) (x) (x 谓词演算的推理.不是闭式例 (2) F(a) ES 证明: (x) F(x) F(a) (1) (x) F(x) P不是新常元第72页，共117页，2022年，5月20日，1点52分，星期六(1) (x)Q(x) P(2) (x)Q(x) P (3) Q(a) T1, ES(4) Q(a) T2, ES(5) Q(a) Q(a) T3,4(6) (x)(Q(x) Q(x) T5,EG 例 Q(x): x是有理数 D:实数(1) (x)Q(x) P(2) (x)Q(x) P (3) Q(a) T1, ES (

47、4) Q(b) T2, ES(5) .谓词逻辑 谓词演算的推理.不是新常元第73页，共117页，2022年，5月20日，1点52分，星期六例 (2)(x)F(x) P (3)F(a) G(a), US(1)(x) (F(x)G(x) ) P前提: (x) (F(x)G(x) ), (x)F(x)结论: (x)G(x)(4)F(a) ES(5)G(a) EG不是新常元(6)(x)G(x) EG (2)(x)F(x) P (4)F(a) G(a) ES(1)(x) (F(x)G(x) ) P(3)F(a) UG(5)G(a) EG(6)(x)G(x) EG谓词逻辑 谓词演算的推理.第74页，共11

48、7页，2022年，5月20日，1点52分，星期六谓词逻辑 谓词演算的推理.例题1 证明 (x)(H(x)M(x) H(s) M(s)证明 (1). (x)(H(x)M(x) P (2). H(s)M(s) US,T1 (3). H(s) P (4). M(s) T2,3, I13(苏格拉底三段论)P76例题1第75页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词例题2 证明 (x)(C(x)W(x)R(x) ) (x)(C(x) Q(x) (x)(Q(x) R(x)证明 (1). (x)(C(x)Q(x) P (2). C(a) Q(a ) T2,ES (3).

49、C(a) T3, I1 (5). (x)(C(x)W(x)R(x) ) P (6). C(a)W(a)R(a) T1,3, US (4). Q(a) T3 (7). W(a)R(a) T4,5, I (8). R(a) T6,I (9). Q(a)R(a) T7,8, I1P77例题2 (10). (x)(Q(x)R(x) T9, EG第76页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词例题3 ( x)(P(x) Q(x) (x)P(x) (x)Q(x)(CP规则) x(P(x)Q(x) xP(x)xQ(x) (1). xP(x) 附加P (2). xP(x)

50、T1, E (3). P(c) T2, ES (6). Q(c) T3,5,I (4). x(P(x)Q(x) P (7). xQ(x) T6,ES (5). P(c)Q(c) T4, US (8). xP(x)xQ(x) CP规则P77例题3第77页，共117页，2022年，5月20日，1点52分，星期六例题3 (x)(P(x) Q(x) (x)P(x) (x)Q(x)(归谬法) (1). (x)P(x)(x)Q(x) 附加 P (2). (x)P(x)(x)Q(x) T1,E (3). (x)P(x) T2, E (4). (x)P(x) T3, E (5). (x)Q(x) T2, I1

51、 (6). (x)Q(x) T5, E (7). P(c) T4,ES (8). Q(c) T6, US (9). P(c)Q(c) T7,8,I (10). (P(c)Q(c) T9,E (11). (x)(P(x)Q(x) P (13). (P(c)Q(c)(P(c) Q(c) T10,12 (12). P(c)Q(c) T11, USP77例题3第78页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词补例 所有的有理数是实数. 某些有理数是整数. 因此, 某些实数是整数. 设: R(x): x是实数 Q(x): x是有理数 P(x): x是整数x(Q(x) R

52、(x), (x) (Q(x) P(x) ) (x) (R(x) P(x)x（Q(x) R(x)）(x) (Q(x) P(x) )(x) (R(x) P(x) )第79页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词补例 每个用功的学生考试不会不及格。 小张是用功的学生。 所以，小张考试及格。设: P(x): x考试及格 Q(x): x是学生 R(x): x是用功的。 a:小张x（Q(x) R(x) P(x)）R (a) Q(a) P (a) Q(a)第80页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词 4. 设R(x):x是实数,

53、P(x): x是有理数, “并非每个实数都是有理数” 符号化为 ( ) A. x ( ( R(x) P( x ) ) B. x ( R(x) P( x ) ) 5. 谓词公式 x P(x)x Q(x)x P(x) 的类型是_. 6. 在解释I:DI=1,2, P(1,1)= P(1,2) =0, P(2,2)=P(2,1)=1下, 谓词公式 x y P(x,y)的真值为_ . 7. 公式x P(x)x Q(x,y) 前束合取范式为_.课堂练习1. 在谓词逻辑中,永真式都是重言式。( )2. 任意谓词公式都有唯一的前束范式与之等价。( ) 3. (x)(A(x)B(x) (x)A(x) (x)B

54、(x) ( ) 第81页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词 8 所有的有理数是实数. 所有的无理数是实数. 虚数不是实数， 所以虚数不是有理数也不是无理数. 设: R(x): x是实数 Q(x): x是有理数 P(x): x是无理数。S(x): x是虚数x（Q(x) R(x)） x（P(x) R(x)）x（S(x) R(x)）x（S(x) Q(x) P(x) ）第82页，共117页，2022年，5月20日，1点52分，星期六命题逻辑 逻辑连接词作 业2-7 （1）（a）,（b） （2） 本节重点掌握的概念: 4个推理规则本节重点掌握的方法: 推理的形式

55、证明方法第83页，共117页，2022年，5月20日，1点52分，星期六谓 词 逻 辑Predicate Logic第二章本 章 小 结谓词逻辑小结 第84页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑小结 一. 谓词的概念和表示 量词和特性谓词 谓词重点掌握的基本概念和方法(一) 个体和个体域谓词公式的翻译 (命题符号化)一元谓词: A( x )n元谓词: A( x1,.xn)个体常元: a,b,c.个体变元: x,y,z.D:个体域全称量词: (x)A(x)存在量词: (x)A(x) (x)(P(x)A(x) (x)( P(x)A(x) )特性谓词P(x)第85页，共1

56、17页，2022年，5月20日，1点52分，星期六谓词逻辑小结 重点掌握的基本概念和方法(二)二.谓词公式及其解释 谓词公式的递归定义 谓词公式的解释 与赋值 变元的约束 求谓词公式在一组解释下的真值有限域无限域 指导变元与辖域 自由变元与约束变元 开式与闭式1).指定个体域DI.2).指定个体常元3).指定个体函数.4).指定谓词5).指定自由变元开式闭式第86页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑小结 三. 公式类型及相互关系重点掌握的基本概念和方法(三)判别公式的类型或等价 公式的类型 等价公式AB : 即 AB 永真 蕴含公式AB : 即 AB 永真代入定理

57、等价演算分析真值 永真式与重言式 永假式 可满足式 AB Iff AB且BA第87页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑小结 四. 前束范式重点掌握的基本概念和内容(四) 前束范式 (v1)(v2).(vn) A 前束析取范式 前束合取范式 换名规则求前束范式的方法步骤 对约束变元换名 对自由变元代入第88页，共117页，2022年，5月20日，1点52分，星期六谓词逻辑小结 构造推理证明归谬法CP规则直接证法五. 推理理论 有效推理: H1H2,Hn C 推理规则:重点掌握的基本概念和方法(五) 前提引入规则 P 结论引入规则 T 全称推广规则 UG 存在推广规则

58、 EG 全称指定规则 US 存在指定规则 ES 第89页，共117页，2022年，5月20日，1点52分，星期六一.在谓词逻辑中将命题符号化1.判断是否复合命题(看有几个主谓结构或连接词).2.对复合命题找出每个原子命题.3.对每个原子命题分出主语和谓语,主语若是泛指需加量 词和特性谓词.并用符号表示.4.分析各原子命题的关系,确定连接词.1.直线A平行于直线B ，当且仅当直线A不相交于直线B.2.如果有限个数的乘积为0,则至少有一个因子等于03.对每一个实数x存在着一个更大的实数y.4.存在着实数x,y,z,使得x与y之和大于x与y之积.5.若xy, zy*z谓词逻辑小结 第90页，共117

59、页，2022年，5月20日，1点52分，星期六谓词逻辑小结 二.求公式在给定解释下的真值P66 3) a) x( P(x) Q(x) ) (T)其中, P(x): x=1 ,Q(x):x=2 , D:1, 2 P66 3) b) x( PQ(x) ) R(a) (F)其中, P: 21 , Q(x):x5, a=5, D:-2, 3, 6 P72 2) d) xy (P(x)Q(x,y) ) (F)其中, D:1, 2 ,a=1; P(1)=F , P(2)=T, Q(1,1)=T , Q(1, 2)=T, Q(2,1)=F ,Q(2, 2)=F xA(x) A(a1)A(a1).A(an)

60、xA(x) A(a1)A(a1).A(an)DI为有限域第91页，共117页，2022年，5月20日，1点52分，星期六三.判定公式类型和等价1.证明谓词公式A是命题永真式的代入实例(重言式)2.利用等价演算证明公式AT3.证明蕴含AB, 只需证AB永真.P72 7) x y ( p(x) Q(y) ) x p(x) y Q(y) P72 4) x(A(x) B(x) xA(x) x B(x) 谓词逻辑小结 第92页，共117页，2022年，5月20日，1点52分，星期六四.求前束范式P75 2) a) (xP(x) xQ(x) ) x (P(x) Q(x) T P75 2) b) x ( p