证明具有6个顶点12条边的连通平面简单图.

离散数学（1）复习题一、单项选择题1、下列命题正确的是（ A ）。

A. φ⋂{φ}=φB. φ⋃{φ}=φC. {a}∈{a，b，c}D. φ∈{a，b，c}2、设集合｛1 2 3 4 ｝，A上的关系R=｛（1 1）（2 3）（2 4）（3 4）｝则R具有（ B ）。

A. 自反性B. 传递性C. 对称性D. 以上答案都不对3、设Z是整数集，函数f定义为：Z Z→, f(x)=|x|-2x,则f是（ A ）。

A. 单射B. 满射C. 双射D. 非单射也非满射4、设R为实数集，定义R上4个二元运算，不满足结合律的是（ B ）。

A. f1(x,y)= x+y B. f2(x,y)=x-yC. f3(x,y)=xy D. f4(x,y)=max{x,y}5、设(A,≤) 是一个有界格，它也是有补格，只要满足（ B ）。

A. 每个元素都有一个补元B. 每个元素至少有一个补元C. 每个元素都无补元D. 每个元素都有多个补元6、图G和'G的结点和边分别存在一一对应关系是G和'G同构的（ B ）。

A. 充分条件B. 必要条件C. 充要条件D. 既不充分也不必要条件7、集合上A的等价关系R，其等价类集合{ [a] 天津大学考试题库及答案R| a∈A }称为（ C ）。

A. A与R的并集，记作A Y RB. A与R的交集，记作A I RC. A关于R的商集，记作A/RD. A与R的差集，记作A—R8、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ C ）。

A. 2B. 3C. 4D. 59、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。

A. 析取范式B. 合取范式C. 主析取范式D. 以上答案都不对10、设谓词():Q x x犯错误，命题“没有不犯错误的人”符号化为P x x是人，():（ D ）。

A. (()())⌝∃→⌝x P x Q x ∀∧ B. (()())x P x Q xC. (()())⌝∃∧⌝x P x Q x ⌝∃∧ D. (()())x P x Q x11、设 |A|=m，|B|=n，则 |ρ(A×B) | 等于（ C ）。

常熟理工学院20 ～20 学年第学期《离散数学》考试试卷（试卷库01卷）试题总分： 100 分考试时限：120 分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1.下列表达式正确的有( )（A）（B）（C）（D）2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。

（A）（B）（C）（D）3.集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y A}，则R 的性质为( )（A）自反的（B）对称的（C）传递的，对称的（D）传递的4.设，，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是( )（A）<0，0> （B）<0，1> （C）<1，0> （D）<1，1>5.下图中既不是Eular图，也不是Hamilton图的图是( )6.设为无向图，，则G一定是( )（A）完全图（B）树（C）简单图（D）多重图7.设P：我将去镇上,Q：我有时间。

命题“我将去镇上,仅当我有时间”符号化为（）。

（A） P Q （B）Q P （C）P Q （D）8.在有n个结点的连通图中,其边数（）（A）最多有n-1条（B）最多有n 条（C）至少有n-1条（D）至少有n条9.设A－B＝,则有（）（A）B＝（B）B（C）A B （D）A B10.设集合A上有3个元素,则A上的不同的等价关系的个数为（）（A）5 （B）7 （C）3 （D）6二、填空题（每题2分，共20分）1．n个命题变元组成的命题公式共有种不同的等价公式。

2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。

3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。

4．设T是一棵树，则T是一个连通且的图。

《离散数学》第四部分---图论练习题答案一、选择或填空1、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图(2) 树(3) 平面图(4) 连通图答：(4)2、下面给出的集合中，哪一个是前缀码？( )(1) {0，10，110，101111} (2) {01，001，000，1}(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}答：（2）3、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次4、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。

答：以v为起点的边的条数，以v为终点的边的条数5、设G是一棵树，则G 的生成树有( )棵。

(1) 0 (2) 1 (3) 2 (4) 不能确定答：16、n阶无向完全图K n 的边数是( )，每个结点的度数是( )。

