谓词演算的永真公式.ppt

《谓词演算的永真公式.ppt》由会员分享，可在线阅读，更多相关《谓词演算的永真公式.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、)=1 L(x,y)L(x,y)为：为：L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0.L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0.在这个解释下，求下列各式的值。1 1 x(F(x)L(x,a)x(F(x)L(x,a)(F(F(2 2)L()L(2 2,2 2)(F(F(3 3)L()L(3 3,2 2)(01)(01)(11)(11)0 02 2 x x y L(x,y)y L(x,y)x(L(x,x(L(x,2 2)L(x,L(x,3 3)(L(L(2 2,2 2)L()L(2 2,3 3)(L(L(3 3,2 2)L()L(3 3,3 3)(10)(1

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

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

6、(x)P(x)xP(x)3A(x)A(3)A(4)A(4)1 1 A(3)111 1 3B(x)B(3)B(4)B(4)1 1B(3)110 04A(x)A(3)A(4)A(4)1 1A(4)110 04B(x)B(3)B(4)B(4)1 1B(4)111 1P(x)xP(x)在E上可满足，xP(x)在E上永真。南京信息工程大学数理学院南京信息工程大学数理学院NUIST7 72 xP(x)xP(x)解：未指明个体域与谓词P(x)的含义 -任意多组解释 设D为任意一个个体域，I为任意一个指派。若xP(x)为真，即对于D中任意x，P(x)均为真。此时在D中当然至少有一个x，使P(x)为真。则xP(

7、x)为真。所以在指派I下，xP(x)xP(x)取值为真。由I的任意性，xP(x)xP(x)为永真式。南京信息工程大学数理学院南京信息工程大学数理学院NUIST8 8n遍及个体域E等价（永真蕴含）给定个体域E上的两个谓词公式A和B，若对E中的任意指派I，1 A、B 都具有相同的真值（即谓词公式AB为永真式），则称谓词公式A和B在E上等价，记作：在E上AB。2 当A为真时，B也为真（即谓词公式AB为永真式），则称谓词公式A在E上永真蕴含B，记作：在E上AB。n等价（永真蕴含）1 若A和B在任意个体域上都是等价的，则称谓词公式A和B 等价，记作：AB。2 若A和B在任意个体域上都有A永真蕴含B，则称

8、谓词公式A 永真蕴含B，记作：AB B。二、谓词演算中的逻辑等价式和永真蕴含式南京信息工程大学数理学院南京信息工程大学数理学院NUIST9 9谓词逻辑中常用的逻辑等价式和永真蕴含式，其来源可分为两类：一、永真命题公式的推广 用原子谓词公式取代命题演算等价公式中的各命题变元，命题演算的等价式就转化为谓词演算的等价式。依据：依据：永真式的任何代入实例也必永真。永真式的任何代入实例也必永真。例如：例如：1 1 由由 P P P 得：得：A(x)A(x)A(x)A(x)2 2 由由 P PQ Q P PQ Q 得：得：xA(x)xA(x)xB(x)xB(x)(xA(x)(xA(x)(xB(x)xB(x

9、)二、由于引入量词而产生的谓词演算中特有的逻辑等价式、永真蕴含式。常用的逻辑等价式和永真蕴含式南京信息工程大学数理学院南京信息工程大学数理学院NUIST10101 1量词的消去律量词的消去律 (1)设个体域为有限集D=a1,a2,an时，则有n x P(x)x P(x)P(a1)P(a2)P(an)P(a1)P(a2)P(an)（1 1）n x P(x)x P(x)P(a1)P(a2)P(an)P(a1)P(a2)P(an)（2 2）(2)设A是不含自由变元x的谓词公式，则有 xA xA A A （3 3）xA xA A A （4 4）(因为A的真值与自由变元x无关)与量词有关的逻辑等价式南京

10、信息工程大学数理学院南京信息工程大学数理学院NUIST11112 2量词的否定律量词的否定律(量词转换律量词转换律 )n xP(x)xP(x)x x P(x)P(x)（5 5）n xP(x)xP(x)x x P(x)P(x)（6 6）量词前面的否定词可深入到量词辖域内。注：出现在量词之前的否定不是否定该量词，而是否定被量化了的整个命题。xP(x)(xP(x)。例如：设个体域D为大学生集合，P(x)：x今天来上课。P(x)：x今天没来校上课。1 xP(x)：不是所有的大学生今天都来上课。与 xP(x)：存在一些大学生今天没来上课。（含义相同）2 xP(x)：今天没有(不存在)来上课的大学生。与

11、xP(x)：所有的大学生今天都没来上课。（含义相同）南京信息工程大学数理学院南京信息工程大学数理学院NUIST1212 3 3量词辖域的扩张与收缩律量词辖域的扩张与收缩律 设P是不含自由变元x的任一谓词公式(包括命题公式)，则有：n xA(x)PxA(x)Px x（A(x)PA(x)P）（7 7）n xA(x)PxA(x)Px x（A(x)PA(x)P）（8 8）n xA(x)PxA(x)Px x（A(x)PA(x)P）（9 9）n xA(x)PxA(x)Px x（A(x)PA(x)P）（1010）证明：当个体域为有限集a1,a2,.,an时，xA(x)PxA(x)P(A(a1)A(a2).A

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

13、)（1313）n xA(x)P xA(x)P x(A(x)P)x(A(x)P)（14）前不变后变证明：证明：(13)(13)x(A(x)P)x(A(x)P)x(x(A(x)P)A(x)P)蕴含等价式 x x A(x)P A(x)P 量词辖域的扩张与收缩律 xA(x)P xA(x)P 量词否定律 xA(x)P xA(x)P 蕴含等价式南京信息工程大学数理学院南京信息工程大学数理学院NUIST14144 4量词的分配律量词的分配律n x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)（1515）n x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)

14、xB(x)（1616）n x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)（1717）例如：设个体域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)：联欢会上有人唱歌，或联欢会上有 人跳舞。（含义相同）南京信息工程大学数理学院南京信息工程大学数理学院NUIST1515证明：设D为任意一个个体域，I为任意一个指派。x(A(x)B(x)：对于D

15、中所有的，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)(17)x(A(x)B(x)x(A(x)B(x)x(x(A(x)B(x)A(x)B(x)蕴含等价式 x x A(x)A(x)xB(x)xB(x)量词分配的等价式 (xA(x)xA(x)xB(x)xB(x)量词否定律 xA(x)xA(x)xB(x)xB(x)蕴含等价式南京信息工程大学数理学院南京

16、信息工程大学数理学院NUIST16165 5量词交换律量词交换律n x x yP(x,y)yP(x,y)y y xP(x,y)xP(x,y)（1818）n x x yP(x,y)yP(x,y)y y xP(x,y)xP(x,y)（1919）证明：当个体域为有限集时，为讨论方便不妨取D=1,2 则则 x x yP(x,y)yP(x,y)x x(yP(x,y)yP(x,y)x x(P(x,P(x,1 1)P(x,)P(x,2 2)(P(P(1 1,1 1)P()P(1 1,2 2)(P(P(2 2,1 1)P()P(2 2,2 2)y y xP(x,y)xP(x,y)y y(P(P(1 1,y)P

17、(,y)P(2 2,y),y)(P(P(1 1,1 1)P()P(2 2,1 1)(P(P(1 1,2 2)P()P(2 2,2 2)当个体域为无限集时，指派分析证明：左右同真假。南京信息工程大学数理学院南京信息工程大学数理学院NUIST17171量词消去的蕴含式量词消去的蕴含式n xP(x)xP(x)P(a)(1)P(a)(1)或或 xP(x)xP(x)P(y)P(y)、xP(x)xP(x)P(x)P(x)nP(a)P(a)xP(x)(2)xP(x)(2)或或 P(y)P(y)xP(x)xP(x)、P(x)P(x)xP(x)xP(x)n xP(x)xP(x)xP(x)(3)xP(x)(3)与

18、量词有关的永真蕴含式与量词有关的永真蕴含式南京信息工程大学数理学院南京信息工程大学数理学院NUIST18182 2量词分配的蕴含式量词分配的蕴含式n xA(x)xA(x)xB(x)xB(x)x(A(x)B(x)x(A(x)B(x)（4 4）n x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xB(x)xB(x)（5 5）n xA(x)xA(x)xB(x)xB(x)x(A(x)B(x)x(A(x)B(x)（6 6）n注意：全称量词注意：全称量词 x x对对、不能等价分配不能等价分配 存在量词存在量词 对对不能等价分配不能等价分配对(4)式，“每一个人都唱歌或者每一个人都跳舞”，那么可

19、以说“每一个人都唱歌或跳舞”。但反之不真（不能保证每个人都是在唱歌，或者每个人都是在跳舞）。对(5)式，“有人既唱歌又跳舞”，那么可以说“有人唱歌且有人跳舞”。反之不真（不能保证是同一个人既唱歌又跳舞）。南京信息工程大学数理学院南京信息工程大学数理学院NUIST1919量词交换的蕴含式量词交换的蕴含式n x x yP(x,y)yP(x,y)y y xP(x,y)xP(x,y)（7 7）n y y x xP(x,y)P(x,y)x x y yP(x,y)P(x,y)（8 8）n x x yP(x,y)yP(x,y)y y xP(x,y)xP(x,y)（9 9）其中其中 x x yP(x,y)yP

20、(x,y)y y xP(x,y)xP(x,y)y y xP(x,y)xP(x,y)x x yP(x,y)yP(x,y)x x yP(x,y)yP(x,y)y y xP(x,y)xP(x,y)(8)(8)反之反之 x x y yP(x,y)P(x,y)y y x xP(x,y)P(x,y)不成立，同不成立，同4 4。交换量词中交换量词中x,yx,y的次序，类似可得：的次序，类似可得：n y y xP(x,y)xP(x,y)x x yP(x,y)yP(x,y)（1010）n x x yP(x,y)yP(x,y)y y xP(x,y)xP(x,y)（1111）n y y xP(x,y)xP(x,y)

21、x x yP(x,y)yP(x,y)（1212）南京信息工程大学数理学院南京信息工程大学数理学院NUIST20201 1 代入规则代入规则n(1)(1)自由个体变元的代入 对公式A中所有的同名自由个体变元都用另一个自由个体变元来代替，且新变元在原来的公式中没有出现过。例如：xF(x)G(x,y)-xF(x)G(u,y)-xF(x)G(y,y)n(2)谓词变元的代入 对公式A中的谓词也可用公式未曾出现过的新的谓词来代替，只要求新的谓词中的变元没有在原来的公式中出现过。例如：x(A(x)x(A(x)A(x)-A(x)-x(F(x,y)x(F(x,y)F(x,y)F(x,y)n代入定理：永真式的任何

22、代入实例仍为永真式。三、谓词公式的等值演算谓词公式的等值演算南京信息工程大学数理学院南京信息工程大学数理学院NUIST21212 2 置换规则置换规则n设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)南京信息工程大学数理学院南京信息工程大学数理学院NUIST22223 3 对偶原理对偶原理nA的对偶公式A*：设谓词公式A中仅含有联结词 、。将A中、

23、分别换成、后 所得到的谓词公式。n对偶原理：设A*、B*分别是命题公式、的对偶式。若 A B，则 A*B*。若 A B，则 B*A*。南京信息工程大学数理学院南京信息工程大学数理学院NUIST2323例1-7-3 1 将 x x y y z zP(x,y,z)P(x,y,z)中的否定词移到量词的辖域中。解：解：x x y y z zP(x,y,z)P(x,y,z)x x(y y z zP(x,y,z)P(x,y,z)多个量词辖域的定义 x x (y y z zP(x,y,z)P(x,y,z)量词的否定律 x x (y y(z zP(x,y,z)P(x,y,z)多个量词辖域的定义 x x y y

24、(z zP(x,y,z)P(x,y,z)量词的否定律 x x y y z z P(x,y,z)P(x,y,z)同上2 设个体域D=a,b,c，将下列公式中的量词消去。(1)x(F(x)G(x)(2)(2)x(F(x)G(x)(3)(3)x(F(x)yG(y)等值演算实例南京信息工程大学数理学院南京信息工程大学数理学院NUIST24243 3 证明：证明：x x y(P(x)Q(y)y(P(x)Q(y)xP(x)xP(x)yQ(y)yQ(y)证明：证明：x x y(P(x)Q(y)y(P(x)Q(y)x x(y(P(x)Q(y)y(P(x)Q(y)多个量词辖域的定义 x x(y(y(P(x)P(

25、x)Q(y)Q(y)蕴含等价式 x(x(P(x)P(x)yQ(y)yQ(y)量词辖域的扩张与收缩律 x x P(x)P(x)yQ(y)yQ(y)同上 (xP(x)xP(x)yQ(y)yQ(y)量词的否定律 xP(x)xP(x)yQ(y)yQ(y)蕴含等价式南京信息工程大学数理学院南京信息工程大学数理学院NUIST2525n前束范式：量词均非否定地放在在全式的开头，没有括 号将它们彼此隔开，而它们的辖域延伸到整 个公式末尾的谓词公式。n前束范式的形式：v1v2.vn A 其中“”表示量词或，v1，v2，.，vn是个体变元，A是不带量词的谓词公式。n前束范式的母式：前束范式中位于所有量词后面的部分

26、，即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-前束析取范式四、前束范式南京信息工程大学数理学院南京信息工程大学数理学院NUIST2626前束范式存在性定理：任意一个谓词公式，均和一个前束 范式等价。证明：构造性算法进行证明，步骤如下：1 消去对、冗余的联结词。2 利用量词否定律和德摩根律将否定词向内深入，使之 只作用于原子公式。3 利用改名规则或代入规则使所有的约束变元与自由变 元的符号均不同。4 利用量词辖域的扩张和收缩，将所有量词以在公式中 出现的顺序移到全式的最前面，扩

27、大量词的辖域到整 个公式。南京信息工程大学数理学院南京信息工程大学数理学院NUIST2727例1-7-4 求下列公式的前束范式。(1)(1)x F(x)x F(x)x G(x)x G(x)x F(x)x F(x)x G(x)x G(x)蕴涵等价式 x x F(x)F(x)x G(x)x G(x)量词否定律 x(x(F(x)G(x)F(x)G(x)量词分配的等价式(2)(2)xF(x)xF(x)xG(x)xG(x)x F(x)x F(x)x G(x)x G(x)蕴涵等值式 x x F(x)F(x)x G(x)x G(x)量词否定律 x x F(x)F(x)yG(y)yG(y)改名规则 x(x(F(x)F(x)yG(y)yG(y)量词辖域的收缩与扩张律 x x y(y(F(x)G(y)F(x)G(y)同上南京信息工程大学数理学院南京信息工程大学数理学院NUIST2828作业1-7南京信息工程大学数理学院南京信息工程大学数理学院