《离散数学课后习题答案第二章资料》由会员分享，可在线阅读，更多相关《离散数学课后习题答案第二章资料（12页珍藏版）》请在金锄头文库上搜索。
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，存在一个0，使得对所有 x，若xa而: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)(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) 对下列谓词公式中的约束变元进
11、行换名。 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 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
12、(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）()()( ( , )( ( ),( )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
13、,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,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）()( ( )( ( ), )
14、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) (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
15、(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)(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
