《离散数学》2004~2005学年第二学期考试试题A卷答案

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.反对称性,{,,,,} 15·={a,1>,,,} f4={a,2>(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={,,,,} 1分 (2)R*R={,,,,} 分 (3)R↑轨,{外}=R个0,1}={,,<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）xP(x) 前提 （2）P(y) （1）；US （3）xQ(x) 假设 （4）xQ(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))，xP(x)xQ(x)。 30 ．证明 a,b G ，存在 k,l  Z 使 a = km,b = lm 。由于 k +l Z ，得知 a + b = km+ lm = (k + l)mG ，即 + 在 G 上是封闭的。 由整数运算的性质可知， + 是可结合的。 0 = 0mG ，对 aG ，有 a + 0 = 0 + a = a ，故 0 是 G 的单位元。 aG ，存在 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,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 为实数，则命题可符号化为 xy(R(x)  R( y) → x  y  x  y) ； 13．B；A；14．{,}，{,,}；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={,,} (2)R1↑{}={,,,} A×C={} (A×B)∩(A×C)={,} ∴Ax(B∩C)=(AxB)∩(AxC 25.解:i)F(R)={0,1,2,3,4,5} (1)因为/(F(R)={,,,,,,,,,,,,,, ,,,} 而(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 } AC = { a,3 , a,4 , b,3 , b,4 } (A B)  (AC) = { a,3 , b,3 } ∴ A (B C) = (A B)  (AC) 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) ，则有

m=lcm(lcm(a,b),c) →kcm(a,b)|m,cl|m →a|m,lm(b,c)|m →kcm(a,km(b,c)|m 同理可证m|n。故有m=n,即(aob)°c=a°(boc)。所以。是可结合的。从而(Z,)是一 个半群。 因为∈2+,有aol=km(a1)=a,故1是单位元,即(2+,)是含单位元的半群 四.计算题(二) 27. Af: abc +abC +bc +abc tabc =ab(c+a)+bc+ab(c+c)(结合律,分配律) 16+6c+ab b((a+a)+c) (交换律,分配律,结合律) b (a+a=1.1+c=1) 8.解:解 121 1010 2111 A(D) l001 2110 7342 167104 5231 A(D)= 11573 A(D) 10463 从v1到v长度为2的通路有1条:ve3v3e,v4

6 m = lcm(lcm(a,b), c)  lcm(a,b) | m, c | m  a | m, b | m, c | m  a | m, lcm(b,c) | m  lcm(a,lcm(b,c)) | m 即 n | m 同理可证 m | n 。故有 m = n ，即 (a  b) c = a (b  c) 。所以  是可结合的。从而 ( , ) Z+ 是一 个半群。 因为 aZ+ ，有 a 1 = lcm(a,1) = a ，故 1 是单位元，即 ( , ) Z+ 是含单位元的半群。 四．计算题（二） 27．解： abc + abc +bc + abc + abc = ab(c + c) + bc + ab(c + c) （结合律，分配律） = ab +bc + ab （ c + c =1 ） = b((a + a) + c) （交换律，分配律，结合律） = b （ a + a = 1, 1+ c = 1 ） 8．解：解               = 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 v 到 4 v 长度为 2 的通路有 1 条： 1 5 3 7 4 v e v e v

从v到v2长度为3的通路有2条:ve2n2e"eyv,ve1ve3v3eV4 四.1.证明(1)Vx(x)vxB(x) (2)VxA(x)v VyB(y T(1)(换名规则) (3)VxVy(A(x)vB() T(2)(前束范式性质2) (4)Vy(A(a)v B() T(3)(US规则) A(a)vb(a T(4)(US规则) (6)x(4(x)B(x) T(5)(LG规则) 证二(1)-x(4(x)B(x) P(附加) (2)3x(-4(x)∧-B(x) T(1)(等值置换) (3)4(a)∧=B(a) T(2)(ES规则 (4)_(a) T(3)(化简规则) (5)3x4(x) T(4)(EG规则) (6)VxA(x)v VxB(x) (7)3x4(x)→VxB(x) T(6)(等值置换) (8)VxB(x) T(5),(7)(假言推理) (9)Ba) T(8)(US规则) (10)=B(a) T(3)(化简规则) (11)B(a)∧_B(a) T(9),(10)(合取引入) 2.证明:Va,b,c∈z aob=a+b-2∈Z

7 从 1 v 到 4 v 长度为 3 的通路有 2 条： 1 2 2 4 3 7 4 v e v e v e v ， 1 1 1 5 3 7 4 v e v e v e v 。 四．1．证明 （1） xA(x)  xB(x) P （2） xA(x)  yB( y) T（1）（换名规则） （3） xy(A(x)  B( y)) T（2）（前束范式性质 2） （4） y(A(a)  B( y)) T（3）（US 规则） （5） A(a)  B(a) T（4）（US 规则） （6） x((A(x)  B(x)) T（5）（UG 规则） 证二 （1） x(A(x)  B(x)) P（附加） （2） x(A(x)  B(x)) T（1）（等值置换） （3） A(a)  B(a) T（2）（ES 规则） （4） A(a) T（3）（化简规则） （5） xA(x) T（4）（EG 规则） （6） xA(x)  xB(x) P （7） xA(x) → xB(x) T（6）（等值置换） （8） xB(x) T（5），（7）（假言推理） （9） B(a) T（8）（US 规则） （10） B(a) T（3）（化简规则） （11） B(a)  B(a) T（9），（10）（合取引入） 2．证明： a,b,c  Z a b = a +b − 2Z

(aoboc=(a+b-2oc=(a+b-2)+c-2=a+b+c-4 n0(bc)=a(b+c-2)=a+(b+c-2)-2=a+b+c-4 (aob)。c=ao(boc) 所以运算。在Z上是封闭的,可结合的。 又Va∈Z,有2∈Z,使2。a=2+a-2=a,ao2=a+2-2=a所以运算o有单位元 Va∈Z,有4-a∈Z,使 4-a)oa=(4-a)+a-2=2,a。(4-a)=a+(4-a)-2=2 所以Z中每一元素均有逆元a-=4-a 综上所述,(Z,)是群

8 (a  b) c = (a + b − 2) c = (a + b − 2) + c − 2 = a + b + c − 4 a (b  c) = a (b + c − 2) = a + (b + c − 2) − 2 = a + b + c − 4 (a  b) c = a (b  c) 所以运算  在 Z 上是封闭的，可结合的。 又 aZ ，有 2  Z ，使 2 a = 2 + a − 2 = a，a  2 = a + 2− 2 = a 所以运算  有单位元 2。 aZ ，有 4 − aZ ，使 (4 − a) a = (4 − a) + a − 2 = 2， a (4 − a) = a + (4 − a) − 2 = 2 所以 Z 中每一元素均有逆元 a = − a − 4 1 。 综上所述， (Z, ) 是群