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）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,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．{,}，{,,}；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 } 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) ，则有
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+ 是一 个半群。 因为 aZ+ ，有 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） xy(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） xA(x) T（4）（EG 规则） （6） xA(x) xB(x) P （7） xA(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 − 2Z
(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 上是封闭的，可结合的。 又 aZ ，有 2 Z ，使 2 a = 2 + a − 2 = a，a 2 = a + 2− 2 = a 所以运算 有单位元 2。 aZ ，有 4 − aZ ，使 (4 − a) a = (4 − a) + a − 2 = 2， a (4 − a) = a + (4 − a) − 2 = 2 所以 Z 中每一元素均有逆元 a = − a − 4 1 。 综上所述， (Z, ) 是群