2006年4月全国自考离散数学试题试卷真题

《离散数学》考试试卷（试卷库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. 下列代数系统中,其中*是加法运算,（）不是群。

2006级《离散数学I》期末考试试题（B卷）一、简答题【本大题共20小题，每小题2分，共40分】(1)设集合A={a,b,c,d}，B={b,d}，求ρ(A－B)。

(2)设集合A={a,b,c}，A上的关系R={(a,a),(a,b),(b,a),(b,b)}，试给出R所满足的性质（自反性、反自反性、对称性、反对称性、传递性）。

应的等价关系R c。

(4)右图是部分序集(A,R)的hasse图，请写出集合A和关系R。

(5)映射的乘积满足交换律吗？若不满足，请举反例说明。

(6)可数无穷多个有限集合的并集是可数集合吗？有限多个可数无穷集合的笛卡尔积是可数集合吗？(7)给出命题公式G=(P∨Q)→R和H=⌝Q∨R的真值表，试判断G蕴涵H吗？(8)写出弄假极大项⌝P∨Q∨R的解释和满足极小项⌝P∧Q∧⌝R的解释。

(9)假设公式(P∧Q) →⌝R的真值为0，求(⌝P∨R)→Q的真值。

(10)命题公式(P→Q)∧(R→Q)与(P∨R)→Q等价吗？(11)设I是如下一个解释：D={a,b}, f(a) f(b) P(a) P(b) Q(a,a) Q(a,b) Q(b,a) Q(b,b)b a 1 0 0 1 1 0试确定公式G＝∃xP(x)→∀yQ(f(y),y)在I下的真值。

(12)设谓词公式G＝∀xP(x)∨∀yQ(y)，H＝∀x(P(x)∨Q(x))，则G蕴涵H吗？H蕴涵G吗？(13)图G是有限连通图，则其支撑子图一定是连通图吗？其支撑树一定是连通图吗？(14)设有限权图G=(P，L)，u0∈G，从u0到G中其它各点的最短路经过的所有边组成的集合为L0，则G0=(P，L0)为图G的一个子图，请问G0是支撑子图吗？G0是树吗？(15)对于完全图K n，删除多少条边后才能得到它的一个支撑树?(16)有限图G的闭合图C(G)中存在Hamilton回路，则图G一定是Hamilton图吗？(17)Euler图一定连通吗？若存在不连通的情况，试画出一个不连通的Euler图。

第2页 共 2页D ．∀x (F (x )∧∃y (G (y )∧H (x ，y )))．2. 4阶无向完全图的非同构的生成子图有 【B 】 A ．1个． B ．2个．C ．3个．D ．4个． 3. 设代数系统〈A ，*〉是独异点，e 是其单位元，若∀a ∈A ，有a *a =e ，则〈A ，*〉 【B 】A ．是群但不是Abel 群．B ．是Abel 群．C ．不是群．D ．不是代数系统．4. 下列图中是哈密尔顿图的有 【C 】A ．K 3，4．B ．K 2．C ．K 4．D ．K 1,1．5. 下列图中是欧拉图的有 【D 】A ．K 2，3．B ．K 4．C ．K 3，3．D ．K 7．三、 计算与简答题（每小题10分，共40分）1. 利用等值演算法求公式(p ∨q )→(q ↔p )的主析取范式，并给出其成真赋值．(p ∨q )→(q ↔p )⇔⌝(p ∨q )∨((⌝p ∨q )∧(p ∨⌝q )) ⇔(⌝p ∧⌝q )∨((⌝p ∨q )∧(p ∨⌝q ))⇔(⌝p ∧⌝q )∨((⌝p ∧p )∨(⌝p ∧⌝q )∨(p ∧q )∨(q ∧⌝q )) ⇔(⌝p ∧⌝q )∨(p ∧q ) ⇔m 0∨m 3此为公式的主析取范式． 公式的成真赋值为00和11．第4页 共 4页4. 设集合Ａ={a ，b ，c ，d }上的二元关系R={〈a ，b 〉，〈b ，a 〉，〈b ，c 〉，〈c ，b 〉}，利用关系矩阵求R 的传递闭包t (R )．解 关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0000001001010010R M ， ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=00000101001001012R M ，⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=00000010010100103R M ，⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0000010100100114R M ， 因此⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=000011101110111)(R t M ，从而R 的传递闭包 t (R )={〈a ，a 〉，〈a ，b 〉，〈a ，c 〉，〈b ，a 〉，〈b ，b 〉，〈b ，c 〉，〈c ，a 〉，〈c ，b 〉，〈c ，c 〉，〈d ，d 〉}．四、 证明题（共20分）1. 在一阶逻辑中构造下面推理的证明：前提：∀x (F (x )→G (x ))，∃x (F (x )∧H (x ))． 结论：∃x (G (x )∧H (x ))．证明 （１）∃x (F (x )∧H (x )) 前提引入 （２）F (a )∧H (a )) EI 规则 （３）F (a ) （２）化简 （４）H (a ) （２）化简 （５）∀x (F (x )→G (x )) 前提引入 （６）F (a )→G (a )， UI 规则 （７）G (a ) 假言推理 （８）G (a ) ∧H (a ) （７）（４）合取第5页 共6页（９）∃x (G (x )∧H (x ))． EG 规则2. 设〈B ，∧，∨，'，1，0〉为一布尔代数，证明：∀a ，b ∈B ，有(a ∨b )' = a'∧b'．证明(a ∨b )∧(a'∧b')=(a ∧a'∧b')∨(b ∧a'∧b') =((a ∧a')∧b')∨(a'∧(b ∧b')) =0∨0=0(a ∨b )∨(a'∧b')=(a ∨b ∨a')∧(a ∨b ∨b') =((a ∨a')∨b )∧(a ∨(b ∨b')) =1∧1=1因此，(a ∨b )' = a'∧b'．3. 证明：设e 为无向连通图G 的桥，则e 在G 的每棵生成树中． 证明 假设存在G 的一棵生成树T ，其中不含G 的桥e ．这样，在G 中去掉桥e 后仍可得该生成树T ．另一方面，由于e 为图G 的桥，在G 中去掉桥e 后，所得图G ′一定不连通，它没有生成树，矛盾．因此，e 在G 的每棵生成树中．。

