离散数学期末考试试题（有几套带答案）

离散试卷及答案 离散数学试题(A卷及答案）

一、证明题（10分）

1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R

证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R)

?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R

2)?x(A(x)?B(x))? ?xA(x)??xB(x)

证明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)??xB(x) 二、求命题公式(P∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式（10分）

证明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))

?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)

?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6

三、推理证明题（10分）

1） C∨D, (C∨D)? ?E, ?E?(A∧?B), (A∧?B)?(R∨

S)?R∨S

证明：(1) (C∨D)??E (2) ?E?(A∧?B) (3) (C∨D)?(A∧?B) (4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D (7) R∨S

2) ?x(P(x)?Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))

证明（1）?xP(x) (2)P(a)

(3)?x(P(x)?Q(y)∧R(x)) (4)P(a)?Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x))

四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍

证明 设a1，a2，…，am?1为任取的m＋1个整数，用m去除它们所得余数只能是0，1，…，m－1，由抽屉原理可知，

a1，a2，…，am?1这m＋1个整数中至少存在两个数as和at，它们被m除所得余数相同，因此as和at的差是m的整

数倍。

五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）

证明 ∵x? A-（B∪C）? x? A∧x?（B∪C）? x? A∧（x?B∧x?C）? （x? A∧x?B）∧（x? A∧x?C）? x?（A-B）∧x?（A-C）? x?（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）

六、已知R、S是N上的关系，其定义如下：R={| x,y?N∧y=x}，S={| x,y?N∧y=x+1}。求R、R*S、S*R、R{1,2}、S[{1,2}]（10分）

解：R={| x,y?N∧y=x}，R*S={| x,y?N∧y=x+1}，S*R={| x,y?N∧y=（x+1）}， 七、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。

第 1 页 共 12 页

-1

-1-1

-1

2

2

2

2

-1

离散试卷及答案

证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。 因为∈fg?存在z（∈g?∈f）?存在z（∈f?∈g）?∈gf?∈（gf）,所以（gf）=fg。

R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。

八、（15分）设是半群，对A中任意元a和b，如a≠b必有a*b≠b*a，证明：

(1)对A中每个元a，有a*a＝a。 (2)对A中任意元a和b，有a*b*a＝a。 (3)对A中任意元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。

2九、给定简单无向图G＝，且|V|＝m，|E|＝n。试证：若n≥Cm?1＋2，则G是哈密尔顿图 2证明 若n≥Cm。 ?1＋2，则2n≥m－3m＋6 （1）

2

-1

-1-1

-1-1

-1

-1

-1

-1

-1-1

若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝

w?V?d(w)＜m＋(m－2)(m－3)＋m＝m－3m＋6，与（1）矛

2

盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m，所以G是哈密尔顿图。

离散数学试题(B卷及答案）

一、证明题（10分）

1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T

证明 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入) 2)?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x))

证明 ?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x))

二、求命题公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式（10分）

解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3 三、推理证明题（10分） 1)(P?(Q?S))∧(?R∨P)∧Q?R?S

证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2),I (4)P?(Q?S) P (5)Q?S T(3)(4),I (6)Q P

(7)S T(5)(6),I

(8)R?S CP

2) ?x(P(x)∨Q(x))，?x?P(x)??x Q(x)

证明：(1)?x?P(x) P (2)?P(c) T(1),US (3)?x(P(x)∨Q(x)) P (4)P(c)∨Q(c) T(3),US (5)Q(c) T(2)(4),I (6)?x Q(x) T(5),EG

四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超

第 2 页 共 12 页

离散试卷及答案

过1/8（10分）。

证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。

五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）

证明：∵x? A∩（B∪C）? x? A∧x?（B∪C）? x? A∧（x?B∨x?C）?（ x? A∧x?B）∨（x? A∧x?C）? x?（A∩B）∨x? A∩C? x?（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）

六、?={A1，A2，…，An}是集合A的一个划分，定义R={|a、b∈Ai，I=1，2，…，n}，则R是A上的等价关系（15分）。 证明：?a∈A必有i使得a∈Ai，由定义知aRa，故R自反。

