《离散数学课件2-5谓词演算的等价式》由会员分享，可在线阅读，更多相关《离散数学课件2-5谓词演算的等价式（22页珍藏版）》请在金锄头文库上搜索。
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): xy 原公式解释成: “3-35”。,2-5
2、谓词演算的等价式,定义2：谓词逻辑有效(永真)式(tautology)： 给定任意谓词公式wff A，其个体域为E，对于A的所有赋值，wff A都为真，则称wff A在E上是有效（永真）式。 命题逻辑永真式（重言式）: 给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称命题公式为重言式或永真公式。,2-5谓词演算的等价式,定义3；谓词逻辑不可满足式： 一个谓词公式wff A，如果在所有赋值下都为假，则称该wff A为不可满足的。 命题逻辑永假式（矛盾式）: 给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称命题公式为永假式或矛盾式。,2-5谓词演算的等价式,
3、定义4：谓词逻辑可满足式： 一个wff A，如果至少在一种赋值下为真，则称该wff A为可满足的。,2-5谓词演算的等价式,定义5：逻辑等价式 (logically equivalent ) ： 给定任何两个谓词公式wff A和wff B，设它们有共同的个体域E，若对A和B的任一组变元进行赋值所得的命题的真值相同，则称谓词公式A和B在E上是等价的，并记作AB。 注记: 1. A和B必须在同一个体域讨论是否等价之问题 2. 必须是任意变元赋值后二者的真值都相同,2-5谓词演算的等价式,举例说明： 等价： AB 读作：A等价于B 含义：A与B在各种赋值下取值均相等 AB 当且仅当 A B是永真式,
4、2-5谓词演算的等价式,假设全体域为所有大学生, F(x): x喜欢玩World of Warcraft (x)F(x)表示有三种相同意义的解释： 每一个大学生都喜欢World of Warcraft这件事不正确 不是每一个大学生都喜欢玩World of Warcraft 存在大学生不喜欢玩World of Warcraft (x)F(x) 故： (x)F(x)(x)F(x),2-5.1命题公式的推广,命题演算中的等价公式和蕴含公式都可以推广到谓词演算中使用。 例1：AA, 令A=(x)F(x), 得到 (x)F(x)(x)F(x) 例2：ABAB, 令A=F(x), B=G(y), 得到 F
5、(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(x) (x)P(x) 注意：出现在量词前的否定表示否定整个被量化的命题。,2-5. 3 量词作用域扩张与收
6、缩,定理：量词作用域扩张与收缩等价式(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: (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 量词作用域扩张与收缩,（
7、2） (x)A(x)B) (x)(A(x)B) (x)A(x)B) (x)(A(x)B) (B(x)A(x) (x)(BA(x) (B(x)A(x) (x)(BA(x) 说明: B中不含x的出现,例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 例2：(x)(BA(x) B(x)A(x) 证明: (x)(BA(x) (x)(BA(x) B(x)A(x) B(x)A(x) B(x)A(x),例3：(x)(A(x)B) (x)A(x)B 证明: (x)(A(x)B) (x)(A(x)B) (x)A
8、(x)B (x)A(x)B (x)A(x)B 例4：(x)(BA(x) B(x)A(x) 证明: (x)(BA(x) (x)(BA(x) B(x)A(x) B(x)A(x) B(x)A(x),2-5. 4 量词分配等价式,定理：量词分配等价式（P69） (1) (x)(A(x)B(x) (x)A(x)(x)B(x) (2) (x)(A(x)B(x) (x)A(x)(x)B(x) 我们称(1)为“对满足分配律”， (2)为“对满足分配律”。 但是要注意：“对”以及“对”不存在分配等价式。,2-5. 4 量词分配等价式,联欢会上所有人既唱歌又跳舞和联欢会上所有人唱歌且所有人跳舞。这两个语句意义相同
9、。因此有： (x)(A(x)B(x) (x)A(x)(x)B(x) 根据上式有： (x)(A(x)B(x) (x)(A(x)B(x) (x)(A(x) B(x) (x)A(x)(x)B(x) ( (x) A(x)(x) B(x) (x) A(x) (x) B(x),2-5. 5 量词分配蕴含式,定理：量词分配蕴含式 1.(x)(A(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) 个体域为全体自然数; A(x): x是偶数 B(x): x是奇数; 左T, 右F,2.(x)(A(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) 个体域为全体自然数; A(x): x是偶数 B(x): x是奇数; 左 F, 右T,2-5. 6 量词分配蕴含式,定理：量词次序等价式 见P70 定理：量词次序蕴含式 见P71,作业(2-5),P72 (2) c) (4) (7),
