离散数学 第二章.ppt

1、第四篇图论,1.命题逻辑,2.谓词逻辑,3.集合与关系,4.函数,6.布尔代数,5.代数结构,目录,.图论,第一篇数理逻辑,第二篇集合论,第三篇代数结构,绪论,用命题逻辑处理苏格拉底三段论：,谓词逻辑,又例: 张华是大学生,李明也是大学生。,所有的自然数都等于1.(F); 存在着自然数等于1.(T),P,Q,R,人总是要死的,苏格拉底是人,苏格拉底是要死的。,若论证有效则有: PQR,即 PQR 永真.,谓词逻辑,对简单命题作进一步分析,分离出个体和谓词, 并考虑到泛指和特指 (全称和存在),在此基础 上,研究命题的逻辑结构及命题间的推理关系。,Predicate Logic,第二章,-1 谓

2、词的概念与表示,-2 量词,-3 谓词公式,-5 等价式与重言式,-7 谓词演算的推理理论,26 前束范式,谓词逻辑,-4 谓词公式的解释,命题是具有确定真值的陈述句。,2-1谓词的概念和表示,如 “电子计算机是科学技术的工具。”,个体:思维的对象,可以是具体的事物或抽象的概念,谓词:刻画个体性质或个体之间关系的词。,1. 个体和谓词,陈述句由主语和谓语两部分构成，,主语,谓语,个体,谓词,一元谓词: 与一个个体相关联的谓词.(描述个体性质),N元谓词: 与N个个体相关联的谓词.(描述个体间的关系),谓词逻辑 谓词的概念和表示,(a).他是三好学生。,(b).7 是质数。,(c).每天作广播操

3、是好习惯。,(d).5 大于 3.,(e).地球绕着太阳转。,一元谓词。 谓词刻画个体性质,(f).张明和张亮是兄弟。,(e).上海位于南京和杭州之间。,谓词刻 画个体 间关系。,在谓词逻辑中,命题是由一个谓词和若干有序个体组成的。,谓词逻辑 谓词的概念和表示,二元谓词,二元谓词,二元谓词,三元谓词,2.个体和谓词的表示,命题由一个谓词和若干个体组成,谓词逻辑 谓词的概念和表示,用大写字母 A, B , C, D,. 代表谓词。 用小写字母代表个体 ： 用小写字母 a , b, c. 表示特定个体: 个体常元 用小写字母 x,y,z.表示任意个体：个体变元.,一个 n 元谓词记作: A ( x

4、1 , x2, xn) 其中 x1 , x2,xn 为个体变元.当A ( x1 , xn)中个体变元用个体常元: a1,an 代入后, A(a1an) 就成为一个命题。,则 A (a) 表示命题: 张华是大学生, A (b) 表示命题: 李明是大学生。,例: 令 A(x) : x 是大学生; a:张华 , b:李明,命题由一个谓词和若干个体组成，但并非任意个体都和任意谓词都能构成命题。,如 2 是偶数,(T),个体域:个体的取值范围,用D表示,如谓词 “. 是偶数” 的个体域 D: 全体整数。 “.是要死的” D:全体生物 或 D: 人类,全总个体域:所有个体的集合称之。,谓词逻辑 谓词的概念

5、和表示,3 是偶数,(F),x 是偶数 (不是命题),当谓词确定后,其允许的个体取值范围称为个体域。,则 A (a) 表示命题: 张华是大学生, A (b) 表示命题: 李明是大学生。,例: 令 A(x) : x 是大学生; D:人类 a:张华 ,b:李明,又例: 上海位于南京和杭州之间。,令 L (x ,y,z) : x 位于 y 和 z 之间, D: 城市,则命题符号化为: L(a,b,c),谓词逻辑 谓词的概念和表示,则 L(2,3) 表示命题: 23. (真),又例: 设 L (x,y) : x 小于 y, D: 实数集合,则 L(5,1):表示命题: 51. (假),a:上海 b:

