离散数学课件 2-5谓词演算的等价式.ppt

《离散数学课件 2-5谓词演算的等价式.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、2-5谓词演算的等价式与蕴含式定义1：谓词公式的赋值（谓词公式的解释）：在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值以后，就成为具有确定真值的命题。2-5谓词演算的等价式谓词公式赋值的举例说明：F(f(a,a),b)解释1：个体域是全体自然数;a:2;b:4;f(x,y)=x+y;F(x,y):x=y原公式解释成:“2+2=4”。解释2：个体域是全体实数;a:3;b:5;f(x,y)=x-y;F(x,y):x>y原公式解释成:“3-3>5”。2-5谓

2、词演算的等价式定义2：谓词逻辑有效(永真)式(tautology)：给定任意谓词公式wffA，其个体域为E，对于A的所有赋值，wffA都为真，则称wffA在E上是有效（永真）式。命题逻辑永真式（重言式）:给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称命题公式为重言式或永真公式。2-5谓词演算的等价式定义3；谓词逻辑不可满足式：一个谓词公式wffA，如果在所有赋值下都为假，则称该wffA为不可满足的。命题逻辑永假式（矛盾式）:给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称命题公式为永假式或矛盾式。2-5

3、谓词演算的等价式定义4：谓词逻辑可满足式：一个wffA，如果至少在一种赋值下为真，则称该wffA为可满足的。2-5谓词演算的等价式定义5：逻辑等价式(logicallyequivalent)：给定任何两个谓词公式wffA和wffB，设它们有共同的个体域E，若对A和B的任一组变元进行赋值所得的命题的真值相同，则称谓词公式A和B在E上是等价的，并记作AB。注记:1.A和B必须在同一个体域讨论是否等价之问题2.必须是任意变元赋值后二者的真值都相同2-5谓词演算的等价式举例说明：等价：AB读作：A等价于B含义：A与B在各种赋值下取值均相等AB当且

4、仅当AB是永真式2-5谓词演算的等价式假设全体域为所有大学生,F(x):x喜欢玩WorldofWarcraft(x)F(x)表示有三种相同意义的解释：每一个大学生都喜欢WorldofWarcraft这件事不正确不是每一个大学生都喜欢玩WorldofWarcraft存在大学生不喜欢玩WorldofWarcraft(x)F(x)故：(x)F(x)(x)F(x)2-5.1命题公式的推广命题演算中的等价公式和蕴含公式都可以推广到谓词演算中使用。例1：AA,令A=(x)F(x),得到(x)F(x)(x)F(x)例2：A

5、→BA∨B,令A=F(x),B=G(y),得到F(x)→G(y)F(x)∨G(y)2-5.2量词与联结词之间的关系定理：量词否定等价式(1)(x)P(x)(x)P(x)假设全体域为所有大学生，P(x)表示x玩WOW.则(x)P(x)表示所有大学生玩WOW(x)P(x)表示所有大学生玩WOW这件事情不对，即存在某些大学生不玩WOW，所以(x)P(x)(x)P(x)2-5.2量词与联结词之间的关系(x)P(x)表示存在大学生玩WOW这件事情不对，即不存在大学生玩WOW，即所有大学生都不玩WOW，故(x)P

6、(x)(x)P(x)注意：出现在量词前的否定表示否定整个被量化的命题。2-5.3量词作用域扩张与收缩定理：量词作用域扩张与收缩等价式(P68)(1)(x)(A(x)∨B)(x)A(x)∨B(x)(A(x)∧B)(x)A(x)∧B(x)(A(x)∨B)(x)A(x)∨B(x)(A(x)∧B)(x)A(x)∧B说明:B中不含x的出现例1:(x)(F(x)∨G(y))(x)F(x)∨G(y)例2:(x)(y)(F(x)∧G(y))(x)(F(x)∧(y)G(y))(x)F(x)∧(y)G(y)例3:

7、(x)(F(x)∨G(y))(x)F(x)∨G(y)例4:(x)(y)(F(x)∧G(y))(x)(F(x)∧(y)G(y))(x)F(x)∧(y)G(y)2-5.3量词作用域扩张与收缩（2）((x)A(x)→B)(x)(A(x)→B)((x)A(x)→B)(x)(A(x)→B)(B→(x)A(x))(x)(B→A(x))(B→(x)A(x))(x)(B→A(x))说明:B中不含x的出现例1：(x)(A(x)→B)(x)A(x)→B证明:(x)(A(x)→B)(x)(A(x)∨B)(

8、x)A(x)∨B(x)A(x)∨B(x)A(x)→B例2：(x)(B→A(x))B→(x)A(x)证明:(x)(B→A(x))