谓词演算的永真公式

《谓词演算的永真公式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、(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=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)∧L(2,2))∧(F(3)∧L(3,2))(0∧1)∧(1∧1)02∀x∃y

3、L(x,y)∀x(L(x,2)∨L(x,3))(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))(1∨0)∧(0∨1)1A在个体域E上的分类给定谓词公式A及个体域E，如果在个体域E中无论怎样构成A的一种指派：1A都取值为真，则称A在E上永真或A在E上上逻辑有效。2A都取值为假，则称A在E上永假或A在E上矛盾。3A至少在一种指派下取值为真，则称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)的类型。xP(x)xP(x)P(x)∧xP(x)3A(x)A(3)∨A(4)1A(3)∧113B(x

5、)B(3)∨B(4)1B(3)∧104A(x)A(3)∨A(4)1A(4)∧104B(x)B(3)∨B(4)1B(4)∧11P(x)∧xP(x)在E上可满足，xP(x)在E上永真。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上的

6、两个谓词公式A和B，若对E中的任意指派I，1A、B都具有相同的真值（即谓词公式A↔B为永真式），则称谓词公式A和B在E上等价，记作：在E上AB。2当A为真时，B也为真（即谓词公式A→B为永真式），则称谓词公式A在E上永真蕴含B，记作：在E上AB。等价（永真蕴含）1若A和B在任意个体域上都是等价的，则称谓词公式A和B等价，记作：AB。2若A和B在任意个体域上都有A永真蕴含B，则称谓词公式A永真蕴含B，记作：AB。二、谓词演算中的逻辑等价式和永真蕴含式谓词逻辑中常用的逻辑等价式和永真蕴含式，其来源可分为两类：一、永真命题公式的推广用原子谓词公式取代命题演算等价公式中的各命

7、题变元，命题演算的等价式就转化为谓词演算的等价式。依据：永真式的任何代入实例也必永真。例如：1由PP得：A(x)A(x)2由P→QP∨Q得：xA(x)→xB(x)(xA(x))∨(xB(x))二、由于引入量词而产生的谓词演算中特有的逻辑等价式、永真蕴含式。常用的逻辑等价式和永真蕴含式1．量词的消去律(1)设个体域为有限集D={a1,a2,…,an}时，则有∀xP(x)P(a1)∧P(a2)∧…∧P(an)（1）∃xP(x)P(a1)∨P(a2)∨…∨P(an)（2）(2)