华中科技大学2013——2014年《离散数学》试卷B卷

《离散数学》试题及答案一、选择题（每题5分，共25分）1. 下列关系中，哪个是等价关系？（）A. 小于等于（≤）B. 大于等于（≥）C. 整除（|）D. 模2同余（≡）答案：D2. 下列哪个图是完全图？（）A. 无向图B. 有向图C. 简单图D. n阶完全图答案：D3. 设A和B为集合，若A∪B=A，则下列哪个结论成立？（）A. A⊆BB. B⊆AC. A=BD. A∩B=∅答案：B4. 下列哪个命题是永真命题？（）A. (p→q)∧(q→p)B. (p∧q)→(p∨q)C. (p→q)∧(p→¬q)D. (p∧¬q)→(p→q)答案：B5. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的最小生成树的边数是（）。

A. 4B. 5C. 6D. 7答案：B二、填空题（每题5分，共25分）6. 设A={1,2,3,4,5}，B={3,4,5,6,7}，则A∩B=_________。

答案：{3,4,5}7. 设图G的顶点集V={a,b,c,d}，边集E={e1,e2,e3,e4,e5}，其中e1=(a,b)，e2=(a,c)，e3=(b,d)，e4=(c,d)，e5=(d,a)，则G的邻接矩阵为_________。

答案：[0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 0; 0 1 1 0 1;0 0 0 1 0]8. 设p为真命题，q为假命题，则(p∧q)∨(¬p∧¬q)的值为_________。

答案：真9. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的度数序列为（3,3,3,3,3,3），则G的边数是_________。

答案：1510. 下列命题中，与“若p，则q”互为逆否命题的是_________。

2020-2021《离散数学》期末课程考试试卷B1专业：考试日期： 所需时间：120分钟 总分：100 分 闭卷一、选择题（每小题2分，共20分） 1．下列语句中是命题的只有（ ）A ．1+8==30B ．5x+6==30C ．5y+1<30D ．x mod 20==3。

2．设命题公式G ：)(R Q P ∧→⌝,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )1,1,1.0,1,0.1,0,0.0,0,0.D C B A3．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。

A 、A ⊆Φ； B 、{6，7，8}∈A ；C 、{{4，5}}⊂A ；D 、{1，2，3}⊂A 。

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

A 、 2,3,4,5,6,7；B 、 1,2,2,3,4；C 、 2,1,1,1,2；D 、 3,3,5,6,0。

5．给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（ ）。

A 、{<V1,V2>,<V7,V8>}；B 、{<V1,V4>,<V3,V4>}；C 、{<V4,V7>,<V4,V8>}；D 、{<V1,V4>,<V2,V3>}。

6．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。

A 、 P Q →； B 、P Q ∧； C 、P Q ⌝→⌝； D 、P Q ⌝∨．7．集合A 上的关系R 为一个等价关系，当且仅当R 具有（ ）。

A 、自反性、对称性和传递性； B 、自反性、反对称性和传递性； C 、反自反性、对称性和传递性； D 、反自反性、反对称性和传递性 8．设Q 为有理数集，〈Q ，•〉（其中•为普通乘法）不能构成（ ）。

