《1.7 谓词演算的永真公式.ppt》由会员分享，可在线阅读，更多相关《1.7 谓词演算的永真公式.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、NUIST1 1 谓词公式是由原子谓词公式通过联结词、量词、小括号组成的字符串。而原子谓词公式(x(x1 1，x x2 2，.，x xn n)中可含有个体常元、个体变元(约束变元和自由变元)、谓词常元、谓词变元。显然，对谓词公式A，只有当把其中的自由个体变元、谓词变元都赋予确定的含义以后，A才成为具有确定内容的命题，同时也具有确定的真假值。1.7 谓词演算的永真公式NUIST2 2n将谓词公式中个体变元由确定的个体来取代，谓词变元 由确定的谓词来取代，称为对谓词公式的赋值或解释。n公式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是有理数。一、谓词公式的赋值谓词公式的赋值NUIST3 3例例1-7-11-7-1 给定一个解释I：D D=2=2，33；D D中的中的特定元素特定元素 a=2a=2 D D上的上的特定谓词特定谓词 F(xF(x)为：为：F(2)=0F(2)=0，F(3)=1F(3)=1 L(x,yL(x,y)为：为：L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=
3、0.L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0.在这个解释下，求下列各式的值。1 1 x(F(x)L(x,ax(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 xy y L(x,yL(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)(10)(01)(01)1 1NUIST4 4nA在个体域E上的分类 给定谓词公式A及个体域E，如果在个体域E
4、中无论怎样构成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为可满足式。谓词公式的类型谓词公式的类型NUIST5 5方法一：真值表法当谓词公式A的个体域E是有限的，谓词变元的解释也 是有限的时，原则上可以用真值表来判断。方法二：指派分析法当谓词公式A的个体域E是无限的，或谓词变元的解释是无限的时，谓词公
5、式A的指派就是无限多个，无法实现用真值表来判断，一般根据联结词、量词的意义，直接用自然语言来叙述进行证明。谓词公式类型的判断谓词公式类型的判断NUIST6 6 例1-7-2 在给定条件下判定谓词公式的类型。1 设谓词P(x)的含义仅为：A(x)：x是奇数。或 B(x)：x是偶数。个体域E=3，4，判定谓词公式P(x)xP(x)的类型。x P(x)xP(x)P(x)xP(x)3 A(x)A(3)A(4)A(4)1 1 A(3)111 1 3 B(x)B(3)B(4)B(4)1 1 B(3)110 0 4 A(x)A(3)A(4)A(4)1 1 A(4)110 0 4 B(x)B(3)B(4)B(
6、4)1 1 B(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(x)为真。所以在指派I下，xP(x)xP(x)取值为真。由I的任意性，xP(x)xP(x)为永真式。NUIST8 8n 遍及个体域E等价（永真蕴含）给定个体域E上的两个谓词公式A和B，若对E中的任意指派I，1 A、B 都具有相同的真值（即谓词公式AB为永真式），则称谓词公式A和
7、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，则称谓词公式A 永真蕴含B，记作：AB B。二、谓词演算中的逻辑等价式和永真蕴含式NUIST9 9 谓词逻辑中常用的逻辑等价式和永真蕴含式，其来源可分为两类：一、永真命题公式的推广 用原子谓词公式取代命题演算等价公式中的各命题变元，命题演算的等价式就转化为谓词演算的等价式。依据：依据：永真式的任何代入实例也必永真。永真式的任何
8、代入实例也必永真。例如：例如：1 1 由由 P P P 得：得：A(xA(x)A(xA(x)2 2 由由 P PQ Q P PQ Q 得：得：xA(x)xA(x)xB(xxB(x)(xA(x)(xA(x)(xB(xxB(x)二、由于引入量词而产生的谓词演算中特有的逻辑等价式、永真蕴含式。常用的逻辑等价式和永真蕴含式NUIST10101 1量词的消去律量词的消去律 (1)设个体域为有限集D=a1,a2,an时，则有nx x P(xP(x)P(a1)P(a2)P(a1)P(a2)P(anP(an)（1 1）nx x P(xP(x)P(a1)P(a2)P(a1)P(a2)P(anP(an)（2 2）
9、(2)设A是不含自由变元x的谓词公式，则有 xAxA A A （3 3）xAxA A A （4 4）(因为A的真值与自由变元x无关)与量词有关的逻辑等价式NUIST11112 2量词的否定律量词的否定律(量词转换律量词转换律 )n xP(xxP(x)x x P(xP(x)（5 5）n xP(xxP(x)x x P(xP(x)（6 6）量词前面的否定词可深入到量词辖域内。注：出现在量词之前的否定不是否定该量词，而是否定被量化了的整个命题。xP(x)(xP(x)。例如：设个体域D为大学生集合，P(x)：x今天来上课。P(x)：x今天没来校上课。1 xP(x)：不是所有的大学生今天都来上课。与 xP
10、(x)：存在一些大学生今天没来上课。（含义相同）2 xP(x)：今天没有(不存在)来上课的大学生。与 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
11、时，xA(x)PxA(x)P(A(a1)A(a2).(A(a1)A(a2).A(an)PA(an)P (A(a1)P)(A(a2)P).(A(a1)P)(A(a2)P).(A(an)PA(an)P)x(A(x)Px(A(x)P)当个体域为无限集时，指派分析证明：左右同真假。NUIST13133 3量词辖域的扩张与收缩律量词辖域的扩张与收缩律 设P是不含自由变元x的任一谓词公式(包括命题公式)，则有：nPP xA(xxA(x)x(x(PA(xPA(x)（1111）nPP xA(xxA(x)x(x(PA(xPA(x)（1212）n xA(x)PxA(x)P x(x(A(x)PA(x)P)（1313
12、）n xA(x)PxA(x)P x(x(A(x)PA(x)P)（14）前不变后变证明：证明：(13)(13)x(A(x)P)x(A(x)P)x(x(A(x)PA(x)P)蕴含等价式 x x A(x)PA(x)P 量词辖域的扩张与收缩律 xA(x)PxA(x)P 量词否定律 xA(x)PxA(x)P 蕴含等价式NUIST14144 4量词的分配律量词的分配律n x(A(x)B(xx(A(x)B(x)xA(xxA(x)xB(xxB(x)（1515）n x(A(x)B(xx(A(x)B(x)xA(xxA(x)xB(xxB(x)（1616）n x(A(x)B(xx(A(x)B(x)xA(xxA(x)x
13、B(xxB(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中所有的，A(x)和B(x)都是真的。xA(x)xB(x)：对于D中所有的，A(x)是真的；同时对 于D中所有的，B(x)也是真的。-两个
14、命题是等价的。x(A(x)B(x)：D中存在，能使()或者()为真。xA(x)xB(x)：D中存在能使()为真，或者D中存在 能使()为真。-两个命题是等价的。(17)(17)x(x(A(x)B(xA(x)B(x)x(x(A(x)B(xA(x)B(x)蕴含等价式 x x A(xA(x)xB(xxB(x)量词分配的等价式 (xA(xxA(x)xB(xxB(x)量词否定律 xA(xxA(x)xB(xxB(x)蕴含等价式NUIST16165 5量词交换律量词交换律n x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)（1818）n x x yP(x,yyP(x,y)y y xP(x
15、,yxP(x,y)（1919）证明：当个体域为有限集时，为讨论方便不妨取D=1,2 则则 x x yP(x,yyP(x,y)x x(yP(x,yyP(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,yxP(x,y)y y(P(P(1 1,y),y)P(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量词消去的蕴含式量词消去的
16、蕴含式n xP(xxP(x)P(aP(a)(1)(1)或或 xP(xxP(x)P(yP(y)、xP(xxP(x)P(xP(x)nP(aP(a)xP(xxP(x)(2)(2)或或 P(yP(y)xP(xxP(x)、P(xP(x)xP(xxP(x)nxP(xxP(x)xP(xxP(x)(3)(3)与量词有关的永真蕴含式与量词有关的永真蕴含式NUIST18182 2量词分配的蕴含式量词分配的蕴含式n xA(xxA(x)xB(xxB(x)x(A(x)B(xx(A(x)B(x)（4 4）n x(A(x)B(xx(A(x)B(x)xA(xxA(x)xB(xxB(x)（5 5）n xA(xxA(x)xB(x
17、xB(x)x(A(x)B(xx(A(x)B(x)（6 6）n注意：全称量词注意：全称量词 x x对对、不能等价分配不能等价分配 存在量词存在量词 对对不能等价分配不能等价分配对(4)式，“每一个人都唱歌或者每一个人都跳舞”，那么可以说“每一个人都唱歌或跳舞”。但反之不真（不能保证每个人都是在唱歌，或者每个人都是在跳舞）。对(5)式，“有人既唱歌又跳舞”，那么可以说“有人唱歌且有人跳舞”。反之不真（不能保证是同一个人既唱歌又跳舞）。NUIST1919量词交换的蕴含式量词交换的蕴含式n x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)（7 7）n y y x xP(x,yP(x
18、,y)x x y yP(x,yP(x,y)（8 8）n x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)（9 9）其中其中 x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)y y xP(x,yxP(x,y)x x yP(x,yyP(x,y)x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)(8)(8)反之反之 x x y yP(x,yP(x,y)y y x xP(x,yP(x,y)不成立，同不成立，同4 4。交换量词中交换量词中x,yx,y的次序，类似可得：的次序，类似可得：n y y xP(x,yxP(x,y)x x yP(x,yyP
19、(x,y)（1010）n x x yP(x,yyP(x,y)y y xP(x,yxP(x,y)（1111）n y y xP(x,yxP(x,y)x x yP(x,yyP(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(xx(A(x)A(xA
20、(x)-)-x(x(F(x,yF(x,y)F(x,yF(x,y)n代入定理：永真式的任何代入实例仍为永真式。三、谓词公式的等值演算谓词公式的等值演算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中、分别换成
21、、后 所得到的谓词公式。n对偶原理：设A*、B*分别是命题公式、的对偶式。若 A B，则 A*B*。若 A B，则 B*A*。NUIST2323例1-7-3 1 将 x x y y z zP(x,y,zP(x,y,z)中的否定词移到量词的辖域中。解：解：x x y y z zP(x,y,zP(x,y,z)x x(y y z zP(x,y,zP(x,y,z)多个量词辖域的定义 x x (y y z zP(x,y,zP(x,y,z)量词的否定律 x x (y y(z zP(x,y,zP(x,y,z)多个量词辖域的定义 x x y y(z zP(x,y,zP(x,y,z)量词的否定律 x x y y
22、 z z P(x,y,zP(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(yy(P(x)Q(y)xP(x)xP(x)yQ(yyQ(y)证明：证明：x x y y(P(x)Q(yP(x)Q(y)x x(y(P(x)Q(yy(P(x)Q(y)多个量词辖域的定义 x x(y(y(P(xP(x)Q(yQ(y)蕴含等价式 x(x(P(xP(x)yQ(yyQ(y)量词辖域的扩张与收缩律 x x P(xP(x)yQ(yyQ
23、(y)同上 (xP(xxP(x)yQ(yyQ(y)量词的否定律 xP(x)xP(x)yQ(yyQ(y)蕴含等价式NUIST2525n前束范式：量词均非否定地放在在全式的开头，没有括 号将它们彼此隔开，而它们的辖域延伸到整 个公式末尾的谓词公式。n前束范式的形式：v1v2.vn A 其中“”表示量词或，v1，v2，.，vn是个体变元，A是不带量词的谓词公式。n前束范式的母式：前束范式中位于所有量词后面的部分，即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-前束析取范式 四、前束范式
24、NUIST2626前束范式存在性定理：任意一个谓词公式，均和一个前束 范式等价。证明：构造性算法进行证明，步骤如下：1 消去对、冗余的联结词。2 利用量词否定律和德摩根律将否定词向内深入，使之 只作用于原子公式。3 利用改名规则或代入规则使所有的约束变元与自由变 元的符号均不同。4 利用量词辖域的扩张和收缩，将所有量词以在公式中 出现的顺序移到全式的最前面，扩大量词的辖域到整 个公式。NUIST2727例1-7-4 求下列公式的前束范式。(1)(1)x x F(xF(x)x x G(xG(x)x x F(x)F(x)x x G(xG(x)蕴涵等价式 x x F(x)F(x)x x G(xG(x)量词否定律 x(x(F(x)G(xF(x)G(x)量词分配的等价式(2)(2)xF(xxF(x)xG(xxG(x)x x F(x)F(x)x x G(xG(x)蕴涵等值式 x x F(x)F(x)x x G(xG(x)量词否定律 x x F(x)F(x)yG(yyG(y)改名规则 x(x(F(x)F(x)yG(yyG(y)量词辖域的收缩与扩张律 x xy y(F(x)G(yF(x)G(y)同上NUIST2828作业 1-7