(完整word版)离散数学期末考试试题(有几套带答案)

1、离散试卷及答案 第 1页共 12页 、证明题(10分) 1) ( -PA ( -QA R) V (QA R) V (P A R)=R 证明：左端-PA-QARVgVPjARj -PA-Q)AR) V(QVP)AR) ：=(-(PVQ)AR)V(QVP)ARi (PVQ)V(QVP)AR ：=(-CPVQ)V(PVQ)AZAR(W)：=R 2) x(A(x) _；B(x) = -xA(x) xB(x) 证明：x(A(x) B(x) x(F(x)VB(x)= xf(x)V xB(x)二-xA(x)V xB(x 建-xA(x) xB(x) 、求命题公式(P V (QA R)_.(P A QA R)的

2、主析取范式和主合取范式(10分) 证明： (P V (Q A R) r (P A QA R)h (P V (QA R) V(P AQA R) (-PA (-QV-R) )V (P A QA R) ：=(-PA P)V ( -PA -R) V (P A QA R) U( -PA PA R) V ( -PA PA -R) V ( PA QA -R) V ( PA QA R) V (P A QA R) :二 mOV mV mV m7 二 M3V M4V MV M6 三、推理证明题(10分) 1) CV D, (C V D) -E, -E (A A -B), (A A-B)=.(R V S)= RV

3、S 证明：(1) (C VD) -E (2) -E 乂 A A -B) (3) (C V D) (A A -B) (4) (A A -B) (R V S) (5) (C V D).(R V S) (6) C V D (7) R V S 2) x(P(x) ；Q(y) A R(x) , xP(x) =Q(y) A x(P(x) A R(x) 四、 设m是一个取定的正整数，证明：在任取 m 1个整数中，至少有两个整数，它们的差是 m的整数倍 证明 设a1 , a2，am1为任取的 冊 1个整数，用m去除它们所得余数只能是 o, 1，m-1,由抽屉原理可知， a1，a2，am 1这阿 1个整数中至少

4、存在两个数 as和at，它们被m除所得余数相同，因此 as和at的差是m的整 数倍。 五、 已知 A B、C是三个集合，证明 A-(B U C)=(A-B) n (A-C) (15分) 证明 /x 三 A- (BU C)：二 x 三 AA x ( BU C) = AA( xBA x ：= (AAxB)A( AA x】C) ：= (A-B) A (A-C) ：= x - (A-B)n( A-C). A- (BU C) = (A-B)n( A-C) 六、已知 R、S 是 N 上的关系，其定义如下： R=| x,y :二 NA y=x2，S=| x,y 二 NA y=x+1。 求 R1、 R*S、S

5、*R、 R 1,2、S1,2 (10 分) 解：R-1=| x,y 三 NA y=x2，R*S=| x,y 三 NA y=x2+1，S*R=| x,y 三 NA y= (x+1) 2， 七、若 f:A -B 和 g:B TC是双射，则(gf) 1=f1g1 (10 分)离散数学试题(A卷及答案) 证明(1) xP(x) P(a) -x(P(x) Q(y) A R(x) (4) P(a) .Q(y) AR(a) (5) Q(y) A R(a) (6) Q(y) (7) R(a) (8) P(a) (9) P(a) A R(a) (10) x(P(x) A R(x) (11)Q(y) A x(P(

6、x) A R(x) 离散试卷及答案 第 2页共 12页 证明：因为 f、g是双射，所以 gf : A-C是双射，所以 gf 有逆函数(gf) -1 : C-A。同理可推 f-1g-1： C-A是双射。 因为 f-1g-1： ：存在 z ( g-1 f-1)；二存在 z ( f g) = vy,x gf：= G(gf) -1, 所以(gf) -1=f-1g-1。 R 1,2=v1,1, , S1,2=1,4。 八、 (15分)设是半群，对A中任意元a和b,如ab必有a*b b*a,证明： (1) 对A中每个元a,有a*a= a。 (2) 对A中任意元a和b,有a* b*a= a。 (3) 对A中

7、任意元a、b和c,有a*b*c = a*c。 证明 由题意可知，若a*b= b*a,则必有a= b。 (1) 由(a* a)* a=a*( a* a)，所以 a*a=a。 (2) 由 a*( a*b*a) = (a*a)*( b*a) = a*b*( a*a) = (a*b*a)*a,所以有 a*b*a= a。 (3) 由(a* c)*( a* b* c) = (a*c*a)*( b*c) = a*( b*c) = (a*b)*c = (a*b)*( c*a*c) = ( a* b* c)*( a*c)，所以有 a*b*c= a*c。 九、 给定简单无向图 G= ,且| V| = m | E|

8、 = n。试证：若n醉+ 2,则G是哈密尔顿图 证明 若n讦+ 2，则 2n卅3m+ 6 (1 )。 若存在两个不相邻结点 u、v使得 d( u ) + d( v ) m则有 2n= d(w) Q(x) A xP(x)二- x(P(x) Q(x) A P(x) x( P(x) V Q(x) A P(x)二- x(P(x) A Q(x)：二- xP(x) A xQ(x) h x(P(x) A Q(x) 二、求命题公式(-PQ)r(P V -Q)的主析取范式和主合取范式(10分) 解：(-P Q) (P VP)u(-PQ)V (P V-Q)=(P V Q)V (P V-Q)=(-PAP)V (P

9、V Q) ：=(PV PVQ)A ( PV PV P)=(P V P)=M匕 mOV m2V m3 四、例 5在边长为 1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形(可能是退化的)面积不超三、推理证明题(10分) 1)(P (Q S) A ( -RV P) A Q ：R S 证明：(1) R 附加前提 (2) -RV P P (3) P T(1) (2),I (4) P ；(Q；S) P (5) Q；S T(3),1 (6) Q P (7) S T(5)(6),1 (8) R S CP 2) -x(P(x) V Q(x)，-x-P(x)= x Q(x) 证明：(1)

10、 x-P(x) P (2) -P(c) T(1),US (3) -x(P(x) V Q(x) P (4) P(c) V Q(c) T(3),US (5) Q(c) T(2X 4),1 (6) x Q(x) T(5),EG 离散试卷及答案 第 3页共 12页 过 1/8 ( 10 分)。 证明：把边长为 1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形(可能是退化的) 面积不超过小正方形的一半，即 1/8。 五、 已知 A B、C是三个集合，证明 An (B U C)=(A n B) U (A n C) ( 10分) 证明：T x 三 A n( BU C)：二

11、x 三 A A x 三(BU C)：二 x 三 A A( x 三 B V x 三 C)：二(x 三 A A x 三 B)V( x 三 A A x 三 C)：二 x 三(An B) V XE A QC= x e (An B)U( An C)二 An( BUC) = (An B)U( An C) 六、 7=A1，A,，An是集合 A的一个划分，定义 R=a，b|a、b A，1=1，2，n，则 R是 A上的等价关系(15分)。 证明：-a A必有 i使得 a A，由定义知 aRa,故 R自反。 a,b A，若 aRb，_则 a,b A，即 b,a A，所以 bRa,故 R对称。 -a,b,c A，若

12、 aRb 且 bRc，则 a,b A及 b,c A。因为 i 工 j 时 A n A=.：，故 i=j，即 a,b,c A，所以 aRc，故 R传递。 总之 R是 A上的等价关系。 七、 若 f:A -B是双射，则 f-1:B -A是双射(15分)。 证明：对任意的 x A，因为 f 是从 A到 B的函数，故存在 y B,使x,y f，y,x f-1。所以,f -1是满射。 对任意的 x A若存在 y1,y2 B，使得y1,x f-1且y2,x f-1,则有x,y1 f 且x,y 2 f。因为 f 是函数，_则 y】=y2。所 以，f 是单射。 因此 f 是双射。 八、 设G *是群，A, *

13、和B, *是G *的子群，证明：若 AU B= G,则A= G或B= G( 10 分)。 证明 假设G且G 则存在aA, aB,且存在 b=B, b-A (否则对任意的 aA, a二B从而 A B 即 AU B=B,得B= G 矛盾。) 对于元素a*bG,若a*bA,因A是子群，a-1.叭，从而a-1 * ( a*b) = b A,所以矛盾，故a*bA。同理可证a*bB,综合 有 a*b -AU B= G 综上所述，假设不成立，得证 A= G或 B= G 九、 若无向图 G是不连通的，证明 G的补图 G是连通的(10分)。 证明 设无向图G是不连通的，其k个连通分支为 G1、G2、Gk。任取结

14、点 u、v G若 u和 v不在图G的同一个连通分 支中，则u , v不是图G的边，因而u , v是图 G的边；若 u和 v在图G的同一个连通分支中，不妨设其在连通分支 G (1 w i w k )中，在不同于 Gi的另一连通分支上取一结点 w，U u , w 和w , v都不是图G的边，因而u , w 和w , v 都是 G的边。综上可知，不管那种情况， u和 v都是可达的。由 u和 v的任意性可知，G是连通的。 一、 选择题.(每小题 2分，总计 30) 1. 给定语句如下： (1) 15 是素数(质数) (2) 10 能被 2整除，3是偶数。 (3) 你下午有会吗？若无会，请到我这儿来！

15、(4) 2x+30. (5) 只有 4是偶数，3才能被 2整除。 (6) 明年 5月 1日是晴天。 以上 6个语句中，是简单命题的为(A),是复合命题的为(B),是真命题的为(C),是假命题的是(D),真值待定的命题是(E) A：(3)(6) (1)(4)(6) (1) ( 6) B: (6) (5) C:(1)(2)(5)(6) 无真命题 3( 5) D: (1)(2) 无假命题 (1)(2)(5) E:(6) 购(6) 无真值待定的命题 离散试卷及答案 第 4页共 12页 2. 将下列语句符号化： (1) 4是偶数或是奇数。(A)设 p： 4是偶数，q： 4是奇数离散试卷及答案 第 5页共

16、 12页 (2) 只有王荣努力学习，她才能取得好成绩。 (B)设 p：王荣努力学习，q：王荣取得好成绩 (3) 每列火车都比某些汽车快。 (C)设 F(x):x 是火车，G(y):y是汽车，H(x,y):x 比 y快。 A: p V q p A q p Tq B: p T q q T p p A q C:-x y (F(x) A G(y) 3. 设 S=1,2,3,下图给出了 1、设P x, y 为 x 整除 y, Qx 为 x : 2,个体域为 1,2/，求公式: _x y P x,y Q x 的真值。 2、设集合A1,2,3,4；A上的关系 R -1,1 , 1,2 , 2,1 / 2,3

17、 Q 2 =P 1,1 Q 1 上 P 2,1 Q 2 山 ii：P 1,2 Q 1 上 P 2,2 Q 2 P 1,2 i；=1,P 2,1i=0,P 2,2 i； = 1,Q 1=1,Q 2 =0 .=11上00i ii11上1 0 =1 该公式的真值是 1，真命题。 x y P x, y Q x = x P x,1 Q x P x,2 Q x P 1,1 Q 1 P1,2 Q1 P 2,1 Q 2 P 2,2 Q 2 或者 T T T T F F T F u T T T F u T T = T 2、r(R)1,1., 1,2, 2,1 , 2,3, 3,4 ,2,2 , 3,3 , 4,

18、4* s(R) 1,1 ,1,2, 2,1, 2,3, 3,4, 3,2, 43? t(R)1,1., 1,2 , 2,1, 2,3, 3,4, 1,3 , 2,2 , 2,4 , 1,4? （2）极小元、最小元是 1,极大元、 最大元是 24 四、3、（ 1） R是A上的偏序关系 离散试卷及答案 7 ) 第 8页共 12页 pqp = 一一 p q p 二 p q p 二 p =p q q =p q p q i 2, .主合取范式| . o , 安徽大学 2004-2005学年第二学期离散数学期末考试试卷（ A卷）参考答案 一、单项选择 在自然数集 N上，下列哪种运算是可结合的？（ A. a

19、* B. a * b = max a, b C. a* D. a* b = a b(mod 3) 下列代数系统S，*中，哪个是群? 离散试卷及答案 7 ) 第 9页共 12页 A. S =0,1,3,5，*是模 7 加法 B. S=Q （有理数集合），*是一般乘法 c. S二Z （整数集合），*是一般减法 D. S =1,3,4,5,9，*是模 11 乘法 若H，A. n整除m C. n整除m且 m整除n D. B. 下面哪个集合关于指定的运算构成环？（ =n， G = m整除n n不整除m且 m不整除n A. a b3 2 |a, b Z，关于数的加法和乘法 B. n阶实数矩阵，关于矩阵的加

20、法和乘法 C. a b 2 |a,b Z，关于数的加法和乘法 D. a,bZ 关于矩阵的加法和乘法 J 在代数系统中，整环和域的关系为（ ） A.域一定是整环 B. 域不一定是整环 C.整环一定是域 D. 域一定不是整环 D. N是自然数集，空是小于等于关系，则（N,乞）是（ A.有界格 B.有补格 C.分配格 D. 有补分配格 图 1-1给岀的哈斯图表示的格中哪个元素无补元？（ A. a B. c C. e D. 图 1-1 d g 离散试卷及答案 7 ) 第 10页共 12页 A. (1，1，2，2, 3) B. (1，3, 4, 4, 5) 给定下列序列，可构成无向简单图的结点度数序列的

21、是（ 离散试卷及答案 第 11页共 12页 9 欧拉回路是（ ）。 2 证明：（1）证明在格中成立：（a * b）二（c* d） _ （a 二 c） * （b 二 d）。 （5分） （2）证明布尔恒等式：（a * c）二（a * b）二（b* c） = （a * c）二（a * b）。 （5分）C. (0, 1, 3, 3, 3) D. (1 , 1, 2, 2, 2) A.路径 B. 简单回路 C.既是基本回路也是简单回路 10 哈密尔顿回路是（ ）。 D.既非基本回路也非简单回路 简单回路 D.既非基本回路也非简单回路 、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空 2 分，

22、共 30分） 1设S是非空有限集，代数系统（p（s）,u,n）中，p（s）对u运算的单位元是 ，零元是 ， p（s）对a运算 的单位元是 。 2 在运算表 2-1中空白处填入适当符号，使 （a,b,c,）成为群。 ， ， ， 。 3 设 H 二0,4,8 , :：: H , 12 是群：:：N12, 12 的子群，其中 N12 二0,1,2,11 , 12 是模 12 加法，则:：:N12, 12 有 个真子群，H的左陪集3H = , 4H二 。 4 设：:：A,，乜是一个布尔代数，如果在 A上定义二元运算 二为： a b c a a b a b c c c a 二 b = （a b） （a

23、b），则：A,三：是一个 。 表 2-1 5 任何一个具有2n个元素的有限布尔代数都是 _ _。 6 若连通平面图G有 4个结点，3个面，则G有 条边。 7 一棵树有两个结点度数为 2，一个结点度数为 3,三个结点度数为 4,它有 个度数为 1的结点 8 无向图G是由k（ k _2）棵数组成的森林，至少要添加 条边才能使 G成为一棵树。 三、求解题（20分） 1 试写出：:：N6, 6 中每个子群及其相应的左陪集。 （6 分） 2 若一个有向图 G是欧拉图，它是否一定是强连通的？若一个有向图 3有向图G如图 3-1所示。 （1） 求G的邻接矩阵A ； （2分） （2） G中V1到V4长度为 4

24、的路径有几条？ （2分） （3） G中V1到自身长度为 3的回路有几条？ （2分） （4） G是哪类连通图？ （2分） 四、证明题（30分） 1 设：:G,* 是一群，x G。定义：a b = a* x G是强连通的，它是否一定是欧拉图？说明理由。 （6分） 图 3-1 b , - a,bG。证明 G/也是一群 离散试卷及答案 第 12页共 12页 3 证明：（1）在 6个结点 12条边的连通平面简单图中，每个面由 3 条边围成。 （5分） （2）证明当每个结点的度数大于等于 3 时，不存在有 7条边的简单连通平面图。 安徽大学 2004-2005学年第二学期离散数学期末考试试卷（ A卷）参考

25、答案 一、 单项选择 1. B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C. 二、 填空题 1 ：,S , S ； 2 c, b , b , a ； 3 5 , 3,7,11 , 4,8,0 ； 4 交换群； 5 同构； 6 5 ; 7 9 ; 8 k -1。 三、 求解题 1 解：子群有：:0, 6 ,讥0,3, 6 , ： 0,2,4, 6 。 :0, 6 的左陪集为：0 , 1 , 2 , 3 , 4 , 5 0,3, 6 的左陪集为：0,3 , 1,4 , 2,5 离散试卷及答案 第 13页共 12页 中, 离散试卷及答案 第 16页共

26、12页 S关于max运算的么兀是 _ ，零兀是 _ 2.设10为模10加法，则在 :0,1川 1,9, 10 a 中，元素5的阶为 _ ， 6的阶为 3.设S|10 =1,2,5,10,11,22,55,110 , gcd和Icm分别为求最大公约数和最小公倍数运算, 则在布尔代数:：:SnQ,gcd,lcm 中，原子的个数为= 一，元素22的补元为一 4.在格：:：5. 一个具有n个结点的简单连通无向图的边数至少为 _ ，至多为= 三、解答题（第 1小题 12分，第 2小题 8分，共 20分） 1.设图G如图 1所示， V4 离散试卷及答案 第 17页共 12页 G，使得对于-x G有f（x）

27、 = 证明：f是：:G, 安徽大离散、单项选择题（每小题 2分，共 20分） 1.A ； 2.C ； 3.D ； 4.D ； 5.C ； 6.B ； 7.B ； 8.B ； 9.A ； 10.A 、填空题（每小空 2分，共 20分） 0， 1 ； 2. 2， 5 ； 3. 3， 5 ； 4. a ， b ； 5. n-1 ， n(n -1)/2 0 0 1 0 1 1 r 0 1. （1） G的邻接矩阵 A = 0 1 0 1 0 1 2 1 0 2 2 2、 0 2 4 2、 A(2)= 0 1 0 1 ； A= 0 0 2 0 ；A(4)= 0 2 0 2 0 0 2 0 0 2 0 2 0 0 4 0 0 1 0 1丿 0 0 2 0 0 2 0 2 从v1到v4的长为2,3, 4的路径的条数分别为1,2,2 ； 0 1 1 r 0 111 G的可达矩阵为P = 0 111 10 0 0 故G的强连通分图的结点集为 w，V2, V3N4。 12 分 三、解答题（第 1小题 12分，第 2小题 8分，共 20 分） 离散试卷及答案 第 18页共 12页 2. : N8, 8 的子群为：:0, 8 ， :： 0, 2,