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

一、证明题（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ab B. a*bmax{a,b} C. a*ba

32，2b D. a*bab(mod3)

2 下列代数系统中，哪个是群？（ ）

A. SC. S，*是一般乘法 {0,1,3,5}，*是模7加法 B. SQ（有理数集合）

，*是一般减法 D. S{1,3,4,5,9}，*是模11乘法 Z（整数集合）

3 若是的真子群，且Hn，Gm，则有（ ）。

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分） eve4 4 3 ee2 6 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）由

210100102 A00100100231100013 A01000010243100104 A001001002001

01000144可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，e1e2e5e6，e1e3e5e6）。 A4中a1431可知，v1到自身长度为3的回路有1条（e1e1e1）。 A3中a11（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a，a*bb，所以(a*b)(c*d)(ac)*(bd)。 （2）因为a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数，所以k有nkm29，而每个面至少由3条边围成，有3k2m，则k，deg(v)3，有3n2m，故n214m，且k是整334；又对任结点vV214m，且n是整数，所以n4。这样就33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}，和lcm分别为求最大公约数和最小公倍数运算，

S110,,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,为独异点。

3. 证明：若(n,m)简单无向图G满足m1(n1)(n2)，则图G是连通图。 2f:GG，使得对于xG有f(x)axa1；

4. 设G,是一个群，aG；定义一个映射

证明：

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0111010； 2分

10101022200200(4)；A02020200242202； 5分

040202(2)

A(2)12101010(3)；A00201010从v1到v4的长为2,3,4的路径的条数分别为1,2,2； 8分

00(3) G的可达矩阵为P0000T(4) 因PP00111111； 10分

111111000111，故G的强连通分图的结点集为{v1}，{v2,v3,v4}。 12分

111111第 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分

因对xR，0*x0x0xx，x*0x0x0x，故0为运算的么元；

R,为独异点。 10分

综合以上，为R上的可结合的二元运算，且R关于运算有么元，所以3. 假设G有k(k因为k2)个连通分图，则因G为简单无向图，故m12(nk)(nk1)， 4分

2，所以0nkn2，0nk1n1， 8分

121(nk)(nk1)12(n1)(n2)，这与m2(n1)(n2)矛盾！

所以m所以图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 页