6、南京 c:杭州,当谓词及其个体域确定后，命题的真值与个体的取值有关，因此一个谓词可看作是一个以个体为自变量,函数值取真值的函数。,由简单命题及连接词可构成复合命题。,与命题逻辑同,张华和李明都是大学生。,例1,P (x) : x 是大学生 , D:人, a:张华, b:李明,命题符号化: P(a)P(b),如果张三比李四高, 李四比王五高, 则张三比王五高。,命题符号化: P(a,b) P(b,c) P( a,c),例3,p:(x,y) x 比 y 高, D: 人;,a: 张三, b: 李四, c: 王五,2 既是偶数又是素数。,例2,P (x) : x 是偶数 , Q(x): x 是素数 ,

7、 D:整数, a: 2,命题符号化: P(a) Q(a),谓词逻辑 谓词的概念和表示,3.复合命题,例如: 张华的母亲爱张华. 设 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), g(a,b) ) 或 P( 2+3, 23 ),自变量和函数值均为个体域中的个体.用小写字母f,g.表示.,谓词逻辑 量词,4.个体函数,例如: 张华的母亲爱

8、张华.,-1 谓词的概念与表示,-2 量词,-3 谓词公式,-5 等价式与蕴含式,-7 谓词演算的推理理论,26 前束范式,谓词逻辑,-4 谓词公式的解释,例如: 任何人都是要死的.(T),有些人是聪明的.(T),所有的自然数都等于1.(F),存在着自然数等于1.(T),对个体域中的 所有个体成立,对个体域中的 某些个体成立,当命题的主语是泛指时,命题的真值还取决于谓词与个体域中个体的数量关系.,谓词逻辑 量词,2-2量词,1.全称量词与存在量词,两种,量词:命题中表示个体数量的词。,全称量词(Universal Quantifier): 表示个体域中全体个体的词，记作 相当于 “任意”,“凡

9、是”,“所有”.,若个体域中所有个体x,均使A(x)为真,记作(x)A(x),存在量词(Existential Quantifier): 表示个体域中部分个体的词， 记作 相当于 “存在”,“至少有一个”,“有些”.,若个体域中存在某些个体x,使A(x)为真,记作(x)A(x),谓词逻辑 量词,设H(x): x 是要死的,任何人都是要死的。,例如:,则命题表示为: (x)H(x),个体域D: 人类,又例如: 有些人是聪明的.,设A(x): x是聪明的,个体域 D:人类,则命题表示为: (x)A(x),谓词逻辑 量词,当在全总个体域中讨论命题时,需在命题表示中增加一个特性谓词,以给出个体变元的个

10、体域。,2.特性谓词,(1)带全称量词的命题,特性谓词作为 加入.,任何人都是要死的,例如:,M(x):x是人,则命题表示为：(x)(M(x)H(x),改为:,谓词逻辑 量词,设 H(x):x是要死的 个体域D: 全人类 则命题表示为：(x)H(x)。,H(x):x是要死的,条件式的前件,例如:有些人是聪明的.,个体域 D：人,设A(x)：x是聪明的,则命题表示为: (x)A(x),改为:,A(x)：x是聪明的,则命题表示为: (x)(M(x)A(x),(2)带存在量词的命题,特性谓词作为合取项加入。,为何特性谓词以前件加在全称量词后,而以合取项加在存在量词后? 能否改为:,(x)(H(x)

11、M(x) 和 (x)(M(x) A(x) ?,谓词逻辑 量词,M(x):x是人,3.命题符号化,谓词逻辑 量词,日常用语翻译,用谓词逻辑处理苏格拉底三段论：,人总是要死的, 苏格拉底是人,所以,苏格拉底是要死的。,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.分析各

12、原子命题的关系,确定连接词.,存在着最小的自然数.,谓词逻辑 量词,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),命题逻辑 逻辑连接词,作 业,2-1， 2-2 （1）（e）,（f）,（g）,（h） 2-3 （3）,本节重点掌握的概念: 个体，谓词, 量词, 个体域。 本节重点掌握的方法: 命题符号

13、化。特别注意特 性谓词的两种使用方法。,谓词逻辑 谓词公式,1.个体和谓词 2.谓词的表示: P(x1,x2,.xn) 每个命题有一个谓词和若干个体组成.当谓词确定后, 命题的真值依赖个体,因此采用函数的记法表示谓词,自变 量的取值范围称为个体域 D 3.量词:当句子的主语是泛指的时候,必须引入量词符号 4.特性谓词: 若在全总个体域讨论问题,还需在命题表达中 增加特性谓词,以说明命题中个体的取值范围. 5.命题符号化 “每个计算机系的学生都学离散数学“ “存在着偶素数”,谓词逻辑 谓词公式,北京是中国的首都 甲是乙的父亲 3介于2与4之间 3大于2仅当3大于4。 张三和李四是同班同学 天下乌

14、鸦一般黑 火车都比汽车跑得快 有的火车比所有汽车快。,课堂练习,在谓词逻辑中符号化：,-1 谓词的概念与表示,-2 量词,-3 谓词公式,-5 等价式与蕴含式,-7 谓词演算的推理理论,26 前束范式,谓词逻辑,-4 谓词公式的解释,2-3谓词公式,如 P, P(x), P(x,y), P( f(x), y ), P(a, y) 均原子公式。,1. 谓词公式,补充定义(项) 1).个体常元和个体变元是项. 2).若f 是n元个体函数,t1,.,tn是项,则 f(t1,.tn)是项. 3).只有有限次运用1),2)规则得到的符号串是项.,如 x, a, f(x), g(x,y), g( f (x

15、),a).,谓词逻辑 谓词公式,项代表公式中以各种形式出现的个体.,原子公式: 把A(t1, t2, tn)称为谓词演算的原子公式, 其中, t1, t2, tn是项.,不含个体变元的原子公式是原子命题.,定义 2-3.1 谓词演算的合式公式wff,由下述各条组成： (1)原子谓词公式是合式公式。 (2)若A是合式公式,则A是合式公式。 (3)若A和B都是合式公式,则(AB),(AB), (AB)和(AB) 是合式公式。 (4)如果A是合式公式,x是A中出现的任何变元, 则 (x)A和 (x)A都是合式公式。 (5)只有经过有限次的应用规则(1),(2),(3),(4) 所得到的公式是合式公式