答：2)1(nn, n-17、一棵无向树的顶点数n与边数m关系是( )。

8、一个图的欧拉回路是一条通过图中( )的回路。

答：所有边一次且恰好一次9、有n个结点的树，其结点度数之和是( )。

答：2n-210、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}答：(1)11、n个结点的有向完全图边数是( )，每个结点的度数是( )。

答：n(n-1),2n-212、一个无向图有生成树的充分必要条件是( )。

答：它是连通图13、设G是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

答：（3）14、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。

答：215、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

《离散数学》练习题和参考答案《离散数学》练习题和参考答案⼀、选择或填空（数理逻辑部分）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、判断下列语句是不是命题。

若是，给出命题的真值。

( )北京是中华⼈民共和国的⾸都。

(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）PQ→（2）QP?→（3）QP?（4）QP→8、设个体域为整数集，则下列公式的意义是( )。

(1) ?x?y(x+y=0) (2) ?y?x(x+y=0)答：（1）对任⼀整数x存在整数 y满⾜x+y=0（2）存在整数y对任⼀整数x满⾜x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( )(3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) ⾃然数(2) 实数 (3) 复数(4) (1)--(3)均成⽴答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

1：什么是欧拉路？如何用欧拉路判定一个图G是否可一笔画出？给定无孤立点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；如果一个图有欧拉路，则这个图能一笔画出。

2：什么是汉密尔顿图？请找出一个无向图具有汉密尔顿路的充分条件。

给定图G，若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作汉密尔顿回路，如果一个图有汉密尔顿回路，则这个图是汉密尔顿图。

一个无向图具有汉密尔顿路的充分条件：设G具有n个结点的简单图，如果G中每一对结点的度数之和大于等于n-1，则在G 中存在一条汉密尔顿路。

3：什么是图的正常着色？简述韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法。

图G的正常着色(或简称为着色)是指对它的每一个结点指定一种颜色，使得没有两个相邻的结点有同一种颜色。

韦尔奇·鲍威尔法(Welch Powell)对图进行着色的方法：⑴将图G的结点按照度数的递减次序进行排列。

(这种排列可能并不是唯一的，因为有些点有相同的度数)。

⑵用第一种颜色对第一点进行着色，并且按排列次序，对前面着色点不邻接的每一点着上同样的颜色。

⑶用第二种颜色对尚未着色的点重复⑵，用第三种颜色继续这种做法，直到所有的点全部着上色为止。

4：什么是平面图？平面图的一个重要性质是欧拉定理，请写出欧拉定理。

设G＝〈V，E〉是一个无向图，如果能够把G的所有结点和边画在平面上，且使任何两条边除了端点外没有其它的交点，就称G是一个平面图。

平面图有一个重要性质是欧拉定理：设有一个连通平面图G，共有v个结点e条边r块面，则欧拉公式 v-e+r＝2 成立。

5：请给出树的至少5个等价的定义。

（每个1分，写对5个以上给满分，）给定树T，以下关于树的定义是等价的：⑴无回路的连通图；⑵无回路且e=v-1，其中e为边数，v为结点数；⑶连通且e=v-1；⑷无回路且增加一条新边，得到一个且仅一个回路；⑸连通且删去任何一个边后不连通；⑹每一对结点之间有一条且仅一条路。

1.证明永真公式Q14,Q15,Q16,Q17和Q18。

2.证明P(x)∧任意xQ(x)==>存在x(P(x)∧Q(x))3.设论述域是{a1,a2,a3,…an},试证明下列关系式。

(a) 任意xA(x)∧P<==>任意x(A(x)∧P)(b) 任意x(A(x)∧B(x))<==>任意xA(x)∧任意xB(x)(c) 存在x(A(x)∧B(x))<==>存在xA(x)∧存在xB(x)4.证明下列关系式(a) 任意x任意y(P(x)∨P(y))<==>任意xP(x)∨任意yP(y)(b) 存在x存在y(P(x)∧Q(y))==>存在xP(x)(c) 任意x任意y(P(x)∧Q(y))<==>任意xP(x)∧任意yQ(y)(d) 存在x存在y(P(x)－＞P(y)) <==>任意xP(x)－＞存在yP(y)(e) 任意x任意y(P(x) －＞Q(y)) <==>(存在xP(x)－＞任意yQ(y))5.写出limf(x)=k的定义的符号形式，并用形成定理两边的否定的方法，找出limf(x)不等x->c x->c于k的条件。

6.给定自然数集合N的下列子集：A={1,2,7,8}B={i|i平方<50}C={i|i可被30整除}D={i|i=2的k次方∧k∈I∧0≤k≤6}求下列集合(a)A∪(B∪(C∪D))(b)A∩(B∩(C∩D))(c)B-(A∪C)(d)(非A∩B) ∪D7.假定A≠空集和A∪B=A∪C，证明这不能得出B=C，假设中增加A∩B=A∩C，你能得出B=C吗？8．(a)证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使A-B≠B-A。

(b)A-B=B-A可能吗？刻划上式出现的全部条件。

(c)“相对补”是一个可结合的运算马？证明你的断言。

9.证明下列恒等式(a)A∪(A∩B)=A(b)A∩(A∪B)=A(c)A-B=A∩非B(d)A∪(非A∩B)=A∪B(e)A∩(非A∪B)=A∩B10.设Sn={a0,a1,…,an}和Sn+1={a0,a1, …,an,an+1},试用p(Sn)和an+1表达出p(Sn+1)。

《离散数学》试题带答案一、填空 20% （每小题2分）1、 P ：你努力，Q ：你失败。

“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为 。

2、论域D={1，2}，指定谓词P则公式x ∃∀真值为 。

2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。

3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R=（列举法）。

R 的关系矩阵M R =。

5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ；A 上既是对称的又是反对称的关系R= 。

6、设代数系统<A ，*>，其中A={a ，b ，c},则幺元是 ；是否有幂等 性 ；是否有对称性 。

群或 群。

8、下面偏序格是分配格的是 。

9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。

10、公式R Q P Q P P ⌝∧∨⌝∧∧⌝∨)(())((的根树表示为。

二、选择 20% （每小题2分）1、在下述公式中是重言式为（ ）A ．)()(Q P Q P ∨→∧；B ．))()(()(P Q Q P Q P →∧→↔↔；C ．Q Q P ∧→⌝)(；D ．)(Q P P ∨→。

2、命题公式 )()(P Q Q P ∨⌝→→⌝ 中极小项的个数为（ ），成真赋值的个数为（ ）。

A ．0；B ．1；C ．2；D ．3 。

3、设}}2,1{},1{,{Φ=S ，则 S2 有（ ）个元素。

A ．3；B ．6；C ．7；D ．8 。

4、 设} 3 ,2 ,1 {=S ，定义S S ⨯上的等价关系},,,, | ,,,{c b d a S S d c S S b a d c b a R +=+⨯>∈<⨯>∈<><><<=则由 R 产 生的S S ⨯上一个划分共有（ ）个分块。

单项选择题第一章第二章1. 下列表达式正确的有( )A. Q Q P ⇒ → ⌝ ) (B.P Q P ⇒∨ C .P Q P Q P ⇔⌝∧∨∧)()( D.T Q P P ⇔→→)(2. 下列推理步骤错在( )①))()((x G x F x →∀P ②)()(y G y F →US① ③)(x xF ∃P ④)(y FES③ ⑤)(y GT②④I ⑥)(x xG ∃ EG⑤A.②B.④C.⑤D.⑥3. 设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，下列( )命题的真值为真。

A.R Q P ∧→B.S P R ∧→C.R Q S ∧→D.)()(S Q R P ∧∨∧4. 下列公式中哪些是永真式？( )A.(┐P ∧Q )→(Q→⌝R)B.P→(Q→Q)C.(P ∧Q)→PD.P→(P ∧Q)5. 下列等价关系正确的是( )A.)()())()((x xQ x xP x Q x P x ∀∨∀⇔∨∀ B .)()())()((x xQ x xP x Q x P x ∃∨∃⇔∨∃C.Q x xP Q x P x →∀⇔→∀)())((D.Q x xP Q x P x →∃⇔→∃)())((6. 下列推导错在( )①)(y x y x >∃∀P ②)(y z y >∃US① ③z z >ES② ④)(x x x >∀ UG③A.②B. ④ C . ③ D.无7. 若公式)()(R P Q P ∧⌝∨∧的主析取范式为111110011001m m m m ∨∨∨则它的主合取范式为( )A.111110011001m m m m ∧∧∧B.101100010000M M M M ∧∧∧ ；C.111110011001M M M M ∧∧∧D.101100010000m m m m ∧∧∧ 。

8. 在下述公式中不是重言式为( )A ．)()(Q P Q P ∨→∧B ．))()(()(P Q Q P Q P →∧→↔↔C ．Q Q P ∧→⌝)(D ．)(Q P P ∨→9. 下列各式中哪个不成立( )A.)()())()((x xQ x xP x Q x P x ∀∨∀⇔∨∀B.)()())()((x xQ x xP x Q x P x ∃∨∃⇔∨∃C .)()())()((x xQ x xP x Q x P x ∀∧∀⇔∧∀ D.Q x xP Q x P x ∧∀⇔∧∀)())((10.命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x 是聪明的，M(x)：x 是人）( )A.)))()((())()((x P x M x x P x M x →∀⌝∧→∃B.)))()((())()((x P x M x x P x M x ∧∀⌝∧∧∃C.)))()((())()((x P x M x x P x M x →∀⌝∧∧∃D.)))()((())()((x P x M x x P x M x →∀⌝∨∧∃11.下述命题公式中，是重言式的为( )A.)()(q p q p ∨→∧B.q p ∨))()((p q q p →∨→⇔C.q q p ∧→⌝)(D.q q p →⌝∧)(12.谓词公式)())()((x Q y yR x P x →∃∨∀中的x 是( )A.自由变元B.约束变元C.既是自由变元又是约束变元D.既不是自由变元又不是约束变元13.命题“有的人喜欢所有的花”的逻辑符号化为( )设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢yA. ))),()(()((y x H y F y x M x →∀→∃B.))),()(()((y x H y F y x M x →∀∧∀C. ))),()(()((y x H y F y x M x →∀→∀D.))),()(()((y x H y F y x M x →∀∧∃14.下列等价式成立的有( )A.Q P Q P ⌝→⌝⇔→B.R R P P ⇔∧∨)(C.Q Q P P ⇔→∧)(D.R Q P R Q P →∧⇔→→)()(15.给定公式)()(x xP x xP ∀→∃，当D={a,b}时，解释( )使该公式真值为0。

第七章 图的基本概念一、 单项选择题1. 设V ＝{a,b,c,d},与V 能构成强连通图的边集E ＝(A ) (A) {<a,b>,<a,c>,<d,a>,<b,d>,<c,d>} (B) {<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}(C) {<a,c>,<b,a>,<b,c>,<d,a>,<d,c>} (D) {<a,d>,<b,a>,<b,d>,<c,d>,<d,c>} 2. n 阶无向完全图K n 中的边数为（ A ）(A)2)1(-n n (B) 2)1(+n n (C) n (D)n(n+1) 3. 给定无向图G 图5－1所示，下面给出的顶点集子集中，不是点割集的为（A ） (A) {b,d} (B) {d} (C) {a,c} (D) {g,e} 4. 下列数组中，不能构成无向图的度数列的数组是( B ) (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)5. 图 中 从v 1到v 3长度为3 的通路有（4）条。

A ． 0；B ． 1；C ． 2；D ． 3。

v 1到v 3长度为3 的通路: V 1V 3V 1V 3 ; V 1V 1V 1V 3 ; V 1V 4V 1V 3 ; V 1V 1V 4V 3 ; 6．给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（ B ）。

A 、},,,{4341><><v v v v ；B 、},,,{6451><><v v v v ；C 、},,,{8474><><v v v v ；D 、},,,{3221><><v v v v。