试卷代号：1009座位号
**广播电视大学2011--2012学年度第一学期“开放本科”期末考试。
离散数学（本） 试题。
2023年1月。
一、单项选择题（每小题3分，本题共15分）
1．若集合a的元素个数为10，则其幂集的元素个数为（ ）
a．10b．100c．1024d．1
2．设a=，b=，r1，r2，r3是a到b的二元关系，且r1=，r2=，r3=，则（ ）是从a到b的函数．
a．r1和r2b．r2c．r3d．r1和r3
3．设a=，r是a上的整除关系，b=，则集合b的最大元、最小元、上界、下界依次为 (
ab．无、2、无、2
cd4．若完全图g中有n个结点(n≥2)，m条边，则当（ ）时，图g中存在欧拉回路．
a．n为奇数 b．n为偶数 c．m为奇数 d．m为偶数。
5．已知图g的邻接矩阵为
则g有（ ）
a．6点，8边b．6点，6边
c．5点，8边d．5点，6边。
二、填空题（每小题3分，本题共15分）
6．设集合a＝，那么集合a的幂集是。
7．若r1和r2是a上的对称关系，则r1∪r2，r1∩r2，r1-r2 ，r2-r1中对称关系有个．
8．设图g是有5个结点的连通图，结点度数总和为10，则可从g中删去条边后使之变成树．
9．设连通平面图g的结点数为5，边数为6，则面数为。
10．设个体域d＝，则谓词公式(x)(a(x)∧b（x））消去量词后的等值式为。
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“今天有联欢活动，明天有文艺晚会．”翻译成命题公式．
12．将语句“如果小王来，则小李去．” 翻译成命题公式．
四、判断说明题（每小题7分，本题共14分）
判断下列各题正误，并说明理由．
13．若偏序集的哈斯图如图一所示，
则集合a的最大元为a，极小元不存在．
14．┐p∧（p→┐q）∨p为永假式．
五．计算题（每小题12分，本题共36分）
15．设集合a=，r=，试。
1）写出r的有序对表示；
（2）画出r的关系图；
3）说明r满足自反性，不满足传递性．
16．设图g=，v=，e=，试。
1) 画出g的图形表示；
2) 写出其邻接矩阵；
3) 求出每个结点的度数；
4) 画出图g的补图的图形．
17．求pq∧r的合取范式与主析取范式．
六、证明题（本题共8分）
18．设连通无向图g有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3，试说明g中可能有的顶点数．
**广播电视大学2011--2012学年度第一学期“开放本科”期末考试。
离散数学（本） 试题解答及评分标准。
供参考)一、单项选择题（每小题3分，本题共15分）
1．c 2．c 3．b 4．a 5．d
二、填空题（每小题3分，本题共15分）
10．(a (a)∧b (b))∧a（a）∧b（b））
三、逻辑公式翻译（每小题6分，本题共12分）
11．设p：今天有联欢活动，q：明天有文艺晚会2分）
p∧q． （6分）
12．设 p：小王来，q：小李去2分）
p → q． （6分）
四、判断说明题（每小题7分，本题共14分）
13．错误． （3分）
对于集合a的任意元素x，均有r（或xra），所以a是集合a中的最大元．（5分）
但按照极小元的定义，在集合a中b,c,d均是极小元7分）
14．错误． （3分）
p∧（p→┐q）∨p是由┐p∧（p→┐q）与p组成的析取式，如果p的值为真，则┐p∧（p→┐q）∨p为真5分）
如果p的值为假，则┐p与p→┐q为真，即┐p∧（p→┐q）为真，也即┐p∧（p→┐q）∨p为真，所以┐p∧（p→┐q）∨p是永真式7分）
另种说明：p∧（p→┐q）∨p是由┐p∧（p→┐q）与p组成的析取式，只要其中一项为真，则整个公式为真5分）
可以看到，不论p的值为真或为假，┐p∧（p→┐q）与p总有一个为真，
所以┐p∧（p→┐q）∨p是永真式7分）
或用等价演算┐p∧（p→┐q）∨pt
五．计算题（每小题12分，本题共36分）
15．（1）r= （3分）
2）关系图如图二：
图二6分）3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于r，即a的每个元素构成的有序对均在r中，故r在a上是自反的． （9分）
因有<2,3>与<3,4>属于r，但<2,4>不属于r，所以r在a上不是传递的．
12分）16．（1）关系图如图三：
（3分）2）邻接矩阵。
（6分）3）deg(v1)=2
deg(v2)=2
deg(v3)=2
deg(v4)=2
deg(v5)=2 （9分）
（4）补图如图四。
（12分）17．p→（r∧q）
p∨(r∧q4分）
（┐p∨q）∧（p∨r） （合取范式6分）
p→（r∧q）
p∨(r∧q)
┐p∧(┐q∨q) )r∧q7分）
┐p∧┐q)∨(p∧q)∨(r∧q8分）
(┐p∧┐q)∧ r∨r))∨p∧q )∨r∧q9分）
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q)∨(r∧q10分）
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q)∧(r∨r))∨r∧q)
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(r∧q)
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨
(┐p∧q∧r)∨(p∨p)∧(r∧q))
┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨
┐p∧q∧r)∨ p∧r∧q) （主析取范式12分）
说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分．
六、证明题（本题共8分）
18．证明： 可利用数列可图化及握手定理解答。
顶点度数和为214=282分）
《离散数学》期中试卷
北京理工大学珠海学院。2011 2012学年第一学期 离散数学 期中试卷。适用年级专业 2010级计算机科学与技术试卷说明 闭卷，考试时间90分钟。一 选择题 每小题2分，共10分 得分 1.下列命题公式等值的是。2 设个体域为d 正整数集合 确定下列公式为真的是 a xy xy yb.xy x y...
离散数学2019二试卷A
合肥师范学院试卷。2010 2011 学年度第 2 学期 课程名称离散数学考核类型考试 a 卷。考试形式闭卷答题时间 120 分钟考试性质期末一 选择题 本大题共6小题，每小题3分，共18分 1.下列语句是命题的有。a 2是素数b c 请帮我把门关上 d 这朵花多好看呀！2 命题公式是 式。a 矛盾...
离散数学复习
离散数学 复习资料 2014年12月。一 单项选择题 每小题3分，本题共15分 1 若集合a b 则下列表述正确的是 a a ab，且a b b ba，且a b c ab，且ab d ab，且a b 2 设有向图 a b c 与 d 如图一所示，则下列结论成立的是 d 图一。a a 是强连通的b b...