离散数学试题(十五套)

《离散数学》试题及答案一、选择题（每题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”互为逆否命题的是_________。

离散期末考试题一、选择题（每题3分，共30分）1. 在离散数学中，以下哪个概念用于描述两个集合之间的一一对应关系？A. 并集B. 交集C. 映射D. 子集2. 以下哪个命题的否定是正确的？A. 如果今天是周一，那么明天是周二。

B. 如果下雨，那么地面会湿。

C. 如果x > 0，则x² > 0。

D. 所有的鸟都会飞。

3. 在图论中，一个连通图是指图中任意两个顶点之间都存在一条路径。

以下哪个选项描述的不是连通图？A. 完全图B. 树C. 环D. 星形图4. 以下哪个逻辑运算符表示逻辑“或”？A. ∧B. ∨C. ¬D. →5. 在集合论中，以下哪个符号表示集合的差集？A. ∪B. ∩C. -D. ×6. 以下哪个命题是永真命题？A. p ∧ ¬pB. p ∨ ¬pC. p → ¬pD. ¬(p → ¬p)7. 在关系R中，如果对于任意的a, b ∈ A，都有(a, b) ∈ R和(b,a) ∈ R，则称R是对称的。

以下哪个关系不是对称的？A. 等价关系B. 子集关系C. 整除关系D. 朋友关系8. 在命题逻辑中，以下哪个等价于“p且q”？A. ¬p ∨ ¬qB. p ∧ qC. ¬p → ¬qD. ¬(p → ¬q)9. 在图论中，以下哪个术语描述的是一个图中没有环的子图？A. 路径B. 连通图C. 树D. 环10. 在集合论中，以下哪个符号表示集合的笛卡尔积？A. ×B. ∪C. ∩D. -二、填空题（每题2分，共20分）11. 如果集合A有n个元素，那么集合A的子集个数是________。

12. 在逻辑中，一个命题的________是当原命题为真时，它为假；当原命题为假时，它为真的命题。

13. 如果一个图的每个顶点的度数都是偶数，则该图一定存在________。

离散数学考试题及答案一、单项选择题（每题2分，共10分）1. 在集合{1,2,3}和{3,4,5}的笛卡尔积中，元素(3,4)属于（）。

A. {1,2,3}B. {3,4,5}C. {1,2,3,4,5}D. {1,2,3}×{3,4,5}答案：D2. 命题“若x>2，则x>1”的逆否命题是（）。

A. 若x≤2，则x≤1B. 若x≤1，则x≤2C. 若x≤1，则x≤2D. 若x≤2，则x≤1答案：C3. 函数f: A→B的定义域是集合A，值域是集合B的（）。

A. 子集B. 真子集C. 任意子集D. 非空子集答案：D4. 以下哪个图是无向图（）。

A. 有向图B. 无向图C. 完全图D. 树答案：B5. 以下哪个命题是真命题（）。

A. 所有的马都是白色的B. 有些马是白色的C. 没有马是白色的D. 以上都不是答案：B二、填空题（每题2分，共10分）6. 集合{1,2,3}的子集个数为______。

答案：87. 命题“若x>0，则x>1”的逆命题是：若x>1，则______。

答案：x>08. 函数f: A→B中，若A={1,2}，B={3,4}，则f的值域可以是{3}或{4}或{3,4}，但不能是______。

答案：{1,2}9. 在有向图中，若存在从顶点A到顶点B的有向路径，则称A到B是______的。

答案：可达10. 命题逻辑中，合取（AND）的符号是______。

答案：∧三、解答题（每题15分，共30分）11. 证明：若p∧q为真，则p和q都为真。

证明：根据合取（AND）的定义，p∧q为真当且仅当p和q都为真。

因此，若p∧q为真，则p和q都为真。

12. 给定函数f: A→B，其中A={1,2,3}，B={4,5,6}，且f(1)=4，f(2)=5，f(3)=6。

请找出f的值域。

答案：根据函数的定义，f的值域是其所有输出值的集合。

因此，f的值域为{4,5,6}。

数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。