16、。,简称谓词公式,如,xy P( x, y),x P( f(x), y),谓词逻辑 谓词公式,P(a,y) Q,2.变元的约束,若给定为一谓词公式,它可带有如下子公式:,( x) A( x ) 或 ( x) A( x ),指导变元,辖域,约束变元,其中,、 后的 x 称为该量词的指导变元; A(x)称为量词的作用域或辖域(scope);在辖域中 x 的一切出现称为x在中的约束出现,x称为约束变元;在中除约束变元以外所出现的变元称为自由变元。,P63例题1,如,x(M(x)R(x) ,yP(x, y)R(y),谓词逻辑 谓词公式,闭式:不含自由变元的公式. 开式:含有自由变元的公式. 其中,含有

17、k个自由变元 x1, x2,.xk的公式称为 k元谓词,记作A(x1,x2,.xk ),0元谓词为闭式.,例如 ( x) P( x,y,z ),x是小于100的质数: L(x,100),又如 任意的实数x,都存在着实数y,使得xy.（不存在最大实数）,令 P(x,y): xy , R( x): x是实数,x y(R( x)R(y) P( x, y ) ),谓词逻辑 谓词公式,闭式 (T),二元谓词,一元谓词,由命题符号化得到的公式是闭式.,-1 谓词的概念与表示,-2 量词,-3 谓词公式,-4 谓词公式的解释,-5 等价式与蕴含式,-7 谓词演算的推理理论,26 前束范式,谓词逻辑,谓词公式

18、的真值与那些因素有关?谓词公式的真值能否像命题逻辑那样总可由真值表给出?,例,xy (P(x) Q( f(x,a), y ,z )R) 的真值,给出个体域,指定谓词,2-4.谓词公式的解释,指定个体函数和个体,指定自由变元,谓词逻辑 谓词公式的解释,令 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): xy; Q(x,y): x+y=0 ,令x=2, y=1, (T) ; 令 x=1, y=2, (F),为公式中的每个自由