?a,b∈A，若aRb ，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。

?a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=?，故i=j，即a,b,c∈Ai，所以aRc，故R传递。 总之R是A上的等价关系。

七、若f:A→B是双射，则f:B→A是双射（15分）。

证明: 对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使∈f，∈f。所以,f是满射。

对任意的x∈A，若存在y1,y2∈B，使得∈f且∈f,则有∈f且∈f。因为f是函数，则y1=y2。所以，f是单射。 因此f是双射。

八、设是群，和是的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）。

证明 假设A≠G且B≠G，则存在a?A，a?B，且存在b?B，b?A（否则对任意的a?A，a?B，从而A?B，即A∪B＝B，得B＝G，矛盾。）

对于元素a*b?G，若a*b?A，因A是子群，a?A，从而a * (a*b)＝b ?A，所以矛盾，故a*b?A。同理可证a*b?B，综合有a*b?A∪B＝G。

综上所述，假设不成立，得证A＝G或B＝G。

九、若无向图G是不连通的，证明G的补图G是连通的（10分）。

证明 设无向图G是不连通的，其k个连通分支为G1、G2、…、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v]是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。

-1

-1

-1

-1

-1

-1

-1

-1

-1

一、 选择题.(每小题2分，总计30) 1. 给定语句如下： （1）15是素数（质数） （2）10能被2整除，3是偶数。

（3）你下午有会吗？若无会，请到我这儿来！ （4）2x+3>0.

（5）只有4是偶数，3才能被2整除。 (6)明年5月1日是晴天。

以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E） A: ①(1)(3)(4)(6) ②(1)(4)(6) ③(1)（6） B: ①(2)(4) ②(2)(4)(6) ③(2)(5) C: ①(1)(2)(5)(6) ②无真命题 ③（5） D: ①(1)(2) ②无假命题 ③(1)(2)(4)(5) E: ①(4)(6) ②（6） ③ 无真值待定的命题 2. 将下列语句符号化：

（1）4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数

第 3 页 共 12 页

离散试卷及答案

（2）只有王荣努力学习，她才能取得好成绩。（B）设p：王荣努力学习，q：王荣取得好成绩 （3）每列火车都比某些汽车快。（C）设F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。 A: ① p∨q ② p∧q ③ p→q B: ① p→q ② q→p ③ p∧q

C: ①?x ?y ((F(x) ∧G(y)) → (H(x,y))②?x (F(x) →?y(G(y)∧H(x,y)))③?x (F(x) ∧?y(G(y)∧H(x,y))) 3. 设S={1,2,3},下图给出了S上的5个关系,则它们只具有以下性质:R1是（A）,R2是(B),R3是(C)。

A B C:①自反的，对称的，传递的 ②反自反的，对称的 ③自反的

④??

反对称的 ⑤对称的 ⑥自反的，对称的，反对称的，传递的

4. 设S={Ф，{1}，{1，2}}，则有

（1）（A）?S （2） (B) ?S

（3） P(S)有（C）个元数。 （4）（D）既是S的元素，又是S的子集 A: ① {1,2} ② 1 B: ③{{1,2}} ④{1} C: ⑤ 3 ⑥ 6 ⑦ 7 ⑧ 8 D: ⑨ {1} ⑩Ф

二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分） 1、用等值演算算法证明等值式 (p∧q)∨(p∧?q)?p 2、构造下面命题推理的证明

如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。

三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分， 总计30分） 1、设P?x,y?为x整除y，Q?x?为x?2，个体域为?1，2?，求公式： ??x???y??P?x,y??Q?x??的真值。

2、设集合3、设A?A??1,2,3,4?,A上的关系 R??1,1,1,2,2,1,2,3,3,4?，求出它的自反闭包，对称闭包和传递闭包。

?1,2,4,8,12,24,?上的整除关系R??a1,a2a1,a2?A,a1整除a2?，R是否为A上的偏序关系？若是，则：

1、画出R的哈斯图；（10分）

2、求它的极小元，最大元，极大元，最大元。（5分） 四、用推导法求公式答案： 一、 选择题

1. A:③ B: ③ C:③ D:① E:② 2.A:① B: ② C:② 3.A:③ B: ④ C:⑥ 4.A:① B: ③ C:⑧ D:⑩ 二、证明题

1. 证明 左边?（(p∧q)∨p）∧（(p∧q)∨?q)） （分配律） ? p∧（(p∧q)∨?q)） (吸收律) ? p∧（(p∨?q) ∧ (q∨?q)） （分配律） ? p∧（(p∨?q)∧1） （排中律）

