离散数学谓词逻辑

1、谓词逻辑习题课第九周2014.11命题符号化命题符号化讨论在给定解释下谓词公式的真值讨论在给定解释下谓词公式的真值判断公式是不是永真式，并加以说明判断公式是不是永真式，并加以说明转换前束合取范式转换前束合取范式推理证明推理证明1.将下列命题符号化将下列命题符号化(1)(1)没有不犯错误的人没有不犯错误的人(2) 发光的不都是金子发光的不都是金子(3) 一切人都不一样高一切人都不一样高(4) 并不是所有的汽车都比火车快并不是所有的汽车都比火车快(5)不管黑猫白猫，抓住老鼠就是好猫不管黑猫白猫，抓住老鼠就是好猫(6)有唯一的偶素数有唯一的偶素数(7)对平面上任意两点，有且仅有一条直线通过这对平面上

2、任意两点，有且仅有一条直线通过这 两点两点(1) 没有不犯错误的人没有不犯错误的人 存在不犯错误的人是不可能的。存在不犯错误的人是不可能的。 只要是人，必然犯错误。只要是人，必然犯错误。 设设 M(x): x是人，是人，F(x):x犯错误犯错误命题符号化为命题符号化为 ( x)(M(x)F(x) ( x)(M(x)F(x)(2) 发光的不都是金子发光的不都是金子 不是发光的东西都是金子。不是发光的东西都是金子。 存在着发光的东西不是金子。存在着发光的东西不是金子。 设设 L(x)：x是发光的东西，是发光的东西，G(x)：x是金子。是金子。 命题符号化为命题符号化为 ( x)(L(x)G(x)

3、( x)(L(x)G(x) (3) 一切人都不一样高一切人都不一样高 设设 F(x):x是人是人, H(x,y), x与与y相同相同, L(x,y): x与与y一样高，一样高， 命题符号化为命题符号化为 ( x)(F(x)y(F(y)H(x,y)L(x,y) 或或 ( x) y(F(x) F(y)H(x,y)L(x,y)(4) 并不是所有的汽车都比火车快并不是所有的汽车都比火车快 设设 F(x):x是汽车是汽车, G(y):y是火车是火车, H(x,y):x比比y快，快， 命题符号化为命题符号化为 ( x) y(F(x) G(y)H(x,y) 或或 ( x) y(F(x) G(y)H(x,y)

4、（5）不管黑猫白猫，抓住老鼠就是好猫不管黑猫白猫，抓住老鼠就是好猫 需要考虑问题：需要考虑问题：只是限制黑猫白猫，还是包含其它颜色的猫？只是限制黑猫白猫，还是包含其它颜色的猫？是指至少抓住一只就可以，还是抓住所有的？是指至少抓住一只就可以，还是抓住所有的？ 设设 C(x):x是猫是猫,W(x):x是白的是白的,B(x):x是黑的是黑的 G(x):x是好的是好的,M(x):x是老鼠是老鼠, K(x):x抓住抓住y命题符号化为命题符号化为( x) y(C(x)M(y)(B(x)W(x)K(x,y)G(x) (6)有唯一的偶素数有唯一的偶素数 设：设：Q(x):x是偶数是偶数,P(x):x是素数是素

5、数, E(x,y):xy 命题符号化为：命题符号化为： ( x)(Q(x) P(x)y(Q(y) P(y)E(x,y) (7)对平面上任意两点，有且仅有一条直线通过这对平面上任意两点，有且仅有一条直线通过这 两点两点 设设 P(x):x是一个点是一个点, L(x):x是一条直线是一条直线 R(x,y,z):z通过通过x,y, E(x,y):x等于等于y 命题符号化为命题符号化为 ( x) y(P(x)P(y)E(x,y) z(L(z)R(x,y,z) u(L(u)R(x,y,u)E(u,z)2.讨论在给定解释下谓词公式的真值讨论在给定解释下谓词公式的真值（1） x(PQ(x)R(a)D=-2,

6、3,6 , P:21,Q(x):x3, R(x):x5,a:5（2） x y(P(x)Q(x,y)D= 1,2，P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F（1） x(PQ(x)R(a)D=-2,3,6 , P:21,Q(x):x3, R(x):x5,a:5 x(PQ(x)R(a)(P xQ(x)R(a)(P(Q(-2)Q(3)Q(6)R(5)(T(T T F )F(TF)FFF F（2） x y(P(x)Q(x,y)D= 1,2，P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F真值为真值为

7、F3.判断下列公式是不是永真式，并加以说明判断下列公式是不是永真式，并加以说明（1）( xP(x) xQ(x) x(P(x) Q(x)解：不是永真式，取解释如下解：不是永真式，取解释如下 D= 1,2 P(1) P(2) Q(1) Q(2) F T F T在该解释下在该解释下 xP(x) 为为T， xQ(x)为为F，所以，所以 xP(x) xQ(x)为为F；而；而(P(1) Q(1)为为T， (P(2) Q(2)为为T，所以所以 x(P(x) Q(x)为为T；综上该公式不是永真式；综上该公式不是永真式4. 转换前束合取范式转换前束合取范式(1) 将谓词公式将谓词公式( x)( y)P(x) (

8、 z)Q(z,y) ( y)R(x,y)化为化为与之等价的前束合取范式与之等价的前束合取范式第一步，取消多余量词：第一步，取消多余量词： ( x)P(x) ( z)Q(z,y) ( y)R(x,y)第二步，约束变量换名：第二步，约束变量换名： ( x)P(x) ( z)Q(z,y) ( w)R(x,w)第三步，消去条件联结词：第三步，消去条件联结词： ( x) (P(x) ( z)Q(z,y) ( w)R(x,w)第四步，将第四步，将 深入：深入： ( x)( P(x) ( z)Q(z,y) ( w) R(x,w) ( x)( P(x) ( z) Q(z,y) ( w) R(x,w)第五步，将

9、量词提前：第五步，将量词提前： ( x)( z)( w)( P(x)Q(z,y) R(x,w) ( x)( z)( w) ( P(x)R(x,w) ( Q(z,y) R(x,w) ) 5.推理证明：推理证明：(1) ( x)(P(x)Q(x) ( x)P(x)( x) Q(x)因为因为( x)P(x)( x) Q(x) ( x)P(x)( x) Q(x) ( x)P(x) P(附加前提附加前提) ( x) P(x) T E P(a) ES ( x)(P(x)Q(x) P P(a)Q(a) US Q(a) T I ( x) Q(x) EG ( x)P(x)( x) Q(x) CP(2) xP(x

10、) xQ(x) x (P(x)Q(x)(1) x (P(x)Q(x)P(假设假设)(2) x (P(x)Q(x)T(1)E(3) (P(c)Q(c)ES(2)(4) P(c) Q(c)T(3)E(5) P(c) T(4)I(6) x P(x)EG(5)(7) x P(x) T(6)E(8) xP(x) xQ(x) P(9) xQ(x) T(7)(8)I(10) Q(c)US(9)(11) Q(c)T(4)I(12) Q(c) Q(c)T(10)(11)I (3)(3)每个大学生不是文科生就是理工科生，有的大学生是每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等

11、生，因此如果小优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生张是大学生，他就是文科生。 设设 A(x):xA(x):x是大学生是大学生, , B(x):xB(x):x是是文科生文科生, , C(x):x C(x):x是理工科生是理工科生，D(x):xD(x):x是优等生是优等生, a:a:小张小张 x(x(A(x)(A(x)( B(x)C(x)B(x)C(x),), x(A(x)x(A(x)D(x)D(x) C(a)C(a)D(a) D(a) A(a)B(a)A(a)B(a) x(x(A(x)(A(x)( B(x)C(x)B(x)C(x),), x(A(x)x(A(

12、x)D(x)D(x) C(a)C(a)D(a) D(a) A(a)B(a)A(a)B(a) A(a) P(A(a) P(附加前提附加前提) ) x(x(A(x)(A(x)( B(x)C(x)B(x)C(x) P) P A(a)(A(a)( B(a)C(a)B(a)C(a) US ) US B(a)C(a)B(a)C(a) T ) T I I C(a)C(a)D(a) PD(a) P C(a) T C(a) T I I B(a) T B(a) T I I B(a) T B(a) T E E A(a)B(a) CPA(a)B(a) CP(4) 所有有理数是实数，某些有理数是整数，因此某些实数是整所

13、有有理数是实数，某些有理数是整数，因此某些实数是整数。数。设设Q(x):x是有理数是有理数 R(x):x是实数是实数 I(x):x是整数是整数 ( x)(Q(x)R(x), ( x)(Q(x)I(x) ( x)(R(x)I(x) ( x)(Q(x)I(x) P Q(a)I(a) ES Q(a) T I I(a) T I ( x)(Q(x)R(x) P Q(a)R(a) US R(a) T I R(a)I(a) T I ( x)(R(x)I(x) EG(5)小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者。没有一个登山者喜

14、欢雨。而所有滑雪者是个滑雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个试证明该俱乐部是否有个是登山者而不是滑雪者的成员。如果有，他是谁？是登山者而不是滑雪者的成员。如果有，他是谁？设：设：M(x):x是高山俱乐部成员。是高山俱乐部成员。H(x):x是滑雪者。是滑雪者。 D(x):x是登山者。是登山者。L(x,y):x喜欢喜欢y。 a:小杨；小杨；b:小刘；小刘；c:小林；小林；d:雨；雨；e:雪。雪。 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