19、变元指定个体域DI中的一个个体.,谓词公式的一个解释I(Interpretation),解释I下的一个赋值,1).指定一个个体域DI. 2).为每个个体常元符号指定DI中的一个个体. 3).为每个n元个体函数符号指定DI上的n元个体函数. 4).为每个n元谓词符号指定一个DI上的n元谓词,闭式在一解释下有一确定真值.,开式在一组解释I及I下一个赋值下, 有一确定真值.,补例,谓词逻辑 谓词公式的解释,给定解释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(

20、x,y) L(x, y ),(2) yz E( h( y,z ), x ),解 在解释I下 E(x,y)为 x=y; L(x, y )为xy,当赋值为v1时,命题解释为:对任意自然数y,均有0y (T),当赋值为v2时,命题解释为:对任意自然数y,均有1y (F),解 在解释I下, E( h( y,z ), x ) 为 yz =x,当赋值为v1时,命题为:对任意自然数y,存在z 使得 yz=0 (T) 当赋值为v2时,命题为:对任意自然数y,存在z 使得 yz =1 (F),谓词逻辑 谓词公式的解释,补例,补例,设解释I的个体域为 a1, a2, an , 则在解释I下,xA(x) A(a1)

21、A(a1).A(an),xA(x) A(a1)A(a1).A(an),当个体域DI中的元素个数有限时,可将变元的所有 可能取值一一列举出来,此时量词可消除.,谓词逻辑 谓词公式的解释,谓词逻辑 谓词公式的解释,求下列闭式在解释I下的真值,给定解释I如下:D= 2, 3 , f (2)=3, f (3)=2, P(2)=T P(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) )

22、=(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)的真值?,补例,谓词逻辑 谓词公式的解释,求(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,

23、1)(P(1) Q( 1, 2 ) (P(2) Q(2,1)(P(2) Q( 2,2 ),= (FT) (F T) (F F) ( T T) ),= F,补例,谓词逻辑 谓词公式的解释,课堂练习 1.“并非一切推理都能用计算机完成”符号化为( ) 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.

24、个体域为自然数集合，F(x,y)为 yx C.个体域为自然数集合，F(x,y)为 x=y D. 均不属于A、B、C 6.在解释I:DI=a,b, P(a,a)=p(b,b)=0 P(a,b)=p(b,a)=1下, 公式x y P(x,y)的真值为_,作 业,2-4 （2）（b）,（c） （3） (4) 2-5 （1）（b） （2） (a), (d),谓词逻辑 谓词公式的解释,本节重点掌握的概念: 谓词公式, 自由变元,约束变元, 开式, 闭式。 本节重点掌握的方法: 求谓词公式的真值,要点回顾,谓词逻辑 等价与蕴含式,1.个体和谓词 2.谓词的表示: P(x1,x2,.xn) 3.量词 4.特

25、性谓词 5.谓词公式 6.谓词公式的赋值: 对谓词公式一个赋值称为一个解释。闭式在一组解释下会求得一个真值；开式还需在此基础上对自由变元赋值，才能求出一个真值。 例: 对任意的自然数x存在着自然数y ,使得 p(x,y) 成立. 解释1：p(x,y) :x=y,(T) 解释2：p(x,y) :x+y=0,(F),-1 谓词的概念与表示,-2 量词,-3 谓词公式,-7 谓词演算的推理理论,26 前束范式,谓词逻辑,-4 谓词公式的解释,-5 等价式与蕴含式,定义2-5.2, 2-5.3 如果公式A在任何解释下均为真,称A为永真式; 如果 A在某个解释I和I的一个赋值下为真,称A可满足; 如果公

26、式在任何解释下均 为假,称A为永假式.,2-5 等价与蕴含,1.永真式,当个体域有限时,原则上可用真值表法判定一公式永真永假或可满足；但当个体域无限时,真值表法失效.,代入定理 、 等价演算,永真(永假)式的判定：,谓词逻辑 等价与蕴含式,命题逻辑永真式（永假式）的代换实例是谓词逻辑的永真式（永假式）。,设A是包含命题变元 P1, P2,.Pn的命题公式, B1,B2,.Bn是谓词公式, 用 B1,B2,.Bn 分别代替P1,P2,.Pn 在A中的所有出现,得到的谓词公式B称A的代换实例,命题逻辑永真式的代换实例称为重言式.,谓词逻辑 等价与蕴含式,命题逻辑的代入定理:一个重言式,对同一分量都

27、用任何合式公式置换,结果仍重言.,谓词逻辑 等价与蕴含式,上式可看作命题公式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)P(x)为重言式,判定公式的类型,重言式是永真式 ,但永真未必重言.,例如 xP( x ) xP( x ) 是永真式，但不是重言式.,补例,2.等价与蕴含,定义 2-5.1 设A,B是公式,若AB是永真式,则称 A,B等价.记作AB.,

28、等价式的判定,等价演算:利用基本公式、等价的性质 和 置换 定理，推演出其他等价式.,定义 2-5.2 设A,B是公式,若AB是永真式,则称 A蕴含B.记作AB.,谓词逻辑 等价与蕴含式,AB 当且仅当 A B且B A,(1) 命题公式的推广,例如 PQPQ,用 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),利用代入定理,将命题逻辑的所有等价式推广到谓词逻辑.,谓词逻辑 等价与蕴含式,(2) 量词与联结词的关

