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

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,

2、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(400,x

4、) 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) q(1

5、,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(x)b(

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

7、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(x)q(

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

9、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) t

10、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)(a(x)

11、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):x是滑雪

12、者。 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,e)

13、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是自然数。i(

14、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是狗，f(

16、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、判断下列各式是否是重言式？证明你的判断。