离散数学-12参考答案

计算机学院 2004-2005 学年第一学期离散数学试题参考答案一、 选择题（每小题 1 分，共 10 分）1 下面哪个命题是命题“张三今天迟到或李四明天请假”的否定？（C ）A. 张三今天迟到或李四明天不请假 B. 张三今天不迟到或李四明天不请假C. 张三今天不迟到且李四明天不请假 D. 不是张三今天不迟到就是李四明天不请假2 PQ 的逆反式是（D ） 。A.QP B. PQ C. QP D. Q P 3 下列各式中不是永真式的是（D ） )()()(. )()()( xxPxPABACcB4 设 A,B 是集合，且 A-B=，则有（B） BDCB.5 幂集( () = ( C )。A. , B. ,C. , D. ,6 设 R,S 是非空集合 A 上的等价关系，则 R S 的对称性（A）A.一定成立 B. 一定不成立 C. 不一定成立 D. 取决于 R 是否包含 S7 若 f:AB, g:BC 是两个函数，且复合函数 f g 是满射的，则（ C ） 。A. f 必是满射 B. f 必是单射 C. g 必是满射 D. g 必是单射8 对于自然数集 N，下列哪种运算不是可结合的？（ A ）A. a*b = a+2b B. a*b=a+b+3 C. a*b=min(a,b) D. a*b=a·b (mod 4)9 群 G1=与群 G2=之间的关系是（ D ）A.同态 B.同构 C.G2 是 G1 的子群 D. A,B,C 都不对10 任何无向图中结点间的连通关系是一个（ D ） 。A. 偏序关系 B. 相容关系 C. 拟序关系 D.等价关系第一题答题表题号 1 2 3 4 5 6 7 8 9 10A B C D 二、 判断题（每小题 1 分，共 10 分）1 命题“十减四等于五”是一个原子命题。 （Y）2 联结词“” （或非）是可结合的。 （N）3 同一个谓词公式在不同的论域上的真值不一定相同 。 （Y）4 A,B 是集合，则命题 可能同时成立。 （Y）BA,5 若 R,S 是集合 A 上的二元关系，则 t(R S)=t(R) t(S) (N)6 A 是有限集 ， f： A A 是单射函数，则 f 是双射的。 （Y）7 设*是 S 上可结合的二元运算，a S,且 a 是可逆的，则 a 亦是可约的。 （Y）8 任何一个 Abel 群不一定是循环群 （Y）9 f 是群 G 到群 H 的同态映射，若 G 是交换群，则 H 也是交换群 （N ）10 若有向图 G 是个欧拉图，则 G 是一个强连通图 （Y）第二题答题表题号 1 2 3 4 5 6 7 8 9 10Y N 三、 演算题（共 40 分，以下第 1.、2.、3.小题每题 6 分，考生可任选答其中两题，若三题均做，则按每题 4 分计分；第 4.-7.题是必答题，每题 7 分）1 （6 分）设 A=a,b,c,c,a,b，B=a,b,b，计算 (1)AB； (2)AB； (3)(B)。2 （6 分）设集合 A = 1,2,3, A 上的关系 R = (1, 1), (1, 2), (2, 2), (2, 3), (3, 3),a) 写出 R 的关系矩阵；b) R 具有关系的哪些特性(自反、反自反、对称、反对称、传递)？(参考答案：a) .10b) R 具有反对称性和自反性 )3 （6 分）求公式 (P Q)（ P Q） 的主析取范式和主合取范式。(答案：主析：（ P Q） (P Q) 主合 ：（ P Q） (P Q)4 （7 分）设 A=1,2,3,4,6,12，R A2，且 R=| a 整除 b。a) 证明 R 是偏序的； （自反、反对称、可传递）b) 画出 R 的哈斯图；c) 给出集合2,3,4,6 的极小元、极大元、最小上界、最大下界。（答：小： 2， 3；大 4， 6；上： 12；下 1）5 （7 分）设 N 是自然数集合， f,g,h 是从 N 到 N 的函数，其中：是 奇 数是 偶 数nhngnf 0)(,)(,1)(给出 fºf, fºg, gºf, hºf, gºh, hºg, (fºg) ºh。 （注：º 是函数的复合运算）（答案： fºf(n)=n+2, ( fºg)(n)=2(n+1), gºf(n)=2n+1： gh(n)=0, hg(n)=0(n 为偶数 )及2（ n 为奇数） ； (fºg) ºh（ n） =0。 ）6（7 分）设 Zn 为模 n 加群，f:Z 12Z 3， f(x)=(x mod 3)，则 f 为同态映射。a) 验证 f 是否为单同态和满同态。b) 令 K=x|f(x)=0，计算 K。答：a）是满同态，因为 Z3 中每个元素 x 至少都有一个像源 x。该映射是保持运算的。即 Z12 中的任何 a， b，有：f(a+12b)=(a+12b )mod 3=a mod3 +3 b mod3=f(a)+3 f(b)。b)K=0,3,6,97 （7 分）已知无向图 G 有 12 条边，1 度顶点有 2 个，2 度、3 度、5 度顶点各 1 个，其余顶点度数均为 4，求 4 度顶点的个数。.（答案： 3）四、 证明题（共 40 分。以下六小题每题 8 分，考生可以任选做其中五题。若六题全做，按前五题计分）1（8 分）用形式演绎法证明： P Q, P R, Q S, R (P Q)蕴涵 S .参考证明：证 : (1) P Q P(2) R (P Q) P(3) R (P Q) Q(2)(4) (P Q) R Q(3)(5) R Q(1)(4)(6) P R P(7) R P Q (6)(8) P Q(5)(7)(9) Q Q(1)(8)(10) Q S P(11) S Q(9)(10)所以 P Q, P R, Q S, R (P Q)蕴涵 S 2 （8 分）用数学归纳法证明：若 R 是集合 A 上的自反和传递关系，则对任意的n， Rn=R。（证明： n=1 时， R1=R。设 n=k 时， Rk=R。 Rk+1=Rk R=ROR=R2.设 R2,则存在c，式 aRc,cRb,由于 R 是传递的，有 aRb。所以， R2R. 设 aRb，由于 R 是自反的， bRb，从而 aRORb,即 aR2b。所以 RR2。综合有 R2=R。进一步有 Rk+1=R。 ）3 （8 分）设 （ A,*） 是一个半群，且对于 A 中的每个 a 和 b，若 a b，则 a*b b*a。证明： aA，有 a*a=a。（ 证明：假设 a*a=b a, 由于 a 是半群，则可结合。从而， a*b=a*(a*a)=(a*a)*a=b*a,矛盾，所以， a*a=a） .4 （8 分）设 H 是群 G 的子群，证明：H 是 G 的正规子群的充要条件是： aG , aHa-1H.（证明 :“”设 H 是正规子群 ,则 aH=Ha.设 b aHa-1 ,h H， b=aha-1ba=ah aH=Ha,h H: ba=ah=ha (利用消去律 )b=h H aHa-1H. “”：设 a: aHa-1H， baH， hH， b=ah ba-1=aha-1 =h ( aHa-1H) b=haHa aHHa; bHa， hH， b=ha a-1b=a-1ha a-1b=h( a-1HaH) b=ah aH HaaH; Ha=aH.即 H 是正规子群） 5 （8 分）设 G 是一个群， H， K 是群 G 的子群，证明：G 上的二元关系 R=| hH,kK,b=hak是一个等价关系。（ 证明： H,K 均是子群， e 是 H,K 中元素。对于任意的 G 中元素 a，有： a=eae,即aRa. R 是自反的 。 设 aRb,由定义， hH， k K， b=hak, H,K 是子群，则 h-1H,k-1K， a=eae =h-1hakk-1= h-1(hak)k-1=h-1bk-1,从而， aRb。 R 也是对称的 。设 aRb,bRc 成立，则有 b=h1ak1,c=h2bk2,从而有 c=h2h1ak1k2, H,K 是子群，封闭性满足，存在h3=h2h1,H， k3=k1k2, K， 从而 c=h3ak3,即 aRc。 R 是传递的 。综合上述， R 是等价关系。 ）6 （8 分）设 G=是简单无向连通图，但不是完全图，证明 G 中必存在三个结点u,v,wV，使得(u,v) E,(v,w) E,但(u,w) E。（ 证明：因为 G 不是完全图，存在 u， wV， (u,w) E,由 G 是连通的，在 u， w 之间必有基本通路 L。设为 uv1v2vnw,n 1,若 n=1， v2=w,这样的话， u,v2,w 即是所求。若 n>1,则 (u,v2) E,否则 L 就不是基本路径，令 v1=v,v2=w,这时， u,v,w 即为所求。 ）