C．2是偶数。

D．铅球是方的。

2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。

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

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

3．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为。

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

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

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

8．图的补图为。

9．设A={a，b，c，d} ，A上二元运算如下：* a b cda bcda b cdb c dac d abd a bc那么代数系统<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 上的二元关系有（ ）个。

A ． 23 ；B ． 32 ；C ． 332⨯；D ． 223⨯。

4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ）A ．若R ，S 是自反的， 则S R 是自反的；B ．若R ，S 是反自反的， 则S R 是反自反的；C ．若R ，S 是对称的， 则S R 是对称的；D ．若R ，S 是传递的， 则S 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是负数”的否定是（）。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）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） 不是 （命题必须满足是陈述句，不能是疑问句或者祈使句。

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

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

3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 。

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

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

8．图的补图为 。

二、选择 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 上的二元关系有（ ）个。

A ． 23 ；B ． 32 ；C ． 332⨯；D ． 223⨯。

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

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则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}}7、下列函数是双射的为（ ）A ．f : I →E , f (x) = 2x ；B ．f : N →N ⨯N, f (n) = <n , n+1> ；C ．f : R →I , f (x) = [x] ；D ．f :I →N, f (x) = | x | 。

离散数学试题及答案一、选择题（每题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. 简述命题逻辑中的德摩根定律，并给出一个例子。

