《离散数学(第7讲)谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学(第7讲)谓词逻辑.ppt（34页珍藏版）》请在三一办公上搜索。
1、栾新成 四川大学软件学院,第2章 一阶谓词逻辑(2),主要内容,谓词公式与解释 1.谓词的合适公式 2.谓词公式的解释 3.几个特殊的公式谓词公式的等价与范式表示 1.谓词公式的等价 2.基本等价式 3.前束范式 4.斯柯林范式,2023年11月16日,2,谓词公式,同命题演算一样，在谓词逻辑中也同样包含命题变元和命题联结词，为了能够进行演绎和推理，为了对谓词逻辑中关于谓词的表达式加以形式化，利用联结词、谓词与量词构成命题函数，我们必须引入公式的概念。,2023年11月16日,3,谓词公式,四类符号:常量符号：一般用a,b,c,a1,b1,c1,来表示，它可以是D中的某个元素;变量符号：一般用
2、x,y,z,x1,y1,z1,来表示.它可以取值于D中的任意元素；函数符号：一般用f,g,h,f1,g1,h1,来表示。n元函数符号f(x1,x2,.xn)可以是DnD的任意一个函数；谓词符号：一般用P,Q,R,.,P1,Q1,R1,.来表示。n元谓词符号P(x1,x2,.xn)可以是Dn0,1的任意一个谓词。注：不含变元的函数是常量；不含客体变元的谓词是命题。,2023年11月16日,4,谓词公式,n元函数符号f(x1,x2,.xn)与n元谓词符号P(x1,x2,.xn)1）两个n元相同吗？2）函数符号f(x1,x2,.xn)中的f 可以用P代换吗？如果能，则代换结果为P(x1,x2,.xn
3、)，与谓词符号P(x1,x2,.xn)的区别是什么？,2023年11月16日,值域不同,5,谓词公式,定义2-2.1 谓词逻辑中的项被递归地定义为：1）任意的常量符号是项；2）任意的变量符号是项；3）若f(x1,x2,x3,xn)是n元函数符号，t1,t2,t3,tn是项，则f(t1,t2,t3,tn)是项；4）只有有限次使用1)-3)产生的符号串才是项。例2.1复合函数f(g(f(a),g(a,x)是一个项,2023年11月16日,6,谓词公式,定义2-2.2 设P(x1,x2,x3,.xn)是n元谓词，t1,t2,t3,.tn是项,则P(t1,t2,t3,.tn)是原子谓词公式，简称原子公
4、式。定义2-2.3 满足下列条件的表达式，称为合适公式,简称公式。1）原子公式是合适公式；2）若G，H是合适公式，则(G)、(H)、(GH)、(GH)、(GH)、(GH)也是合适公式；3）若G是合适公式，x是个体变量，则(x)G、(x)G也是合适公式；4）仅仅由1)-3)产生的表达式才是合适公式。,2023年11月16日,G的区别:G与(x)G（x),7,谓词公式,例2.2(P(x)(Q(x,y)R(x,a,f(z)(P(x)R(y)(x)(P(x)等都是公式。而(x)(P(x)R(x)(x)P(x)(y)等则不是公式，前者括号不匹配，后者量词无辖域。,2023年11月16日,8,谓词公式的翻
5、译,例1 并非每个实数都是有理数解：设R(x):x是实数,Q(x):x是有理数原命题为：x(R(x)Q(x)例2 没有不犯错误的人解：设M(x)：x是人,F(x):x犯错原命题为：x（(M(x)F(x)例3 尽管有人聪明，但未必一切人都聪明。解：设M(x):x是人,P(x):x聪明原题为：x(M(x)P(x)x(M(x)P(x),2023年11月16日,9,谓词公式的翻译,多元谓词可以多重量化例4 翻译每个人都有缺点。解：设F（x,y）:x有y,M(x):x是人 G(y):y有缺点原命题为:x(M(x)y(G(y)F(x,y)例5:翻译某些人对某些食物过敏。解：设F（x,y）:x对y过敏,M(
6、x):x是人 G(y):y是食物。原命题为:xy(M(x)G(y)F(x,y),2023年11月16日,10,谓词公式的翻译,谓词对于个体刻划的深度的机动灵活性例6 翻译那只小花猫逮住这只大老鼠。解：设 a:F(x,y):x逮住y,P(x):x是小花猫,Q(y):y是大老鼠,S(a):a是那只,R(b):b是这只原命题为：ab(P(a)Q(b)F(a,b)S(a)R(b)b A(x):x是猫,B(x):x是小的,C(x):x是花的,D(y):y是的,E(y):y是老鼠,F(x,y),S(a),R(b)同上。原命题为：ab(A(a)B(a)C(a)D(b)E(b)F(a,b)S(a)R(b)。,
7、2023年11月16日,11,谓词公式的解释,定义2-2.4 一个定义在论域D上的公式G的每一个解释（指派）由如下四部分组成：1、非空的个体域集合D；2、G中的每个常量符号,指定D中的一个元素；3、G中的每个n元函数符号,指定Dn到D的一个函数；4、G中的每个n元谓词符号,指定Gn到0,1的一个谓词。注：定义中所谓指定一个具体函数，即是对每组可能的变量值给出函数的对应值；（值域？）所谓指定一个具体命题函数，就是对每组可能的客体变元取值给出谓词的对应值，1表示逻辑真，0表示逻辑假。,2023年11月16日,12,谓词公式的解释,含有量词的公式的解释 对于含有量词的公式的解释，需要根据量词的逻辑意
8、义来决定公式的值。设论域 D=a1,a2,，an1）（x)P(x)P(a1)P(a2)P(an)表示公式（x)P(x)值为1“当且仅当”对论域D中每个元素a，P(a)的值为1。2）（x)P(x)P(a1)P(a2)P(an)表示公式（x)P(x)值为0“当且仅当”对论域D中每个元素a，P(a)的值为0。,2023年11月16日,13,谓词公式的解释,例2.3 设公式：(x)(y)(P(x,y)Q(x,y)。在如下给定的解释下,判断该公式的真值。1)、解释I为：.个体域为N+(严格大于0的整数)；.P(x,y)指定为：“yx”；.Q(x,y)指定为：“y1”。则原公式的真值为“真”。因确能找到一
9、个xN+，使得对任意y,都有yx和y1。此时蕴涵公式的前件为真，后件也为真。所以，整个公式为真。,2023年11月16日,14,谓词公式的解释,2)、解释I为：(x)(y)(P(x,y)Q(x,y)。.个体域为N；.P(x,y)指定为：“xy0”；.Q(x,y)指定为：“xy”；则原公式的真值为“假”。因对任意的x0,当y0时，有P(x,y)Q(x,y)为“假”，即有：(y)(P(x,y)Q(x,y)为“假”。而对x0，当y1时，有P(x,y)Q(x,y)为“假”。即有：(y)(p(x,y)Q(x,y)为“假”。所以，对任意xN,都有：(y)(P(x,y)Q(x,y)为“假”。即有：(x)(y
10、)(P(x,y)Q(x,y)为“假”。,2023年11月16日,15,谓词公式的解释,3)、解释I为：(x)(y)(P(x,y)Q(x,y)。.个体域为N；.P(x,y)指定为：“x+y0”；.Q(x,y)指定为：“xy”。则原公式的真值为“真”。因对任意的x0,任意yN，有x+y0为“假”，所以无论后件如何，都有 P(x,y)Q(x,y)为“真”，即有：(y)(P(x,y)Q(x,y)为“真”。所以：(x)(y)(P(x,y)Q(x,y)为“真”。,2023年11月16日,16,几个特殊公式,定义2-2.5：1、设A是以D为论域的谓词公式，如果在关于D的任一解释之下，A的值都为真（或1）时，
11、称公式A是D上的永真公式(重言式)；2）设A是以D为论域的谓词公式，如果在关于D的任一解释之下，A的值都为假（或0）时，称公式A是D上的永假公式(矛盾式，不可满足公式）；3）设A是以D为论域的谓词公式，如果在关于D的某个解释之下，A取值为真（或1），称公式A是D上的可满足公式。,2023年11月16日,17,谓词公式的等价,定义2-3.1：设A和B是以D为论域的谓词公式,如果在任一解释下,A和B都取相同的真值,则称A和B在D上是等价的,记作A B。定理2-3.1：A B iff A B是D上的永真公式。,2023年11月16日,18,谓词演算的基本等价式,命题演算中的等价式在谓词演算中都成立,
12、下面只涉及量词(Quanitifier)的一些等价式。,2023年11月16日,19,谓词演算的基本等价式,定理2-3.2：量词否定(量词转换)25：（x）P(x)（x）P(x)26：（x）P(x)（x）P(x)显然,并非所有的人都是学生和有些人不是学生 有相同含义。不存在长生不老的人 和 所有的人都不是长生不老的有相同含义。量词的转换可以推广到含多个量词的谓词公式。（x）（y）（z）P(x,y,z)（x）（y）（z）P(x,y,z)（x）（y）（z）P(x,y,z)（x）（y）（z）P(x,y,z),2023年11月16日,规律？,规律？,20,谓词演算的基本等价式,定理2-3.：（量词辖域
13、的扩充与收缩）设Q是不含指导变元的谓词公式27：（x）P(x)Q（x）P(x)Q28：（x）P(x)Q（x）P(x)Q29：（x）P(x)Q（x）P(x)Q30：（x）P(x)Q（x）P(x)Q31：（x）P(x)Q（x）P(x)Q32：（x）P(x)Q（x）P(x)Q33：Q（x）P(x)（x）Q P(x)34：Q（x）P(x)（x）Q P(x),2023年11月16日,21,谓词演算的基本等价式,定理2-3.：（量词分配侓）35:(x)(P(x)Q(x)（x）P(x)（x）Q(x)36:(x)(y)(P(x)Q()(x)P(x)(x)Q(x)37:(x)()(P(x)Q()（x）P(x)（
14、x）Q(x)38：（x）(P(x)Q(x)（x）P(x)（x）Q(x)39：（x）(P(x)Q(x)（x）p(x)（x）Q(x)定理2-3.：（双量词公式的等价性）40：(x)()(x，)（）（x）(x，)41：(x)()(x，)（）（x）(x，),2023年11月16日,同一类型的量词，可以交换顺序而不影响其等价性。,22,不同类型量词可交换顺序吗？,解释给定为:D=1，2，分别求公式A=（x）（y）P(x,y)和公式B=（y）（x）P(x,y)的值。A=(P(1,1）P(1,2)(P(2,1)P(2,2)=(10)(01)=1B=(P(1,1）P(1,2)(P(2,1)P(2,2)=(1
15、0)(0 1)=0,2023年11月16日,23,含有“”“”公式的共同点,2023年11月16日,27：(x)(P(x)Q)（x）P(x)Q28：(x)(P(x)Q)（x）P(x)Q29：(x)(P(x)Q)（x）P(x)Q30：(x)(P(x)Q)（x）P(x)Q,35：（x）(P(x)Q(x)（x）P(x)（x）Q(x)36：（x）（）(P(x)Q()（x）P(x)（x）Q(x)37：（x）（）(P(x)Q()（x）P(x)（x）Q(x)38：（x）(P(x)Q(x)（x）P(x)（x）Q(x),24,含有“”公式的共同点,2023年11月16日,31：（x）P(x)Q（x）P(x)Q3
16、2：（x）P(x)Q（x）P(x)Q33：Q（x）P(x)（x）Q P(x)34：Q（x）P(x)（x）Q P(x),39：（x）(P(x)Q(x)（x）p(x)（x）Q(x)（x）(P(x)Q(x)（x）p(x)（xQ(x）,25,前束范式,与命题演算类似,谓词演算也有范式(规范(标准)的公式)定义2-3.:如果谓词公式 A=（Q1x1）（Q2x2）（Qnxn）G,其中Qixi是xi或xi(1 i n),G是不含量词的公式,则称A是前束范式,称G是A的母式。(所有量词均非否定地出现在公式的最前面,且辖域一直延伸到公式之末)如（x）（y）（z）(P(x,y)Q(y,z)（x）（y）p(x,y,
17、z),2023年11月16日,26,前束范式,定义2-3.:如果在前束范式（Q1x1）（Q2x2）（Qnxn）G中,母式G是合取(或析取)范式,相应地称这个前束范式为前束合取(或析取)范式。定理2-3.6 每一个含量词的谓词公式都存在着与之等价的前束范式。化规过程:1.将公式中,化成,2.利用量词转换律25,26和德.摩根定律,将否定直接移到原子公式前。3.利用约束变元的改名和自由变元的代入规则,使所有约束变元之间,自由变元与约束变元之间均不同名。4.利用量词的扩张与收缩,把量词移到全式的最前面。,2023年11月16日,27,前束范式,例2.4 将公式(xP(x)yR(y)xF(x)化规为前
18、束范式。解：(xP(x)yR(y)xF(x)(xP(x)yR(y)xF(x)(1)(xP(x)yR(y)xF(x)(2)（xP(x)yR(y)）z F(z)(3)xyz(P(x)R(y)F(z)(4)(析取范式)xyz(P(x)F(z)(R(y)F(z)(合取范式),2023年11月16日,28,前束范式的不足,把一个谓词公式变成等价的前束范式时,可能存在多个全称量词和存在量词.凡是同一类型的量词,可以交换顺序而不影响等价性；全称量词和存在量词一般不能交换顺序；两种量词出现的顺序可能组成多种情况；在处理实际问题时很不方便。人们设计了一种解决办法：只保留全称量词,而把存在量词转化为相应的依赖函数
19、,这就是Skolem范式的思路。,2023年11月16日,29,斯柯林(Skolem)范式,斯柯林(Skolem)范式-不含存在量词的前束合取范式定义23.4 设谓词公式A的等价前束合取范式是（Q1x1）（Q2x2）（Qnxn）G,）从左到右扫描量词，设Qi是第一个遇到的存在量词:如i=1,则选择一个在G中未使用过的常量标识符代替G中的全部x1,然后删去Q1x1;如果i1,则Q1,Q2,Qi-1都是全称量词,这时选择一个在G中未使用过的函数标识符(如g)，并用g(x1,x2,.,xi-1)去代替G中的全部xi,然后删去Qixi;2）重复这一过程,直到公式中不含存在量词为止。这样得到的公式称为S
20、kolem范式,而取代存在量词时使用的常量标识符或函数,称为Skolem函数。,2023年11月16日,30,斯柯林(Skolem)范式,例2.5 求xyzuvwP(x,y,z,u,v,w)的Skolem范式。解：xyzuvwP(x,y,z,u,v,w)yzuvwP(a,y,z,u,v,w)（消去x）yzvw P(a,y,z,f(y,z),v,w)（消去）yzvP(a,y,z,f(y,z),v,g(y,z,v)（消去）,2023年11月16日,31,Skolem范式的理解,消去存在量词,将相应变元以函数代入的理解:如 xyP(x,y)的Skolem范式是xP(x,f(x)xyP(x,y)的意思
21、是对任一x都有一个y使P(x,y)成立,这个y通常是依赖x的,可视为x的某个函数f(x),从而有Skolem范式xP(x,f(x)。然而能找到的y不一定是x的函数f,于是xyP(x,y)与xP(x,f(x)并不等值。如=1,2,xyP(x,y)(P(1,1)P(1,2)(P(2,1)P(2,2)与xP(x,f(x)P(1,f(1)P(2,f(2)两者明显不等值,但在不可满足的意义下是一致的。,2023年11月16日,32,斯柯林(Skolem)范式,定理23.7 设谓词公式G的Skolem范式为S,则G为矛盾式当且仅当 S为矛盾式。Skolem范式是一种重要的范式形式，机器定理证明和逻辑程序设计中的消解(或称归结)原理就建立在这种范式的基础上。,2023年11月16日,33,作业,习题二 5（1）、（3）6（2）7（2）、（3）8 9 10 11（1）、（2）,2023年11月16日,34,
