离散数学第二章谓词逻辑习题课谷风教学

1、离离 散散 数数 学学第二章第二章 谓词逻辑谓词逻辑习题课习题课一. 命题符号化 60页(2)a) ( x)(j(x)l(x)b) ( x)(l(x)s(x)c) ( x)(j(x)o(x)v(x)d) j(j) o(j) v(j) e) ( x)(l(x)j(x) 或者或者 ( x)(l(x) j(x)f)( x)(s(x)l(x)c(x) g) ( 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)

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

3、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:这本 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、题:“年号能被年号能被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,-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

5、)(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) y(p(2)q(2,y)(p(1)q(1,1)(p(1)q(1,2) (p(2)q(2,1)(p(

6、2)q(2,2)(ft)(ft)(tf)(tf)(ff)(ff)f6)判断下面推证是否正确。 ( 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)

7、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 pqq p ( 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)(z

8、q(z)r(x)( x)( yp(x,y)( z q(z)r(x)( x)( yp(x,y) z( q(z)r(x)( x) y z(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) u z t( p(x)(q(u,z)r(u,y,t)( x) u z t( p(x)q(u,z)r(u,y,t)此式既是前束析取范式，也是前束合取范式。此式既是前束

9、析取范式，也是前束合取范式。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 i ( x) q(x) eg ( x)p(x)( x) q(x) cp习题课3)a)所有有理数是实数，某些有理数是整数，因此某些实所有有理数是实数，某些有理数是整数，因此某些实数是整数。数是整数。设设q(x):x是有理数是有理数 r

10、(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)任何人如果他喜欢步行，他就不喜欢乘汽车；每任何人如果他喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因此有的人不爱步行。爱骑自行车，因此有的人不爱

11、步行。设设 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) 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)

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

13、a)(b(a)c(a) us b(a)c(a) t i c(a)d(a) p习题课补充题：小杨、小刘和小林为高山俱乐部成员，该俱乐部的每个成员是个滑雪者或登山者。没有一个登山者喜欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个是登山者而不是滑雪者的成员。如果有，他是谁？设：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):

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

15、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是自然数。i(x):x是整数。 表示所有的。 a: (x)(n(x)i(x)b :n(8) c :i(8)n(8)n(8)i(8)i(8)推理如此实现：推理如此实现

16、： n(8)i(8)n(8)i(8)符号符号 s(x)s(x)、n(x)n(x)、i(x)i(x)就是所谓的谓词就是所谓的谓词。习题选讲命题符号化1. 1. 在一阶逻辑中将下列命题符号化。在一阶逻辑中将下列命题符号化。（1 1） 每个人都有心脏。每个人都有心脏。（2 2） 有的狗会飞。有的狗会飞。（3 3） 没有不犯错误的人。没有不犯错误的人。（4 4） 发光的不都是金子。发光的不都是金子。（5 5） 一切人都不一样高。一切人都不一样高。（6 6） 并不是所有的汽车都比火车快。并不是所有的汽车都比火车快。（7 7） 没有一个自然数大于等于任何自然数。没有一个自然数大于等于任何自然数。（8 8）

17、 有唯一的偶素数。有唯一的偶素数。（9 9） 不管黑猫白猫，抓住老鼠就是好猫。不管黑猫白猫，抓住老鼠就是好猫。（1010）对平面上任意两点，有且仅有一条直线通过这两点。）对平面上任意两点，有且仅有一条直线通过这两点。习题选讲命题符号化解：由于没指出个体域，故用全总个体域解：由于没指出个体域，故用全总个体域（1）每个人都有心脏。）每个人都有心脏。本命题的含义：对于每一个本命题的含义：对于每一个x，如果，如果x是人，则是人，则x有心脏。有心脏。因而应首先从宇宙间的一切事物中，将人分离出来，这就因而应首先从宇宙间的一切事物中，将人分离出来，这就必须引入特性谓词。必须引入特性谓词。 令令m(x):x是

18、人，是人，h(x):x有心脏。有心脏。 命题符号化为：命题符号化为： ( x)(m(x)h(x)如果将其中的如果将其中的改为改为，即，即( x)(p(x)h(x)，它表示的，它表示的意思是：意思是：“对于每个对于每个x，x是人且是人且x有心脏有心脏”。这是一个假命题，。这是一个假命题，而而“每个人都有心脏每个人都有心脏”是真命题。是真命题。这 说 明 将 命 题这 说 明 将 命 题 “ 每 个 人 都 有 心 脏每 个 人 都 有 心 脏 ” 符 号 化 为符 号 化 为(x)(p(x)h(x)是错误的。是错误的。 习题选讲命题符号化（2）有的狗会飞。）有的狗会飞。 命题的意思是：存在一个命

19、题的意思是：存在一个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）没有不犯错误的人。）没有不犯错误的人。 命题的意思是：命

20、题的意思是： 存在不犯错误的人是不可能的。存在不犯错误的人是不可能的。 只要是人，必然犯错误。只要是人，必然犯错误。 设设 m(x): x是人，是人，f(x):x犯错误犯错误命题符号化为命题符号化为 ( x)(m(x)f(x) ( x)(m(x)f(x)（4）发光的不都是金子。）发光的不都是金子。 命题的意思是：命题的意思是： 不是发光的东西都是金子。不是发光的东西都是金子。 存在着发光的东西不是金子。存在着发光的东西不是金子。 设设 l(x)：x是发光的东西，是发光的东西，g(x)：x是金子。是金子。 命题符号化为命题符号化为 ( x)(l(x)g(x) ( x)(l(x)g(x) （5）一

21、切人都不一样高。）一切人都不一样高。 设设 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)习题选讲命题符号化习题选讲命题符号化（

22、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）不管黑猫白猫，抓住老鼠就是好猫。）不管黑猫白猫，抓住老鼠就是好猫。 需要考虑问题：需要考虑问题：只是限制黑猫白猫，还是包含其它颜色的猫？只是限制黑猫白猫，还是包含其它颜色的猫？是指至少抓住一只就可以，还是抓住所有的？是指至少抓住一只就可以，还是抓住所有的？ 因此在描

23、述命题时，总是将这些模糊概念做某种确切理解。因此在描述命题时，总是将这些模糊概念做某种确切理解。 设设 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、判断下列各式是否是重言式？证明你的判断。、判断下列各式是否是重言式？证明你的判断。(1) ( x)(f(x) g(x)(2) ( x)(f(x) g(x)(3) ( x) y(f(x) g(y