《1.7谓词演算的永真公式》由会员分享，可在线阅读，更多相关《1.7谓词演算的永真公式（28页珍藏版）》请在金锄头文库上搜索。
1、NUIST11谓词公式是由原子谓词公式通过联结词、量词 、 小括号组成的字符串。而原子谓词公式(x1，x2，.，xn)中可含有 个体常元、个体变元(约束变元和自由变元)、 谓词常元、谓词变元。显然，对谓词公式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-1 给定一个解释I：D=2，3；D中的特定元素 a=2D上的特定谓词 F(x)为：F(2)=0，F(3)=1L(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
3、)L(2,2)(F(3)L(3,2) (01)(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南京信息工程大学数理学院NUIST44nA在个体域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为永假式(或矛
4、盾式)。 3 如果A至少在一个个体域上可满足，则称A为可满足式。谓词公式的类型南京信息工程大学数理学院NUIST5 5方法一：真值表法 当谓词公式A的个体域E是有限的，谓词变元的解释 也 是有限的时，原则上可以用真值表来判断。方法二：指派分析法 当谓词公式A的个体域E是无限的，或谓词变元的解 释是无限的时，谓词公式A的指派就是无限多个，无 法实现用真值表来判断，一般根据联结词、量词的意 义，直接用自然语言来叙述进行证明。谓词公式类型的判断南京信息工程大学数理学院NUIST6 6例1-7-2 在给定条件下判定谓词公式的类型。 1 设谓词P(x)的含义仅为：A(x)：x是奇数。或 B(x)：x是偶
5、数 。个体域E=3，4，判定谓词公式P(x) xP(x)的类型。x P(x) xP(x) P(x) xP(x)3 A(x)A(3)A(4) 1 A(3) 1 1 3 B(x)B(3)B(4) 1 B(3) 1 04 A(x)A(3)A(4) 1 A(4) 1 04 B(x)B(3)B(4) 1 B(4) 1 1P(x) xP(x)在E上可满足， xP(x)在E上永真。 南京信息工程大学数理学院NUIST772 xP(x)xP(x) 解： 未指明个体域与谓词P(x)的含义-任意多组解释设D为任意一个个体域，I为任意一个指派。若xP(x)为真，即对于D中任意x，P(x)均为真。此时在D中当然至少有
6、一个x，使P(x)为真。则xP(x)为真。所以在指派I下，xP(x)xP(x)取值为真。由I的任意性，xP(x) xP(x)为永真式。 南京信息工程大学数理学院NUIST88n 遍及个体域E等价（永真蕴含）给定个体域E上的两个谓词公式A和B，若对E中的任意指派I ， 1 A、B 都具有相同的真值（即谓词公式AB为永真式）， 则称谓词公式A和B在E上等价，记作：在E上A B。 2 当A为真时，B也为真（即谓词公式AB为永真式），则称谓词公式A在E上永真蕴含B，记作：在E上A B。n等价（永真蕴含） 1 若A和B在任意个体域上都是等价的，则称谓词公式A和B等价，记作：A B。 2 若A和B在任意个
7、体域上都有A永真蕴含B，则称谓词公式A永真蕴含B，记作：A B。二、谓词演算中的逻辑等价式和永真蕴含式南京信息工程大学数理学院NUIST99谓词逻辑中常用的逻辑等价式和永真蕴含式，其来源 可分为两类：一、永真命题公式的推广用原子谓词公式取代命题演算等价公式中的各命题变元， 命题演算的等价式就转化为谓词演算的等价式。 依据：永真式的任何代入实实例也必永真。 例如：1 由 P P 得： A(x) A(x)2 由 PQ PQ 得： xA(x) xB(x) ( xA(x)( xB(x)二、由于引入量词而产生的谓词演算中特有的逻辑等价式、永真蕴含式。常用的逻辑等价式和永真蕴含式南京信息工程大学数理学院N
8、UIST10101量词的消去律 (1)设个体域为有限集D=a1, a2, ,an时，则有nx P(x) P(a1)P(a2)P(an) （1）nx P(x) P(a1) P(a2) P(an) （2）(2) 设A是不含自由变元x的谓词公式，则有 xA A （3） xA A （4）(因为A的真值与自由变元x无关) 与量词有关的逻辑等价式南京信息工程大学数理学院NUIST11112量词的否定律( 量词转换律 )n xP(x) x P(x) （5）n xP(x) x P(x) （6）量词前面的否定词可深入到量词辖域内。 注：出现在量词之前的否定不是否定该量词，而是否定被 量化了的整个命题。 xP(x
9、) ( xP(x)。 例如： 设个体域D为大学生集合，P(x)：x今天来上课。 P(x)：x今天没来校上课。 1 xP(x)：不是所有的大学生今天都来上课。 与 x P(x)：存在一些大学生今天没来上课。（含义相同 ） 2 xP(x)：今天没有(不存在)来上课的大学生。 与 x P(x)：所有的大学生今天都没来上课。（含义相同 ）南京信息工程大学数理学院NUIST12123量词辖域的扩张与收缩律设P是不含自由变元x的任一谓词公式(包括命题公式)，则有：n xA(x)P x（A(x)P） （7）n xA(x)P x（A(x)P） （8）n xA(x)P x（A(x)P） （9）n xA(x)P
10、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)当个体域为无限集时，指派分析证明： 左右同真假 。 南京信息工程大学数理学院NUIST13133量词辖域的扩张与收缩律设P是不含自由变元x的任一谓词公式(包括命题公式) ， 则有：nP xA(x) x( PA(x) ) （11）nP xA(x) x( PA(x) ) （12）n xA(x)P x( A(x)P ) （13）n xA(x)P x( A(x)P ) （14） 前不变后变证明：(13) x
11、(A(x)P) x( A(x)P) 蕴含等价式 x A(x)P 量词辖域的扩张与收缩 律 xA(x)P 量词否定律 xA(x)P 蕴含等价式南京信息工程大学数理学院NUIST14144量词的分配律n x(A(x)B(x) xA(x) xB(x) （15） n x(A(x)B(x) xA(x) xB(x) （16）n 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)： 联欢会上所有的人唱歌且所有的 人跳舞。（含义相同）
12、 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)也是真的。-两个命题是等价的 。 x(A(x)B(x)：D中存在，能使()或者()为真 。 xA(x) xB(x)：D中存在能使()为真，或者D中存 在能使()为真。 -两个命题是等价的。(17) x( A(x)B(
13、x) ) x( A(x)B(x) 蕴含等价式 x A(x) xB(x) 量词分配的等价式 ( xA(x) xB(x) 量词否定律 xA(x) xB(x) 蕴含等价式南京信息工程大学数理学院NUIST16165量词交换律n x yP(x,y) y xP(x,y) （18）n x yP(x,y) y xP(x,y) （19） 证明：当个体域为有限集时，为讨论方便不妨取D=1,2则 x yP(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) ) y xP(x,y) y( P(1,y) P(2,y) ) ( P(1,1)P(2,1) )( P(1,2) P(2,2) ) 当个体域为无限集时，指派分析证明： 左右同真假。南京信息工程大学数理学院NUIST17171量词消去的蕴含式n xP(x) P(a) (1)或 xP(x) P(y)、 xP(x) P(x)nP(a) xP(x) (2)或 P(y) xP(x)、 P(x) xP(x)nxP(x) xP(x) (3)与量词有关的永真蕴含式南京信息工程大学数理学院NUIST18182量词分配的蕴含式n xA(x) x
