离散数学课后习题答案(第二章)

1、习题习题 2-1,2-22-1,2-2 （1） 用谓词表达式写出下列命题。 a) 小张不是工人。 解：设 W（x） ：x 是工人。c：小张。 则有( )W c b) 他是田径或球类运动员。 解：设 S（x） ：x 是田径运动员。B（x） ：x 是球类运动员。h：他 则有S（h）B（h） c) 小莉是非常聪明和美丽的。 解：设 C（x） ：x 是聪明的。B（x） ：x 是美丽的。l：小莉。 则有 C（l） B（l） d）若 m 是奇数，则 2m 不是奇数。 解：设 O（x） ：x 是奇数。 则有O（m） O（2m） 。 e)每一个有理数是实数。 解：设 R（x） ：x 是实数。Q（x） ：x 是

2、有理数。 则有 （x） （Q（x）R（x） ） f) 某些实数是有理数。 解：设 R（x） ：x 是实数。Q（x） ：x 是有理数。 则有 （x） （R（x）Q（x） ） g) 并非每个实数都是有理数。 解：设 R（x） ：x 是实数。Q（x） ：x 是有理数。 则有 （x） （R（x）Q（x） ） h)直线 A 平行于直线 B，当且仅当直线 A 不相交于直线 B。 解：设 P（x，y） ：直线 x 平行于直线 y，G（x，y） ：直线 x 相交于直线 y。 则有P（A，B）G（A，B） （2） 找出以下十二个句子所对应的谓词表达式。 a) 所有的教练员是运动员。 （J(x)，L(x)） 解：

3、设 J(x)：x 是教练员。L(x)：x 是运动员。 则有 （x） （J（x）L（x） ） b) 某些运动员是大学生。 （S(x)） 解：设 S(x)：x 是大学生。L(x)：x 是运动员。 则有 （x） （L（x）S（x） ） c) 某些教练是年老的，但是健壮的。 （O(x)，V（x） ） 解：设 J(x)：x 是教练员。O(x)：x 是年老的。V（x） ：x 是健壮的。 则有（x） （J（x）O（x）V（x） ） d) 金教练既不老但也不健壮的。 （j） 解：设 O(x)：x 是年老的。V（x） ：x 是健壮的。j：金教练 则有 O（j）V（j） e) 不是所有的运动员都是教练。 解：设

4、L(x)：x 是运动员。J(x)：x 是教练员。 则（x） （L（x）J（x） ） f) 某些大学生运动员是国家选手。 （C（x） ） 解：设 S（x） ：x 是大学生。L（x） ：x 是运动员。C（x） ：x 是国家选手。 则有 （x） （S（x）L（x）C（x） ） g) 没有一个国家选手不是健壮的。 解：设 C（x） ：x 是国家选手。V（x） ：x 是健壮的。 则有（x） （C（x）V（x） ）或（x） （C（x）V（x） ） h) 所有老的国家选手都是运动员。 解：设 C（x） ：x 是国家选手。O（x） ：x 是老的。L（x） ：x 是运动员。 则有 （x） （O（x）C（x）L（

5、x） ） i) 没有一位女同志既是国家选手又是家庭妇女。 （W（x） ，H（x） ） 解：设 W（x） ：x 是女同志。H（x） ：x 是家庭妇女。C（x） ：x 是国家选手。 则有 （x） （W（x）C（x）H（x） ） j）有些女同志既是教练员又是国家选手。 解：W（x） ：x 是女同志。J（x） ：x 是教练。C（x） ：x 是国家选手。 则有（x） （W（x）J（x）C（x） ） k）所有运动员都钦佩某些教练。 （A（x，y） ） 解：L（x） ：x 是运动员。J（y） ：y 是教练。A(x,y)：x 钦佩 y。 则有（x） （L（x） （y） （J（y）A（x，y） ） ） l）有些