29、系,例 设 P(x) : x今天来校上课, D:学生 则 P(x)表示: x今天没来校上课,“并非所有人今天来校上课” (x)P(x) 等价 “有人今天没来校上课” (x)P(x),(x)P(x) (x)P(x),“ 没有人今天来校上课” (x) P(x) 等价 “所有人今天都没来校上课” (x)P(x),(x) P(x) (x)P(x),谓词逻辑 等价与蕴含式,(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

30、) B),B (x) A(x) (B (x)A(x),B (x)A(x) (B (x)A(x),由上式可推出,谓词逻辑 等价与蕴含式,(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),对满足分配律,对满足分配律,“联欢会上所有人即唱歌又跳舞

31、. ”,谓词逻辑 等价与蕴含式,(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)或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

32、(x)成立.,(x)A(x)(x)B(x):存在着x,使A(x)成立, 且存在x, 使B(x)成立.,(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,同理可得,谓词逻辑 等价与蕴含式,(6) 多个量词的使用,公式中多个量词的出现次序关系到命题的含义,不能随意交换.,例如,xy A(x,y): 对任意x ,都存在y, 使得A成立.,例 (x

33、) (y)(x+y=0) 为真命题 , y = -x,yxA (x,y) : 存在着y, 对所有的x 都有A成立.,(y) (x)(x+y=0) 为假命题,谓词逻辑 等价与蕴含式,y 的值独立于x .,y 的值依赖于x .,特殊情况:,全称量词之间可交换,存在量词之间可交换.,全称与存在之间存在如下关系:,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 (x) (y)A(x,y) ( y)(x)A(x,y),I22 (x) (y)A(x,y)

34、( y)(x)A(x,y),I23 (y) (x)A(x,y) ( x)(y)A(x,y),谓词逻辑 等价与蕴含式,例题,谓词逻辑 等价与蕴含式,右式,验证 (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(x) 为永假式。,例题,谓词逻辑 等价与蕴含式,(x)P(x) (x)P(x),分析真值法:左右 且 右左., 给定公式(x)P(x)(x)P(x) 一组解释I,若 (x)P(

35、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)为假,-1 谓词的概念与表示,-2 量词,-3 谓词公式,-5 等价式与蕴含式,-7 谓词演算的推理理论,26 前束范式,谓词逻辑,-4 谓词公式的解释,谓词逻辑 前束范式,2-6前束范式,定义 2-6.1 一个公式,如果量词均在全式的开头,它们的作用域,延伸到整个公式的末尾,则该公式叫做前束范式。,前束范式简记为:

36、,(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 任一谓词公式,均和一个前束范式等价.,化前束范式的方法,(1).将公式中的连接词化为,.(非必须) (2).利用否定律,德.摩根律,及量词转化律,将否 定深入到谓词字母前. (3).利用换名规则或代入规则使所有约束变元均 不相同且使所有的自由变元与约束变元不同. (4).利用量词的的扩张与收缩,扩大量词的辖域 至整个公式.,谓词逻辑 前束范式,例如 (x) P(x,y)Q(x),(x)P(x) (

37、x)Q(x),因为 (x)P(x) (y)P(y), (x)P(x) (y)P(y), 所以,若谓词公式中有变元既约束出现,又自由出现,为避免混淆,可对约束变元进行换名或对自由变元代入, 使得一个变元在公式中只呈一种出现.,(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)

38、=?,代入规则,(1).代入须对公式中该自由变元的所有出现同 时进行. (2).代入的变元不能与公式中其它变元同名.,例如 (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),谓词逻辑 前束范式,(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=

39、b),定理2-6.2 每一个wff A都可以转换为与它等价的 前束合取范式。,谓词逻辑 前束范式,其中可能是量词或,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)(,谓词逻辑 前束范式,谓词逻辑 前束范式,化前束范式的方法,(1).将公式中的连接词化为,.(非必须) (2).利用否定律,德.摩根律,及量词转化律,将否 定深入到谓词字母

40、前. (3).利用换名规则或代入规则使所有约束变元均 不相同且使所有的自由变元与约束变元不同. (4).利用量词的的扩张与收缩,扩大量词的辖域 至整个公式.,前束范式：(v1)(v2).(vn) A,谓词逻辑 前束范式,例题 xyz(P(x,z)P(y,z)uQ(x,y,u) 化为前束析取范式 .,谓词逻辑 前束范式,例题 x yP(x) zQ(z, y) yR(x, y) 的前束合取范式,原式,消去多余,xP(x)zQ(z, y)y R(x, y),换名,xP(x)zQ(z, y)wR(x, w),自由,w,消去其它,x(P(x)zQ(z, y)wR(x, w),否定深入,x(P(x)zQ(

41、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,联结词,前束析取范式,作 业,2-5 （4）, （6） 2-6 (1) (a) (2) (a), (b),谓词逻辑 前束范式,本节重点掌握的概念: 谓词演算的永真式，重言式，等价式, 蕴含式; 前束范式. 本节重点掌握的方法: 证明永真式，等价式, 求前束合取范式, 析取范式.,-1 谓词的概念与表示,-2 量词,-3 谓词公式,-5 等价式与蕴含式,26 前束范式,谓词逻辑,-4 谓词公式的解释,-7 谓词演算的推理理论,2-7

42、谓词演算的推理理论,设H1,H2Hn和C是谓词公式, 当且仅当 H1H2,HnC 称C是一组前提H1,H2Hn的有效结论.,等价演算、 分析真值、 证明法。,判定谓词公式永真的各种方法都可用于判断推理正确性,谓词逻辑 谓词演算的推理.,等价演算：AB 即 A B T,例： xP(x) xQ(x) x（P(x) Q(x) ）,分析真值：设前件在一组解释下为真,推出后件也真； 或证明后件在一组解释下为假时，前件也为假。,要证C是一组前提H1,H2Hn的有效结论, 需证 : H1H2,HnC 是重言式 即证: H1,H2Hn 均为真时, C必为真. 为描述这样一个推理过程,可构造一个命题公式序列:

43、其中每个公式或是前提,或是由某些前提利用推理规则推出的.序列的最后一个命题公式就是所要结论.这样一个描述推理过程的命题公式序 列称为形式论证 (证明或演绎法).,证明法,谓词逻辑 谓词演算的推理.,P规则(前提引入规则):前提在推理过程中的任何 时候均可引用. T规则(结论引入规则):在推理过程中,如有一个或 多个公式蕴含公式 S,则 S可引入推导过程.,推理规则,命题逻辑 推理理论,由于谓词公式中包含量词,还需增加一组处理量词的推理规则.,首先命题逻辑中的推理规则都可应用于谓词逻辑的推理中:,谓词逻辑 谓词演算的推理.,(1)全称指定规则 US,含义:若D中所有个体使A真,则 D中任一个体t

44、也使A真.,例 (x) (y) (x y) P (不存在最大实数),例 (x) P(x) : 所有的人都是要死的 P, P(a) : 苏格拉底是要死的. US, (y) (a y) US 或 (y) (x y) US,(y) (y y) ?,或 P(x) : x是要死的. US,使用限制: t 不能与其它指导变元同名.,(2)全称推广规则 UG,含义: 若D中任意一个体使A真,则D中所有个体都 使A真.,使用限制: x 不能是前提中的自由变元.,例: P(x) : x是偶数 D:正整数 . (1) P(x) P (2) (x) P(x) UG ?,谓词逻辑 谓词演算的推理.,(3)存在指定规则

45、 ES,含义:若D中存在个体使A真,则D中必有某个体c使A真.,使用限制:(x)A(x)为闭式,c为一个新常元(歧义名称).,(4)存在推广规则 EG,含义: 若项t使A真,则D中存在个体使A为真.,谓词逻辑 谓词演算的推理.,使用限制: x 不能与A(t)中的自由变元或指导变元同名,例,(2) (y) (x y) US,(3) x a ES,(1) (x) (y) (x y) P,取 D:有理数,(4) (x) (x a) UG,(5) (y) (x) (x y) EG,谓词逻辑 谓词演算的推理.,不是闭式,例,(2) F(a) ES,证明: (x) F(x) F(a),(1) (x) F(

46、x) P,不是新常元,(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,(4) Q(b) T2, ES,(5) .,谓词逻辑 谓词演算的推理.,不是新常元,例,(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)

47、 结论: (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,谓词逻辑 谓词演算的推理.,谓词逻辑 谓词演算的推理.,例题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,命题逻辑 逻辑连接

48、词,例题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). 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, I1,P77例题2,(10). (x)(Q(x)R(x) T9, EG,命题逻辑 逻辑连接词,例题3 ( x)(P(x

49、) 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) 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,例题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)

50、P(x) T2, E,(4). (x)P(x) T3, E,(5). (x)Q(x) T2, I1,(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, US,P77例题3,命题逻辑 逻辑连接词,补例 所有的有理数是实数. 某些有理数是整数. 因此, 某些实数是整数.,设: R(x): x是实数 Q(x): x是有理

51、数,P(x): x是整数,x(Q(x) R(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) ),命题逻辑 逻辑连接词,补例 每个用功的学生考试不会不及格。 小张是用功的学生。 所以，小张考试及格。,设: 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),命题逻辑 逻辑连接词,4. 设R(x):x是实数, P(x): x是有理数, “并非每个实数都是有理数” 符号化为 (

52、) 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(x) ( ),命题逻辑 逻辑连接词,8 所有的有理数是实数.

53、 所有的无理数是实数. 虚数不是实数， 所以虚数不是有理数也不是无理数.,设: 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) ）,命题逻辑 逻辑连接词,作 业,2-7 （1）（a）,（b） （2）,本节重点掌握的概念: 4个推理规则 本节重点掌握的方法: 推理的形式证明方法,谓 词 逻 辑,Predicate Logic,第二章,本 章 小 结,谓词逻辑小结,谓词逻辑小结,一. 谓词的概念和表示,量词和特性谓词,谓词,重点掌握的基本概念和

54、方法(一),个体和个体域,谓词公式的翻译 (命题符号化),一元谓词: 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),谓词逻辑小结,重点掌握的基本概念和方法(二),二.谓词公式及其解释,谓词公式的递归定义,谓词公式的解释 与赋值,变元的约束,求谓词公式在一组解释下的真值,有限域,无限域,指导变元与辖域 自由变元与约束变元 开式与闭式,1).指定个体域DI. 2).指定个体常元 3).指定个体函数.

55、4).指定谓词 5).指定自由变元,开 式,闭 式,谓词逻辑小结,三. 公式类型及相互关系,重点掌握的基本概念和方法(三),判别公式的类型或等价,公式的类型,等价公式AB : 即 AB 永真,蕴含公式AB : 即 AB 永真,代入定理,等价演算,分析真值,永真式与重言式 永假式 可满足式,AB Iff AB且BA,谓词逻辑小结,四. 前束范式,重点掌握的基本概念和内容(四),前束范式 (v1)(v2).(vn) A,前束析取范式 前束合取范式,换名规则,求前束范式的方法步骤,对约束变元换名 对自由变元代入,谓词逻辑小结,构造推理证明,归谬法,CP规则,直接证法,五. 推理理论,有效推理: H1H2,Hn C,推理规则:,重点掌握的基本概念和方法(五),前提引入规则 P 结论引入规则 T 全称推广规则 UG 存在推广规则 EG 全称指定规则 US 存在指定规则 ES,一.在谓词逻辑中将命题符号化,1.判断是否复合命题(看有几个主谓结构或连接词). 2.对复合命题找出每个原子命题. 3.对每个原子命题分出主语和谓语,主语若是泛指需加量 词和特性谓词.并用符号表示. 4.分析各原子命题的关系,确定连接词.,1.直线A平行于直线B ，当且仅当直线A不相交于直线B. 2.如果有限个数的乘积为0,则至少有一个因子等于0 3.对每一个实数x存在着一个更大的实数y. 4.存在着实数x,y,z