离散数学--第二章-谓词逻辑---习题课 PPT课件

1、离 散 数 学,第二章 谓词逻辑 习题课,一. 命题符号化 60页(2),(x)(J(x)L(x) (x)(L(x)S(x) (x)(J(x)O(x)V(x) J(j)O(j)V(j) (x)(L(x)J(x) 或者 (x)(L(x)J(x) (x)(S(x)L(x)C(x) (x)(C(x)V(x) 或者(x)(C(x)V(x) h) (x)(C(x)O(x)L(x) i) (x)(W(x)C(x)H(x) j) (x)(W(x)J(x)C(x) k) (x)(L(x)y(J(y)A(x,y) l) (x)(S(x)y(L(y)A(x,y),习题课,62页 (2) (x)y(P(x)P(y)

2、E(x,y) z(L(z)R(x,y,z)t(L(t)R(x,y,t)E(t,z) (3)b)设R(x):x是实数，G(x,y):xy (x)(R(x)y(R(y)G(y,x) c)设R(x):x是实数，G(x,y):xy f(x,y)=x+y g(x,y)=xy (x)yz(R(x)R(y)R(z)G(f(x,y),g(x,z) 或者 (x)yz(R(x)R(y)R(z)G(x+y,xz),习题课,5)b)设N(x):x是数，A(x,y):y是x的后继数 (x)(N(x)A(x,1) (6)设A(x):x是戴眼镜的,B(x):x是用功的,C(x):x是大学生,D(x):x是大的,E(x):x

3、是厚的，F(x):x是巨著, A(x,y):x在看y,a:那位，b:这本 A(a)B(a)C(a)D(b)E(b)F(b) A(a,b),补充题：,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(4

4、00,x) R(x),66页,(3)b)P:21,Q(x):x3, R(x):x5,a:5,-2,3,6 (x)(PQ(x)R(a)(P(x)Q(x)R(a) (P(Q(-2)Q(3)Q(6)R(5) (T(T T F )F (TF)FFF F 4)b)对约束变元换名 (x)(P(x)(R(x)Q(x) (x)R(x)zS(x,z) y(P(y)(R(y)Q(y) tR(t)uS(x,u) (5)a)对自由变元代入 (yA(x,y)(x)B(x,z) (x)zC(x,y,z) (yA(u,y)(x)B(x,v) (x)zC(x,w,z),习题课,72页(2)d)论域为1,2 P(1) P(2)

5、 Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F (x)y(P(x)Q(x,y) y(P(1)Q(1,y)y(P(2)Q(2,y) (P(1)Q(1,1)(P(1)Q(1,2) (P(2)Q(2,1)(P(2)Q(2,2) (FT)(FT)(TF)(TF) (FF)(FF)F,6)判断下面推证是否正确。,(x)(A(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) (x)A(x)(x)B(x) 第步错，由到用的是公式： (x)(A(

6、x)B(x)(x)A(x)(x)B(x) 无此公式，而是 (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)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) (x)A(x)(x)B(x) 因为由公式E18 PQQP (x)(A(x)B(x) (x)A(x)(x)B(x) ， P Q 得 (x)A(x)(x)B(x)(x)(A(x)B(x),75页,(1)b)(x)(yP(x,y)(zQ(z)R(x)

7、(x)(yP(x,y)(zQ(z)R(x) (x)(yP(x,y)(zQ(z)R(x) (x)(yP(x,y) z(Q(z)R(x) (x)yz(P(x,y)(Q(z)R(x) (2)c)(x)P(x)(x)(zQ(x,z)zR(x,y,z) (x)P(x)(x)(zQ(x,z)zR(x,y,z) (x)P(x)(x)(zQ(x,z)zR(x,y,z) (x)P(x)u(zQ(u,z)tR(u,y,t) (x)uzt(P(x)(Q(u,z)R(u,y,t) (x)uzt(P(x)Q(u,z)R(u,y,t) 此式既是前束析取范式，也是前束合取范式。,79页(2)a)用CP规则证明,(x)(P(

8、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,习题课,3)a)所有有理数是实数，某些有理数是整数，因此某些实数是整数。设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

9、) 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,习题课,b)任何人如果他喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因此有的人不爱步行。 设 A(x):x是人, B(x):x是喜欢步行, C(x):x喜欢乘汽车，D(x):x喜欢骑自行车 (x)(A(x)(B(x)C(x), (x)(A(x)(C(x)D(x), (x)(A(x)D(x) (x)(A(x)B(x), (x)(A(x)D(x) P A(a)D(a) ES A(a) T I D(a

10、) T I (x)(A(x)(B(x)C(x) P A(a)(B(a)C(a) US B(a)C(a) T I (x)(A(x)(C(x)D(x) P A(a)(C(a)D(a) US C(a)D(a) T I C(a) T I B(a) T I A(a)B(a) T I (x)(A(x)B(x) EG ,习题课,c)每个大学生不是文科生就是理工科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生。 设 A(x):x是大学生, B(x):x是文科生, C(x):x是理工科生，D(x):x是优等生, a:小张 (x)(A(x)(B(x)C(x), (x)(

11、A(x)D(x) C(a)D(a) A(a)B(a),习题课,(x)(A(x)(B(x)C(x),(x)(A(x)D(x) C(a)D(a) A(a)B(A) A(a) P(附加前提) (x)(A(x)(B(x)C(x) P A(a)(B(a)C(a) US B(a)C(a) T I C(a)D(a) P,习题课,补充题：小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个 是登山者而不是滑雪者的成员。如果有，他是谁？ 设：M(x):x是高山俱乐部成员。H(x):

12、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)(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

13、,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 ,谓词逻辑,解决这个问题的方法： 在表示命题时，既表示出主语，也表示出谓语， 就可以解决上述问题。这就提出了谓词的概念。 令S(x)表示x是大学生，a:小张，b:小李 命题P表示成S(a):小张是大学生。 命题Q表示成S(b):小李是大学生。 从符号S(a)、S(b)可看出小张和小李都是大学生的共性。,谓词逻辑,令N(x):x是自然

14、数。I(x):x是整数。 表示所有的。 A: (x)(N(x)I(x)B :N(8) C :I(8),N(8),I(8),推理如此实现：,N(8)I(8),符号 S(x)、N(x)、I(x)就是所谓的谓词。,习题选讲命题符号化,1. 在一阶逻辑中将下列命题符号化。（1） 每个人都有心脏。（2） 有的狗会飞。（3） 没有不犯错误的人。（4） 发光的不都是金子。（5） 一切人都不一样高。（6） 并不是所有的汽车都比火车快。（7） 没有一个自然数大于等于任何自然数。（8） 有唯一的偶素数。（9） 不管黑猫白猫，抓住老鼠就是好猫。（10）对平面上任意两点，有且仅有一条直线通过这两点。,习题选讲命题符号

15、化,解：由于没指出个体域，故用全总个体域 （1）每个人都有心脏。 本命题的含义：对于每一个x，如果x是人，则x有心脏。 因而应首先从宇宙间的一切事物中，将人分离出来，这就必须引入特性谓词。 令M(x):x是人，H(x):x有心脏。 命题符号化为： (x)(M(x)H(x) 如果将其中的改为，即(x)(P(x)H(x)，它表示的意思是：“对于每个x，x是人且x有心脏”。这是一个假命题，而“每个人都有心脏”是真命题。 这说明将命题“每个人都有心脏”符号化为(x)(P(x)H(x)是错误的。,习题选讲命题符号化,（2）有的狗会飞。 命题的意思是：存在一个x，使得x是狗，并且x会飞。 设D(x)：x是

16、狗，F(x)：x会飞。 命题符号化为：(x)(D(x)F(x) 如果将其中的改为，即(x)(D(x)F(x)， 如果用a表示某只猫，则D(a)为假，因而，D(a)F(a)为真，所以(x)(D(x)F(x)为真，而“有的狗会飞”为假， 这说明将“有的狗会飞”符号化为 ( x)(D(x)F(x)是错误的。,（3）没有不犯错误的人。,命题的意思是： 存在不犯错误的人是不可能的。 只要是人，必然犯错误。 设 M(x): x是人，F(x):x犯错误 命题符号化为 (x)(M(x)F(x) (x)(M(x)F(x) （4）发光的不都是金子。 命题的意思是： 不是发光的东西都是金子。 存在着发光的东西不是金

17、子。 设 L(x)：x是发光的东西，G(x)：x是金子。 命题符号化为 (x)(L(x)G(x) (x)(L(x)G(x),（5）一切人都不一样高。 设 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) （6）并不是所有的汽车都比火车快。 设 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),习题选讲命题符号化,习题选讲命题符

18、号化,（7）没有一个自然数大于等于任何自然数。 设N(x):x是自然数，G(x,y):xy 命题符号化为： (x)(N(x) y(N(y)G(x,y) （8）有唯一的偶素数。 设：Q(x):x是偶数，P(x):x是素数， E(x,y):xy 命题符号化为： (x)(Q(x)P(x)y(Q(y)P(y)E(x,y),习题选讲命题符号化,（9）不管黑猫白猫，抓住老鼠就是好猫。 需要考虑问题： 只是限制黑猫白猫，还是包含其它颜色的猫？ 是指至少抓住一只就可以，还是抓住所有的？ 因此在描述命题时，总是将这些模糊概念做某种确切理解。 设 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),习题选讲命题符号化,（10）对平面上任意两点，有且仅有一条直线通过这两点。 设 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、判断下列各式是否是重言式？证明你的判断。