自考离散数学考试题库及答案一、选择题1. 在离散数学中，命题逻辑的主要研究对象是什么？A. 命题的真假B. 命题的类型C. 命题的表达D. 命题的证明答案：A2. 有限集合M的基数是指什么？A. M中元素的数量B. M的子集数量C. M的幂集D. M的幂集的基数答案：A3. 以下哪个不是图论中的基本概念？A. 顶点B. 边C. 集合D. 子图答案：C二、填空题4. 在命题逻辑中，德摩根定律表示了________和________之间的逻辑关系。

答案：¬(P ∧ Q)；¬P ∨ ¬Q5. 一个集合的幂集是指该集合所有________的集合。

答案：子集6. 在图论中，无向图中的路径是顶点和边的________。

答案：交替序列三、解答题7. 证明：若命题P是真命题，则其否定¬P是假命题。

证明：根据命题逻辑的定义，一个命题要么是真要么是假。

如果P 是真命题，那么根据否定的定义，¬P表示P不是真的，这与P是真命题的事实相矛盾。

因此，¬P必须是假命题。

8. 给定集合A={1, 2, 3}，求其幂集及其基数。

解答：集合A的幂集包括A的所有子集，即∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}。

共有2^3=8个子集，所以A的幂集的基数是8。

四、应用题9. 在一个无向图中，定义了两个顶点之间的距离为它们之间的最短路径上的边数。

如果图G中有两个顶点u和v，且它们之间的距离是3，证明存在一个顶点w，使得u和w之间的距离是1，v和w之间的距离是2。

证明：由于u和v之间的距离是3，根据距离的定义，存在一条最短路径连接u和v，这条路径至少包含3条边。

设这条路径为u=w1, w2, w3, w4=v，其中每对相邻的顶点之间存在一条边。

根据题设，我们可以取w2作为w，这样u和w之间的距离是1（因为它们之间有一条边w1w2），而v和w之间的距离是2（因为它们之间有两条边w2w3和w3w4）。

