安徽大学期末试卷离散数学(下)A卷试卷.doc

安徽大学20 xx —20 xx 学年第 2 学期《 离散数学（下） 》考试试卷（A 卷）（闭卷 时间120分钟）一、单项选择题（每小题2分，共20分） 1．设R 为实数集合，则下列集合关于加法运算不是,R <+>的子代数的是（ ） A.偶数集合； B.奇数集合； C.自然数集合； D.整数集合。

2．下列关于群的说法正确的是（ ）A.质数阶的群必为循环群；B.有限群必为循环群；C.循环群必为质数阶群；D.循环群必为有限群。

3．设R 为实数集合，则20(),0a M R a b R b ⎧⎫⎛⎫=∈⎨⎬⎪⎝⎭⎩⎭关于矩阵的加法和乘法构成（ ） A.有幺元的交换环； B.无幺元的非交换环； C.无幺元的交换环； D.有幺元的非交换环。

4．设I 为整数集合，则下列关系是代数,I <+>上的同余关系的是（ ）A.||0x y x y ⇔-≤；B.(00)(00)x y x y x y ⇔<∧<∨≥∧≥；C.xy x y ⇔≤； D.(0)(00)xy x y x y ⇔==∨≠∧≠。

5．下列集合关于整除关系构成格的是（ ）A.{1,2,3,4,6}；B.{1,2,3,6}；C.{2,3,6}；D.{1,2,3}。

6．在布尔代数,,,,0,1B '<*⊕>中任取两元素,a b ，下列命题与a b ≤不一定等价的是（） A.a b a *=； B.a b b ⊕=； C.0a b '*=； D.1a b '⊕=。

7．在布尔代数>'⊕*<1,0,,,,B 上定义的n 元布尔表达式所对应的不同主析取范式总个数为（ ） A.n2； B.nBB； C.nB2； D.nB 。

8．设无向图,G V E =<>中{1,2,3,4,5}V =，{(1,2),(2,3),(3,4),(4,5),(5,1),(2,5)}E =， 则{2,4}V '=不是图G 的（ ）A.点割；B.支配集；C.点覆盖；D.独立集。

一．判断题（共10小题，每题1分，共10分）在各题末尾的括号内画 表示正确，画 表示错误：1．设p、q为任意命题公式，则(p∧q)∨p ⇔ p ( )2．∀x(F(y)→G(x)) ⇔ F(y)→∃xG(x)。

( )3．初级回路一定是简单回路。

( )4．自然映射是双射。

( )5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。

( )6．群的运算是可交换的。

( )7．自然数集关于数的加法和乘法<N，+， >构成环。

( )8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。

( )9．设A={a,b,c},则A上的关系R={<a,b>,<a,c>}是传递的。

( )10．设A、B、C为任意集合，则A⨯(B⨯C)=(A⨯B)⨯C。

( )二、填空题（共10题，每题3分，共30分）11．设p：天气热。

q：他去游泳。

则命题“只有天气热，他才去游泳”可符号化为。

12．设M(x)：x是人。

S(x)：x到过月球。

则命题“有人到过月球”可符号化为。

13．p↔q的主合取范式是。

14．完全二部图K r,s（r < s）的边连通度等于。

15．设A={a,b}，,则A上共有个不同的偏序关系。

16．模6加群<Z6，⊕>中，4是阶元。

17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。

.18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度列为。

19．n阶无向简单连通图G的生成树有条边。

20．7阶圈的点色数是。

三、运算题（共5小题，每小题8分，共40分）21．求∃xF(x)→∃yG(x,y)的前束范式。

22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。

