下载文档原格式
《离散数学》考试试卷（试卷库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. 下列代数系统中,其中*是加法运算,（）不是群。
2012年各高校离散数学试题答案一、填空（每题5分共20分）1、数集A={1,2,3}与运算“min ”构成的代数系统的单位元是 3 。
2、一个连通的(n,m)平面图的面数为k ，则m ，n ，k 满足的Euler 公式为 n-m+k=2 。
3、设T 是一棵完全二元树，有n 个结点，n 0片树叶，则n 和n 0满足如下的公式 2n 0-1。
4、减法“-” 不是 正整数集N 上的二元运算。
二、单项选择（每题5分共10分） 1.⊆ρI ×I, i 1ρi 2⇔ ︱i 1-i 2︱≦10,则ρ是 b 。
(a) 反自反的；(b)对称的；(c)反对称的；(d)传递的。
2. 下列各图是Euler 图的是 d。
（a ） （b ） （c ） （d ） 三、设A={1},B={2,3},求A ×2B(8分)。
解：因}}3,2{},3{},2{,{2φ=B ， 4分 则})}3,2{,1(}),3{,1(}),2{,1(),,1{(2φ=⨯B A 。
8分 四、证明：集合论中的德·摩根律：(A ∩B)/=A /∪B /(8分)。
证 )B A (a '⋂∈∀,则B A a ⋂∉,所以B a A a ∉∉或,即B a A a '∉'∈或, 2分 因此B A a '⋃'∈, 故B A B A '⋃'⊆'⋂)(. 5分 同理B A a '⋃'∈∀,则B a A a '∉'∈或,所以B a A a ∉∉或,因此B A ⋂∉a , 7分 即)B A (a '⋂∈∀, 故)('⋂⊆'⋃'B A B A . 8分 五、设X={1,2,3,4}上的关系R={(1,1)，(2,3)，(3,2)}, 求R 的传递闭包t(R)。
(10分)。
解法一==R R R 2)3,3(),2,2(),1,1{(， 3分==R R R 23{(1,1)，(2,3)，(3,2)}， 5分 R R R 34==)3,3(),2,2(),1,1{(， 7分则=⋃⋃⋃=432)(R R R R R t )3,3(),2,3(),3,2(),2,2(),1,1{( 10分 解法二⎪⎪⎪⎪⎪⎭⎫⎝⎛=0000001001000001R M ，(3分)⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=∧=00000100001000012R R R M M M ， (4分) ⎪⎪⎪⎪⎪⎭⎫⎝⎛=∧=000000100100000123M M M R R (5分)，⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=∧=000001000010000134M M M R R (6分) 则432432)(R R R R R R R R t M M M M M M ∨∨∨==⋃⋃⋃⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0000011001100001,(7分) 因此=)(R t )3,3(),2,3(),3,2(),2,2(),1,1{(。
第 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. 下列哪个是离散数学的基础？A. 微积分B. 线性代数C. 集合论D. 概率论2. 以下哪个是正命题？A. 如果今天下雨，那么我就带伞。
B. 如果今天下雨，我没有带伞。
C. 如果今天下雨，我可能会带雨鞋。
D. 如果今天下雨，我带了雨伞。
3. 若集合 A={1,2,3}，集合 B={2,3,4}，则A∩B等于：A. {1,2}B. {2,3}C. {3}D. {2}4. 下列命题中，哪个是概率命题？A. 今天下雨了。
B. 明天会是晴天。
C. 抛硬币正面朝上的概率是0.5。
D. 人类能登陆火星。
5. 若命题 p 为“今天下雨”，命题 q 为“我带了雨伞”，则p→q 的真值表为：A. T T TB. T F TC. F T TD. F F T二、填空题1. 若集合 A={1,2,3,4}，集合 B={3,4,5}，则A∪B等于______。
2. 命题p:“我今天去看电影”，q:“电影院放映时间是晚上8点”，则p∧q 的真值为______。
3. 若命题 p 为“5是一个奇数”，则非命题p的否定形式为______。
三、简答题1. 解释离散数学在计算机科学中的重要性。
2. 说明集合的基本运算并给出一个例子。
3. 论述命题逻辑和谓词逻辑的区别。
四、综合题1. 设集合 A={a, b, c}，B={c, d, e}，C={e, f, g}，求(A∩B)∪C。
2. 用真值表验证以下推理是否成立：p∨(q∧r)与(p∨q)∧(p∨r)等价。
以上就是离散数学自考试题，希。
《离散数学》题库及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式某((A(某)B(y，某))zC(y，z))D(某)中，自由变元是(变元是()。
答：某,y,某,z5、判断下列语句是不是命题。
若是，给出命题的真值。
((1)北京是中华人民共和国的首都。
(2)陕西师大是一座工厂。
)，约束)(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。
(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。
答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()。
(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）QP（2）PQ（3）PQ（4）PQ8、设个体域为整数集，则下列公式的意义是()。
(1)某y(某+y=0)(2)y某(某+y=0)答：（1）对任一整数某存在整数y满足某+y=0（2）存在整数y对任一整数某满足某+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)某y(某y=y)()(2)某y(某+y=y)()(3)某y(某+y=某)()(4)某y(y=2某)()答：（1）F（2）F（3）F（4）T10、设谓词P(某)：某是奇数，Q(某)：某是偶数，谓词公式某(P(某)Q(某))在哪个个体域中为真()2(1)自然数(2)实数(3)复数(4)(1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。
离散数学自考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 命题逻辑中，下列哪个命题是永真命题？A. (p ∧ ¬p) → qB. p ∨ (q ∧ ¬q)C. (p → q) ∧ (q → p)D. ¬(p → ¬p)答案：B3. 函数f: A → B中，如果A中的每个元素都映射到B中的不同元素，则称f为：A. 注入函数B. 满射C. 双射D. 单射答案：C4. 在图论中，下列哪项不是无向图的基本术语？A. 顶点B. 边C. 路径D. 子图答案：D5. 以下哪个算法用于判断一个图是否包含汉密尔顿回路？A. 深度优先搜索B. 广度优先搜索C. 弗洛伊德算法D.Dijkstra算法答案：A6. 命题逻辑中，德摩根定律描述了哪些命题的等价关系？A. ¬(p ∧ q) ≡ ¬p ∨ ¬qB. ¬(p ∨ q) ≡ ¬p ∧ ¬qC. ¬(p → q) ≡ p ∧ ¬qD. 所有以上答案：D7. 在关系数据库中，下列哪个操作用于删除表中的行？A. SELECTB. INSERTC. DELETED. UPDATE答案：C8. 以下哪个是有限自动机的组成部分？A. 状态B. 转移C. 输入D. 所有以上答案：D9. 在布尔代数中，下列哪个操作不是基本操作？A. ANDB. ORC. NOTD. XOR答案：D10. 以下哪个是命题逻辑中的有效论证形式？A. 假言三段论B. 假言推理C. 析取三段论D. 所有以上答案：D二、填空题（每题2分，共20分）11. 在集合{1, 2, 3}的幂集中，含有2个元素的子集有_________。
答案：{{1, 2}, {1, 3}, {2, 3}}12. 如果命题P表示“今天是晴天”，命题Q表示“我去公园”，那么(P ∧ Q)表示_________。
自考离散数学考试题及答案一、选择题（每题2分，共10分）1. 在集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ∩答案：A2. 有限自动机中的一个状态不包括以下哪个元素？A. 初始状态B. 终止状态C. 转移函数D. 输入符号答案：C3. 在命题逻辑中，德摩根定律描述了哪些命题的等价性？A. (¬P ∧ ¬Q) ↔¬(P ∨ Q)B. (P ∨ Q) ↔¬(¬P ∧ ¬Q)C. (P ∧ Q) ↔¬(P ∨ Q)D. (¬P ∨ ¬Q) ↔¬(P ∧ Q)答案：A4. 以下哪个算法是用于解决图的最短路径问题？A. 欧几里得算法B. 迪杰斯特拉算法C. 快速排序算法D. 弗洛伊德算法答案：B5. 布尔代数中，一个表达式可以有的最大项数是多少？A. nB. 2^nC. n^2D. 2n答案：B二、填空题（每题3分，共15分）6. 在关系数据库中，确保实体完整性的约束称为________。
答案：主键7. 一个有向图中，如果存在从顶点A到顶点B的路径，则称顶点A可以________顶点B。
答案：到达8. 在命题逻辑中，如果命题P和命题Q都为真，则命题P → Q的真值是________。
答案：真9. 一个命题函数的真值表中，如果某一行的P和Q都为假，那么这一行的结果是________。
答案：真10. 在图论中，一个完全图是指图中任意两个顶点都________。
答案：相连三、解答题（共75分）11. （15分）证明：在任何非空集合中，至少存在一个元素不包含于该集合的任何子集中。
答案：略12. （20分）给定一个有向图，描述如何使用拓扑排序算法来对图中的顶点进行排序。
答案：略13. （20分）解释什么是正规表达式，并给出一个例子来说明如何使用它来匹配字符串。
答案：略14. （20分）证明：在任何无向图中，边数最多的生成子图最多有3n/2条边，其中n是顶点的数量。
自考离散数学试题及答案一、选择题（每题2分，共20分）1. 在集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 命题逻辑中，下列哪个表达式表示“非”操作？A. ∧B. ∨C. ¬D. →答案：C3. 在下列哪个图论的术语中，表示图中任意两个顶点都相连？A. 无向图B. 有向图C. 完全图D. 二分图答案：C4. 布尔代数中，下列哪个操作是“或”？A. ∧C. ¬D. →答案：B5. 以下哪个是等价关系的属性？A. 自反性B. 对称性C. 反对称性D. 传递性答案：A6. 有限自动机中，状态可以被分为哪两种类型？A. 初始状态和终止状态B. 接受状态和拒绝状态C. 确定状态和非确定状态D. 静态状态和动态状态答案：B7. 在关系数据库中，下列哪个操作用于删除表中的行？A. INSERTB. DELETEC. UPDATED. SELECT答案：B8. 以下哪个是谓词逻辑中的量词？B. ∃C. ∧D. ∨答案：A9. 在命题逻辑中，德摩根定律描述了哪些逻辑运算的对偶性？A. ∧ 和∨B. ¬和→C. ¬和↔D. → 和↔答案：A10. 树的深度优先搜索（DFS）算法通常使用哪种数据结构来实现？A. 队列B. 栈C. 链表D. 哈希表答案：B二、填空题（每题3分，共30分）11. 在集合{1, 2, 3, 4, 5}中，子集的总数是_________。
答案：3212. 如果命题P为真，则命题P → Q的真值表中，Q的值必须为_________。
答案：真13. 在有向图中，一个顶点的入度是指_________。
答案：指向该顶点的边的数量14. 一个关系R(A, B, C)中，如果对于任意两个元组，当它们在属性A上的值相等时，它们在属性B和C上的值也相等，则称R具有_________。
答案：候选键15. 在布尔代数中，表达式(A ∧ B) ∨ (A ∧ ¬B)的结果是_________。
孝感学院新技术学院Array 2011 — 2012 学年度第二学期期中考核试卷考核课程：离散数学考核类型：考试考核形式：闭卷学生所在院系：信息工程系年级： 21117141 试卷： A一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1．下列句子是．命题的是（）A．我们要努力学习！B．今天是星期天吗？C．雪是黑色的D．太好了！2．下列式子不是．．析取的性质的是（）A．P∨P⇔PB．P∧┐P⇔ 0C．P∨(P∧Q)P⇔ PD．P∨(Q∧R) ⇔(P∨Q) ∧(P∨R)3．下列式子是命题公式的是（）A．┐P∨Q∨B．(┐P∨Q∨R) ∧（┐P∧┐Q）C．（┐P∧Q）→D．P∨（Q∨R∨4．张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，则说真话的是（）A．张三说真话B．李四说真话C．王五说真话D．张三和王五都说真话5．下列各式不是前束范式的是（）A．∀x∃y∀z（P（x，y，z）→Q（x，y））B．∀x∃y∀z（P（x，y，z）→∀x∃y Q（x，y）C．∀x∃y（P（x，y，z）→Q（x，y））D．∀x∃y（P（x，y）∧Q（x，y））命题教师院系负责人签字6．已知指定一个解释I如下：（1）个体域为自然数集合N；（2）指定常项a=0；（3）指定谓词F（x，y）为x=y；（4）N上的指定函数f（x，y）=x+y，g（x，y）=x*y。
在以上指定的解释I下，下列公式的真值为假的是（）A．∀x F（g（x，a），x）B．∀x∃y（F(f（x，a），y) →F(f（y，a），x)C．F(f（x，y），f（y，z）) D．F(g（x，y），f（y，x）)7．下列有关图的概念不正确的是（）A．规定顶点集和边集均为空的图为空图B．规定含有平行边的图称为多重图C．规定有自环和平行边的图称为简单图D．规定顶点集和边集均不为有限集的图称为有限图8．下列有关的命题等价式错位的是（）A．幂等率：A∨A⇔A A∧A⇔AB．吸收率：A∧（A∨B）⇔B A∨（A∧B）⇔BC．互补率：A∨┐A⇔1 A∧┐A⇔0D．假言易位：A→B⇔┐B→┐A9．有题9图得出的如下结论错误的是（） d gA．（g，h，c，d，a，b，c，e，f，g）是回路，但不是环 a c fB．（h，c，d，a，b，c，e，f）是通路，也是基本通路C．（a，b，c，d，a）是环 b eD．（h，g，f）是h与f之间的短程题9图10．下列图是欧拉图的是（）二、填空题（本大题共5小题，每空2分，共20分）请在每小题的空格中填上正确答案。