一、填空题（每小题3分，共15分）1.设F(x)：x是苹果，H(x，y)：x与y完全相同，L(x，y)：x=y，则命题“没有完全相同的苹果”的符号化（利用全称量词）为∀x∀y(F(x)∧F(y)∧⌝L(x，y)→⌝H(x，y))．2.命题“设L是有补格，在L中求补元运算‘′’是L中的一元运算”的真值是0．3.设G={e，a，b，c}是Klein四元群，H=〈a〉是G的子群，则商群G/H={〈a〉，{b，c}}={{e，a}，{b，c}}．4.设群G=〈P({a，b，c})，⊕〉，其中⊕为集合的对称差运算，则由集合{a，b}生成的子群〈{a，b}〉 ={∅，{a，b}}．5.已知n阶无向简单图G有m条边，则G的补图有n(n-1)/2-m条边．二、选择题（每小题3分，共15分）1.命题“只要别人有困难(p)，小王就会帮助他(q)，除非困难已经解决了(r)”的符号化为【B】A．⌝(p∧r)→q．B．(⌝r∧p)→q．C．⌝r→(p∧q)．D．⌝r→(q→ p)．2.设N为自然数集合，“≤”为通常意义上的小于等于关系，则偏序集〈N，≤〉是【C】A．有界格．B．有补格．C．分配格．D．布尔代数．3.设n (n≥3) 阶无向图G=〈V，E〉是哈密尔顿图，则下列结论中不成立的是【D】A．∀V1⊂V，p(G-V1)≤|V1|．B．|E|≥n．C．无1度顶点．D．δ(G)≥n/2．4.设A={a，b，c}，在A上可以定义个二元运算，其中有个是可交换的，有个是幂等的．【A】A．39，36，36．B．39，36，33．C．36，36，33．D．39，36，39．5.下列图中是欧拉图的有【C】A．K4，3．B．K6．C．K5．D．K3，3．三、计算与简答题（每小题8分，共40分）1.利用等值演算方法求命题公式(p∨q) → (q→p)的主合取范式；利用该主合取范式求公式的主析取范式，并指出该公式的成真赋值和成假赋值．(p∨q) → (q→p)⇔⌝(p∨q)∨(⌝q∨p)⇔(⌝p∧⌝q)∨(⌝q∨p)⇔(⌝p∨⌝q∨p)∧(⌝q∨⌝q∨p)⇔⌝q∨p⇔p∨⌝q⇔M1此为公式的主合取范式．该公式的主析取范式是m0∨m2∨m3．公式的成真赋值为00，10，11．公式的成假赋值为01．哈尔滨工程大学试卷考试科目：离散数学（041121，041131-32）考试时间：14:00-16:3012. 求群〈Z 18，⊕18〉的所有生成元和子群，画出〈Z 18，⊕18〉的子群格，指出该子群格的全下界、全上界和有补元，并求其补元． 与18互质的数有1，5，7，11，13，17，因此，1，5，7，11，13，17是群〈Z 18，⊕18〉的生成元．18的因数有1，2，3，6，9，18，因此，群〈Z 18，⊕18〉的子群有 〈1〉=〈Z 18，⊕18〉，〈2〉=〈{0，2，4，6，8，10，12，14，16}，⊕18〉， 〈3〉=〈{0，3，6，9，12，15}，⊕18〉，〈6〉=〈{0，6，12}，⊕18〉， 〈9〉=〈{0，9}，⊕18〉，〈18〉=〈{0}，⊕18〉． 〈Z 18，⊕18〉的子群格为〈{〈18〉，〈9〉，〈6〉，〈3〉，〈2〉，〈1〉}，⊆〉，其哈斯图为 全下界为〈18〉，全上界为〈1〉， 〈18〉’=〈1〉，〈1〉’=〈18〉，〈2〉’=〈9〉，〈9〉’=〈2〉，〈3〉和〈6〉没有补元． 3. 若R 1，R 2均是非空集合A 上的等价关系，那么R 1，R 2的交R 1∩R 2、并R 1∪R 2和复合R 1○ R 2也是A 上的等价关系吗？若是，证明你的结论．R 1∩R 2是A 上的等价关系．事实上， (1) 因R 1，R 2是A 上的自反关系，有I A ⊆R 1，I A ⊆R 2，因此，I A ⊆R 1∩R 2，即R 1∩R 2是A 上的自反关系．(2) 因R 1，R 2是A 上的对称关系，有R 1＝R 1-1，R 2＝R 2-1，而(R 1∩R 2)-1=R 1-1∩R 2-1=R 1∩R 2，因此，R 1∩R 2是A 上的对称关系．(3) 因R 1，R 2是A 上的传递关系，有R 12⊆R 1，R 22⊆R 2，而(R 1∩R 2)2=(R 1∩R 2)ο(R 1∩R 2)=R 12∩R 22∩R 1οR 2∩R 2οR 1⊆R 12∩R 22⊆R 1∩R 2，因此，R 1∩R 2是A 上的传递关系．4. 设无向连通图G 如下图，求其最小生成树T 及T 的权W (T )，写出G 的对应于T 的基本回路系统和基本割集系统．G 的最小生成树T 如图（以实线表示），权W (T )=11． G 的对应于T 的基本回路系统为{C bd ，C cd ，C de }，其中 C bd =bdab ，C cd =cdabc ， C de =dead ．G 的对应于T 的基本割集系统为{S ab ，S ad ，S ae ，S bc }，其中 S ab ={ab ，bd ，cd }，S ad ={ad ，bd ，cd ，de }， S ae ={ae ，de }，S bc ={bc ，cd }．5. 设〈Ｂ，∧，∨，′，0，1〉是布尔代数，a ，b ，c ∈B ，化简公式 (a ∧b )∨(a ∧(b ∧c )’ )∨c ．(a ∧b )∨(a ∧(b ∧c )’ )∨c =(a ∧b )∨(a ∧(b’∨c’ ))∨c =(a ∧b )∨((a ∧(b’∨c’ ))∨c ) =(a ∧b )∨((a ∨c )∧(b’ ∨c’ ∨c )) =(a ∧b )∨(a ∨c ) =(a ∨(a ∨c ))∧(b ∨a ∨c ) =(a ∨c )∧(a ∨c ∨b ) =a ∨c〈3〉3四、 证明题（共20分）1. 在自然推理系统中，构造推理证明： 前提：∀x (F (x )∨G (x )) 结论：⌝∀xF (x )→ ∃xG (x )证明：(1) ⌝∀xF (x ) 附加前提引入 (2) ∃x ⌝F (x ) (1)置换 (3) ⌝F (c ) (2)EI 规则 (4) ∀x (F (x )∨G (x )) 前提引入 (5) F (c )∨G (c ) (4)UI 规则(6) G (c )) (3)(5)析取三段论 (7) ∃xG (x ) (6)EG 规则2. 设代数系统〈A ，*〉是独异点，e 是其单位元．若∀a ∈A ，有a *a =e ，证明：〈A ，*〉是Abel 群．证明：由于对∀a ∈A ，有a *a =e ，因此，A 中任意元素a 都有逆元，且a=a -1．又〈A ，*〉是有单位元的独异点，从而〈A ，*〉是群． ∀a ，b ∈A ，有a *b ∈A ，且a=a -1，b=b -1，(a *b )-1=a *b ．又(a *b )-1=b -1*a -1=b *a ，因此 a *b =b *a ，即〈A ，*〉是Abel 群．3. 证明：若无向图G 为欧拉图，则G 无桥．证明：（1）假设G 中有桥，不妨设e =(u ，v ) 为其一座桥．这样，从中删去边e =(u ，v )后，所得图G ’一定不连通（G ’至少含有两个连通分支）．由于G 为欧拉图，因此它是连通图，且有经过每条边一次且仅一次的回路，这条回路必经过G 的所有顶点．从而存在顶点v 1，v 2，…，v s ，使得uv 1v 2…v s vu 是G 的一条回路．从G 中删去边e =(u ，v )后，所得图G ’仍有从u 到v 的通路uv 1v 2…v s v ，这样G ’仍是连通图．矛盾．因此，G 中一定无桥．（2）由于G 为欧拉图，其每个顶点的度数均为偶数．假设G 中有桥，不妨设e =(u ，v ) 为其一座桥．这样，从中删去边e =(u ，v )后，所得图G ’至少有两个连通分支．而且，顶点u ，v 的度数都是奇数，这与每个连通分支为图矛盾（与握手定理矛盾），因此，G 中一定无桥．五、 应用题（10分）今有a ，b ，c ，d ，e ，f 和g 七人，已知a 会讲英语；b 会讲英语和汉语；c 会讲英语、意大利语和俄语；d 会讲汉语和日语；e 会讲德语和意大利语；f 会讲法语、日语和俄语；g 会讲法语和德语，试问：如何将这七个人安排围坐在一张圆桌上，使得每个人都可和他身边的人交谈．以a ，b ，c ，d ，e ，f 和g 七人为顶点，如果两人有共同语言，连接这两个顶点，以此为边做一个图，如右图．在图中如果能找到一条哈密尔顿回路，则将这七个人安排围坐在一张圆桌上，每个人都可和他身边的人交谈．该回路为abdfgeca ．。