??p?q??p?的主析取范式和主合取范式。（本大题10分）

第 4 页 共 12 页

离散试卷及答案

? p∧ (p∨?q) （同一律） ? p （吸收律） 2.解：p：今天是星期三。 q：我有一次英语测验。 r：我有一次数学测验。 s：数学老师有事。

前提：p?(q∨r) , s??r , p∧s 结论：q

证明：①p∧s 前提引入

②p ①化简 ③p?(q∨r) 前提引入 ④q∨r ②③假言推理 ⑤s ①化简 ⑥s??r 前提引入 ⑦?r ⑤⑥假言推理 ⑧q ④⑦析取三段论 推理正确。

三、计算

??x???y??P?x,y??Q?x??1. ???y???P?1,y??Q?1????P?2,y??Q?2????

??P?1,1??Q?1????P?2,1??Q?2??????P?1,2??Q?1????P?2,2??Q?2???

P?1,1??1,P?1,2??1,P?2,1??0,P?2,2??1,Q?1??1,Q?2??0????1?1???0?0?????1?1???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????P?1,2??Q?1??????P?2,1??Q?2????P?2,2??Q?2???或者

???T?T???T?T?????F?F???T?F????T?T???T?F??T?T?T2、r(R)??1,1,1,2,2,1,2,3,3,4,2,2,3,3,4,4?

s(R)??1,1,1,2,2,1,2,3,3,4,3,2,4,3?

t(R)??1,1,1,2,2,1,2,3,3,4,1,3,2,2,2,4,1,4?

3、（1） R是

A上的偏序关系。

（2）极小元、最小元是1,极大元、 最大元是24。 四、

第 5 页 共 12 页

离散试卷及答案

??p?q??p??????p?q??p????p??q??p??p?p??q??q???p??q???p?q????主合取范式??0，1?安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案

一、单项选择

1 在自然数集N上，下列哪种运算是可结合的？（ ）

A. a*b

3??2，?a?b B. a*b?max{a,b}

?2b D. a*b?a?b(mod3)

C. a*b?a2 下列代数系统中，哪个是群？（ ）

A. SC. S?{0,1,3,5}，*是模7加法 B. S?Q（有理数集合），*是一般乘法 ?Z（整数集合），*是一般减法 D. S?{1,3,4,5,9}，*是模11乘法

。 H?n，G?m，则有（ ）

3 若是的真子群，且

A. n整除m B. m整除n

C. n整除m且 m整除n D. n不整除m且 m不整除n 4 下面哪个集合关于指定的运算构成环？（ ）

A. {a?b32|a,b?Z}，关于数的加法和乘法

B.{n阶实数矩阵}，关于矩阵的加法和乘法

a C. {a?b2|a,b?Z}，关于数的加法和乘法

b e c f d g ????ab??a,b?Z?D. ???，关于矩阵的加法和乘法 ?ba???????5 在代数系统中，整环和域的关系为（ ）。

A. 域一定是整环 B.域不一定是整环 C. 整环一定是域 D. 域一定不是整环

6 N是自然数集，?是小于等于关系，则(N,?)是（ ）。

A. 有界格 B.有补格 C. 分配格 D. 有补分配格 7 图1-1给出的哈斯图表示的格中哪个元素无补元？（ ）

A. a B. c C. e D.

f 图1-1

8 给定下列序列，可构成无向简单图的结点度数序列的是（ ）。

A.（1，1，2，2，3） B.（1，3，4，4，5）

第 6 页 共 12 页

离散试卷及答案

C.（0，1，3，3，3） D.（1，1，2，2，2） 9 欧拉回路是（ ）。

