离散数学(谓词逻辑)课后总结.doc

第2章 谓词逻辑21基本概念 例题 . 所有的自然数都是整数。 设 N(x)：x是自然数。I(x)：x是整数。此命题可以写成 x(N(x)I(x) 例题. 有些自然数是偶数。设 E(x)：x是偶数。此命题可以写成 $x(N(x)E(x) 例题3. 每个人都有一个生母。 设 P(x):x是个人。M(x,y):y是x的生母。此命题可以写成： x(P(x)$y(P(y)M(x,y)2-2 谓词公式及命题符号化 例题1. 如果x是奇数，则2x是偶数。 其中客体x与客体2x之间就有函数关系，可以设客体函数 g(x)=2x， 谓词 O(x)：x是奇数， E(x)：x是偶数， 则此命题可以表示为： x(O(x)E(g(x) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲，谓词D(x):x是个医生，a:小王，此命题可以表示为D(f(a)。 例题3 如果x和y都是奇数，则x+y是偶数。 设 h(x,y)=x+y ，此命题可以表示为:xy(O(x)O(y)E(h(x,y)命题的符号表达式与论域有关系两个公式：一般地，设论域为a1,a2,.,an，则有 (1). xA(x)A(a1)A(a2).A(an) (2). $xB(x)B(a1)B(a2).B(an)1.每个自然数都是整数。该命题的真值是真的。 表达式x(N(x)I(x)在全总个体域的真值是真的,因x(N(x)I(x)(N(a1)I(a1) (N(a2)I(a2) (N(an)I(an) 式中的x不论用自然数客体代入，还是用非自然数客体代入均为真。例如(N(0.1)I(0.1)也为真。 而x(N(x)I(x)在全总个体域却不是永真式。 x(N(x)I(x)(N(a1)I(a1)(N(a2)I(a2) (N(an)I(an) 比如x用0.2代入(N(0.2)I(0.2)就为假。所以此表达式不能表示这个命题。 2.有些大学生吸烟。 此命题的真值也是真的。 $x(S(x)A(x)(S(a1)A(a1)(S(a2)A(a2) (S(an)A(an)且x只有用吸烟的大学生代入才为真，例如a2不是大学生或者不会吸烟的客体，则(S(a2)A(a2)为假。所以用$x(S(x)A(x)表示此命题是对的。 而$x(S(x)A(x)中的x用非大学生的客体代入时也为真，例如(S(a2)A(a2)为真。所以表达式$x(S(x)A(x)不能表示这个命题。3.所有大学生都喜欢一些歌星。 令S(x)：x是大学生，X(x)：x是歌星，L(x,y)：x喜欢y。 则命题的表达式为： x(S(x)$y(X(y)L(x,y) 4.没有不犯错误的人。 此话就是“没有人不犯错误”，“没有”就是“不存在”之意。令P(x)：x是人，F(x)：x犯错误， 此命题的表达式为：$x(P(x)F(x) 或者 x(P(x)F(x)5.不是所有的自然数都是偶数。 令N(x)：x是自然数，E(x)：x是偶数， 命题的表达式为: x(N(x)E(x) 或者 $x(N(x)E(x)6.如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。 令A(x)：x是人，B(x,y)：y是x说的话，C(x):x是谎话，D(x)：x是可以相信的 命题的表达式为: x(A(x)(y(B(x,y)C(y)$z(B(x,z)D(z)7.每个自然数都有唯一的后继数。 令N(x)：x是自然数，A(x,y)：y是x的后继数， E(x,y)：x=y 则命题的表达式为 x(N(x)$y(N(y)A(x,y)z(N(z)A(x,z)E(y,z) 小结1.命题的符号表达式形式与论域有关系。 论域扩大需要用特性谓词对客体进行说明.注意如何添加特性谓词(即要注意特性谓词后边是什么联结词)。2.如果量词前有否定符号，如“没有.”“不是所有的.”等，可以按照字面直译。如“$x” “x.”3.命题的符号表达式中所有客体变元必须都是约束变元，才表示命题。有时给定命题中有些量词没有明确给出，要仔细分析并写出这隐含的量词。 例如 a) 金子闪光，但闪光的不一定都是金子。G(x),F(x) x(G(x)F(x)x(F(x) G(x) b) 没有大学生不懂外语。S(x),K(x,y),F(x)$x(S(x)y(F(y)K(x,y)2-3谓词演算的等价式与蕴涵式 例1.设论域D=1,2 a=1 b=2 f(1)=2 ，f(2)=1P(1,1)=T ，P(1,2)=T ，P(2 ,1)=F P(2,2)=F求谓词公式x$y(P(x,y)P(f(x),f(y)的真值。解： x$y(P(x,y)P(f(x),f(y)$y(P(1,y) P(f(1),f(y) $y(P(2,y) P(f(2),f(y)(P(1,1) P(f(1),f(1) (P(1,2) P(f(1),f(2) (P(2,1) P(f(2),f(1)(P(2,2) P(f(2),f(2) (P(1,1) P(2,2)(P(1,2) P(2,1) (P(2,1) P(1,2)(P(2,2) P(1,1)(TF ) (TF)(FT) (FT)(F F)(T T)FT F量词辖域的扩充公式 1. xA(x)Bx(A(x)B) 2. xA(x)Bx(A(x)B) 3. $xA(x)B$x(A(x)B) 4. $xA(x)B$x(x)B) 5. BxA(x)x(BA(x) 6. B$xA(x)$x(BA(x) 7. xA(x)B$x(A(x)B) 8. $xA(x)Bx(A(x)B)量词分配公式1. $x(A(x)B(x)$xA(x)$xB(x)2. x(A(x)B(x)xA(x)xB(x)3. $x(A(x)B(x)$xA(x)$xB(x)4. xA(x)xB(x)x(A(x)B(x)其它公式1. $x(A(x)B(x)xA(x)$xB(x) 2. $xA(x)xB(x)x(A(x)B(x)两个量词的公式1. xyA(x,y)yxA(x,y)2. xyA(x,y)$yxA(x,y)3. $yxA(x,y)x$yA(x,y)4. x$yA(x,y)$x$yA(x,y)5. yxA(x,y)$xyA(x,y)6. $xyA(x,y)y$xA(x,y)7. y$xA(x,y)$x$yA(x,y)8. $x$yA(x,y)$y$xA(x,y)下面证明公式1.。 证明：设论域为a1,a2,.,an，则xyA(x,y)yA(a1,y)yA(a2,y)yA(an,y) (A(a1,a1)A(a1,a2)A(a1,an)(A(a2,a1)A(a2,a2)A(a2,an) (A(an,a1)A(an,a2)A(an,an) (A(a1,a1)A(a2,a1)A(an,a1) (A(a1,a2)A(a2,a2)A(an,a2) (A(a1,an)(A(a2,an)A(an,an) xA(x,a1)xA(x,a2)xA(x,an) yxA(x,y)例2. 令A(x,y)表示x+y=xy, 论域是1,2,3, 求谓词公式x$yA(x,y)的真值。解： x$yA(x,y)$xyA(x,y) yA(1,y)yA(2,y)yA(3,y) (A(1,1)A(1,2)A(1,3) (A(2,1)A(2,2)A(2,3)(A(3,1)A(3,2)A(3,3) (TTT)(TFT)(TTT) TFTT2-4前束范式例1. xA(x)$xB(x) xA(x)$xB(x) $xA(x)$xB(x) $xA(x)$yB(y) (换元) $x(A(x)$yB(y) (量词辖域扩充) $x$y(A(x)B(y)另一个方法：xA(x)$xB(x) xA(x)$xB(x) $xA(x)$xB(x) $x(A(x)B(x) (量词分配公式)例2.x(P(x)R(x)($xP(x)Q(x) x(P(x)R(x)($xP(x)Q(x) (去) $x(P(x)R(x)(xP(x)Q(x) (量词转换) $x(P(x)R(x)(xP(x)Q(x) (后移) $x(P(x)R(x)(yP(y)Q(z) (换变元) $x(P(x)R(x)y(P(y)Q(z) (扩量词辖域) $xy(P(x)R(x)(P(y)Q(z)(扩量词辖域)2-5 谓词演算的推理理论例1. 令A(x)表示x是自然数，B(x)表示x是整数。 x(A(x)B(x) P A(c)B(c) US 如c=0.1 $xA(x) P A(c) ES A(0.1)为F $xB(x) P B(c) ES 如c=-1 $xA(x) P A(c) ES A(-1)为F正确解法如下： $xA(x) P A(c) ES x(A(x)B(x) P A(c)B(c) US B(c) T I11例2 所有金属都导电。铜是金属。故铜导电。令 M(x):x是金属。C(x):x导电。a:铜。符号化为： x(M(x)C(x),M(a) C(a) x(M(x)C(x) P M(a)C(a) US M(a) P C(a) T I11 例3 所有自然数都是整数。有些数是自然数。因此有些数是整数。令A(x)表示x是自然数，B(x)表示x是整数。x(A(x)B(x)， $xA(x) $xB(x) $xA(x) P A(c) ES x(A(x)B(x) P A(c)B(c) US B(c) T I11 $xB(x) EG 例4不认识错误的人，也不能改正错误。有些诚实的人改正了错误。所以有些诚实的人是认识了错误的人。设A(x):x是认识错误的人。B(x):x改正了错误。C(x):x是诚实的人。符号化为：x(A(x)B(x)，$x(C(x)B(x), $x(C(x)A(x) $x(C(x)B(x) P C(c)B(c) ES C(c) T I1 B(c) T I2 x(A(x)B(x)P A(c)B(c) US A(c) T I12 A(c) T E1 C(c)A(c) T I9 $x(C(x)A(x) EG 例5.“鸟都会飞。猴子都不会飞。所以，猴子都不是鸟。”设 B(x):x是鸟；F(x):x会飞；M(x):x是猴子。x(B(x)F(x),x(M(x)F(x)x(M(x)B(x) 证明： x(B(x)F(x) P B(a)F(a) US x(M(x)F(x) P M(a)F(a) US F(a)B(a) T E18 M(a)B(a) T I13 x(M(x)B(x) UG 例6.$x(A(x)B(x),x(B(x)C(x),xC(x)$xA(x) (1) $x(A(x)B(x) P (2) A(a)B(a) ES (1) (3) x(B(x)C(x) P (4) B(a)C(a) US (3) (5) xC(x) P (6) C(a) US (5) (7) B(a) T (4)(6) I12 (8) A(a) T (2)(7) I10 (9) $xA(x) EG (8)例7 一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。设: P(x):x是病人, D(x):x是医生, Q(x):x是庸医, L(x,y): x喜欢y.请同学将上述各个命题符号化： $x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y) $y(D(y)Q(y)$x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y) $y(D(y)Q(y) $x(P(x)y(D(y)L(x,y) P P(a)y(D(y)L(a,y) ES P(a) T I1 y(D(y)L(a,y) T I2 x(P(x)y(Q(y)L(x,y) P P(a)y(Q(y)L(a,y) US y(Q(y)L(a,y) T I11 D(b)L(a,b) US Q(b)L(a,b) US L(a,b) Q(b) T E18 D(b)Q(b) T I13 D(b)Q(b) T E16 (D(b)Q(b) T E8 y(D(y)Q(y) UG $y(D(y)Q(y) T E25例8 $x(P(x)Q(x) xP(x)$xQ(x)用条件论证证明： xP(x) P (附加前提) $x(P(x)Q(x) P P(a)Q(a) ES P(a) US Q(a) T I11 $xQ(x) EG xP(x)$xQ(x) CP用反证法证明例5： $x(P(x)Q(x) xP(x)$xQ(x) (xP(x)$xQ(x) P(假设前提) (xP(x)$xQ(x) T E16 xP(x)$xQ(x) T E9 xP(x) T I1 $xQ(x) T I2 $x(P(x)Q(x) P P(a)Q(a) ES P(a) US Q(a) T I11 $xQ(x) EG $xQ(x)$xQ(x) T I9 例9.给定谓词如下：S(x):x是学生；L(x):x是校领导； G(x):x是好的；T(x):x是老师；P(x): x受过处分； C(x,y):y表扬x用上述谓词表达下面各个命题，并且用谓词逻辑推理方法证明下面推理的有效性。“没有受过处分的学生，都受到过校领导的表扬；有些好学生，仅仅受到老师的表扬；所有好学生，都没有受过处分。所以，有的老师是校领导。”先请同学将上述各个命题符号化，然后推理。x(S(x)P(x)$y(L(y)C(x,y),$x(S(x)G(x)y(C(x,y)T(y) ,x(S(x) G(x) P(x)$y(T(y)L(y) $x(S(x)G(x)y(C(x,y)T(y) P (S(a)G(a)y(C(a,y)T(y) ES S(a)G(a) T I1 x(S(x) G(x) P(x) P (S(a) G(a) P(a) US P(a) T I11 S(a) T I1 S(a) P(a) T I9 x(S(x)P(x)$y(L(y)C(x,y) P (S(a)P(a)$y(L(y)C(a,y) US $y(L(y)C(a,y) T I11 y(C(a,y)T(y) T I2 L(b) C(a,b) ES C(a,b)T(b) US L(b) T I1 C(a,b) T I2 T(b) T I11 T(b)L(b) T I9 $y(T(y)L(y) EG 例10.用推理证明公式：$yxA(x,y)x$yA(x,y) $yxA(x,y) P xA(x,b) ES A(a,b) US $yA(a,y) EG x$yA(x,y) UG 补充题1.每个人的叔叔都是他父亲的弟弟。 设：P(x):x是人，U(x,y):y是x的叔叔， B(x,y):x是y的弟弟，f(x)=x的父亲 x(P(x)y(U(x,y)B(y,f(x) 2.下面是判定一个年号是否为闰年的命题:“年号能被4整除并且不能被100整除的为闰年， 或者年号能被400整除的也是闰年。” 设 Y(x):x是年号; D(x,y):x可整除y; R(x):x是闰年 x(Y(x)(D(4,x)D(100,x)R(x)(D(400,x) R(x)此式有些问题，因为它等价于 x(Y(x)(D(4,x)D(100,x)D(400,x)R(x)正确答案：1)x(Y(x)(D(4,x)D(100,x)R(x) x(Y(x)(D(400,x) R(x) 2）x(Y(x)(D(4,x)D(100,x)D(400,x) R(x)小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个是登山者而不是滑雪者的成员。如果有，他是谁？设：M(x):x是高山俱乐部成员。H(x):x是滑雪者。 D(x):x是登山者。L(x,y):x喜欢y