下载文档原格式
离散数学考试试题（A卷及答案）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？1)((P→Q)∧Q)↔((Q∨R)∧Q) 2)⌝((Q→P)∨⌝P)∧(P∨R)3)((⌝P∨Q)→R)→((P∧Q)∨R)解：1)永真式；2）永假式；3)可满足式。
二、（8分）个体域为{1，2}，求∀x∃y（x+y=4）的真值。
解：∀x∃y（x+y=4）⇔∀x（（x+1=4）∨（x+2=4））⇔（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））⇔（0∨0）∧（0∨1）⇔1∧1⇔0三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。
因为|BA|=|B||A|=mn，所以A到B的函数mn个。
四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。
《离散数学》考试试卷（试卷库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. 下列代数系统中,其中*是加法运算,（）不是群。
离散数学期末考试试题一、选择题（每题2分，共20分）1. 在离散数学中，以下哪个概念不是布尔代数的基本元素？A. 变量B. 常量C. 逻辑运算符D. 函数2. 以下哪个命题不是命题逻辑中的命题？A. p ∧ qB. p ∨ qC. ¬pD. 5 > 33. 集合{1, 2, 3}与集合{2, 3, 4}的交集是什么？A. {1}B. {2, 3}C. {1, 2, 3}D. {2, 4}4. 以下哪个选项不是关系的性质？A. 自反性B. 对称性C. 传递性D. 唯一性5. 函数f(x) = x^2 + 1的值域是什么？A. {x | x > 0}B. {x | x ≥ 1}C. {x | x ≠ 0}D. {x | x ≥ 0}6. 以下哪个命题的否定是真命题？A. 如果今天是星期一，那么太阳从东方升起。
B. 所有的狗都是哺乳动物。
C. 存在一个整数x，使得x^2 = -1。
D. 所有的苹果都是红色的。
7. 以下哪个选项不是图论中的基本概念？A. 顶点B. 边C. 路径D. 函数8. 以下哪个选项是有限自动机的组成部分？A. 状态B. 函数C. 变量D. 集合9. 在命题逻辑中，以下哪个命题是重言式？A. (p ∨ ¬p) ∧ (¬p ∨ p)B. (p → q) ∧ (q → p)C. (p → q) → (¬q → ¬p)D. (p ∧ q) → (p ∨ q)10. 以下哪个选项是P vs NP问题的核心？A. 问题是否可解B. 问题是否可证明C. 问题是否可快速验证D. 问题是否可并行处理二、填空题（每空2分，共20分）11. 命题逻辑中的合取范式是将所有可能的________组合起来的形式。
12. 在集合论中，如果集合A的所有元素都是集合B的元素，则称A是B的________。
13. 函数f: A → B是________的，当且仅当对于B中的每一个元素y，存在唯一的x使得f(x) = y。
《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( A )(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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z（考察定义在公式∀x A和∃x A中，称x为指导变元，A为量词的辖域。
在∀x A和∃x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。
于是A(x)、B(y，x)和∃z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华人民共和国的首都。
(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。
(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。
）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
华东交通大学2014—2015学年第一学期考试卷试卷编号： （ A ）卷离散数学 课程 课程类别：必修 考试日期： 月 日 开卷(范围：可带含课程内容的手写的不超过A4大小的纸一张）注意事项：1、本试卷共 8 页（其中试题4页），总分 100 分，考试时间 120 分钟。
2、所有答案必须填在答题纸上，写在试卷上无效；3、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、单项选择题（2分×10=20分）1．下列语句是命题的有[ ]。
A. 122>+y x ；B. 2010年的国庆节是晴天；C. 青年学生多么朝气蓬勃呀！D. 学生不准吸烟!2．若一个代数系统是独异点（含幺半群），则以下选项中一定满足的是[ ]。
A. 封闭性，且有零元;B. 结合律，且有幺元；C. 交换性，且有幺元;D. 结合律，且每个元素有逆元.3．Z是整数集合，下列函数都是Z→Z的映射，则[ ]是单射而非满射函数。
A．ϕ (x) =0B．ϕ (x) =x2C．ϕ (x) =2x D．ϕ (x) =x4. 与命题p ∧ (p∨q)等值的公式是[ ]。
A. p；B. q；C. p∨q；D. p∧q.5. 设M={a,b,c}，M上的等价关系R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}确定的集合M的划分是[ ]。
A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c}}6. 设D：全总个体域，F(x)：x是花，M(x) ：x是人，H(x,y)：x喜欢y ，则命题“每个人都喜欢某种花”的逻辑符号化为[ ]。
A. ))xFMy∃y∀；∧x→(y()(()x,(HB. ))yFyHM→∃x→∀；x)(,(((y()xC. ))yFyxH→∃x∧∀；M)(,(((y()xD. ))xyFMy→∀x∧∃.()(,()xH(y(7. 下列图中，不是哈密顿图的为[ ]。
离散考试试题及答案一、选择题（每题5分，共20分）1. 在离散数学中，下列哪个概念不是布尔代数的基本运算？A. 与B. 或C. 非D. 模答案：D2. 集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A3. 命题逻辑中，下列哪个符号表示“蕴含”关系？A. ∧B. ∨C. →D. ↔答案：C4. 关系R在集合A上是自反的，意味着什么？A. 对于所有a∈A，(a, a)∈RB. 对于所有a∈A，(a, a)∉RC. 对于所有a∈A，(a, b)∈RD. 对于所有a∈A，(a, b)∉R答案：A二、填空题（每题5分，共20分）1. 一个集合的基数是集合中元素的________。
答案：数量2. 在有向图中，如果存在一条从顶点u到顶点v的路径，则称顶点v 是顶点u的________。
答案：可达的3. 一个图是连通的，当且仅当图中任意两个顶点都是________。
答案：连通的4. 在命题逻辑中，一个命题的否定是________。
答案：它的对立命题三、简答题（每题10分，共30分）1. 请解释什么是图的哈密顿回路。
答案：哈密顿回路是一个图中的闭合回路，它恰好访问图中的每个顶点一次。
2. 描述一下什么是二元关系，并给出一个例子。
答案：二元关系是定义在两个集合上的一个关系，它关联了第一个集合中的元素和第二个集合中的元素。
例如，小于关系是数字集合上的一个二元关系。
3. 什么是图的生成树？答案：图的生成树是图的一个子图，它包含图中的所有顶点，并且是一棵树，即它是连通的且没有环。
四、计算题（每题15分，共30分）1. 给定一个集合A={1,2,3,4,5}，计算它的幂集。
答案：幂集P(A)={∅, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5},{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}, A}。
一、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.4. 已知命题公式G＝⌝(P→Q)∧R，则G的主析取范式是_________________________________________________________________________________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝_________________________; A⋃B＝_________________________;A－B＝_____________________ .7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________,________________________, _______________________________.8. 设命题公式G＝⌝(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________.9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1•R2 =________________________,R2•R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = _____________________________.11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B =__________________________ , B-A = __________________________ ,A∩B = __________________________ , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为__________________________________________________________________.14. 设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G的前束范式是__________________________ _____.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( A )(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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z（考察定义在公式∀x A和∃x A中，称x为指导变元，A为量词的辖域。
在∀x A和∃x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。
于是A(x)、B(y，x)和∃z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华人民共和国的首都。
(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。
(5) 前进！ (6) 给我一杯水吧！答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 （命题必须满足是陈述句，不能是疑问句或者祈使句。
《离散数学》练习题库（加粗红色字体为2013下新增题目）一、选择题1、G是一棵根树，贝ij （）oA、G—定是连通的C、G只有一个顶点的出度为02、下而哪个语句不是命题（）。
A、中国将成功举办2008年奥运会C、我说的不是真话B、G —定是强连通的D、G只有一个顶点的入度为1B、一亿年前地球发生了大灾难D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算佗a, bWR, a*b=a+b-ab,则F面的论断屮正确的是（）。
A、（）是*的零元B、1是*的幺元C、0是*的幺元D、*没有等幕元4、下面说法中正确的是（）。
C、有些无限集合没有可数子集D、有理数集合是不可数集合5、无向完全图心的不同构的生成了图有（）个。
A. 6B.5C.4D. 36、下I何哪一种图彳、一定是无向树？A、无回路的连通图有n个顶点n-1条边的连通图C、每对顶点间都有通路的图D、连通但删去一条边则不连通的图7、设集合A ={{1,2,3}, {4,5}, {6,7,8}},则下列各式为真的是（）。
A. I E A B・{{4,5}}uAC. (1,2, 3}cAD. 0G A8、在有界格屮，若一个元素有补元，则补元（）。
A、必惟一B、不惟一c、不一定惟一D、可能惟一9、设集合A={l,2,3,・・・,10},下面定义的哪种运算关于集合A是不封闭的？（）A、x*y=max{x,y}B、x*y=min{x,y}C^ x*y=GCD(x,y),即x,y的最大公约数D、x*y=LCM(x,y),即x,y的最小公倍数_i o r10.集合X中的关系R,其矩阵是110,则关于R的论述中正确的是()o1 I 1A、R是对称的B、R是反对称的C、R是反自反的D、R中有7个元素11.下列各组数中，哪个可以构成无向图的度数列()。
A.1, 1, 1, 2, 2B.2, 2, 2, 2, 3C.1, 2, 2, 4, 6D.2, 3, 3, 312.*是定义在Z上的二元运算，Vx,yeZ,x^y = xy + x-y,则*的幺元和零元分别是()。
证明：设T=(V,E)是一棵树，若T中最多只有一片树叶，则有∑d(v) ≥1+2(|V|-1)=2|E|+1,这与结论∑ d(v) =2|E| 矛盾! 矛盾说明T 不止一片树叶。
证明：因为G不连通，则G可以分为若干连通子图:G1=（V1，E1），--- ，Gn=（Vn，En）根据G的补图的构造过程知V1中每个顶点与其它顶点集V2，--- ，Vn中顶点有边相连。
这样，在G的补图中，有ν分别属于两个顶点子集Vi与Vj中的任意两个顶点之间有边直接相连，ν属于同一个顶点子集Vi的任意两个顶点借助顶点子集Vj的任意一个顶点连通。
所以，根据连通的定义知：G的补图一定连通。
解: A×B={({a},{b}), ({a},a), (a, {b}), (a, a), (b, {b}), (b, a)}AÅB=(A-B) ∪(B-A)={{a}, b, {b}}P(A)={Ø, {a}, a, b, {{a}, a}, {{a},b}, {a,b}, A}.证明: 不妨记A={a1, a2, a3, …,an, …}B={b1, b2, b3, …, bm}作映射φ: A→A∪Bφ(ai)=bi (i=1,…,m)φ(ai)=ai-m (i=m+1,m+2,…)则可以说明φ为A→A∪B的双射，故结论得证。
解: 一般地, R1∘R2≠ R1∘R2.反例: R1={(1,3), (3,1)} 对称!R2={(3,2), (2,3)} 对称!R1∘R2 ={(1,2)} 不对称!因为n个顶点的无向完全图有n(n-1)/2个边，所以自互补图各有n(n-1)/4个边，因此，n=4k或4k+1。
证明: (1) "a,bÎ HÇK,就有a,bÎ H, a,bÎ K，因为H, K是群G的子群，所以，a*b-1ÎH，a*b-1ÎK，因此a*b-1Î HÇK。