离散数学试题与答案试卷一一、填空20% （每小题2分）1．设}7|{)},5()(|{<∈=<∈=+xExxBxNxxA且且（N：自然数集，E+正偶数）则=⋃BA{0，1，2，3，4，6} 。

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

3．设P，Q 的真值为0，R，S的真值为1，则)()))(((SRPRQP⌝∨→⌝∧→∨⌝的真值= 1 。

4．公式PRSRP⌝∨∧∨∧)()(的主合取范式为)()(RSPRSP∨⌝∨⌝∧∨∨⌝。

5．若解释I的论域D仅包含一个元素，则)()(xxPxxP∀→∃在I下真值为1 。

6．设A={1，2，3，4}，A上关系图为则R2 = {<>,<a,c>,<a,d>,<b,d>,<c,d> 。

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

8．图的补图为9．设A={a，b，c，d} ，A上二元运算如下：* a b c dabcda b c db c d ac d a bd a b c那么代数系统<A，*>的幺元是 a ，有逆元的元素为a , b , c ,d，它们的逆元分别为 a , d , c , d 。

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

二、选择20% （每小题2分）1、下列是真命题的有（CD）A．}}{{}{aa⊆；B．}}{,{}}{{ΦΦ∈Φ；C．}},{{ΦΦ∈Φ；D．}}{{}{Φ∈Φ。

2、下列集合中相等的有（BC ）A．{4，3}Φ⋃；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。

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

A．23 ；B．32 ；C．332⨯；D．223⨯。

4、设R，S是集合A上的关系，则下列说法正确的是（A ）A．若R，S 是自反的，则SR 是自反的；A BCB ．若R ，S 是反自反的， 则S R 是反自反的；C ．若R ，S 是对称的， 则S R 是对称的；D ．若R ，S 是传递的， 则S R 是传递的。

离散数学试题+答案⼀、单项选择题(本⼤题共15⼩题，每⼩题1分，共15分)在每⼩题列出的四个选项中只有⼀个选项是符合题⽬要求的，请将正确选项前的字母填在题后的括号内。

1.⼀个连通的⽆向图G，如果它的所有结点的度数都是偶数，那么它具有⼀条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G是连通简单平⾯图，G中有11个顶点5个⾯，则G中的边是( )A.10B.12C.16D.143.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(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∈ZR具有的性质是A.⾃反性B.对称性C.传递性D.反⾃反性8.设A={a,b,c}，A上⼆元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A.R∪I AB.RC.R∪{〈c,a〉}D.R∩I A9.设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( )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)→BB.(?x)A(x)→BC.A(x)→BD.(?x)A(x)→(?x)B13.谓词公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中变元x( )A.是⾃由变元但不是约束变元C.既是⾃由变元⼜是约束变元D.是约束变元但不是⾃由变元14.若P：他聪明；Q：他⽤功；则“他虽聪明，但不⽤功”，可符号化为( )A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命题公式中，为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)⼆、填空题(每空1分，共20分)16.在⼀棵根树中，仅有⼀个结点的⼊度为______，称为树根，其余结点的⼊度均为______。

离散数学试题与答案试卷一3、设A={1，2，3}，则A 上的二元关系有（ c ）个。

A ． 23 ；B ． 32 ；C ． 332⨯； D ． 223⨯。

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ d ）A ．A ；B ．P(A) ；C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}试卷二试题与答案1、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 6、设 ,+ 为普通加法和乘法，则（ a ）>+< ,,S 是域。

A ．},,3|{Q b a b a x x S ∈+== B ．},,2|{Z b a n x x S ∈==C ．},12|{Z n n x x S ∈+== D ．}0|{≥∧∈=x Z x x S = N 。

1、 设R 是A 上一个二元关系，)},,,(),(|,{R b c R c a A c A b a b a S >∈<>∈<∈∧∈><=且有对于某一个试证明若R 是A 上一个等价关系，则S 也是A 上的一个等价关系。

（9分）一、 证明 46%1、（9分）（1） S 自反的A a ∈∀，由R 自反，),(),(R a a R a a >∈<∧>∈<∴，S a a >∈∴<,（2） S 对称的传递对称定义R Sa b R R b c R c a S R b c R c a S b a Ab a >∈⇒<>∈<∧>∈<⇒>∈<∧>∈<⇒>∈<∈∀,),(),(),(),(,,（3） S 传递的定义传递S Sc a R R c b R b a R c e R e b R bd R d a Sc b S b a Ac b a >∈⇒<>∈<∧>∈<⇒>∈<∧>∈<∧>∈<∧>∈<⇒>∈<∧>∈<∈∀,),(),(),(),(),(),(,,,,由（1）、（2）、（3）得；S 是等价关系。

离散数学期末考试题及答案一、单项选择题（每题2分，共20分）1. 集合{1, 2, 3}的子集个数是：A. 3B. 4C. 8D. 2^3答案：C2. 命题逻辑中，命题p∧(q∨¬p)的真值表中，真值个数为：A. 1B. 2C. 3D. 4答案：B3. 函数f: A→B中，若A={1, 2}，B={a, b}，则f是单射的必要条件是：A. |A| ≤ |B|B. |A| < |B|C. |A| = |B|D. |A| > |B|答案：B4. 以下哪个图是无向图？A. 有向图B. 无向图C. 完全图D. 树答案：B5. 在图论中，一个图的生成树是：A. 包含图中所有顶点的最小连通子图B. 包含图中所有边的最小连通子图C. 包含图中所有顶点和边的连通子图D. 包含图中所有顶点和边的无环子图答案：A6. 以下哪个命题是真命题？A. 所有偶数都是整数B. 所有整数都是偶数C. 所有奇数都是整数D. 所有整数都是奇数答案：A7. 在布尔代数中，以下哪个运算符表示逻辑与？A. ∨B. ∧C. ¬D. →答案：B8. 有限状态机中，状态的转移是由以下哪个决定的？A. 当前状态B. 输入符号C. 当前状态和输入符号D. 输出符号答案：C9. 以下哪个是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 动态规划D. 分治算法答案：A10. 在集合论中，以下哪个符号表示集合的交集？A. ∪B. ∩C. ×D. ÷答案：B二、填空题（每题2分，共20分）1. 集合{1, 2, 3}的幂集是{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}，其中包含元素个数最多的子集是_。

答案：{1, 2, 3}2. 在命题逻辑中，如果p和q都为真，则p∨q的真值为_。

答案：真3. 函数f: A→B中，若A={1, 2}，B={a, b, c}，则f是满射的必要条件是_。

院（系） 班级 学号（9位） 姓名 ———————————阅————卷————密————封————装————订————线——————————第 1 页/共 39 页常熟理工学院20 ～20 学年第 学期《离散数学》考试试卷（试卷库01卷）试题总分： 100 分 考试时限：120 分钟题号 一 二 三 四 五 总分 阅卷人 得分一、单项选择题（每题2分，共20分）1. 下列表达式正确的有( )（A ） Q Q P ⇒ → ⌝ ) ( （B ）P Q P ⇒∨（C ）P Q P Q P ⇔⌝∧∨∧)()( （D ）T Q P P ⇔→→)(2. 设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 ∧∨∧ 3. 集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y ∈A}，则R 的性质为( )（A ）自反的 （B ）对称的 （C ）传递的，对称的 （D ）传递的4. 设>=< },2,1,0{1G ，>=<},*1,0{2G ，其中 表示模3加法，*表示模2乘法，在集合21G G ⨯上定义如下运算：,,,,21G G d c b a ⨯>∈<><∀有,,,,>*>=<<∙><d b c a d c b a 称>∙⨯<,21G G 为21G G ⨯的积代数，则21G G ⨯的积代数幺元是( )（A ）<0，0>（B ）<0，1>（C ）<1，0>（D ）<1，1>5. 下图中既不是Eular 图，也不是Hamilton 图的图是( )6. 设>=<E V G ,为无向图，23,7==E V ，则G 一定是( )（A ）完全图 （B ）树 （C ）简单图 （D ）多重图7. 设P ：我将去镇上,Q ：我有时间。

《离散数学》题库与答案一、选择或填空（数理逻辑部分）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、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

《离散数学》考试试卷（试卷库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= 。

离散数学试题及答案解析一、单项选择题（每题2分，共10分）1. 集合A={1,2,3}，集合B={2,3,4}，则A∩B等于：A. {1,2,3}B. {2,3}C. {1,4}D. {3,4}答案：B2. 以下哪个命题是真命题？A. 所有天鹅都是白色的。

B. 有些天鹅不是白色的。

C. 所有天鹅都不是白色的。

D. 没有天鹅是白色的。

答案：B3. 函数f: A→B的定义域是A，值域是B，那么f是：A. 单射B. 满射C. 双射D. 既不是单射也不是满射答案：D4. 逻辑表达式(p∧q)→r的逆否命题是：A. ¬r→¬(p∧q)B. ¬r→¬p∨¬qC. r→(p∧q)D. ¬r∧¬p∨¬q答案：B5. 有限集合A={a, b, c}的子集个数为：A. 3B. 4C. 7D. 8答案：D二、填空题（每题3分，共15分）1. 如果一个关系R在集合A上是自反的，那么对于A中的每一个元素a，都有___________。

答案：(a, a)∈R2. 命题逻辑中，合取（AND）的逻辑运算符用___________表示。

答案：∧3. 在图论中，一个连通图是指图中任意两个顶点之间都存在___________。

答案：路径4. 集合{1, 2, 3}的幂集包含___________个元素。

答案：85. 如果一个函数f是单射，那么对于任意的x1, x2∈A，如果f(x1)=f(x2)，则x1___________x2。

答案：=三、解答题（每题10分，共20分）1. 证明：若p是q的充分条件，q是r的充分条件，则p是r的充分条件。

证明：假设p成立，由于p是q的充分条件，所以q成立。

又因为q是r的充分条件，所以r成立。

因此，p成立可以推出r成立，即p是r的充分条件。

2. 给定一个有向图，其中包含顶点A、B、C、D，边为(A, B)，(B, C)，(C, D)，(D, A)，(A, C)。

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

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

3．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 。

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

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

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

8．图的补图为 。

9．设A={a ，b ，c ，d} ，A 上二元运算如下：那么代数系统<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 上的二元关系有（ ）个。

A ． 23 ； B ． 32 ； C ． 332⨯； D ． 223⨯。

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

5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A p t s t s R =∧∈><=则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 : I→E , f (x) = 2x ；B．f : N→N⨯N, f (n) = <n , n+1> ；C．f : R→I , f (x) = [x] ；D．f :I→N, f (x) = | x | 。