2016 - 2017学年度第二学期试卷 a(闭卷)
课程名称离散数学二级学院计算机学院专业计算机科学与技术年级、班级学号姓名。
一、填空题：（每空2分，共20分）
1．若n阶无向图g（v,e）为平凡图，则|v
为重言式a的主合取范式为 ，a为矛盾式 a的主析取范式为 。
3.设ａ=,r={}求r(rs(rt(r
4.既无平行边也无环的图称为含平行边的图称为。
5.若ab为 ，则称a与b是等值的，记作 ab，并称ab为。
二、选择题：（每题2分，共10分）
1．若6阶无向图g（v,e）为完全图，则包含多少条环（ ）
a) 5 (b)0 (c)6 (d)1
是a上关系，则r是自反的，当且仅当（ ）
a）r(r)=rb） s(r)=r
c）t(r)=rd）r=r
3.对公式的说法正确的是（ ）
a）x是约束出现，y是自由出现，z是约束出现自由出现。
b）x是约束出现，y既是约束出现又是自由出现，z是自由出现。
c）x是约束出现，y既是约束出现又是自由出现，z是约束出现。
d）x是约束出现，y是约束出现，z是自由出现。
4.下列各序列不可以构成无向简单图的度数序列的是（ ）
a） （b） （c） （d
5.一棵根树可看成一棵家族树，顶点a可达顶点b,则称b是a的（ ）
a）后代b）兄弟 （c）祖先 （d）儿子。
三、计算题：（5小题，共50分）
1. (本题10分) 构造(p∧q)∧ p的真值表。
2. (本题10分) 求(pq)r的析取范式与合取范式。
3.（本题10分）某中学有3个课外小组：物理、化学、生物今有张、王、李、赵、陈5名同学。
若已知张、王为物理组，张、李、赵为化学组，李、赵、陈为生物组。使二部图说明能选出3名不兼任的组长。
4.（本题10分）画出4阶的所有非同构的生成子图。
5.（本题10分）有向图d如下图所示，用邻接矩阵法求d中长度为3的路径的数目和长度为3的回路数。
四、证明题：（2小题，共20分）
1.（本题10分）若图g是不连通的，则g的补图是连通的。
2.（本题10分）构造推理证明：乌鸦都不是白色的。 北京鸭是白色的。 因此，北京鸭不是乌鸦。
2016--2017学年度第二学期离散数学试卷答案(a卷)
一、填空题：（每空2分，共20分），0 3、, t(r)= 4、简单图、多重图5.重言式，等值式。
二、选择题：（每题2分，共10分）
1、b 2、 a 3、d 4、a 5、a
三、计算题：（5小题，共50分）
1 (本题10分)
错一格扣一分。
2 (本题10分)
pq)r ((p∨q)∧(p∨q))∨r
(p∧q)∨(p∧q)∨r --析取范式…..5分。
pq)r((p∧q)∨(p∧q))∨r
((p∨q)∧(p∨q))∨r
(p∨q∨r)∧(p∨q∨r) -合取范式…..5分。
3(本题10分)
物理化学生物。
张王李赵陈。
错一条扣一分，共8分。
分别选择张，李，赵。2分。
4、(本题10分)
少一个扣一分。
5、(本题10分)
d3’d==…
d3==…3分。
则长度为3的路径数为7，长度为3的回路数为3。……2’
四、证明题：（2小题，共20分）
1(本题10分)证明：设g=（v，e）不连通，则设其连通分支为g1，g2，…gs，其相应的节点集为v1，v2，…vs，任取中的两个节点u，v∈v，..2分。
1）、若u，v分属于g中不同的连通分支，则(u,v)∈ 因此u，v在中连通。..2分。
2）、若u，v分属于g中同一个连通分支，则从另一连通分支中任取一结点w，则(u,w)∈g补，(v,w)∈ g补，..2分。
于是在中存在一条道路uwv，使得u，v连通。..2分。
综上所述可知，对于中任意2个结点，u，v总有路相连，故是连通的。..2分。
2(本题10分)
法1 p:乌鸦；
q北京鸦；r：白色。
证明qp…….3分。
证明：qr 前提引入。
q 前提引入。
r 假言推理…….3分。
pr前提引入。
p拒取式…….3分。
所以qp成立 ……1分。
法2：令 f(x): x是乌鸦， g(x): x是北京鸭，
h(x): x是白色的。
前提：x(f(x)h(x))，x(g(x)h(x))
结论：x(g(x)f(x))
证明：① x(f(x)h(x)) 前提引入。
② f(y)h(yui…….3分。
③ x(g(x)h(x前提引入。
④ g(y)h(yui
⑤ h(y)g(y置换…….3分。
⑥ f(y)g(y假言三段论。
⑦ g(y)f(y置换…….3分。
⑧ x(g(x)f(xug…….1分。
离散数学试卷A
2011 2012 课程名称 离散数学考试时间120分钟 一 填空题 每空2分，共16分 1 已知个体域是 p 1,1 1 p 1,2 1,p 2,1 0,p 2,2 0,则公式xy p x，y 的真值为。2 公式 x p x y q x,y 的前束范式为。3 设二元关系f g a 则fdom f。...
离散数学试卷
一 判断题。1.设g为无向图，若g中恰好n个结点，n 1条边，则g必为一棵树。2.若a b，则p a p b 3.设g为无向图，若g无回路，则g必为一棵树。4.设a，b是集合，若a b，则p a p b 5.无向图g是欧拉图当且仅当g连通且具有零个或两个奇数度结点。6.设a,b是任意集合，则 a b...
离散数学试卷 A
2014 2015学年第二学期。每题10分，共100分，答案一律写在答题纸上 1.化为主析取范式与主合取范式。2.证明 3.甲 乙 丙 丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的 1 甲和乙只有一人参加 2 丙参加，丁必参加 3 乙或丁至多参加一人 4 丁不参加，...