离散数学试题(B卷答案1〕一、证明题〔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))∧RT∧R(置换)R2)x(A(x)B(x))xA(x)xB(x)证明：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取X式和主合取X式〔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∨m7M3∨M4∨M5∨M6三、推理证明题〔10分〕1〕C∨D，(C∨D)E，E(A∧B)，(A∧B)(R∨S)R∨S证明：(1)(C∨D)EP(2)E(A∧B)P(3)(C∨D)(A∧B)T(1)(2)，I(4)(A∧B)(R∨S)P(5)(C∨D)(R∨S)T(3)(4)，I(6)C∨DP(7)R∨ST(5)，I2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x)P(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。

《离散数学》考试试卷（试卷库20卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库20卷）试题总分： 100 分考试时限：120 分钟、选择题（每题2分，共20分）1. 设论域为全总个体域，M(x)：x 是人，Mortal(x)：x 是要死的，则“人总是要死的”谓词公式表示为( )（A ）)()(x Mortal x M → （B ）)()(x Mortal x M ∧（C ）))()((x Mortal x M x →?（D ）))()((x Mortal x M x ∧?2. 判断下列命题哪个正确？( )（A ）若A∪B＝A∪C，则B ＝C （B ）{a,b}={b,a}（C ）P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集）（D ）若A 为非空集，则A ≠A∪A 成立3. 集合},2{N n x x A n∈==对( )运算封闭（A ）乘法（B ）减法（C ）加法（D ）y x -4. 设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于”关系，则N b a ∈?,有=∨b a ( )（A ）a（B ）b（C ）min(a ，b)（D ） max(a ，b)5. 有向图D=，则41v v 到长度为2的通路有( )条（A ）0 （B ）1 （C ）2 （D ）36. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点（A ）10 （B ）4 （C ）8 （D ）127. 下面哪一种图不一定是树？（）（A ）无回路的连通图（B ）有n 个结点n-1条边的连通图（C ）每对结点间都有通路的图（D ）连通但删去一条边则不连通的图 8. 设P ：我将去镇上,Q ：我有时间。

命题“我将去镇上,仅当我有时间”符号化为（）（A ）P →Q （B ）Q →P （C ）P Q （D ）Q P ?∨? 9. 下列代数系统中,其中*是加法运算,（）不是群。

大学期末考试试卷（A 卷）2013-2014学年第二学期 考试科目： 离散数学 考试类型：（闭卷）考试 考试时间： 120 分钟学号 姓名 年级专业(在下划线上填空. 在圆括号内填✓或✗. 笔字符✐表示用铅笔作图或在图上答题)一. 逻辑24分1. (8分)公式(p ∧q ) →(p ∨r )是重言式( ); {∨, ↔}是联结词完备集( ); ∀x ∃y (F (x ,y )∨G (x ,y ))是闭式( ); ∀xF (x ) → ∀yG (x , y )是前束范式()..2. (4分) (p →q ) ∨ (q →r )的成真赋值是______________________________________. 论域是人, F (x ): x 量小; G (x ): x 是君子, “量小非君子”符号化为______________________.3.(4分)用等值演算法证明(p → q ) ∧ (p → r ) ⇔ p → q ∧r .4. (4分)求(p ∨q ) ∨r 的主析取范式.5. (4分)前提: p→q, ⌝(q∧r), r, 结论: ⌝p. 构造推理的证明.序号公式依据(只填序号)①二. 关系24分1. (6分)设R={〈0,2〉,〈1,3〉,〈2,2〉,〈3,4〉}, 则R是函数( ), R是单射(), R是反对称的().2. (4分)设R= {〈a, a〉, 〈a, c〉, 〈d, e〉}, 则|r(R)|= ________ , dom R={________________}.3. (6分)设R= {〈a, a〉, 〈b, c〉, 〈d, e〉}, S= {〈a, b〉, 〈b, c〉, 〈c, b〉}. 画出R的关系图并求R S.3. (4分)写出集合A的划分{{1}, {2, 3}, {4}}}导出的等价关系R, 并写出A.4. (4分) 画出{2, 3, 12, 18}上的整除关系的哈斯图 , 并写出偏序集的极小元.三. 组合计数16分1. (2分) x1 + x2 + x3 = 13 (x1, x2, x3≥ 0)有________个整数解.2. (4分)有多少个十进制三位数的数字恰有一个8和一个9?3. (4分)把3只蓝球, 2只红球, 2只黄球排成一列, 黄球不相邻, 有多少种方法?4. (6分)运用二项式定理和微积分技巧证明11112111n n k n k k n ++=⎛⎫-=⎪-+⎝⎭∑.四. 图论36分1.(6分)图1的各图中, 割边最多的是________; 点色数最大的是________; 支配数最小的是________ (填相应字母).2.(8分)图2中的两个实心点之间有____条简单通路. 该图有____条简单回路, 它有____个点割集; 要使它成为哈密顿图, 至少要加有____条边.3.(4分)森林里有5棵树, 18片树叶, 其余顶点是2度或3度的. 森林里有几个3度分枝点?4.(4分)证明数列2, 3, 3, 5, 5, 6, 6不可简单图化.5. (4分)证明K 5不是平面图.图1图27. (6分)(a)画一个5阶自对偶图. (b)画一个6阶3正则的平面图.。

第 1 页/共 4 页《离散数学》考试试卷（试卷库14卷）试题总分： 100 分 考试时限：120 分钟一、选择题（每题2分，共20分）1. 下述命题公式中，是重言式的为( )（A ）)()(q p q p ∨→∧ （B ）q p ∨))()((p q q p →∨→⇔（C ）q q p ∧→⌝)(（D ）q q p →⌝∧)(2. 对任意集合A,B,C,下列结论正确的是（ ）（A ）若A ⊆B,B ∈C,则A ⊆C ； （B ）若A ∈B,B⊆C,则A ⊆C ； （C ）若A ⊆B,B ∈C,则A ∈C ； （D ）若A ∈B,B ⊆C,则A ∈C ； 3. 设} 3 ,2 ,1 {=S ，定义S S ⨯上的等价关系,,则由R 产生的S S ⨯上一个划分共有( )个分块。

（A ）4（B ）5（C ）6（D ）94. 下列偏序集( )能构成格5. 连通图G 是一棵树当且仅当G 中( )（A ）有些边是割边 （B ）每条边都是割边（C ）所有边都不是割边 （D ）图中存在一条欧拉路径6. 有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件( )（A ） 63-≤n m（B ）63-≤m n （C ）63-≥n m （D ） 63-≥m n7. 设P,Q 的真值为0,R,S 的真值为1,则下面命题公式中真值为1的是（ ）（A ）R →P （B ）Q ∧S （C ）P S （D ）Q ∨R 8. 在图G=<V,E>中,结点总度数与边数的关系是（ ）（A ）deg()2||i v E =（B ）deg()||i v E =（C ）deg()2||iv Vv E ∈=∑（D ）deg()||iv Vv E ∈=∑9. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（ ）（A ）７ （B ）８ （C ）９ （D ）１４ 10. 设集合A 上有四个元素,则A 上的不同的等价关系的个数为（ ）（A ）11 （B ）14 （C ）17（D ）15二、填空题（每题2分，共20分）1. 设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则R= 。

《离散数学》题库大全及答案为离散数学领域的经典教材,全世界几乎所有知名的院校都曾经使用本书作为教材.以我个人观点看来,这本书可以称之为离散数学百科.书中不但介绍了离散数学的理论和方法,还有丰富的历史资料和相关学习网站资源.更为令人激动的便是这本书少有的将离散数学理论与应用结合得如此的好.你可以看到离散数学理论在逻辑电路,程序设计,商业和互联网等诸多领域的应用实例.本书的英文版(第六版)当中更增添了相当多的数学和计算机科学家的传记,是计算机科学历史不可多得的参考资料.作为教材这本书配有相当数量的练习.每一章后面还有一组课题,把学生已经学到的计算和离散数学的内容结合在一起进行训练.这本书也是我个人在学习离散数学时读的唯一的英文教材,实为一本值得推荐的好书。

《离散数学》题库答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P答：（2），（3），（4），（5），（6）4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

离散数学试题及答案一、选择题（每题2分，共20分）1. 在集合论中，下列哪个选项不是集合的运算？A. 并集B. 交集C. 差集D. 乘法2. 命题逻辑中，下列哪个命题是真命题？A. (P ∧ ¬P) → QB. (P ∨ Q) ∧ ¬(P ∧ Q)C. P → (Q → P)D. (P → Q) ∧ (Q → R) → (P → R)3. 函数f: A → B，如果f是单射，那么下列哪个选项是正确的？A. A中不同的元素在B中可能有相同的像B. B中每个元素都有原像C. A中不同的元素在B中有不同的像D. B中不同的元素在A中有不同的原像4. 在图论中，下列哪个选项不是图的基本术语？A. 顶点B. 边C. 邻接D. 矩阵5. 组合数学中，从n个不同元素中取出k个元素的组合数记作C(n, k)，下列哪个选项是错误的？A. C(n, k) = C(n, n-k)B. C(n, 0) = 1C. C(n, 1) = nD. C(n, k) = C(k, n)6. 关系R是A×B上的二元关系，下列哪个选项不是关系R的性质？A. 自反性B. 对称性C. 传递性D. 可数性7. 在命题逻辑中，下列哪个命题等价于P ∨ (Q ∧ R)？A. (P ∨ Q) ∧ (P ∨ R)B. (P ∧ Q) ∨ (P ∧ R)C. (P ∨ Q) ∨ RD. (P ∨ Q) ∧ R8. 集合{1, 2, 3}的幂集含有多少个元素？A. 3B. 6C. 8D. 99. 在图论中，下列哪个选项不是树的性质？A. 无环B. 至少有两个顶点C. 任意两个顶点都由唯一路径连接D. 至少有一个环10. 在集合论中，下列哪个选项是正确的？A. 空集是任何集合的子集B. 任何集合都是其自身的超集C. 空集是任何非空集合的真子集D. 空集是其自身的并集二、简答题（每题10分，共30分）11. 简述命题逻辑中的德摩根定律，并给出一个例子。

2007-2008学年第2学期期末考试试卷（B卷）参考答案及评分标准一、填空题（4小题，每空2分，共20分）1、2n2、T3、225，220，52，55，5！4、ℵ，ℵ0二、判断题（4小题，每小题2分，共8分。

正确的划√，错误的划×。

）1、√2、×3、√4、√三、计算或简答题（5小题，共36分）1、在命题逻辑中把下列命题符号化（3小题，每题3分，共9分）（1）设P：别人有困难，Q：老王帮助别人，R：困难解决了。

符号化为(P∧⌝R)→Q或⌝R→(P→Q)（2）设P：我今天上街，Q：我有时间。

符号化为Q→P（3）设P：n是整数，Q：n是偶数，R：n能被2整除。

符号化为(P∧Q)⇄R2、在谓词逻辑中把下列命题符号化（3小题，每题3分，共9分）（1）设P(x)：x是无理数，Q(x)：x能表示成分数。

符号化为⌝∃x (P(x)∧Q(x)) 或∀x(P(x)→⌝Q(x))（2）设P(x,y)：x=y，Q(x)：x是实数，符号化为∀x(Q(x)∧⌝P(x,0)→∃y(Q(y)∧P(xy,1)))或者∀x∃y (Q(x)∧⌝P(x,0)→(Q(y)∧P(xy,1)))（3）设P(x)：x是人，Q(x)：x努力，R(x)：x成功。

符号化为∀x(P(x)∧R(x)→Q(x))3、用等价演算法求下面公式的主析取范式.主合取范式：P→(Q→R)⇔⌝P∨(⌝Q∨R) ⇔⌝P∨⌝Q∨R...............[斟酌给0～2分]公式的所有极小项有⌝P∧⌝Q∧⌝R，⌝P∧⌝Q∧R，⌝P∧Q∧⌝R，⌝P∧Q∧R，P∧⌝Q∧⌝R，P∧⌝Q∧R，P∧Q∧⌝R，故主析取范式为...........................[斟酌给0～2分] (⌝P∧⌝Q∧⌝R)∨(⌝P∧⌝Q∧R)∨(⌝P∧Q∧⌝R)∨(⌝P∧Q∧R)∨(P∧⌝Q∧⌝R)∨(P∧⌝Q∧R)∨(P∧Q∧⌝R)........................................................[斟酌给0～1分] 4、求下面公式的前束范式（5分）∀x(∃yF(x,y)→⌝∀y(G(x,y)∧∃zH(x,y,z)))⇔∀x(∃yF(x,y)→∃y(⌝G(x,y)∨∀z⌝H(x,y,z)))........................[斟酌给0～1分]⇔∀x(∃uF(x,u)→∃y(⌝G(x,y)∨∀z⌝H(x,y,z))) ........................[斟酌给0～2分]⇔∀x∀u∃y∀z (F(x,u)→(⌝G(x,y)∨⌝H(x,y,z))) .....................[斟酌给0～2分] 5、解：不满足自反性、反自反性、反对称性和传递性。

2020-2021《离散数学》期末课程考试试卷B一、选择题（在下列各题的括号处选择一最恰当的答案，共5小题，每小题3分，共15分）1．设S 表示二年级大学生的集合,R 表示计算机科学系学生的集合,T 表示选修离散数学的学生的集合,G 表示星期一晚上参加音乐会的学生的集合，则命题“听离散数学课的学生都没有参加星期一晚上的音乐会。

”可表示为 （ ）。

A 、T ⊆GB 、T ∩G=φC 、G ⊆TD 、(R ∩T)⊆G2．下列推理错误的是（ ）（1）如果今天是1号，则明天是5号。

今天是1号，所以明天是5号。

（2）如果今天是1号，则明天是5号。

明天是5号，所以今天是1号。

（3）如果今天是1号，则明天是5号。

明天不是5号，所以今天不是1号。

（4）如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。

A 、（3） B 、（1）（2）（4） C 、（2）（4） D 、（2）（3） 3．n 阶无向完全图K n 的边数m 是多少？（ ）A 、nB 、n 2C 、n(n-1)D 、2)1(-n n4．设有序对<2x+3,8>=<9,2x+y>则x 与y 分别是（ ）。

A 、3，2B 、-3，2C 、-3，-2D 、3，-25．已知n 阶无向简单图G 有m 条边，则G 的补图G 有( )条边。

A 、21)-n(n B 、n(n-1) C 、m n n --2)1( D 、m二、在命题逻辑中将下列命题符号化（共2小题，每小题3分，共6分）1．只有6能被2整除，6才能被4整除。

2．除非你努力，否则你将失败。

三、在一阶逻辑中将下列命题符号化（共2小题，每小题5分，共10分）1．没有不能表示成分数的有理数。

2．在北京卖菜的人不全是外地人。

四、设A={a ，b ，c ，d}，R={<a ，b>，<b ，a>，<b ，c>，<c ，d>}，求R 4。

武汉大学国际软件学院2007-2008学年第二学期期末考试试卷课程名称：《离散数学》（B 卷）专业：软件工程/空间信息与数字技术 层次：本科 年级：2007级/2006级 姓名： 学号： 考分：一、填空题（本大题共8小题，每空2分，共20分）1、P 、Q 均为命题，在 条件下，P Q P Q ∨=⊕。

2、()P Q Q →∧⌝⇒ 为拒取式推理规则。

3、命题“只有不怕困难，才能战胜困难。

”的符号化形式为 。

4、(,)x yF x y ⌝∃∀的前束范式为 。

5、设{}1,2,4A =，A 上的关系{},R x y x y =，R = ，关系R 具有 性质，它是 关系。

6、设A A f →:，如果f 是双射的，则=-1f f 。

7、设{}{}{}{}1,2,1=A ，则A 的幂集P ( A )= 。

8、当n 为 时，完全图n K 既是欧拉图，又是哈密图。

二、计算题（本大题共4小题，共39分）1、（本题10分）已知由三个变元P 、Q 、R 组成的合式公式为()()P Q Q R →∧→。

（1）用真值表的方法求主合取范式；（2）用等值演算的方法求主析取范式；（3）说明你所得结果的关系。

2、（本题9分）设{}{}{}1,2,,12,1,3,5,7,9,11,2,3,5,7,11,U A B === {}{}2,3,6,12,2,4,8,C D ==求：（1） ()C A B - ；（2）B D ⊕；（3）C D ⨯。

3、（本题10分）列出集合{}4,3,2=A 上的恒等关系I A ，全域关系E A ，小于或等于关系L A ，整除关系D A 。

4、（本题10分）设{}{}1,2,,,A B a b c ==，求B A 。

三、证明题（本大题共2小题，每小题10分，共20分）1、证明下列推理。

前提：()())(,)()(,)()(x R x x R x G x x G x F x ∀⌝∨⌝∀∨∀ 结论：)(x F x ∀2、Show that if A and B are sets, then ()()()A B C A B A C = 。

离散数学试题（A卷答案）一、（10分）求(P↓Q)→(P∧⌝(Q∨⌝R))的主析取范式解：(P↓Q)→(P∧⌝(Q∨⌝R))⇔⌝(⌝( P∨Q))∨(P∧⌝Q∧R))⇔(P∨Q)∨(P∧⌝Q∧R))⇔(P∨Q∨P)∧(P∨Q∨⌝Q)∧(P∨Q∨R)⇔(P∨Q)∧(P∨Q∨R)⇔(P∨Q∨(R∧⌝R))∧(P∨Q∨R)⇔(P∨Q∨R)∧(P∨Q∨⌝R)∧(P∨Q∨R)⇔M∧1M⇔m∨3m∨4m∨5m∨6m∨7m2二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。

乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。

试判断王教授是哪里人？解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。

则根据题意应有：甲：⌝P∧Q乙：⌝Q∧P丙：⌝Q∧⌝R王教授只可能是其中一个城市的人或者3个城市都不是。

所以，丙至少说对了一半。

因此，可得甲或乙必有一人全错了。

又因为，若甲全错了，则有⌝Q ∧P，因此，乙全对。

同理，乙全错则甲全对。

所以丙必是一对一错。

故王教授的话符号化为：((⌝P ∧Q )∧((Q ∧⌝R )∨(⌝Q ∧R )))∨((⌝Q ∧P )∧(⌝Q ∧R ))⇔(⌝P ∧Q ∧Q ∧⌝R )∨(⌝P ∧Q ∧⌝Q ∧R )∨(⌝Q ∧P ∧⌝Q ∧R )⇔(⌝P ∧Q ∧⌝R )∨(P ∧⌝Q ∧R )⇔⌝P ∧Q ∧⌝R⇔T因此，王教授是上海人。

三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。

证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。

若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )⊆'R 。

华科离散数学试题与答案试卷离散数学试题与答案试卷一一、填空 20% (每小题2分)，+A,{x|(x,N)且(x,5)},B,{x|x,E且x,7}1(设 (N:自然数集，E 正偶A,B,数) 则。

2(A，B，C表示三个集合，文图中阴影部分的集合表达式为。

A B C 3(设P，Q 的真值为0，R，S的真值为1，则，(P,(Q,(R,，P))),(R,，S)的真值= 。

(P,R),(S,R),，P4(公式的主合取范式为。

，xP(x),,xP(x)5(若解释I的论域D仅包含一个元素，则在I下真值为。

6(设A={1，2，3，4}，A上关系图为2则 R = 。

7(设A={a，b，c，d}，其上偏序关系R的哈斯图为则 R= 。

8(图的补图为。

9(设A={a，b，c，d} ，A上二元运算如下:* a b c da abc db bcd ac cd a bd d a b c 那么代数系统<A，*>的幺元是，有逆元的元素为，它们的逆元分别为。

10(下图所示的偏序集中，是格的为。

二、选择 20%(每小题 2分)1、下列是真命题的有( ){a},{{a}}{{,}},{,,{,}}A( ; B(;,,{{,},,}{,},{{,}}C( ; D( 。

2、下列集合中相等的有( ),,,, A({4，3};B({，3，4};C({4，，3，3};D( {3，4}。

3、设A={1，2，3}，则A上的二元关系有( )个。

2，23，33 2 32 A( 2;B( 3;C( ; D( 。

4、设R，S是集合A上的关系，则下列说法正确的是( )R,S A(若R，S 是自反的，则是自反的;R,S B(若R，S 是反自反的，则是反自反的;R,S C(若R，S 是对称的，则是对称的;R,S D(若R，S 是传递的，则是传递的。

5、设A={1，2，3，4}，P(A)(A的幂集)上规定二元系如下R,{,s,t,|s,t,p(A),(|s|,|t|}则P(A)/ R=( )A(A ;B(P(A) ;C({{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}};,D({{}，{2}，{2，3}，{{2，3，4}}，{A}},,6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为( )7、下列函数是双射的为( ),,，A(f : IE , f (x) = 2x ; B(f : NNN, f (n) = <n , n+1> ;,,C(f : RI , f (x) = [x] ; D(f :IN, f (x) = | x | 。

《离散数学》试题及答案一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。

1. 命题公式Q Q P →∨)(为 ( )(A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式2．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。

(A)． P Q →； (B)．P Q ∧； (C)．P Q ⌝→⌝； (D)．P Q ⌝∨．3.设集合A ={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( )(A) 1∈A (B) {1,2, 3}⊆A(C) {{4,5}}⊂A (D) ∅∈A4. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ⋂C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >} (C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>}5. 设G 如右图：那么G 不是( ). (A)哈密顿图； (B)完全图；(C)欧拉图； (D) 平面图.二、填空题：本大题共5小题，每小题4分，共206. 设集合A ={∅,{a }}，则A 的幂集P (A )=7. 设集合A ={1,2,3,4 }, B ={6,8,12}, A 到B 的关系R ＝},,2,{B y A x x y y x ∈∈=><,那么R －1＝8. 在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9. 写出一个不含“→”的逻辑联结词的完备集 .10.设X ＝{a ,b ,c }，R 是X 上的二元关系，其关系矩阵为 M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001001101，那么R 的关系图为三、证明题（共30分）11. （10分）已知A 、B 、C 是三个集合，证明A ∩(B ∪C)=(A ∩B)∪(A ∩C)12. （10分）构造证明：(P →(Q →S))∧(⌝R ∨P)∧Q ⇒R →S13.（10分）证明（0,1）与[0,1)，[0,1)与[0,1]等势。

B 卷1． Show that ((p ∨q)∧⌝p) → q are tautologies. (10 scores)2. Suppose that f(x),g(x) and h(x) are functions such that f(x ) is Ω(g(x)) and g(x) is Ω (h(x)).Show that f(x) is Ω (h(x)).(10 scores)3. Let ⎥⎦⎤⎢⎣⎡=0312A and ⎥⎦⎤⎢⎣⎡=3221B .Find B t A t . (10 scores) 4. Find a compatible total ordering for the poset ({2,4,6,9,12,18,27,36,48,60,72},|).(10 scores) 5 . Let R be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) ∈ R if and only if a+d = b + c. Show that R is an equivalence relation. (15 scores)6. Use adjacency matrix to find the numbers paths between U 1 and U 5 in the graph in Figure1 of length 3, determine whether it is planar and if it is planar ,into how many regions does this graph split the plane? (10 scores)7. Suppose there are 7 finals to be scheduled so that no student has two exams at the same time. Suppose the courses are numbered 1 through 7. Suppose that the following pairs of courses have common students : 1 and 2, 1 and 3, 1 and 4, 1 and 5, 2 and 3, 3 and 4 ,4 and 5.Please schedule the final exams for this. (10 scores)8 . Use Prim ’s algorithm to find a minimum spannig tree in the followinggraph,then use Kruskal ‘s algorithm to find a minimum spannig tree in the same graph. (10 scores)9. Suppose T is an ordered rooted tree.And the inorder listing of T is h,d,b,i,e,j,a,f,c,k,gThe preorder listing of T is a,b,d,h,e,I,j,c,f,g,kPlease draw T and find the postorder listing of T. (15 scores)【本文档内容可以自由复制内容或自由编辑修改内容期待你的好评和关注，我们将会做得更好】。

.1 / 11大学2013—2014学年度第二学期期末考试《离散数学》试卷A第一局部选择题〔共20分〕一、单项选择题〔本大题共10小题，每题只有一个正确答案，答对一题得2分共20分〕 1、对任意集合A 、B 、和C ，以下论断中正确的选项是： 【】A. 假设A ∈B ，B ⊆C ，那么A ∈CB. 假设A ∈B ，B ⊆C ，那么A ⊆CC. 假设A ⊆B ，B ∈C ，那么A ∈CD. 假设A ⊆B ，B ∈C ，那么A ⊆C2、设A={a,{a}},以下式子中正确的有： 【】A. {a}∈ρ(A)B. a ∈ρ(A)C. {a}Íρ(A)D. 以上都不是3、P ：我将去镇上。

Q ：我有时间。

命题“我将去镇上，当且仅当我有时间〞符号化为：【】A. P →QB. Q →PC. P ↔QD. Q ∨¬P4、命题公式：〔P ∧〔P →Q 〕〕→Q 是 【】A ．矛盾式B. 可满足式 C. 重言式 D. 不能确定5、谓词公式)())()((x Q y yR x P x →∃∨∀中，量词x ∀的辖域是： 【】A. ))()((y yR x P x ∃∨∀B. )(x PC. )(),(x Q x PD.)()(y yR x P ∃∨6、在如下各图中，哪一个是欧拉图？ 【】7、设|V|>1，G= < V , E >是强连通图，当且仅当： 【】A ．G 中至少有一条通路B ．G 中至少有一条回路C ．G 中有通过每个结点至少一次的通路D ．G 中有通过每个结点至少一次的回路8、设}}2,1{},1{,{Φ=S ，那么 ρ(S) 有多少个元素？ 【】A ．3；B ．6；C ．7；D ．8 ；9、集合A={1，2，3，4，5，6，7，8，9，10}上的关系R={<x, y> | x + y = 10}，那么R 的性质为：【】A ．自反的；B ．对称的；C ．传递的、对称的；D ．反自反的、传递的10、集合A 上的等价关系R ，其等价类集合{[ a]R | a ∈ A}称为： 【】A ．A 与R 的并集，记作A ∪RB ．A 与R 的交集，记作A ∩RC ．A 与R 的商集，记作A/RD ．A 与R 的差集，记作A - R二、填空题(本大题共10小题，每题2分,共20分)11、集合A={φ,{φ}}，那么A 的幂集为。