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

2—1基本概念

 例题１ . 所有的自然数都是整数。

    设 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

求谓词公式xy(P(x,y)P(f(x),f(y)))的真值。

解： xy(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)∨Bx(A(x)∨B)

      4. xA(x)∧Bx(Ａ(x)∧B)

      5. B→xA(x)x(B→A(x))

      6. B→xA(x)x(B→A(x))

      7. xA(x)→Bx(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)xyA(x,y)

4. xyA(x,y)xyA(x,y)

5. yxA(x,y)xyA(x,y)

6. xyA(x,y)yxA(x,y)

7. yxA(x,y)xyA(x,y)

8. xyA(x,y)yxA(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}, 求谓词公式xyA(x,y)的真值。

解： xyA(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))

   (T∧T∧T)∨(T∧F∧T)∨(T∧T∧T)

   T∨F∨TT

2-4    前束范式

例1. xA(x)→xB(x)

   xA(x)∨xB(x)  xA(x)∨xB(x)

   xA(x)∨yB(y)     (换元)

   x(A(x)∨yB(y))   (量词辖域扩充)

   xy(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)xyA(x,y)

    ⑴ yxA(x,y)    P

    ⑵ xA(x,b)        ES ⑴

    ⑶ A(a,b)            US  ⑵

    ⑷ yA(a,y)        EG ⑶

⑸ xyA(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。

       a:小杨；b:小刘；c:小林；d:雨；e:雪。

命题符号化为：M(a),  M(b),  M(c),   x(M(x)→( H(x)∨D(x))), x(D(x)∧L(x,d)),  x(H(x)→L(x,e))x(L(a,x)→L(b,x)),  L(a,d)∧L(a,e)

⑴  L(a,d)∧L(a,e)                   P

⑵  L(a,e)                                 T   ⑴ 

⑶  x(L(a,x)→L(b,x))      P 

⑷  L(a,e)→L(b,e)               US ⑶

⑸  L(b,e)                             T   ⑵ ⑷ I11

⑹ x(H(x)→L(x,e))              P

⑺ H(b)→L(b,e)                     US  ⑹

⑻ H(b)                                T    ⑸ ⑺ I12

⑼ x(M(x)→(H(x)∨D(x))) P

⑽ M(b)→(H(b)∨D(b))        US ⑼

⑾ M(b)                                   P

⑿ H(b)∨D(b)                       T    ⑽ ⑾ I11

⒀ D(b)                                   T    ⑻ ⑿ I10

⒁ D(b)∧H(b)                    T    ⑻ ⒀

一 .将下面命题符号化

  1.只有你考试和体检都合格，才会被录取。

  2.上大学的人都需要参加高考。（A(x):x是人，B(x):x上大学，C(x,y)：x参加y，D(x)：x是高考。） 

二.将命题公式A(P,Q,R)化简。其中

A(P,Q,R)(PQR)(PQR)(PQR)(PQR)

(PQR)(PQR)

三.令f(x)=x2,P(x):x是奇数,Q(x,y):x≥y,论域 D 

  D={-1,0,1},求谓词公式x(P(f(x))Q(f(x),x))

的真值.(要求有解题的过程)

四.用谓词逻辑推理证明下面推理的有效性。(按照教材格式写出推理过程)

  x(A(x)y(B(y)C(x,y))), x(A(x)y(C(x,y)D(y))), x(A(x)yD(y)) 

yB(y)

第二章  小结

本章重点掌握内容：

1.各基本概念清楚。

2.会命题符号化。

3.熟练掌握等价公式和永真蕴涵式。

4.会写前束范式。

5.熟练掌握谓词逻辑的三种推理方法。