离散数学(第五章)

1、2.1谓词的概念与表示谓词的概念与表示(2.2谓词公式与翻译谓词公式与翻译(Predicate formulae2.3谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式(Equivalences & implications of predicate calculus)2.4前束范式前束范式(Prenex normal form2.5谓词演算的推理理论谓词演算的推理理论(Inference theory of predicate calculus)一、一、谓词的等价和永真的概念谓词的等价和永真的概念定义定义1:给定任意的谓词公式给定任意的谓词公式A,其个体域为其个体域为E,对于对于A的所

2、的所有赋值有赋值,公式公式A都为真都为真,则称则称A在在E上是上是永真的永真的(或有效或有效的的);若对于若对于A的所有赋值的所有赋值,公式公式A都为假都为假,则称则称A在在E上上是是永假的永假的(或不可满足的或不可满足的);若至少存在着一种赋值使若至少存在着一种赋值使得公式得公式A为真为真,则称则称A在在E上是上是可满足的可满足的.v定义定义2:给定任何两个谓词公式给定任何两个谓词公式A、B，设它们有共同，设它们有共同的个体域的个体域E，若对，若对A和和B的任一组变元进行赋值，所的任一组变元进行赋值，所得命题的真值相同，则称得命题的真值相同，则称谓词公式谓词公式A和和B在在E上等价上等价，并

3、记为，并记为A B2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 在命题逻辑中给出了一些常见等价公式和在命题逻辑中给出了一些常见等价公式和蕴含式蕴含式,只要用只要用原子谓词公式原子谓词公式去代替第一章去代替第一章中永真蕴含式和等价公式中的中永真蕴含式和等价公式中的原子命题变原子命题变元元，则在第一章中永真蕴含式和等价公式，则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真蕴含式和等价均可变成谓词演算中的永真蕴含式和等价公式：公式：2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 命题逻辑命题逻辑 谓词逻辑谓词逻辑

4、(x)(x) (x)(x)(x) . . . . (x)(x) (x) (x) (x)(x)(x) (x)(x) (x) . . . . . .2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则下面给出涉及量词的一些等价式。下面给出涉及量词的一些等价式。(1) (1) 消去量词的等价式消去量词的等价式设个体域为：设个体域为：S=aS=a1 1,a,a2 2,a,an n ，我们有：，我们有： x xA(x)A(x)A(A(a a1 1) ) A( A(a a2 2) ) A( A(a an n) ) xA(x) xA(x) A(A(a a1 1) ) A(A(a a2 2) ) A( A

5、(a an n) ) 2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则v例例1 设设 P(x)表示表示x喜欢梦八队，则喜欢梦八队，则 P(x)表示表示x不不喜欢梦八队。喜欢梦八队。(个体域限定为人个体域限定为人)（1）不是所有人都喜欢梦八队：）不是所有人都喜欢梦八队： ( x)P(x) （2）存在一些人不喜欢梦八队：）存在一些人不喜欢梦八队： ( x) P(x) （3）不会有人喜欢梦八队：）不会有人喜欢梦八队： ( x)P(x) （4）所有人都不喜欢梦八队：）所有人都不喜欢梦八队： ( x) P(x) v可以看出命题可以看出命题(1)(2)意义完全相同，意义完全相同，(3)(4)意义也

6、完全相同意义也完全相同2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则（2）量词否定转换律）量词否定转换律 xP(x) xP(x) xP(x) xP(x) 下面证明：下面证明： xP(x) xP(x)设个体域为：设个体域为： S=a1,a2,an xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an) xP(x)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则举例说明量化命题和非量化命题的差别举例说明量化命题和非量化命题的差别:否定形式不同否定形式不同例：例： 否定下列命题：否定下列命题： (a)上海是一个小城镇上海是一个小城镇 A(s) (b)每

7、一个自然数都是偶数每一个自然数都是偶数 x(N(x)E(x)上述二命题的否定为：上述二命题的否定为： (a)上海不是一个小城镇上海不是一个小城镇 A(s) (b)有一些自然数不是偶数有一些自然数不是偶数 x(N(x)E(x)x(N(x)E(x) x(N(x) E(x) x (N(x) E(x)结论：对于非量化命题的否定只需将动词否定，而对结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是：时进行否定，其方法是： x的否定变为的否定变为 x ， x的的否定变为否定变为 x 。2.3 一阶逻

8、辑等值式与置换规则一阶逻辑等值式与置换规则量词转换律的推广应用量词转换律的推广应用:把把深入到谓深入到谓词公式前面去的方法。词公式前面去的方法。 x yP(x,y,z) x yP(x,y,z) x yP(x,y,z) 2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则（3 3）量词辖域的扩张与收缩）量词辖域的扩张与收缩量词辖域中如果有合取或析取项，且其中有一个量词辖域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词辖域之外：是命题，则可将该命题移至量词辖域之外：（ x）（A(x)B）（ x）A(x)B（ x）（A(x)B）（ x）A(x) B（ x）（A(x)B）（ x）A

9、(x)B（ x）（A(x)B）（ x）A(x)B 2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则证明：证明： xA(x) B x(A(x) B)设个体域为：设个体域为： S=a1,a2,an xA(x) B (A(a1) A(a2) A(an) B (A(a1) B) (A(a2) B) (A(an) B) x(A(x) B) 2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则从上述几个等价公式可以推出如下的等价式：从上述几个等价公式可以推出如下的等价式： xA(x)B x(A(x)B) xA(x)B x(A(x)B)A xB(x) x(AB (x)A x B(x) x(AB

10、(x)证明证明： xA(x)B x(A(x)B) xA(x)B xA(x) B x A(x) B x （ A(x) B） x(A(x)B)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则（4 4）量词分配律）量词分配律 x(A(x) B(x) xA(x) xB(x) x (A(x) B(x) xA(x) xB(x) x (A(x) B(x) xA(x) xB(x) x (A(x) B(x) xA(x) xB(x) xA(x) xB(x) x(A(x) B(x) xA(x) xB(x) x(A(x) B(x)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则证明：证明： x(A(x

11、) B(x) xA(x) xB(x)设个体域为：设个体域为： S=a1,a2,an x(A(x) B(x) (A(a1) B(a1) . (A(an) B(an) (A(a1) A(an) (B(a1) B(an) xA(x) x B(x)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则x(A(x)B(x) x A(x) x B(x)？ 举例：举例：令令 x x的个体域为正整数。的个体域为正整数。 A(x) A(x)：x x是奇数是奇数 B(x)B(x)：x x是偶数是偶数 x x ( (A(x) A(x) B(x)B(x) ) 所有正整数是奇数所有正整数是奇数或者或者偶数。偶数。 x

12、 A(x) x A(x) x B(x)x B(x) 所有正整数都是奇数所有正整数都是奇数或者或者所有正整数都是所有正整数都是偶数。偶数。2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则(x)(A(x)B(x) (x)A(x) (x)B(x)？举例：举例：令令 x x的个体域为正整数。的个体域为正整数。 A(x) A(x)：x x是奇数是奇数 B(x)B(x)：x x是偶数是偶数 x x ( (A(x) A(x) B(x)B(x) ) 存在既是奇数存在既是奇数又是又是偶数的正整数。偶数的正整数。 x A(x) x A(x) x B(x)x B(x) 存在为奇数的正整数存在为奇数的正整数且

13、且存在为偶数的正整存在为偶数的正整数。数。2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 量词与联结词量词与联结词，的关系总结的关系总结：1) x(A(x) B(x) x A(x) xB(x) x(A(x)B(x) x A(x) x B(x)2) x (A(x) B(x) x A(x) x B(x) x (A(x) B(x) x A(x) x B(x)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则v对于二元谓词有八种情况：对于二元谓词有八种情况：1.( x)( y)A(x,y)2.( x)( y)A(x,y)3.( x)( y)A(x,y)4.( x)( y)A(x,y)5

14、.( y)( x)A(x,y)6.( y)( x)A(x,y)7.( y)( x)A(x,y)8.( y)( x)A(x,y)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则（5）含有多个量词的）含有多个量词的等价式等价式 在含有多个量词的谓词公式中在含有多个量词的谓词公式中, x y, x y的位置是可以改变的的位置是可以改变的,且不影响命题的真值。且不影响命题的真值。 即即相同量词间的次序是可以任意调动的，相同量词间的次序是可以任意调动的，不同量词间的次序则不能随意调动。所以不同量词间的次序则不能随意调动。所以有：有： x yP(x,y) y xP(x,y) x yP(x,y) y

15、 xP(x,y)2.3 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则 若谓词公式中出现多个不同量词时，则按照若谓词公式中出现多个不同量词时，则按照从左到右从左到右的次序读出，不能颠倒次序。的次序读出，不能颠倒次序。例：例： y x(xy-2)表示任何表示任何y均存在均存在x，使得，使得x( x)P(x)( x)Q(x) (附加前提法附加前提法)v证明：证明：(1) ( x)P(x) P(附加前提附加前提) (2) ( x)P(x) T(1) (3) P(c) ES(2) (4) x(P(x)Q(x) P (5) P(c)Q(c) US(4)2.5 一阶逻辑的推理理论一阶逻辑的推理理论v(6

16、) Q(c) T(3)(5)v(7)( x)Q(x) EG(6)v(8) ( x)P(x) ( x)Q(x) CP小结：小结：本节介绍了谓词演算的推理规则本节介绍了谓词演算的推理规则,并举例说并举例说明了它们的应用明了它们的应用. 重点重点:深刻理解四个推理规则深刻理解四个推理规则,会应用它们推理证明会应用它们推理证明.作业作业: P85 12、15、 242.5 一阶逻辑的推理理论一阶逻辑的推理理论Cp 规则证明规则证明例：证例：证: x (P(x)Q(x) x P(x) xQ(x) 证明：证明：(1) x P(x)附加前提附加前提 (2) x (P(x)Q(x) P (3)P(c) Q(c

17、) ES (2) (4) P(c) US(1) (5) Q(c) T(3)(4)I (6) xQ(x) EG(5) (7) x P(x)xQ(x) CP2.5 一阶逻辑的推理理论一阶逻辑的推理理论反证法反证法例：证明：例：证明： x(P(x) Q(x), xP(x) xQ(x) (1) xQ(x) 附加前提附加前提 (2) xQ(x) T(1)E (3) Q(c) US(2) (4) xP(x) P (5) P(c) US(4) (6) P(c) Q(c) T(3)(5)I (7) x(P(x) Q(x) UG(6) (8) x(P(x) Q(x) P (9) x(P(x) Q(x) x(P(

18、x) Q(x) T(7)(8)I (10) F2.5 一阶逻辑的推理理论一阶逻辑的推理理论例例 将下列推理符号化并给出形式证明将下列推理符号化并给出形式证明: : 每一个大学生不是文科生就是理科生；有的大每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。此，如果小张是大学生，他就是理科生。n解解 个体域取全总个体域，设个体域取全总个体域，设P(x)：x是大学生，是大学生，Q(x)：x是文科生，是文科生，S(x)：x是理科生，是理科生，T(x)：x是优等生，是优等生，c：小张，则：小张，则前提：前提： x(P(x)(Q(x) S(x)， x(P(x) T(x)， Q(c) T(c)结论：结论：P(c)S(c)2.5 一阶逻辑的推理理论一阶逻辑的推理理论推理形式：推理形式： x(P(x)(Q(x) S(x), x(P(x) T(x)， Q(c) T(c)P(c)S(c) 证明：证明： (1) P(c) 附加前提附加前提 (2) x(P(x)(Q(x) S(x) P (3) P(c)(Q(c) S(c) US(