A.路径 B.简单回路

C.既是基本回路也是简单回路 D.既非基本回路也非简单回路 10 哈密尔顿回路是（ ）。

A.路径 B.简单回路

C.既是基本回路也是简单回路 D.既非基本回路也非简单回路

二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）。

1 设S是非空有限集，代数系统(P(S),?,?）中，P(S)对?运算的单位元是＿＿＿＿，零元是＿＿＿＿，P(S)对?运算的单位元是＿＿＿＿。

2 在运算表2-1中空白处填入适当符号，使({a,b,c},?)成为群。 ? a b c ①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。 a ① a ② 3 设H?{0,4,8}，?H,?12?是群?N12,?12?的子群，其中

b a b c c ③ c ④ N12?{0,1,2,???,11}，?12是模12加法，则?N12,?12?有＿＿＿＿

个真子群，H的左陪集3H?＿＿＿＿，4H?＿＿＿＿。

4设?A,?,?,??是一个布尔代数，如果在A上定义二元运算?为：

a?b?(a?b)?(a?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是欧拉图，它是否一定是强连通的？若一个有向图G是强连通的，它是否一定是欧拉图？说明理由。3 有向图G如图3-1所示。 e1 （1）求G的邻接矩阵

A； （2分）

（2）G中vv1 1到v4长度为4的路径有几条？ （2分） ee4 v4 3 e2 e6 e7 （3）G中v1到自身长度为3的回路有几条？ （2分） v2 e5 v3

（4）G是哪类连通图？ （2分）

图3-1

四、证明题（30分）

1 设?G,*?是一群，x?G。定义：a?b?a*x*b，?a,b?G。证明?G,??也是一群。 2 证明：（1）证明在格中成立：(a*b)?(c*d)?(a?c)*(b?d)。 （5分）

（2）证明布尔恒等式：(a*c)?(a?*b)?(b*c)?(a*c)?(a?*b)。 （5分）

第 7 页 共 12 页

6分） （离散试卷及答案

3 证明：（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （5分）

（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。

安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案

一、单项选择

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； 5 同构； 三、求解题

1 解：子群有：?{0},?6

6 5；

3 5，{3,7,11}，{4,8,0}； 4 交换群； 7 9；

8 k?1。

?，?{0,3},?6?，?{0,2,4},?6?。

?{0},?6?的左陪集为：{0}，{1}，{2}，{3}，{4}，{5} ?{0,3},?6?的左陪集为：{0,3}，{1,4}，{2,5}

?{0,2,4},?6?的左陪集为：{0,2,4}，{1,3,5}

2 答：（1）一个有向欧拉图一定是强连通图。因为G是欧拉图，存在欧拉回路C，G中的每个结点至少在C中出现一次。因而G中任意两点u，v都在C中，相互可达，故G是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。 3 解：

?1?0（1）A???0??0（2）由

200011010??1?00?2? A??1??0??0??0200030101??1?01?3? A??0??0??1??0200041013??1?00?4? A??1??0??0??0200060104?1?? 0??1?4A4中a14。 ?4可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，e1e2e5e6，e1e3e5e6）3A3中a11。 ?1可知，v1到自身长度为3的回路有1条（e1e1e1）

（3）由

（4）G是单向连通图。 四、证明题

1 证明：显然?是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有单位元，每个元素有逆元。 ?a,b,c?G，有

(a?b)?c?(a*x*b)*x*c?a*x*(b*x*c)?a?(b?c) 运算是可结合的。 其次，x?1是?G,??的单位元。事实上，?a?G，有

a?x?1?a*x*x?1?a；x?1?a?x?1*x*a?a

最后证明，?a?G，x?1*a?1*x?1是a在?G,??中的逆元。事实上，

第 8 页 共 12 页

离散试卷及答案

a?(x?1*a?1*x?1)?a*x*x?1*a?1*x?1?x?1 (x?1*a?1*x?1)?a?x?1*a?1*x?1*x*a?x?1

由以上证明，?G,??是群。

2 证明：（1）(a*b)?(c*d)?((a*b)?c)*((a*b)?d) （公式(13)分配不等式） 又因为a*b?（2）因为aa，a*b?b，所以(a*b)?(c*d)?(a?c)*(b?d)。

?a??1，1*(b*c)?(b*c)，所以有，

(a*c)?(a?*b)?(b*c)?(a*c)?(a?*b)?((a?a?)*(b*c)) ?(a*c)?(a?*b)?((a*b*c)?(a?*b*c))

?((a*c)?(a*c*b))?((a?*b)?(a?*b*c)) （吸收律） ?(a*c)?(a?*b)

即等式成立。

3 证明：（1）因图中结点数和边数分别为

in?6，

m?12，根据欧拉公式

n?m?k?2，得

k?8。又

?deg(v)?2m?24，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个

面由3条边围成。

（2）设(n,m)图为简单连通平面图，有k个面。（反证法） 若m?7，由欧拉公式知n?k?m?2?9，而每个面至少由3条边围成，有3k?2m，则k?214m?，且k是整33数，所以k有n?4；又对任结点v?V，deg(v)?3，有3n?2m，故n?214m?，且n是整数，所以n?4。这样就33?k?4?4?8，与n?k?9矛盾，所以结论正确。

安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A卷）

一、单项选择题（每小题2分，共20分）

1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）

A.自然数集合； B.整数集合； C.有理数集合； D.实数集合。 2. 设I为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）

A.I； B.{2k|k?I}； C.{2k?1|k?I}； D.{3m?5n|m,n?I}。

3. 设N6?{0,1,?,5}，?6为模6加法，则下列元素是?N6,?6?的生成元的是（ ）

A.2； B.3； C.4； D.5。

第 9 页 共 12 页

离散试卷及答案

4. 设?F,?,??是整环，则?F,?,??不一定是（ ）

A.可交换环； B.无零因子环； C.含么环； D.域。 5. 格不一定具有（ ）

A.交换律； B.结合律； C.分配律； D.吸收律。 6. 设S?{1,2,4,8}，?和?分别表示求最小公倍数和最大公约数运算，则?S,?,??是（ ）

A.有补格； B.分配格； C.有补分配格； D.布尔代数。

7. 一个含4个结点的无向图中有3个结点的度数分别为1,2,3，则第4个结点的度数不可能是（ ）

A.0； B.1； C.2； D.4。

8. 设连通的简单平面图G中有10条边和5个面，则G的结点数为（ ）

A.6； B.7； C.8； D.9。

9. 设无向树T中有1个结点度数为2，2个结点度数为3，3个结点度数为4，则T中的树叶数为（ ）

A.10； B.11； C.12； D.13。

10.设G为连通的无向图，若G仅有2个结点的度数是奇数，则G一定具有（ ）

A、欧拉路径； B、欧拉回路； C、哈密尔顿路径； D、哈密尔顿回路。 二、填空题（每小空2分，共20分） 1. 设R为实数集合，S?{x|x?R?0?x?1}，则在代数?S,max>中，

S关于max运算的么元是＿ ＿＿，零元是＿ ＿＿。

2. 设?10为模10加法，则在?{0,1,?,9},?10?中，元素5的阶为 ，6的阶为＿ ＿＿。

3. 设S110?{1,2,5,10,11,22,55,110}，gcd和lcm分别为求最大公约数和最小公倍数运算，

则在布尔代数?S110,gcd,lcm?中，原子的个数为＿ ＿＿，元素22的补元为＿ ＿＿。

4. 在格?L,?,??中，?a,b?L，a?b当且仅当a?b?＿ ＿＿当且仅当a?b?＿ ＿＿。

5. 一个具有n个结点的简单连通无向图的边数至少为＿ ＿＿，至多为＿ ＿＿。 三、解答题（第1小题12分，第2小题8分，共20分） 1. 设图G如图1所示， (1) 求G的邻接矩阵(2) 求A(2)A；

,A(3),A(4)，说明从v1到v4的长为2,3,4的路径各有几条；

第 10 页 共 12 页

离散试卷及答案

(3) 求G的可达矩阵P； (4) 求G的强连通分图。 2. 求群?N8,?8?的所有子群及由元素5确定的各子群的左陪集，其中N8?{0,1,???,7}，?8是模8加法。

四、证明题（每小题10分，共40分）

1. 证明布尔恒等式：(a?b)?(a??c)?(b??c)?(a?b)?c。 2. 设R为实数集合，?和?为数的加法和乘法运算，对?a,b?R，a*b证明：??a?b?a?b，

R,??为独异点。

?1(n?1)(n?2)，则图G是连通图。 23. 证明：若(n,m)简单无向图G满足m4. 设?G,??是一个群，a?G；定义一个映射

证明：

f:G?G，使得对于?x?G有f(x)?a?x?a?1；

f是?G,??

安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A卷）

一、单项选择题（每小题2分，共20分）

1.A； 2.C； 3.D； 4.D； 5.C； 6.B； 7.B； 8.B； 9.A； 10.A。 二、填空题（每小空2分，共20分）

1.0，1； 2.2，5； 3.3，5； 4.a，b； 5.n?1，n(n?1)/2。 三、解答题（第1小题12分，第2小题8分，共20分）

?0?01. (1) G的邻接矩阵A???0??0?0?0???0??011012020101011011??0?； 2分 1??0?202022022??0??0?0；A(4)???02???0??0220240402??2?； 5分 0??2?(2)

A(2)1??0??1?0；A(3)???00???1??0从v1到v4的长为2,3,4的路径的条数分别为1,2,2； 8分

?0?0(3) G的可达矩阵为P???0??0?0?0(4) 因P?PT???0??001110111111111111??1?； 10分 1??1?0??1?，故G的强连通分图的结点集为{v1}，{v2,v3,v4}。 12分 1??1?第 11 页 共 12 页

离散试卷及答案

2. ?N8,?8?的子群为：?{0},?8?，?{0,2,4,6},?8?，?{0,4},?8?，?N8,?8?； 4分

元素5确定的各子群的左陪集对应为：{5}，{1,3,5,7}，{1,5}，N8。 8分 四、证明题（每小题10分，共40分）

1. (a?b)?(a??c)?(b??c)?(a?b)?((a??b?)?c) 2分

?(a?b)?((a?b)??c)?((a?b)?(a?b)?)?((a?b)?c) 6分 ?1?((a?b)?c)?(a?b)?c。 10分

2. 因R对?和?运算封闭，故R对?运算封闭；对?x,y,z?R， 2分

(x*y)*z?(x?y?x?y)*z?x?y?xy?z?(x?y?xy)z?x?y?z?xy?xz?yz?xyz, x*(y*z)?x*(y?z?y?z)?x?y?z?yz?x(y?z?yz)?x?y?z?xy?xz?yz?xyz

故(x?y)?z?x?(y?z)，从而R上的?运算满足结合律； 6分

?0?x?0?x?x，x*0?x?0?x?0?x，故0为?运算的么元；

因对?x?R，0*x综合以上，?为R上的可结合的二元运算，且R关于?运算有么元，所以?3. 假设G有k(k因为kR,??为独异点。 10分

?2)个连通分图，则因G为简单无向图，故m?1， 4分 2(n?k)(n?k?1)?2，所以0?n?k?n?2，0?n?k?1?n?1， 8分

12所以m?，这与m?1矛盾！ (n?k)(n?k?1)?12(n?1)(n?2)2(n?1)(n?2)所以图G是连通图。 10分 4. 对?x1,x2?G，若

f(x1)?f(x2)，则a?x1?a?1?a?x2?a?1，故x1?x2，从而f为单射； 3分

?y?G，a?1?y?a?G且f(a?1?y?a)?y，因此?x?G，使f(x)?y，所以f为满射； 6分

?x,y?G，f(x?y)?a?(x?y)?a?1?(a?x?a?1)?(a?y?a?1)?f(x)?f(y)，故f所以

为同态； 9分

f是?G,??的群自同构。 10分

第 12 页 共 12 页

本文来源：https://www.bwwdw.com/article/6bbr.html