2020-2021《离散数学》期末课程考试试卷A一、填空题（每空3分，共15分）1．命题公式)(r q p p ∨∨→的类型是 。

2．设p ：我将去镇上。

q ：我有时间。

则命题“我将去镇上，仅当我有时间。

”的符号化形式为 。

3．化简下面集合表达式：)())((C B A C A B -= 。

4．已知一有向图的D 的度序列为（2,3,2,3），出度序列为（1,2,1,1），则D 的入度序列为 。

5．5个顶点的非同构的无向树共有 棵。

二、选择题（单项选择题，每题3分，共30分）1．设命题公式)(p q p ⌝→∧，记作A ，则使A 的真值指派为1的p ，q 的取值是（ ）。

A 、00B 、 01C 、10D 、112．设p ：你努力。

q ：你将失败。

则命题“除非你努力，否则你将失败。

”符号化为（ ）。

A 、p →q B 、q →p C 、┐p →q D 、┐q →p 3．下列公式中不与)(q p ↔⌝等值的是（ ）。

A 、)()(q p q p ∨⌝∧⌝∨B 、)()(q p q p ∧⌝∨⌝∧C 、q p ↔⌝D 、q p ⌝↔4．下面公式正确的是（ ）。

A 、)()())()((x xB x xA x B x A x ∀∨∀⇔∨∀ B 、)()())()((x xB x xA x B x A x ∃∨∃⇔∨∃C 、)())((x xB A x B A x ∃→⇔→∀D 、)()(x A x x xA ⌝∃⇔⌝∃5．下列命题错误的是（ ）。

A 、}},,{,,,{},{c b a c b a b a ⊆ B 、}},{,,,{},{b a c b a b a ∈ C 、}}},{{,,{},{b a b a b a ⊆D 、}}},{{,,{},{b a b a b a ∈6．设R={<x,y>|x,y ∈R ，x-y+2>0且x-y-2<0}，则R 具有的性质是（ ）。

--北京工商大学离散数学试卷(A)答案及评分标准题号 一 二三 四 五 六 七总分得分一、（30分）设A ={1,2,3,4}，给定A 上二元关系R 如下：R ={<1,1>, <1,2>, <2,3>, <3,3>, <4,4>}请回答以下各问题：1.写出R 的关系矩阵. （3分）2.画出R 的关系图. （3分）3.求包含R 的最小的等价关系，并写出由其确定的划分. （6分）4.分别用关系矩阵表示出R 的自反闭包r (R )、对称闭包s (R ). （6分）5.求传递闭包t (R ).（写出计算步骤）（6分）6.求R 2的关系矩阵. （3分）7.集合A 上最多可以确定多少个不同的二元关系？说明理由。

（3分）[解] (1)⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000010001000011R M 。

……（3分）（2） ……（3分）(3)法一：直接由等价关系与划分之间的一一对应可知，包含R 的最小等价关系为: {<1, 2>, <1, 3>, <2, 1>,<2, 3>, <3, 1> <3, 2>}∪I A , ……（3分） 对应的划分为{{1, 2, 3},{4}}. ……（6分） 法二：包含R 的最小的等价关系就是tsr (R ), 计算过程如下：⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=100001000110001110000100001000011000010001000011)(E M M R R r,100001100111001110000110001100011000010001100011][)()()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+=T R r R r R sr M M M ,3,10001110111011110000110011100111000011001110011)]([)()()]([2≥=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛⨯⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⨯=k M M M M k R sr R sr R sr R sr 从而,10000111011101111000011101110111100001110111011110000111011101111000011001110011432)]([)]([)]([)()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=R sr R sr R sr R sr R tsr M M M M M即}2,3,1,3,3,2,1,2,3,1,2,1{)(><><><><><><⋃=A I R tsr =包含R 的最小的等价关系， ……（3分） 故其对应的划分为{{1, 2, 3},{4}}. ……（6分） 法三：由于4=A ，包含R 的最小的等价关系就是4131211)()()()()()(----⋃⋃⋃⋃⋃⋃⋃⋃==R R R R R R R R I R rts R tsr A ,计算过程如下：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃100001100101001110000110000100011000010001000011][1TR R R R M M M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃10000111011101111000011001010011)][(22)(21T R R R R M M M412131)()(33)(10000111011101111000011001010011)][(---⋃⋃⋃==⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=R R R R T R R R R M M M M M 考试纪律承诺本人自愿遵守学校考试纪律，保证以诚信认真的态度作答试卷。

安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A 卷）参考答案一、单项选择1 在自然数集N 上，下列哪种运算是可结合的？（ ）A. b a b a -=*B. },max{*b a b a =C. b ab a 2*+= D. )3(mod *b a b a ⋅=2 下列代数系统<S ，*>中，哪个是群？（ ）A. }5,3,1,0{=S ，*是模7加法B. Q S =（有理数集合），*是一般乘法 C. Z S=（整数集合），*是一般减法 D. }9,5,4,3,1{=S ，*是模11乘法 3 若<H ，*>是<G ，*>的真子群，且n H =，m G =，则有（ ）。

A. n 整除m B. m 整除nC. n 整除m 且 m 整除nD. n 不整除m 且 m 不整除n 4 下面哪个集合关于指定的运算构成环？（ ）A. },|2{3Z b a b a∈+，关于数的加法和乘法B.n {阶实数矩阵}，关于矩阵的加法和乘法C. },|2{Z b a b a∈+，关于数的加法和乘法D. ⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧∈⎪⎪⎭⎫ ⎝⎛Z b a a b b a ,，关于矩阵的加法和乘法 5 在代数系统中，整环和域的关系为（ ）。

A. 域一定是整环B.域不一定是整环C. 整环一定是域D. 域一定不是整环6 N 是自然数集，≤是小于等于关系，则),(≤N 是（ ）。

A. 有界格B.有补格C. 分配格D. 有补分配格 7 图1-1给出的哈斯图表示的格中哪个元素无补元？（ ）A. aB. cC. eD.f图1-18 给定下列序列，可构成无向简单图的结点度数序列的是（ ）。

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

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

安徽大学2021—2022 学年第 1 学期《离散数学》考试试卷（A卷）（时间120分钟）院/系专业姓名学号一、单项选择题（每小题2分，共20分）1. 设天没下雪，我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ D）A.；B. ；C.；D. 。

2.下列命题是重言式的是（ C ）A.；B. ；C. ；D. 。

3. 设解释R如下：论域D为实数集，a=0, f(x,y)=x-y, A(x,y):x<y.下列公式在R下为真的是( )A.(x)(y)(z)(A(x,y)→A(f(x,z),f(y,z)))B.(x)A(f(a,x),a)C.(x)(y)（A(f(x,y),x))D.(x)(y)(A(x,y)→A(f(x,a),a))4. 对任意集合，下列结论正确的是（ B ）A. ；B. ；C. ；D. 。

5. 9．关于到的函数，下列结论不正确的是（）A、；B、；C、；D、。

6. 设为整数集合，则上的二元关系具有（ B ）A.自反性和对称性；B.反自反性和对称性；C.反自反性和传递性；D.反对称性和传递性。

7. 设为非空集合上的关系的逆关系，则下列结论不成立的是（ D ）A.若为偏序，则为偏序；B.若为拟序，则为拟序；C.若为线序，则为线序；D.若为良序，则为良序。

8. 设和是非空集合的划分，则下列结论正确的是（ B ）A. 细分；B. 细分；C. 非空集合的划分细分；D. 细分非空集合的划分。

9. 设X={a,b,c},I x是X上恒等关系，要使I x∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( D )A. ｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C. {〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10. 设和分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（ D ）A.；B.；C.；D.（）。

分，共10分。

对的打√，错的打×）1.（）命题联结词{⌝，∧，∨}是最小联结词组。

2005下离散数学（A）参考答案注：解答思路可能存在差异，描述方式也常常不唯一，下面仅仅给出典型的求解过程。

1.设E 为a,b,c,d 这4个字母的全排列集合，A 为出现ab 的排列集合，B 为出现cd 的排列集合。

由容斥原理，不允许出现ab 和cd 的排列个数为：| E |-|A ∪B|=4!-(3!+3!-2!)=102.（1）R 的关系矩阵是：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100101100001001（2）R 不是自反的，不是反自反的，不是对称的，不是反对称的，不是传递的；（3）r(R)={(0,0),(0,3),(1,1),(2,0),(2,1),(2,2),(2,3),(3,2),(3,3)}；s(R)={(0,0),(0,2),(0,3),(1,2),(2,0),(2,1),(2,3),(3,0),(3,2)}；t(R)={(0,0),(0,1),(0,2),(0,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3)}。

3. (1)对任意x ∈R,有3x x −=0，即(x,x)∈S,所以S 是自反的； (2)对任意x,y∈R,设(x,y)∈S,则3y x −为整数，那么3x y −也为整数，即(y,x)∈S,所以S 是对称的；(3)对任意x,y,z ∈R,设(x,y)∈S 且(y,z)∈S ，则3y x −，3z y −为整数，那么3y x −+3z y −=3z x −也为整数，即(x,z)∈S,所以S 是可传递的； 由(1)(2)(3)知S 是等价关系。

4.（1）可满足式 （2）可满足式 （3）可满足式（4）矛盾式 （5）重言式 （6）重言式5.（1）主析取范式：(P ∧¬Q)∨(P ∧Q) 主合取范式：(P ∨Q)∧(P ∨¬Q)（2）前束合取范式：∀x ∃z ∃u((¬P(x)∨¬Q(y)∨R(z))∧(¬P(x)∨¬Q(y)∨¬S(u)))6.令Q(x)：x 是有理数 R(x)：x 是实数 I(x)：x 是整数 则整个命题符号化为：∀x(Q(x)→R(x)), ∃x(Q(x)∧I(x)) |- ∃x(R(x)∧I(x))证明：(1) ∃x(Q(x)∧I(x)) P(2) Q(a)∧I(a) ES(1)(3) Q(a) I(2)(4) I(a) I(2)(5) ∀x(Q(x)→R(x)) P(6) Q(a)→R(a) US(5)(7) R(a) I(3)(6)(8) R(a)∧I(a) I(4)(7)(9) ∃x(R(x)∧I(x)) EG(8)7. 要证明Vρh 与V’同构，需要证明如下几点：1）同型：Vρh 与V’同型？2）双射：定义映射f，并证明其为双射定义映射f：因为h是一个从S到S’的满射，S/ρh的可允许划分，所以对于每一个[x]ρh ∈S/ρh必存在某个x’∈S’，使得x’=h(x)，于是可以如下定义函数：f: S/ρh →S’ ，使得f([x]ρh)=h(x)。

《离散数学》期末试卷A学号 姓名 成绩一、 判断题（每题1分，共10分）1．“如果321=+，那么雪是黑的。

”这是一个真命题。

（ ）2．下面的推理过程是正确的： （ ）（1）P x Q x P x ))()((∨∀（2）)1()()(US b Q a P ∨3． 图G 没有环当且仅当G 的邻接矩阵主对角元都是0。

（ ）4。

若有关系f 和g ，则f g g f = （ ）5．{}c b a A ,,=到{}x B =的关系共有8个。

（ ）6．右图是强连通的。

（ ）7． 若关系R 是对称的，则它一定不是反对称的 （ ）8． 集合A 上的不等关系≠可确定A 的一个划分。

（ ）9． 序列（1，2，3，4，5）不能构成某无向图的度序列。

（ ）10. 3度正则图必有偶数个结点。

（ ）二、 填空题（共24分）1．集合}}{,{ΦΦ=A ，求A 的幂集)(A P = 。

2．设公式))()((x Q x P x →∃，其中3:)(,2:)(≤>x x Q x x P ，个体域为}6,3,2{-，则该式的真值为：3．在任何图E V G ,=中，顶点度数之和等于 ，度数为奇数的顶点必有 个。

4．设 }2,1{},1,0{==B A ，则=⨯B A5．图G 如下图，求G 的补图G ：G ：G ：6．设{}3,2,1=A 上的关系{}3,3,3,1,2,1,1,1=R ，则关系R 具有 ， 性。

三、将下列命题符号化（第4、5题谓词符号化）（每题3分，共15分）1. 如果他学习努力且学习方法得当，那么他的学习成绩一定很好。

2. 李强不是不聪明，而是不用功。

3. 如果你在，他是否演唱就取决于你是否伴奏了。

4. 有些人喜欢花。

5. 鸟都会飞翔。

四、 求公式)()(P Q Q P ∨⌝→→⌝的主析取范式，主合取范式（15分）五、 证明下面论证的有效性（10分）：S P S R R Q Q P →⇒→∨⌝∨⌝,,六、集 合{}3,2,1=A 上给定关系{}2,1,1,1=R ，求它的关系矩阵和自反闭包，对称闭包，传递闭包。

安徽⼤学期末试卷离散数学期末试卷及答案.doc⼀．判断题（共10⼩题，每题1分，共10分）在各题末尾的括号内画表⽰正确，画表⽰错误：1．设p、q为任意命题公式，则(p∧q)∨p ? p ( )2．?x(F(y)→G(x)) ? F(y)→?xG(x)。

( )3．初级回路⼀定是简单回路。

( )4．⾃然映射是双射。

( )5．对于给定的集合及其上的⼆元运算，可逆元素的逆元是唯⼀的。

( )6．群的运算是可交换的。

( )7．⾃然数集关于数的加法和乘法构成环。

( )8．若⽆向连通图G中有桥，则G的点连通度和边连通度皆为1。

( )9．设A={a,b,c},则A上的关系R={,}是传递的。

( )10．设A、B、C为任意集合，则A?(B?C)=(A?B)?C。

( )⼆、填空题（共10题，每题3分，共30分）11．设p：天⽓热。

q：他去游泳。

则命题“只有天⽓热，他才去游泳”可符号化为。

12．设M(x)：x是⼈。

S(x)：x到过⽉球。

则命题“有⼈到过⽉球”可符号化为。

13．p?q的主合取范式是。

14．完全⼆部图K r,s（r < s）的边连通度等于。

15．设A={a,b}，,则A上共有个不同的偏序关系。

16．模6加群中，4是阶元。

17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。

.18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的⼊度列为。

19．n阶⽆向简单连通图G的⽣成树有条边。

20．7阶圈的点⾊数是。

三、运算题（共5⼩题，每⼩题8分，共40分）21．求?xF(x)→?yG(x,y)的前束范式。

22．已知⽆向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。

23．设A={a,b,c,d,e,f}，R=I A?{,}，则R是A上的等价关系。