6、大学生不钦佩运动员。 解：设 S（x） ：x 是大学生。L（x） ：x 是运动员。A(x,y)：x 钦佩 y。 则（x） （S（x）（y） （L（y） A(x,y)） ） 习题习题 2-32-3 （1）令( )P x为“x是质数” ；( )E x为“x是偶数” ；( )O x为“x是奇数” ；( , )D x y为“x 除尽y” ，把以下各式翻译成汉语： 解： a） (5)P 。 解：5 是质数。 b）(2)(2)EP。 解：2 是偶数且 2 是质数。 c）()(2, )( )x DxE x。 解：对所有的 x，若 x 能被 2 除尽，则 x 是偶数。 d）()( ( )( ,6)x E xD

7、 x。 解：存在 x，x 是偶数，且 x 能除尽 6。 （即某些偶数能除尽 6） e）()( )(2, )xE xDx 。 解：对所有的 x，若 x 不是偶数，则 x 不能被 2 除尽。 f）()( ( )()( , )( )x E xy D x yE y 。 解：对所有的 x，若 x 是偶数，则对所有的 y，若 x 能除尽 y，则 y 也是偶数。 g）()( ( )()( ( )( , )x P xy E yD x y 。 解：对所有的 x，若 x 是质数，则存在 y，y 是偶数且 x 能除尽 y（即所有质数能 除尽某些偶数） 。 h）()( ( )()( ( )( , )x O xy P

8、yD x y 。 解：对所有的 x，若 x 是奇数，则对所有 y，y 是质数，则 x 不能除尽 y（即任何 奇数不能除尽任何质数） 。 （2）令( ), ( ),( , , ),( , )P x L x R x y z E x y分别表示“x 是一个点” ， “x 是一条直线” ， “z 通过 x 和 y”和“x=y” 。符号化下面的句子。 对每两个点有且仅有一条直线通过该两点。 解： （x）(y)(P(x)P(y)E(x,y)(!z)(L(z)R(x,y,z) 或 （x） (y)(P(x)P(y)E(x,y)(z)(L(z)R(x,y,z) (u)(E(z,u) L(u) R(x,y,u)

9、（3）利用谓词公式翻译下列命题。 A）如果有限个数的乘积为零，那么至少有一个因子等于零。 B）对于每一个实数 x，存在一个更大的实数 y。 C）存在实数 x，y 和 z，使得 x 与 y 之和大于 x 与 z 之积。 解：a) 设 N(x):x 是有限个数的乘积。z(y):y 为 0。 P(x):x 的乘积为零。 F(y):y 是乘积中的一个因子。 则有 (x)(N(x)P(x)(y)(F(y)z(y) b) 设 R(x):x 是实数。Q(x,y):y 大于 x。 故(x)(R(x)(y)(Q(x,y)R(y) c) R(x):x 是实数。G(x,y):x 大于 y。 则(x)(y)(z)(R

10、(x)R(y)R(z)G(x+y,xz) （4）用谓词公式写出下式： 若xy和0z。 解：设 G(x,y):x 大于 y。 则有(x)(y)(z)(G(y,x)G(0,z)G(xz,yz) （5）自然数一共三条公理： A）每个数都有唯一的一个数是它的后继数。 B）没有一个数使数 1 是它的后继数。 C）每个不等于 1 的数都是唯一的一个数是它的直接先行者。 用两个谓词表达上述三条公理。 解：设 N(x):x 是一个数。 S(x,y):y 是 x 的后继数。E(x,y)：x=y.则 a) (x)(N(x)(!y)(N(y)S(x,y) 或(x)(N(x)(y)(N(y)S(x,y) (z)(E(

11、y,z) N(z)S(x,z) b)(x)(N(x)S(x,1) c)(x)(N(x)S(x,2)(!y)(N(y)S(y,x) 或(x)(N(x)S(x,2)(y)(N(y)S(y,x)(z)(E(y,z)N(z)S(z,x) （6）用谓词公式刻画下述命题： 那位戴眼睛的用功的大学生在看这本而厚的巨著。 解：设 S(x):x 是大学生。E(x):x 是戴眼睛的。 F(x):x 是用功的。R(x,y):x 在看 y。 G(y):y 是大的。K(y):y 是厚的。J(y):y 是巨著。 a:这本。b:那位。 则有 E(b)F(b)S(b)R(b,a)G(a)K(a)J(a) （7）取个体域为实数

12、集 R，函数 f 在 a 点连续的定义是：f 在点 a 连续，当且仅当对每 个0，存在一个0，使得对所有 x，若xa，则( )( )f xf ay。 则 P(f,a)()()(x)(Q(,0)(Q(,0)Q(,|x-a|)Q(,|f(x)-f(a)|) 习题习题 2-42-4 (1) 对下面每个公式指出约束变元和自由变元。 A）() ( )( )x P xp y B）()( ( )( )() ( )x P xQ xx S x C）()()( ( )( )() ( )xy P xQ yx R x D）()()( ( , )( )xy P x yQ z 解：a) x 是约束变元，y 是自由变元。

13、b) x 是约束变元，P(x)Q(x)中的 x 受全称量词的约束，S(x)中的 x 受存在量词$ 的约束。 c) x，y 都是约束变元,P(x)中的 x 受的约束，R(x)中的 x 受的约束。 d) x，y 是约束变元，z 是自由变元。 (2) 如果论域是集合, ,a b c，试消去下面公式中的量词。 A）() ( )x P x B）() ( )() ( )x R xx S x C）()( ( )( )x P xQ x D）()( )() ( )xP xx P x 解：a) P(a)P(b)P(c) b) R(a)R(b)R(c)S(a)S(b)S(c) c) (P(a)Q(a)(P(b)Q(

14、b)(P(c)Q(c) d) (P(a)P(b)P(c)(P(z)P(b)P(c) (3) 寻求下列各式的真假值。 A）()( ( )( )x P xQ x，其中( ):1,( ):2P xxQ xx=，且论域是1,2 B）()( )( )x PQ xR a， 其中:21,( ):3,( ):5PQ xxR xx而:5a， 论域是2,3,6 解：a) (x)(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)， 但 P(1)为 T，Q(1)为 F，P(2)为 F，Q(2)为 T, 所以(x)(P(x)Q(x)(TF)(FT) T。 b) (x)(PQ(x)R(a) (PQ(2)(PQ(3)(

15、PQ(6)R(a) 因为 P 为 T，Q(2)为 T，Q(3)为 T，Q(6)为 F，R(5)为 F， 所以(x)(PQ(x)R(a)(TT)(TT)(TF)F F (4) 对下列谓词公式中的约束变元进行换名。 A）( ( , )( )( , )x y P x zQ yS x y B）( )( ( )( )( )( , )xP xR xQ xxR xzS x z 解：a)(u)(v)(P(u，z)Q(v)S(x，y) b)(u)(P(u) (R(u)Q(u)(v)R(v)(z)S(x,z) (5) 对下列谓词公式中的自由变元进行代入。 A）( , )( , )( , , )yA x yxB x

16、 zx zC x y z B）( , )( , )( , )yP x yzQ x zxR x y 解：a)(y)A(u，y)(x)B(x，v)(x)(z)C(x，t，z) b)(y)P(u，y)(z)Q(u，z)(x)R(x，t) 习题习题 2-52-5 （1）考虑以下赋值，论域： 1,2D= 指定常数 a 和 b： ab 12 指定函数f： 指定谓词 P： 求以下各公式的真值。 (1)f(2)f 21 (1,1)P(1,2)P(2,1)P(2,2)P TTFF A）( ,( )( ,( )P a f aP b f b B）()() ( , )xy P y x C）()()( ( , )( (

17、 ),( )xy P x yP f xf y 解： a)P(a,f(a)P(b,f(b) P(1,f(1)P(2,f(2) P(1,2)P(2,1) TFF b)(x)(y)P(y,x) (x)(P(1,x)P(2,x) (P(1,1)P(2,1)(P(1,2)P(2,2) (TF)(TF) T c)(x)(y)(P(x,y)P(f(x),f(y) (x)(P(x,1)P(f(x),f(1)(P(x,2)P(f(x)f(2) (P(1,1)P(f(1),f(1)(P(1,2)P(f(1),f(2) (P(2,1)P(f(2),f(1)(P(2,2) P(f(2),f(2) (P(1,1)P(2

18、,2)(P(1,2)P(2,1)(P(2,1)P(1,2)(P(2,2) P(1,1) (TF(TF)(FT)(FT) FFTT F （2）对以下各公式赋值后求真值。 A）()( ( )( ( ), )x P xQ f x a B）()( ( ( )( ,( )x P f xQ x f a C）()( ( )( , )x P xQ x a D）()()( ( )( , )xy P xQ x y 其中，论域1,2 ,1;Da= :fP： :Q (1)f(2)f 21 (1)P(2)P FT (1,1)Q(1,2)Q(2,1)Q(2,2)Q TTFF 解：a) (x)(P(x)Q(f(x),a)

19、(P(1)Q(f(1),1)(P(2)Q(f(2),1) (FQ(2,1)(TQ(1,1) (FF)(TT) T b)(x)(P(f(x)Q(x,f(a) (P(f(1)Q(1,f(1)(P(f(2)Q(2,f(1) (TT)(FF) T c)(x)(P(x)Q(x,a) (P(1)Q(1,a)(P(2)Q(2,a) (P(1)Q(1,1)(P(2)Q(2,1) (FT)(TF) F d) (x)( y)(P(x)Q(x,y) (x) (P(x)(y)Q(x,y) (x) (P(x)(Q(x,1)Q(x,2) (P(1)(Q(1,1)Q(1,2)(P(2)(Q(2,1)Q(2,2) (F(TT

20、)(T(FF) F (3) 举例说明下列各蕴含式。 a) (x)(P(x)Q(a)(x)P(x) Q(a) b) (x)( P(x)Q(x), (x) Q(x)P(a) c) (x)(P(x)Q(x), (x)(Q(x)R(x)(x)(P(x) R(x) d) (x)(P(x)Q(x), (x) P(x)(x)Q(x) e) (x)(P(x)Q(x), (x) P(x)(x)Q(x) 解：a）因为(x)(P(x)Q(a) (x)P(x)Q(a) 故原式为(x)P(x)Q(a) (x)P(x)Q(a) 设 P（x） ：x 是大学生。Q（x） ：x 是运动员 前提：或者不存在 x，x 是大学生，或

21、者 a 是运动员 结论：如果存在 x 是大学生，则必有 a 是运动员。 b)设 P（x） ：x 是研究生。Q（x） ：x 是大学生。a：论域中的某人。 前提：对论域中所有 x，如果 x 不是研究生则 x 是大学生。 对论域中所有 x，x 不是大学生。 结论：对论域中所有 x 都是研究生。 故，对论域中某个 a，必有结论 a 是研究生，即 P（a）成立。 c）设 P（x） ：x 是研究生。Q（x） ：x 曾读过大学。R（x） ：x 曾读过中学。 前提：对所有 x，如果 x 是研究生，则 x 曾读过大学。 对所有 x，如果 x 曾读过大学，则 x 曾读过中学。 结论：对所有 x，如果 x 是研究生

22、，则 x 曾读过中学。 d）设 P（x） ：x 是研究生。Q（x） ：x 是运动员。 前提：对所有 x，或者 x 是研究生，或者 x 是运动员。 对所有 x，x 不是研究生 结论：必存在 x，x 是运动员。 e）设 P（x） ：x 是研究生。Q（x） ：x 是运动员。 前提：对所有 x，或者 x 是研究生，或者 x 是运动员。 对所有 x，x 不是研究生 结论：对所有 x，x 是运动员。 （4）求证：()( ( )( )() ( )() ( )x A xB xx A xx B x 证明：(x)(A(x)B(x) (x)(A(x)B(x) (x)A(x) (x) B(x) (x)A(x)(x)

23、B(x) (x)A(x)(x) B(x) （5）设论域 D=a，b，c，求证(x)A(x)(x)B(x)( x)(A(x)B(x) 证明：因为论域 D=a，b，c，所以 (x)A(x)(x)B(x) (A(a)A(b)A(c)(B(a)B(b)B(c) (A(a)B(a)(A(a)B(b)(A(a)B(c)(A(b)B(a)(A(b)B(b) (A(b)B(c)(A(c)B(a)(A(c)B(b)(A(c)B(c) (A(a)B(a)(A(b)B(b)(A(c)B(c) (x)(A(x)B(x) 所以(x)A(x)(x)B(x)(x)(A(x)B(x) （7）求证(x)( y)(P(x)Q(y

24、)(x)P(x)(y)Q(y) 证明：(x)(y)(P(x)Q(y) (x)(y)(P(x)Q(y) (x)P(x)(y)Q(y) (x)P(x)(y)Q(y) (x)P(x)(y)Q(y) 习题习题 2-62-6 （1）把以下各式化为前束范式。 解：a)(x)(P(x)(y)Q(x,y) (x)( P(x) (y)Q(x,y) (x) (y) (P(x) Q(x,y) b)(x)(y)P(x,y)(z)Q(z)R(x) (x)(y)P(x,y)(z)Q(z)R(x) (x)(y)P(x,y) (z)Q(z) R(x) (x)(y)P(x,y) (z)Q(z) R(x) (x) (y) (z)

25、 ( P(x,y) Q(z) R(x) c)(x)( y)(zP(x,y,z)(u)Q(x,u)(v)Q(y,v) (x)( y)( (z)P(x,y,z)(u)Q(x,u)(v)Q(y,v) (x)( y)( (z)P(x,y,z) (u)Q(x,u)(v)Q(y,v) (x)( y)( (z)P(x,y,z) (u)Q(x,u)(v)Q(y,v) (x)( y) (z) (u) (v) (P(x,y,z) Q(x,u)Q(y,v) （2）求等价于下面 wff 的前束合取范式与前束析取范式。 解：a)(x)P(x)(x)Q(x)(x)(P(x)Q(x) (x)P(x)(x)Q(x) (x)(

26、P(x)Q(x) (x) (P(x)Q(x) (x)(P(x)Q(x) T b) (x)(P(x)(y)(z)Q(x,y)(z)R(y,x) (x)( P(x) (y)( Q(x,y)R(y,x) (x) (y) ( P(x) Q(x,y) R(y,x) 前束合取范式 (x) (y)( (P(x) Q(x,y) R(y,x) (P(x) Q(x,y) R(y,x) (P(x) Q(x,y) R(y,x) (P(x) Q(x,y) R(y,x) (P(x) Q(x,y) R(y,x) ( (P(x) Q(x,y) R(y,x) (P(x) Q(x,y) R(y,x) 前束析取范式 c) (x)P

27、(x)(x)(z)Q(x,z)(z)R(x,y,z) (x)P(x) (x)(z)Q(x,z)(z)R(x,y,z) (x)P(x) (x)(z)Q(x,z)(u)R(x,y,u) (x)(P(x) (z)Q(x,z)(u)R(x,y,u) (x) (z) (u)(P(x) Q(x,z)R(x,y,u) 前束合取范式 (x) (z) (u)( P(x) Q(x,z) R(x,y,u) (P(x) Q(x,z) R(x,y,u) (P(x) Q(x,z) R(x,y,u) (P(x) Q(x,z) R(x,y,u) (P(x) Q(x,z) R(x,y,u) (P(x) Q(x,z) R(x,y

28、,u) (P(x) Q(x,z) R(x,y,u) 前束析取范式 d)(x)(P(x)Q(x,y)(y)P(y)(z)Q(y,z) (x)( P(x) Q(x,y) (y)P(y)(z)Q(y,z) (x)( P(x) Q(x,y) (u)P(u)(z)Q(y,z) (x) (u) (z) ( P(x) Q(x,y) (P(u)Q(y,z) 前束析取范式 (x) (u) (z) ( P(x)P(u) (P(x)Q(y,z) (Q(x,y)P(u) (Q(x,y)Q(y,z) 前束合取范式 习题习题 2-72-7 (1)证明下列各式 证明： a)(x)(A(x)B(x)P A(u)B(u)US

29、( x)B(x)P B(u)US A(u)B(u)TE A(u)TI ( x)A(x)EG b)( x)(A(x)B(x)P（附加前提） ( x)(A(x)B(x)TE (A(c)B(c)ES A(c)TI B(c)TI ( x)A(x)EG (x)A(x)(x)B(x)P (x)B(x)TI B(c)US B(c) B(c)T矛盾 c）(x)(A(x)B(x)P A(u)B(u)US ( x)(C(x)B(x)P C(u)B(u)US B(u) A(u)TE C(u)A(u)TI (x)(C(x)A(x)UG d)(x)(A(x)B(x),( x)(B(x)C(x),( x)C(x) (x)

30、A(x) ( x)(B(x)C(x)P B(u)C(u)US ( x)C(x)P C(u)US B(u)TI (x)(A(x)B(x)P A(u)B(u)US A(u)TI (x)A(x)UG (2)用 CP 规则证明。 证明： a)( x)P(x)P（附加前提） P(u)US (x)(P(x)Q(x)P P(u)Q(u)US Q(u)TI (x)Q(x)UG ( x)P(x)(x)Q(x)CP b)因为(x)P(x)(x)Q(x)(x)P(x) (x)Q(x) 故本题就是推证(x)(P(x)Q(x) (x)P(x) (x)Q(x) (x)P(x)P（附加前提） ( x)P(x)TE P(c)ES (x)(P(x)Q(x)P P(c)Q(c)ES