2004~2005学年第二学期 科目:离散数学考试试题A卷答案 命题教师:李伟勋使用班级:计科041班 、1.A2.C3.C4.D5.A6.B7.B8.A9.C10.C 、1l.(P谀)?R12.("x)(x萎Ax?B)13.{a,b,c},{b,c,d 14.反对称性,{<a,a>,<a,b>,<ba>,<bc>,<Cb>} 15·={a,1>,<b2}={a,2>,<b1}={a,1>,<b1>} f4={a,2><b,2少}:f1,f2 16.≤4:17.a·(a+b)=a·b:8·1,l;19.4,18:20.m×n 21.解:(1)令P:天下雨,Q:我们去郊游。 1分 该命题可符号化为_P→O。 1分 天不下雨是去郊游的充分条件 1分 (2)令P:天下雨,g:我们去郊游。 该命题可符号化为Q→P或P→-Q。 1分 天不下雨是去郊游的必要条件 分 22.解:设题中的公式为A,则 A(pV(q∧r)→>(PAqr) 分-(pV(qAr)V(p∧q∧r) 1分 分中p∧(-qV-)v(PAq∧r) 分(pA-q)V(A)V(pAq∧r) 2分 分(pA-qA(rVr)V(p∧(-qVq)∧)V( PAqAr) 分(p-qA)V(p∧-qAr)V(pA-qA)v(p∧qA-)V( paqAr) 分(p-qA-)V(p∧-qAr)V(PAqA)V(pAq∧r) 分 台m0Vm1Vm2Vm2,此即该公式的主析取范式由此即推得它的主合取范式为
1 2004～2005 学年第 二 学期 科目: 离散数学 考试试题 A 卷答案 命题教师： 李伟勋 使用班级：计科 04-1 班 一、1．A 2．C 3．C 4．D 5．A 6．B 7．B 8．A 9．C 10．C 二、11．( ) P Q R 谫 ? 12．( )( ) " x x A x B 萎 ? 13．{a，b，c}，{b，c，d} 14．反对称性， { , , , , , , , , , } < > < > < > < > < > a a a b b a b c c b 15． f a b f a b f a b 1 2 3 = < > < > = < > < > = < > < > { ,1 , , 2 }, { , 2 , ,1 }, { ,1 , ,1 }, { ,2 , ,2 } f 4 = a b ； 1 2 f , f ； 16． 4 ； 17． a (a + b) = a b ； 8．1，1； 19．4，18；20．m n× 三、21．解：（1）令 P：天下雨，Q：我们去郊游。 1 分 该命题可符号化为 P → Q 。 1 分 天不下雨是去郊游的充分条件 1 分 （2）令 P：天下雨，Q：我们去郊游。 该命题可符号化为 Q → P 或 P → Q 。 1 分 天不下雨是去郊游的必要条件 1 分 22．解：设题中的公式为 A，则 A ( p (q r)) → ( p q r) ( p (q r)) ( p q r) 1 分 p (q r) ( p q r) (p q) (p r) ( p q r) 2 分 (p q (r r)) (p (q q) r) ( p q r) (p q r) (p q r) (p q r) (p q r) ( p q r) (p q r) (p q r) (p q r) ( p q r) 4 分 m0 m1 m2 m7 ,此即该公式的主析取范式.由此即推得它的主合取范式为
MAAMAMSAM6 -(pvngvr)ApvgvrApvgvarApvngvr 23.解:(1)R*R={<0,0>,<1,1>,<1,2>,<2,1>,<2,2>} 1分 (2)R*R={<0,0>,<,1>,<1,2>,<2,1>,<2,2>} 分 (3)R↑轨,{外}=R个0,1}={<0,1>,<0,2>,<1,0} 分 (4)R[U,}]=R[{0,1}]={0,12} 24.解:从R的表达式可知,x∈A,(x,x)∈R,即R具有自反性, 1分 由R的表达式,Mx,y∈A(xy)∈R则(yx)∈R,R具有对称性 3分 又有x,y,z∈A,(x,y)∈R且(y,z)∈R,则(x,z)∈R 于是R具有传递性。故R是A上的等价关系。 5分 6.解:强分图为 2分。单向分图为: 3分 3 3 25.解:易知,二元运算满足交换律 对Va∈2,a*2=a+2-2=a=2*a即2∈2是单位元 va∈Z,a的逆元记作a-,有a*a1=a+a--2=2(单位元) a-1=4-a 三.计算题(二) 27.解:a+ab(ca+b) =a+abcatabb 分 a+ 2分
2 M3 M 4 M5 M6 = ( p q r) (p q r) (p q r) (p q r) 5 分 23．解： ⑴ R R = { 0,0 , 1,1 , 1,2 , 2,1 , 2,2 } 1 分 ⑵ 1 R R { 0,0 , 1,1 , 1,2 , 2,1 , 2,2 } − = 1 分 ⑶ R R = = { ,{ }} {0,1} { 0,1 , 0,2 , 1,0 } 2 分 ⑷ R R [{ ,{ }}] [{0,1}] {0,1, 2} f f = = 24．解：从Ｒ的表达式可知， x∈A，（x，x）∈R，即Ｒ具有自反性， 1 分 由Ｒ的表达式， x，y∈A,(x,y)∈R,则(y,x)∈Ｒ，Ｒ具有对称性。 3 分 又有 x，y，z∈Ａ，(x，y)∈R 且（y，ｚ）∈Ｒ，则（x，ｚ）∈Ｒ， 于是Ｒ具有传递性。故Ｒ是Ａ上的等价关系。 5 分 6．解：强分图为 2 分。单向分图为： 3 分 25．解：易知，二元运算满足交换律 . 对 a Z , a 2 = a + 2 − 2 = a = 2 a 即 2 Z 是单位元. a Z , a 的逆元记作 −1 a ，有 2 2 1 1 = + − = − − a a a a （单位元） a = − a − 4 1 ． 三．计算题（二） 27．解： a + ab(ca + b) = a + abca + abb 1 分 = a + ab 2 分
=(a+aa+b)(加法对乘法的分配律) 4分 a+ 5分 1110 7342 1010 2111 A(D) A2(D)= 1001 0 A(D)=14231 312 167104 11573 A+(D)= P(D)=A√A2)A)vA4)=1111 10463 四.29.证明:(参考答案) 用反证法,假设彐xQx)成立。 (1)x-P(x) 前提 (2)-PU) (1);U (3)彐-xQx 假设 (4)x-Qx) (6)-P()^QU) (2),(5) (7)-(P(v)vQU) (6) (8)Vx(P(xlv(x) 前提 (8),US (10)(P()vQU)(P()vQ)(7),(9) 因为(PU)Q)(P()vQ)是恒假公式,所以vx(PxQ(x),Vx-P(x)→3xQx) 30.证明a.b∈G,存在k、l∈Z使a=kmb=Ⅶm。由于k+l∈Z,得知 a+b=km+m=(k+1)m∈G,即+在G上是封闭的 由整数运算的性质可知,+是可结合的。 0=0.m∈G,对a∈G,有a+0=0+a=a,故0是G的单位元。 Va∈G,存在k∈Z使a=km,由于-k∈Z,-a=(-km∈G,且a+(-a)=(-a)+a=0 故一a是a的逆元 综上所述,(G+)是一个群
3 = (a + a)(a + b) （加法对乘法的分配律） 4 分 = a + b 5 分 28．解： = 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 A(D) = 1 1 1 0 2 1 1 0 2 1 1 1 3 1 2 1 ( ) 2 A D = 3 1 2 1 4 2 3 1 5 2 3 1 7 3 4 2 ( ) 3 A D = 7 3 4 2 10 4 6 3 11 5 7 3 16 7 10 4 ( ) 4 A D (1) (2) (3) (4) 1111 1111 ( ) 1111 1111 P D A A A A = = 四．29．证明：（参考答案） 用反证法，假设xQ(x)成立。 （1）xP(x) 前提 （2）P(y) （1）；US （3）xQ(x) 假设 （4）xQ(x) （3） （5）Q(y) （4）；US （6）P(y)Q(y) （2），（5） （7）(P(y) Q(y)) （6） （8）x(P(x)Q(x)) 前提 （9）P(y) Q(y) （8），US （10）(P(y) Q(y)) (P(y) Q(y)) （7），（9） 因为(P(y) Q(y)) (P(y) Q(y))是恒假公式，所以x(P(x)Q(x))，xP(x)xQ(x)。 30 ．证明 a,b G ，存在 k,l Z 使 a = km,b = lm 。由于 k +l Z ，得知 a + b = km+ lm = (k + l)mG ，即 + 在 G 上是封闭的。 由整数运算的性质可知， + 是可结合的。 0 = 0mG ，对 aG ，有 a + 0 = 0 + a = a ，故 0 是 G 的单位元。 aG ，存在 k Z 使 a = km ，由于 − k Z ，− a = (−k)m G ，且 a + (−a) = (−a) + a = 0 。 故 −a 是 a 的逆元。 综上所述， (G,+) 是一个群
2004~2005学年第二学期 科目:离散数学考试试题B卷答案 命题教师:李伟勋使用班级:计科04-1班 、选择题 1.A2.B3.C C5.A6.C7.B8.A9.C10.C 、11.矛盾式;重言 2.设Rxx为实数,则命题可符号化为vxvy(R(x)入R(y)→x≥yyx<y) 3.B;A;14.{ac,a},{aa,ab>,a,};15.{a,b,e},{b,c,d;16.反对称 性;17·a(a+b)=ab:18.1,1:19.4,18:20.偶数 21.解:(1)令P:天下雨,Q:我们去郊游。 该命题可符号化为一P→O。(天不下雨是去郊游的充分条件) 分 (2)令P:天下雨,Q:我们去郊游 该命题可符号化为Q→P或P→_Q。(天不下雨是去郊游的必要条件) 22.解:P∧O√R 分(PAQ∧(RV=R)v(P-P)∧QV-Q∧R 台(PAQ∧R)V(PAQ R)Vv(P∧Q∧R) v(PA=Q∧R)V(P∧Q∧R)V(-P∧=Q∧R 分(PA=QAR)V(P∧Q∧R)V(P入=QARV(P∧QA=RV(P∧QAR) s moot v mou v moi v muo v mu s m, v m3 v ms vm v m 分 ∑(3567) ∴命题公式P∧OR的主析取范式为 GPATOARVGPAOAR)V(PAOA R)V(PAOATRV(PAOAR
4 2004～2005 学年第 二 学期 科目: 离散数学 考试试题 B 卷答案 命题教师： 李伟勋 使用班级：计科 04－1 班 一、选择题 1．A 2．B 3．C 4．C 5．A 6．C 7．B 8．A 9．C 10．C 二、11．矛盾式；重言式； 12．设 R(x)：x 为实数，则命题可符号化为 xy(R(x) R( y) → x y x y) ； 13．B；A；14．{<a,c>,<a,d>}，{<a,a>,<a,b>,<a,d>}；15．{a，b，c}，{b，c，d}；16．反对称 性；17． a (a + b) = a b ；18．1，1；19．4，18；20．偶数 三、21．解：（1）令 P：天下雨，Q：我们去郊游。 该命题可符号化为 P → Q 。（天不下雨是去郊游的充分条件） 3 分 （2）令 P：天下雨，Q：我们去郊游。 该命题可符号化为 Q → P 或 P → Q 。（天不下雨是去郊游的必要条件） 5 分 22．解： P Q R (P Q (R R)) ((P P) (Q Q) R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) m001 m011 m101 m110 m111 m1 m3 m5 m6 m7 4 分 (1,3,5,6,7) ∴命题公式 P Q R 的主析取范式为 (P Q R) (P Q R) (P Q R) (P Q R) (P Q R)
m√m3m3mVm台∑(1357) ②求主合取范式 由①知命题公式 PAOVR的主合取范式为 ∏(2.4)MAM2AM4( PvOVR)A(PvQ√RA(PQvR)5分 23.解:(1)R*R={<0,2>,<0,3>,<1,3>} (2)R1↑{}={<1,0x} (3)R1?{}{23} 24.解Ax(B∩C)={a,b}×{3}={<a,3>,<b,3习} A×B={<a,1>,<a,2><a,3>,<b,1><b,2><b3>} A×C={<a,3><a,4><b,3><b4>} (A×B)∩(A×C)={<a,3>,<b,3>} ∴Ax(B∩C)=(AxB)∩(AxC 25.解:i)F(R)={0,1,2,3,4,5} (1)因为/(F(R)={<0,0>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5}三R, 所以R是自反的 (2)因为 R={<0,0>,<1,1>,<2,1>,<3,1>,<1,2><2,2>,<3,2>,<,3>,<2,3>,<3,3>, <4,4>,<5,4>,<4,5>,<5,5>} 而(R)=R-,所以R是对称的 (3)因为R*RcR,所以具有传递性.由(1)(23)可知R在A上式等价关系。 26.解:任意两个正整数的最小公倍数仍是一个正整数,即。在Z+上是封闭的,故。是2+上的 二元运算。 va,b,c∈2+,设m=(a°b)c,n=a°(b°c),则有
5 (1,3,5,6,7) m1 m3 m5 m6 m7 。 ②求主合取范式 由①知命题公式 P Q R 的主合取范式为 (0,2,4) ( ) ( ) ( ) M0 M2 M4 P Q R P Q R P Q R 5 分 23．解： (1) { 0,2 , 0,3 , 1,3 } R R = 1 (2) {1} { 1,0 } R − = 1 (3) {1} {2, 3} R - ? 24．解 A (B C) = {a,b}{3} = { a,3 , b,3 } A B = { a,1 , a,2 , a,3 , b,1 , b,2 , b,3 } AC = { a,3 , a,4 , b,3 , b,4 } (A B) (AC) = { a,3 , b,3 } ∴ A (B C) = (A B) (AC) 25．解：i) F R( ) {0,1,2,3,4,5} = （1）因为 I F R R ( ( )) { 0,0 , 1,1 , 2,2 , 3,3 , 4,4 , 5,5 } = ， 所以 R 是自反的； （2）因为 1 { 0,0 , 1,1 , 2,1 , 3,1 , 1,2 , 2,2 , 3,2 , 1,3 , 2,3 , 3,3 , 4,4 , 5,4 , 4,5 , 5,5 } R − = 而 1 1 1 ( ) R R − − − = ，所以 R 是对称的； （3）因为 R R R ，所以具有传递性．由（1）(2)(3)可知 R 在 A 上式等价关系。 26．解：任意两个正整数的最小公倍数仍是一个正整数，即 在 Z+上是封闭的，故 是 Z+上的 二元运算。 Z+ a,b,c ，设 m = (a b) c ， n = a (b c) ，则有