谓词演算的永真公式.ppt

《谓词演算的永真公式.ppt》由会员分享，可在线阅读，更多相关《谓词演算的永真公式.ppt（28页珍藏版）》请在三一办公上搜索。

1、南京信息工程大学数理学院,谓词公式是由原子谓词公式通过联结词、量词、小括号组成的字符串。而原子谓词公式(x1，x2，.，xn)中可含有个体常元、个体变元(约束变元和自由变元)、谓词常元、谓词变元。显然，对谓词公式A，只有当把其中的自由个体变元、谓词变元都赋予确定的含义以后，A才成为具有确定内容的命题，同时也具有确定的真假值。,1.7 谓词演算的永真公式,南京信息工程大学数理学院,将谓词公式中个体变元由确定的个体来取代，谓词变元 由确定的谓词来取代，称为对谓词公式的赋值或解释。公式A的每一个指派或解释I由以下三部分组成：1 非空个体域；2 D中一部分特定元素(用来解释个体常元)3 D上一些特定的

2、谓词(用来解释谓词变元)例如：对 x(P(x)Q(x)指定：1.个体域D为全总个体域 2.(x)：x是人；(x)：x是黄种人。则x(P(x)Q(x)：所有的人都是黄种人。F思考：若 个体域D为实数集(x)：x是自然数；(x)：x是有理数。,一、谓词公式的赋值,南京信息工程大学数理学院,例1-7-1 给定一个解释I：D=2，3；D中的特定元素 a=2 D上的特定谓词 F(x)为：F(2)=0，F(3)=1 L(x,y)为：L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0.在这个解释下，求下列各式的值。1 x(F(x)L(x,a)(F(2)L(2,2)(F(3)L(3,2)(01)(

3、11)02 xy L(x,y)x(L(x,2)L(x,3)(L(2,2)L(2,3)(L(3,2)L(3,3)(10)(01)1,南京信息工程大学数理学院,A在个体域E上的分类 给定谓词公式A及个体域E，如果在个体域E中无论怎样构成A的一种指派：1 A都取值为真，则称A在E上永真或A在E上上逻辑有效。2 A都取值为假，则称A在E上永假或A在E上矛盾。3 A至少在一种指派下取值为真，则称A在E上可满足。A的分类1 如果A在任意个体域上永真，则称A为永真式(或逻辑有效式)。2 如果A在任意个体域永假，则称A为永假式(或矛盾式)。3 如果A至少在一个个体域上可满足，则称A为可满足式。,谓词公式的类型

4、,南京信息工程大学数理学院,方法一：真值表法当谓词公式A的个体域E是有限的，谓词变元的解释也 是有限的时，原则上可以用真值表来判断。方法二：指派分析法当谓词公式A的个体域E是无限的，或谓词变元的解释是无限的时，谓词公式A的指派就是无限多个，无法实现用真值表来判断，一般根据联结词、量词的意义，直接用自然语言来叙述进行证明。,谓词公式类型的判断,南京信息工程大学数理学院,例1-7-2 在给定条件下判定谓词公式的类型。1 设谓词P(x)的含义仅为：A(x)：x是奇数。或 B(x)：x是偶数。个体域E=3，4，判定谓词公式P(x)xP(x)的类型。,P(x)xP(x)在E上可满足，xP(x)在E上永真

5、。,南京信息工程大学数理学院,2 xP(x)xP(x)解：未指明个体域与谓词P(x)的含义-任意多组解释 设D为任意一个个体域，I为任意一个指派。若xP(x)为真，即对于D中任意x，P(x)均为真。此时在D中当然至少有一个x，使P(x)为真。则xP(x)为真。所以在指派I下，xP(x)xP(x)取值为真。由I的任意性，xP(x)xP(x)为永真式。,南京信息工程大学数理学院,遍及个体域E等价（永真蕴含）给定个体域E上的两个谓词公式A和B，若对E中的任意指派I，1 A、B 都具有相同的真值（即谓词公式AB为永真式），则称谓词公式A和B在E上等价，记作：在E上AB。2 当A为真时，B也为真（即谓词

6、公式AB为永真式），则称谓词公式A在E上永真蕴含B，记作：在E上AB。等价（永真蕴含）1 若A和B在任意个体域上都是等价的，则称谓词公式A和B 等价，记作：AB。2 若A和B在任意个体域上都有A永真蕴含B，则称谓词公式A 永真蕴含B，记作：AB。,二、谓词演算中的逻辑等价式和永真蕴含式,南京信息工程大学数理学院,谓词逻辑中常用的逻辑等价式和永真蕴含式，其来源可分为两类：一、永真命题公式的推广 用原子谓词公式取代命题演算等价公式中的各命题变元，命题演算的等价式就转化为谓词演算的等价式。依据：永真式的任何代入实例也必永真。例如：1 由 P P 得：A(x)A(x)2 由 PQ PQ 得：xA(x)

7、xB(x)(xA(x)(xB(x)二、由于引入量词而产生的谓词演算中特有的逻辑等价式、永真蕴含式。,常用的逻辑等价式和永真蕴含式,南京信息工程大学数理学院,1量词的消去律(1)设个体域为有限集D=a1,a2,an时，则有x P(x)P(a1)P(a2)P(an)（1）x P(x)P(a1)P(a2)P(an)（2）(2)设A是不含自由变元x的谓词公式，则有 xA A（3）xA A（4）(因为A的真值与自由变元x无关),与量词有关的逻辑等价式,南京信息工程大学数理学院,2量词的否定律(量词转换律)xP(x)x P(x)（5）xP(x)x P(x)（6）量词前面的否定词可深入到量词辖域内。注：出现

8、在量词之前的否定不是否定该量词，而是否定被量化了的整个命题。xP(x)(xP(x)。例如：设个体域D为大学生集合，P(x)：x今天来上课。P(x)：x今天没来校上课。1 xP(x)：不是所有的大学生今天都来上课。与 xP(x)：存在一些大学生今天没来上课。（含义相同）2 xP(x)：今天没有(不存在)来上课的大学生。与 xP(x)：所有的大学生今天都没来上课。（含义相同）,南京信息工程大学数理学院,3量词辖域的扩张与收缩律 设P是不含自由变元x的任一谓词公式(包括命题公式)，则有：xA(x)Px（A(x)P）（7）xA(x)Px（A(x)P）（8）xA(x)Px（A(x)P）（9）xA(x)P

9、x（A(x)P）（10）证明：当个体域为有限集a1,a2,.,an时，xA(x)P(A(a1)A(a2).A(an)P(A(a1)P)(A(a2)P).(A(an)P)x(A(x)P)当个体域为无限集时，指派分析证明：左右同真假。,南京信息工程大学数理学院,3量词辖域的扩张与收缩律 设P是不含自由变元x的任一谓词公式(包括命题公式)，则有：PxA(x)x(PA(x)（11）PxA(x)x(PA(x)（12）xA(x)P x(A(x)P)（13）xA(x)P x(A(x)P)（14）前不变后变证明：(13)x(A(x)P)x(A(x)P)蕴含等价式 xA(x)P 量词辖域的扩张与收缩律 xA(x

10、)P 量词否定律 xA(x)P 蕴含等价式,南京信息工程大学数理学院,4量词的分配律x(A(x)B(x)xA(x)xB(x)（15）x(A(x)B(x)xA(x)xB(x)（16）x(A(x)B(x)xA(x)xB(x)（17）例如：设个体域D为联欢会上所有的人组成的集合，A(x)：x唱歌。B(x)：x跳舞。1 x(A(x)B(x)：联欢会上所有的人既唱歌又跳舞。与 xA(x)xB(x)：联欢会上所有的人唱歌且所有的人 跳舞。（含义相同）2 x(A(x)B(x)：联欢会上有人唱歌或跳舞。与 xA(x)xB(x)：联欢会上有人唱歌，或联欢会上有 人跳舞。（含义相同）,南京信息工程大学数理学院,证

11、明：设D为任意一个个体域，I为任意一个指派。x(A(x)B(x)：对于D中所有的，A(x)和B(x)都是真的。xA(x)xB(x)：对于D中所有的，A(x)是真的；同时对 于D中所有的，B(x)也是真的。-两个命题是等价的。x(A(x)B(x)：D中存在，能使()或者()为真。xA(x)xB(x)：D中存在能使()为真，或者D中存在 能使()为真。-两个命题是等价的。(17)x(A(x)B(x)x(A(x)B(x)蕴含等价式 xA(x)xB(x)量词分配的等价式(xA(x)xB(x)量词否定律 xA(x)xB(x)蕴含等价式,南京信息工程大学数理学院,5量词交换律 xyP(x,y)yxP(x,

12、y)（18）xyP(x,y)yxP(x,y)（19）证明：当个体域为有限集时，为讨论方便不妨取D=1,2 则 xyP(x,y)x(yP(x,y)x(P(x,1)P(x,2)(P(1,1)P(1,2)(P(2,1)P(2,2)yxP(x,y)y(P(1,y)P(2,y)(P(1,1)P(2,1)(P(1,2)P(2,2)当个体域为无限集时，指派分析证明：左右同真假。,南京信息工程大学数理学院,1量词消去的蕴含式xP(x)P(a)(1)或 xP(x)P(y)、xP(x)P(x)P(a)xP(x)(2)或 P(y)xP(x)、P(x)xP(x)xP(x)xP(x)(3),与量词有关的永真蕴含式,南京

13、信息工程大学数理学院,2量词分配的蕴含式xA(x)xB(x)x(A(x)B(x)（4）x(A(x)B(x)xA(x)xB(x)（5）xA(x)xB(x)x(A(x)B(x)（6）注意：全称量词x对、不能等价分配 存在量词对不能等价分配对(4)式，“每一个人都唱歌或者每一个人都跳舞”，那么可以说“每一个人都唱歌或跳舞”。但反之不真（不能保证每个人都是在唱歌，或者每个人都是在跳舞）。对(5)式，“有人既唱歌又跳舞”，那么可以说“有人唱歌且有人跳舞”。反之不真（不能保证是同一个人既唱歌又跳舞）。,南京信息工程大学数理学院,量词交换的蕴含式 xyP(x,y)yxP(x,y)（7）yxP(x,y)xyP

14、(x,y)（8）xyP(x,y)yxP(x,y)（9）其中 xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)(8)反之xyP(x,y)yxP(x,y)不成立，同4。交换量词中x,y的次序，类似可得：yxP(x,y)xyP(x,y)（10）xyP(x,y)yxP(x,y)（11）yxP(x,y)xyP(x,y)（12）,南京信息工程大学数理学院,1 代入规则(1)自由个体变元的代入 对公式A中所有的同名自由个体变元都用另一个自由个体变元来代替，且新变元在原来的公式中没有出现过。例如：xF(x)G(x,y)-xF(x)G(u,y)-xF(x)G(y,

15、y)(2)谓词变元的代入 对公式A中的谓词也可用公式未曾出现过的新的谓词来代替，只要求新的谓词中的变元没有在原来的公式中出现过。例如：x(A(x)A(x)-x(F(x,y)F(x,y)代入定理：永真式的任何代入实例仍为永真式。,三、谓词公式的等值演算,南京信息工程大学数理学院,2 置换规则设C是含子公式A的谓词公式，D是用公式B置换了C中的A（不必每一处）之后得到的谓词公式，A、B都仅含有n个自由个体变元。如果AB，则CD。例如：公式C：P(x)(Q(x,t)R(x,t)其中子公式A：Q(x,t)R(x,t)Q(x,t)R(x,t)代入规则 故C P(x)(Q(x,t)R(x,t),南京信息工

16、程大学数理学院,3 对偶原理A的对偶公式A*：设谓词公式A中仅含有联结词、。将A中、分别换成、后 所得到的谓词公式。对偶原理：设A*、B*分别是命题公式、的对偶式。若 A B，则 A*B*。若 A B，则 B*A*。,南京信息工程大学数理学院,例1-7-3 1 将 xyzP(x,y,z)中的否定词移到量词的辖域中。解：xyzP(x,y,z)x(yzP(x,y,z)多个量词辖域的定义 x(yzP(x,y,z)量词的否定律 x(y(zP(x,y,z)多个量词辖域的定义 xy(zP(x,y,z)量词的否定律 xyz P(x,y,z)同上2 设个体域D=a,b,c，将下列公式中的量词消去。(1)x(F

17、(x)G(x)(2)x(F(x)G(x)(3)x(F(x)yG(y),等值演算实例,南京信息工程大学数理学院,3 证明：xy(P(x)Q(y)xP(x)yQ(y)证明：xy(P(x)Q(y)x(y(P(x)Q(y)多个量词辖域的定义 x(y(P(x)Q(y)蕴含等价式 x(P(x)yQ(y)量词辖域的扩张与收缩律 xP(x)yQ(y)同上(xP(x)yQ(y)量词的否定律 xP(x)yQ(y)蕴含等价式,南京信息工程大学数理学院,前束范式：量词均非否定地放在在全式的开头，没有括 号将它们彼此隔开，而它们的辖域延伸到整 个公式末尾的谓词公式。前束范式的形式：v1v2.vn A 其中“”表示量词或

18、，v1，v2，.，vn是个体变元，A是不带量词的谓词公式。前束范式的母式：前束范式中位于所有量词后面的部分，即A。例如：1 xyz(Q(x,y)R(z)2 xyQ(x,y)zR(z)3 Q(x,y)其中1、3是前束范式，2不是前束范式 1的母式：Q(x,y)R(z)，1-前束析取范式,四、前束范式,南京信息工程大学数理学院,前束范式存在性定理：任意一个谓词公式，均和一个前束 范式等价。证明：构造性算法进行证明，步骤如下：1 消去对、冗余的联结词。2 利用量词否定律和德摩根律将否定词向内深入，使之 只作用于原子公式。3 利用改名规则或代入规则使所有的约束变元与自由变 元的符号均不同。4 利用量词辖域的扩张和收缩，将所有量词以在公式中 出现的顺序移到全式的最前面，扩大量词的辖域到整 个公式。,南京信息工程大学数理学院,例1-7-4 求下列公式的前束范式。,(1)x F(x)x G(x)x F(x)x G(x)蕴涵等价式 x F(x)x G(x)量词否定律 x(F(x)G(x)量词分配的等价式(2)xF(x)xG(x)x F(x)x G(x)蕴涵等值式 x F(x)x G(x)量词否定律 x F(x)yG(y)改名规则 x(F(x)yG(y)量词辖域的收缩与扩张律 xy(F(x)G(y)同上,南京信息工程大学数理学院,作业 1-7,