1.7谓词演算的永真公式.ppt

《1.7谓词演算的永真公式.ppt》由会员分享，可在线阅读，更多相关《1.7谓词演算的永真公式.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)(11) 0 2 xy L

3、(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上永真。,2 xP(x)xP(x) 解： 未指明个体域与谓词P(x)

5、的含义 -任意多组解释 设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也为真（即谓词公式AB为永真式）， 则称谓词公式A在E上永真蕴含B，记作：在E上AB。 等价（永真蕴

6、含） 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)xB(x) (xA(x)(xB(x) 二、由于引入量词而产生的谓词演算中特有的逻辑等价式、

7、永真蕴含式。,常用的逻辑等价式和永真蕴含式,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） 量词前面的否定词可深入到量词辖域内。 注：出现在量词之前的否定不是否定该量词，而是否定被量化了的整个命题。 xP(x) (xP(

8、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)Px（A(x)P） （10） 证明：当个体域为有限集a1, a2,., an

9、时， 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)P 量词否定律 xA(x)P

10、 蕴含等价式,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)： 联欢会上有人唱歌，或联欢会上有 人跳舞。（含义相同）,证明：设D为任意一个个体域，I为任意一

11、个指派。 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,y) （18） xyP

12、(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)

13、xP(x) xP(x) (3),与量词有关的永真蕴含式,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)

14、yxP(x,y) （7） yxP(x,y) xyP(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中所有的同名自由个体变元都用另一个自由个体变元来代替，且新变元在原来的公式中没有出现过

15、。 例如：xF(x)G(x,y) xF(x)G(u,y) xF(x)G(y,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)

16、 Q(x,t)R(x,t) 代入规则 故C P(x)(Q(x,t) R(x,t) ),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(

17、x,y,z) ) 量词的否定律 xyz P(x,y,z) 同上 2 设个体域D=a,b,c， 将下列公式中的量词消去。 (1) x(F(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) 蕴含等价式,前束范式：量

18、词均非否定地放在在全式的开头，没有括 号将它们彼此隔开，而它们的辖域延伸到整 个公式末尾的谓词公式。 前束范式的形式： v1v2.vn A 其中“”表示量词或，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 消去对、冗余的联

19、结词。 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,