离散数学第二章谓词逻辑习题课.ppt

《离散数学第二章谓词逻辑习题课.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章谓词逻辑习题课.ppt（32页珍藏版）》请在三一办公上搜索。

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)E(x,y)z(L(z)R(x,y,z)t(L

2、(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是厚的，F(x):x是巨著,A(x,y):x在看y,a:那位，b

3、:这本 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(400,x)R(x),66页,(3)b)P:21,Q(x):x3,R(x):x5,a:5,-

4、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)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)

5、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(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

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

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

8、 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)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

9、(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)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)每个大学生不是文科生就是理工

10、科生，有的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生。设 A(x):x是大学生,B(x):x是文科生,C(x):x是理工科生，D(x):x是优等生,a:小张(x)(A(x)(B(x)C(x),(x)(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,习题课,补充题：小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑

11、雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个是登山者而不是滑雪者的成员。如果有，他是谁？设：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,

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

13、小张是大学生。命题Q表示成S(b):小李是大学生。从符号S(a)、S(b)可看出小张和小李都是大学生的共性。,谓词逻辑,令N(x):x是自然数。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）有唯一的偶素数。（

14、9）不管黑猫白猫，抓住老鼠就是好猫。（10）对平面上任意两点，有且仅有一条直线通过这两点。,习题选讲命题符号化,解：由于没指出个体域，故用全总个体域（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)是错误的。,习题选讲命题符号

15、化,（2）有的狗会飞。命题的意思是：存在一个x，使得x是狗，并且x会飞。设D(x)：x是狗，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）发光的不都是金子。命题的

16、意思是：不是发光的东西都是金子。存在着发光的东西不是金子。设 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),习题选讲命题符号化,

17、习题选讲命题符号化,（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

18、(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、判断下列各式是否是重言式？证明你的判断。(1)(x)(F(x)G(x)(2)(x)(F(x)G(x)(3)(x)y(F(x)G(y)H(x,y)(4)(x)y(P(x

19、,y)Q(a,y)(x)y(P(x,y)Q(x,y)其中a是客体常量。解：(1)不是重言式。(2)不是重言式。(3)不是重言式。(4)不是重言式。,习题选讲公式判断,(4)(x)y(P(x,y)Q(a,y)(x)y(P(x,y)Q(x,y)其中a是客体常量。令个体域为某个元素个数大于等于2的有限整数集，其中a为最小的数。P(x,y)：x大于等于y，Q(x,y)：x小于等于y。(x)yP(x,y)Q(a,y)解释为：存在一个x，对于所有的y，有x大于等于y，并且a小于等于y。命题为真，只要取x为个体域中最大数即可。(x)y(P(x,y)Q(x,y)解释为：存在一个x，对于所有的y，有x大于等于y，并且x小于等于y。命题为假。,3、判断下列公式是否为永真公式。（1）(x)A(x)(x)B(x)(x)(A(x)B(x)（2）(x)A(x)(x)B(x)(x)(A(x)B(x)（3）(x)A(x)(x)B(x)(x)(A(x)B(x)（4）(x)A(x)(x)B(x)(x)(A(x)B(x)解：（1）永真公式。（2）不是永真公式。（3）永真公式。（4）永真公式。,小节结束,习题选讲公式判断,