离散数学自考试题及答案一、选择题（每题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是顶点的数量。

全国2006年4月高等教育自学考试离散数学试卷课程代码：02324一、单项选择题<本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．下列命题公式为重言式的是< ）A．p→ (p∨q>B．(p∨┐p>→qC．q∧┐q D．p→┐q2．下列语句中不是．．命题的只有< ）A．这个语句是假的。

B．1+1=1.0C．飞碟来自地球外的星球。

D．凡石头都可练成金。

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是A．┐p∧qB．┐p→qC．┐p→┐q D．p→┐q4．下列等价式正确的是< ）A．┐)))()((∀(⇔y∀∀∃x)x∃A(x(⇔)Axy∃┐A B．AC．┐)Axxx(xB)(x⇔(∧∀∀∨Ax∀xBx∃⇔∀┐A D．)A(x)(()(())))()(5．在公式)yxQyPz∀∃中变元y是< ）P∧→x∃yy()))(,(z()())((,A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元6．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是< ）A．自反关系B．反自反关系C．对称关系D．传递关系7．设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的父亲}，S={<a，b>|a，b∈X∧a是b的母亲}，那么关系{<a，b>|a，b∈x∧a是b的祖母}的表达式为< ）A．R S B．R-1 SC．S R D．R S-18．设A是正整数集，R={(x，y>|x，y∈A∧x+3y=12}，则R∩({2，3，4，6}×{2，3，4，6}>=< ）A．O/B．{<3，3>}C．{<3，3>，<6，2>}D．{<3，3>，<6，2>，<9，1>}9．下列式子不正确的是< ）A．(A-B>-C=(A-C>-B B．(A-B>-C=A-(B∪C>C．(A-B>-C=(A-C>-(B-C> D．A-(B∪C>=(A-B>∪ C10．下列命题正确的是< ）A．{l，2}⊆{{1，2}，{l，2，3}，1}B．{1，2}⊆{1，{l，2}，{l，2，3}，2}C．{1，2}⊆{{1}，{2}，{1，2}}D．{1，2}∈{1，2，{2}，{l，2，3}}11．在下列代数系统中，不是环的只有< ）A．<Z，+，*>，其中Z为整数集，+，*分别为整数加法和乘法。

06级离散数学期末试题A 答案一、计算题（本题共20分，每小题5分）1、设A ={1, 2, 3, 4}，A 上的二元关系R 定义如下：R = {<1,2>,<2,2>,<2,4>,<3,4>}，求其自反闭包、对称闭包。

解：自反闭包 (){1,2,2,2,2,4,3,4,1,1,3,3,4,4}r R =<><><><><><><>对称闭包 (){1,2,2,2,2,4,3,4,2,1,4,2,4,3}s R =<><><><><><><>2、设N 是自然数集合，定义N 上的二元关系R ={<x , y >|x ∈N ，y ∈N ，x +y 是偶数}，求关系 R 的等价类。

解 关系R 的等价类有 [1]R ={1, 3, 5, ……}，[0]R ={0, 2, 4, ……}3、设集合{}15,9,5,3=A ，A 上的整除关系{}212121,,,a a A a a a a R 整除∈=，R 是否为A 上的偏序关系？若是，则：（1）画出R 的哈斯图；（2）求A 的极大元和A 的极小元。

解 R 是A 上的偏序关系。

（1）R 的哈斯图：（2）A 的极大元为 9，15；极小元为 3，5。

4、画出五个6阶非同构的无向树解 可能的度数列: (1) 1,1,1,1,1,5 ；(2) 1,1,1,1,2,4 ；(3) 1,1,1,1,3,3 ；(4) 1,1,1,2,2,3 ；(5) 1,1,2,2,2,2二、判断题（本题共15分，每小题5分）1、对给定的集合A={1,2,3,4,5},B={6,7,8,9,10}和f ={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}，判断是否构成能函数f : A →B , 如果能，说明是否为满射、单射、双射的；如果不能，说明理由。

106级离散数学期末试题B 答案一、计算题（共20分，每小题5分）1、 设A={}b a ,，B={}2,1,0，求笛卡尔乘积A ×B 和A 的幂集P(A)。

解 A ×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2.>} P(A)={Φ,{a},{b},{a.b}} 2、 设A={1,2,3,4},A 上的关系R={‹1,1›,‹1,2›,‹2,4›,‹3,1›,‹4,3›},求domR 、ranR 、R –1。

解 domR={1,2,3,4}, ranR={1,2,3,4}, R –1 ={‹1,1›,‹2,1›,‹4,2›,‹1,3›,‹3,4›}3、 画出集合{2, 3, 4, 8, 9, 10, 11}上整除关系的哈斯图，并求它的最大元、最小元、极大元、极小元。

解 它的最大元、最小元都不存在；极大元为8, 9, 10, 11；极小元为2, 3, 11。

4、 设f ：N N N →⨯（N 为自然数集合），22),(y x y x f +=><，说明f 是否为单射、满射的？计算})0({1-f 。

解 })0({1-f ={<0,0>} 不是单射 ,是满射的二、判断题（共10分，每小题5分）1、设A={}8,5,4,3,2,1，R 是A 上的“模3同余”关系。

问R 是否为A 上的等价关系？若是，给出其等价类，并画出R 的关系图。

解 R 是A 上的等价关系，等价类为 [1]=[4]={1,4} [2]=[5]=[8]={2,5,8} [3]={3}R 的关系图如下：2、下列语句中哪些是命题？是命题的句子中哪些是复合命题？并将复合命题符号化。

（1）小张与小刘住一个寝室。

（2）只要天气好，飞机就能正常降落。

（3）请上楼！解 （1）是命题，不是复合命题； （2）是复合命题；设P ：天气好,q ：飞机能正常降落，p →q ；（3）不是命题；三、（共10分，每小题5分）1、某电路中有1个灯泡和3个开关A 、B 、C 。

离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G ，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G 是连通简单平面图，G 中有11个顶点5个面，则G 中的边是( )3.在布尔代数L 中，表达式(a ∧b)∨(a∧b ∧c)∨(b ∧c)的等价式是( )∧(a ∨c)B.(a ∧b)∨(a ’∧b)C.(a ∨b)∧(a ∨b ∨c)∧(b ∨c)D.(b ∨c)∧(a ∨c)4.设i 是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( )A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.设Z 为整数集，A 为集合，A 的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( )A.〈Z ，+，/〉B.〈Z ，/〉C.〈Z ，-，/〉D.〈P(A)，∩〉6.下列各代数系统中不含有零元素的是( )A.〈Q ，*〉Q 是全体有理数集，*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n 阶实矩阵集合，*是矩阵乘法运算C.〈Z ，ο〉，Z 是整数集，ο定义为x οxy=xy,∀x,y ∈ZD.〈Z ，+〉，Z 是整数集，+是数的加法运算 7.设A={1,2,3}，A 上二元关系R 的关系图如下： R 具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) ∪I A ∪{〈c,a 〉} ∩I A 9.设X={a,b,c},Ix 是X 上恒等关系，要使Ix ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等价关系，R 应取( ) A.｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C.{〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 10.下列式子正确的是( ) A. ∅∈∅ B.∅⊆∅ C.{∅}⊆∅ D.{∅}∈∅11.设解释R 如下：论域D 为实数集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R 下为真的是( ) A.( ∀ x)( ∀y)( ∀z)(A(x,y))→A(f(x,z),f(y,z)) B.( ∀x)A(f(a,x),a) C.(∀x)(∀y)（A(f(x,y),x)) D.(∀x)(∀y)(A(x,y)→A(f(x,a),a)) 12.设B 是不含变元x 的公式，谓词公式(∀x)(A(x)→B)等价于( ) A.(∃x)A(x)→B B.(∀x)A(x)→B (x)→B D.(∀x)A(x)→(∀x)B 13.谓词公式(∀x)(P(x,y))→(∃z)Q(x,z)∧(∀y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P ：他聪明；Q ：他用功；则“他虽聪明，但不用功”，可符号化为( )∨Q ∧┐Q →┐Q ∨┐Q15.以下命题公式中，为永假式的是( )→(p ∨q ∨r)B.(p →┐p)→┐pC.┐(q →q)∧pD.┐(q ∨┐p)→(p ∧┐p)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。

一、填空题:(每空1分，本大题共15分）1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。

2．命题公式)(Q P →⌝的主析取范式为 ，主合取范式的编码表示为 。

3．设E 为全集， ,称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ，～Φ= 。

4．设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =,}},,{{4c b a S =}}{},{},{{5c b a S =，}},{},{{6c a a S =则A 的覆盖有 ，A 的划分有 。

5．设S 是非空有限集，代数系统＜（S ），，＞中，（S)对的幺元为 ，零元为 。

（S ）对的幺元为 ，零元为 .6．若>=<E V G ,为汉密尔顿图，则对于结点集V 的每个非空子集S ，均有W(G-S) S 成立，其中W （G —S)是 。

二、单项选择题：（每小题1分，本大题共10分)1．下面命题公式（ )不是重言式。

A 、)(Q P Q ∨→；B 、P Q P →∧)(；C 、)()(Q P Q P ∨⌝∧⌝∧⌝;D 、)()(Q P Q P ∨⌝↔→。

2．命题“没有不犯错误的人”符号化为( ）。

设x x M ：)(是人，x x P ：)(犯错误。

A 、))()((x P x M x ∧∀; B 、)))()(((x P x M x ⌝→∃⌝；C 、)))()(((x P x M x ∧∃⌝；D 、)))()(((x P x M x ⌝∧∃⌝。

3．设}{Φ=A ，B =((A ））,下列各式中哪个是错误的（ ）。

A 、B ⊆Φ; B 、B ⊆Φ}{，C 、B ∈Φ}}{{；D 、⊆ΦΦ}}{,{(A ）。

4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）.A 、),min(b a b a =*;B 、b a b a 2+=*;C 、3++=*b a b a ；D 、)3(mod ,b a b a =*。

《离散数学》考试试卷（试卷库14卷）及答案第 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,BC,则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=中,结点总度数与边数的关系是（）（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= 。

4. 设〈G,*〉是群，且|G|>1，则下列命题不成立的是 （ ）A. G 中有幺元B. G 中有零元C. G 中任一元素有逆元D. G 中除了幺元外无其他幕等元 5. 设Z 是整数集合，则下面定义的二元运算不能使Z 与二构成代数系统的是（）A. i : j=|i-j|, 一口 € ZB. i ： j=i • j-j 2, 一 i ，j € ZC. i ： j=i/j, 一 i,j € ZD. i :-戸 2+j 2+1, - i,j € Z6.设A 是非空集合，P （A ）是A 的幕集，门是集合交运算，则代数系统〈P （A ）, Q 〉的幺元是（ ）A.P （A ） B. 0 C.A D.|0 |7. 设N 为自然数集（含0），函数F : N T N X N,F （n ）=<n,n+1>是（ ）A. 满射，不是入射B. 入射，不是满射 C 双射D.不是入射，不是满射全国2019年4月高等教育自学考试 离散数学试题课程代码：02324、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个选项中只有 一个选项符合题目要求的。

请将其代码填写在题后的括号内。

错选、多选或未选均无分。

C.4 A.8B.16 D.321•下列不是平面图的是（ 3•如下图所示的有界格中，元素 A. a B.b 的补元是（8•设A={a,b,c},则下列是集合A的划分的是()A. {{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},c}D.{{a},{b,c}}9•设集合X={0,1,2,3} ,R 是X 上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，则R的关系矩阵M R是()-10101[10101000们[111011100B.001110100011A.00011100C.0101D.0001-001 1_10001_11110_11010一10. 下列命题中，不正确的是()A. { 0 } € { 0 ,{ 0}}B. { 0 } € { 0 ,{{ 0 }}}C. { 0 }』{ 0,{ 0 }}D. 0 三{ 0 ,{ 0 }}11. 设个体域是正整数集，则下列公式中真值为真的公式是()A. ( - x)( y)(x • y=0)B. ( —x)( y)(x • y=1)C. ( x)( y)(x • y=2)D. (一x)( - y)( z)(x-y=z)12. 令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为()A. (- x)(F(x) A ( y)(G(y) A H(x,y)))B. (-x)( (x)F(x) T (G(y) H(x,y)))C. (—x)(F(x) T( y)(G(y) A H(x,y)))x)(F(x) T( y)(G(y) T H(x,y))13. 在个体域D={a,b}中，与公式(x)A(x)等价又不含量词的公式是()A.A(a) A A(b)B.A(a) T A(b)C.A(a) V A(b)D.A(b) T A(a)14. 下列句子是命题的是()A. 水开了吗？B. x>1.5C. 再过5000年，地球上就没水了。

1全国2006年4月高等教育自学考试一、单项选择题（本大题共15小题，每小题1分，共15分）1．下列命题公式为重言式的是（ ）A ．p → (p ∨q)B ．(p ∨┐p)→qC ．q ∧┐qD ．p →┐q2．下列语句中不是．．命题的只有（ ） A ．这个语句是假的。

B ．1+1=1.0C ．飞碟来自地球外的星球。

D ．凡石头都可练成金。

3．设p ：我很累，q ：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（ ）A ．┐p ∧qB ．┐p →qC ．┐p →┐qD ．p →┐q4．下列等价式正确的是（ ）A ．┐)()(x A x ∃⇔∃┐AB ．A y x A y x ))(())((∀∃⇔∀∀C ．┐)()(x A x ∃⇔∀┐AD ．)()()()())()()((x B x x A x x B x A x ∀∨∀⇔∧∀5．在公式),()())(),()()((z y P y z Q y x P y x ∃→∧∀∃中变元y 是（ ）A ．自由变元B ．约束变元C ．既是自由变元，又是约束变元D ．既不是自由变元，又不是约束变元6．设A={1，2，3}，A 上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S 是（ ）A ．自反关系B ．反自反关系C ．对称关系D ．传递关系7．设集合X 为人的全体，在X 上定义关系R 、S 为R={<a ，b|a ，b ∈X ∧a 是b 的父亲}，S={<a ，b>|a ，b∈X ∧a 是b 的母亲}，那么关系{<a ，b>|a ，b ∈x ∧ a 是b 的祖母}的表达式为（ ）A ．R SB ．R -1 SC ．S RD ．R S -18．设A 是正整数集，R={(x ，y)|x ，y ∈A ∧x+3y=12}，则R ∩ ({2，3，4，6}×{2，3，4，6})=（ ）A ． O /B ．{<3，3>}C ．{<3，3>，<6，2>}D ．{<3，3>，<6，2>，<9，1>}9．下列式子不正确的是（ ）A ．(A-B)-C=(A-C)-BB ．(A-B)-C=A-(B ∪C)C ．(A-B)-C=(A-C)-(B-C)D ．A-(B ∪C)=(A-B)∪ C 10．下列命题正确的是（ ）A ．{l ，2}⊆{{1，2}，{l ，2，3}，1}B ．{1，2}⊆{1，{l ，2}，{l ，2，3}，2}C ．{1，2}⊆{{1}，{2}，{1，2}}D ．{1，2}∈{1，2，{2}，{l ，2，3}}11．在下列代数系统中，不是环的只有（ ）A ．<Z ，+，*)，其中Z 为整数集，+，*分别为整数加法和乘法。

xx年4月自学考试自考全国离散数学历年试卷试题真题专注于收集各类历年试卷和答案更多试卷答案下载试听网校课程全国xx年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．下列命题公式中不是重言式的是．A．p→(q→r) C．p →(p→p)2．下列语句中为命题的是 A．这朵花是谁的？ C．这朵花是你的吗？B．这朵花真美丽啊！ D．这朵花是他的。

B．p→(q→p)D．(p→(q→r))(q→(p→r))3．设个体域是整数集，则下列命题的真值为真的是A．yx(x·y=1) C．xy (x·y=y)2B．xy (x·y≠0) D．yx(x·y=x)24．关于谓词公式(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是．．A．的辖域是∧Q(y,z)） B．z是该谓词公式的约束变元 C．的辖域是PD．x是该谓词公式的约束变元5．设论域D={a,b}，与公式xA等价的命题公式是 A．A ∧A C．A∨AB．A→A D．A→A6．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是1A．?0??0?1?C．?0??10101101??0 ?1??0??1 ?1 1?B．?0??1?1?D．?1??10100111??0 ?1??0??0 ?1?? 1 专注于收集各类历年试卷和答案7．设A={?}，B=P），以下不正确的式子是．A．{{? }，{{? }}，{? ，{? }}}包含于B C．{{? ，{? }}}包括于B B．{{{? }}}包含于BD．{{? }，{{? ，{? }}}}包含于B8．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，f=2x，则f A．仅是满射 C．是双射B．仅是入射 D．无逆函数9．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，-1-1〈3，1〉，〈4，2〉}，则S?R的运算结果是A．{〈4，1〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉}B．{〈2，4〉，〈2，3〉，〈4，2〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是 A．矛盾式 C．可满足式B．重言式 D．公式p∧q11．在实数集合R上，下列定义的运算中不可结合的是．A．a*b=a+b+2ab C．a*b=a+b+abB．a*b=a+b D．a*b=a-b12．下列集合关于所给定的运算成为群的是A．已给实数a的正整数次幂的全体，且a?{0，1，-1}，关于数的乘法 B．所有非负整数的集合，关于数的加法 C．所有正有理数的集合，关于数的乘法 D．实数集，关于数的除法13．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是 A．3 C．5B．4 D．614．下列各图中既是欧拉图，又是汉密尔顿图的是2专注于收集各类历年试卷和答案A．B．C．D． 15．设无向图G的边数为m，结点数为n，则G是树等价于 A．G连通且m=n+1 C．G连通且m=2nB．G连通且n=m+1D．每对结点之间至少有一条通路二、填空题请在每小题的空格中填上正确答案。