2017离散数学问题详解(1--5)

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

第十四章部分课后习题参考答案5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3,问G至少有多少个顶点？在最少顶点的情况下，写出度数列、厶(G)、.(G)。

解：由握手定理图G的度数之和为：2 10=203度与4度顶点各2个，这4个顶点的度数之和为14度。

其余顶点的度数共有6度。

其余顶点的度数均小于3,欲使G的顶点最少，其余顶点的度数应都取2,所以，G至少有7个顶点,出度数列为3,3,4,4,2,22 .1(G) = 4「(G) = 2 .7、设有向图D的度数列为2, 3, 2, 3,出度列为1, 2，1，1，求D的入度列，并求厶(D),、：(D)，：(D)「.(D),.厂(D),解：D的度数列为2, 3, 2, 3,出度列为1, 2, 1, 1, D的入度列为1,1,1,2..：(D) =3,、(D) =2, ：(D) =2,、• (D) = 1,.厂(D) = 2,、_(D) = 18设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G的度数之和为：2 6=12设2度点x个，则3 1 5 1 2x =12 , x=2，该图有4个顶点.14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。

(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化；⑵2 + 2+2+2+3+3+4+4=16,是偶数，可图化；18、设有3个4阶4条边的无向简单图G1、G2、G3,证明它们至少有两个是同构的。

证明：4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列为2, 2, 2, 2;3, 2, 2, 1; 3, 3, 1, 1。

但3, 3, 1, 1对应的图不是简单图。

所以从同构的观点看，4阶4条边的无向简单图只有两个：所以，G i 、G 2、G 3至少有两个是同构的。

第一章集合论基础§ 1.1基本要求1.掌握集合、子集、超集、空集、幕集、集合族的概念。

懂得两个集合间相等和包含关系的泄义和性质，能够利用泄义证明两个集合相等。

熟悉常用的集合表示方法。

2.掌握集合的基本运算：并、交、余、差、直乘积、对称差的左义以及集合运算满足的基本算律，能够利用它们来证明更复杂的集合等式。

3.掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：自反性、对称性、反对称性、传递性。

会做关系的乘积。

了解关系的闭包运算：自反闭包、对称闭包、传递闭包。

4.掌握等价关系、等价类、商集的概念，了解等价关系和划分的在联系。

5.掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、小确界的左义。

能画岀有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。

6.掌握映射、映像、1-1映射等概念，会做映射的乘枳。

了解可数集合的槪念，掌握可数集合的判定方法。

7.了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。

§ 1.2主要解题方法1.2.1证明集合的包含关系方法一.用泄义来证明集合的包含关系是最常用也是最基本的一种方法。

要证明ACB,首先任取xeA,再演绎地证出xeB成立。

由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。

当A是无限集时，因为我们不能对xwA,逐一地证明xeB成立，所以证明时的假设“x是任取的” 就特别重要。

例121设A, B, C, D是任意四个非空集合，若ACC, BCD,则AxBcCxDo证明：任取(x, y) e AxBt 往证(x, y) e CxD°由(x, y) e AxB 知，xe A, K ye Bo 又由AcC, BcD 知，xeC,且ye D,因此，(Xt y) e CxDo 故，AxBcCxDo方法二.还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质ACB<=> AnB=A <=> AuB=B以及一些已经证岀的集合等式。

离散数学证明题解题方法离散数学是现代数学的一个主要分支，是计算机科学中基础理论的中心课程。

离散数学以研讨离散量的结构和彼此间的联系为主要方针，其研讨对象一般地是有限个或可数个元素，因而他充分描绘了计算机科学离散性的特色。

1、界说和定理多。

离散数学是建立在很多界说上面的逻辑推理学科。

因而对概念的了解是咱们学习这门学科的中心。

在这些概念的基础上，格外要注意概念之间的联络，而描绘这些联络的实体则是很多的定理和性质。

●证实等价联系：即要证实联系有自反、对称、传递的性质。

●证实偏序联系：即要证实联系有自反、反对称、传递的性质。

(特殊联系的证实就列出来两种，要证实剩余的几种只需要联系界说来进行)。

●证实满射：函数f：XY，即要证实关于恣意的yY，都有x或许关于恣意的f(x1)=f(x2)，则有x1=x2。

●证实调集等势：即证实两个调集中存在双射。

有三种情况：榜首、证实两个详细的调集等势，用结构法，或许直接结构一个双射，或许结构两个调集彼此间的入射;第二、已知某个调集的基数，假如为?，就设它和R之间存在双射f，然后通过f的性质推出别的的双射，因而等势;假如为?0，则设和N之间存在双射;第三、已知两个调集等势，然后再证实别的的两个调集等势，这时，先设已知的两个调集存在双射，然后依据剩余题设条件证实要证的两个调集存在双射。

●证实群：即要证实代数系统关闭、可联系、有幺元和逆元。

(相同，这一有些能够作为证实题的概念更多，要联系界说把它们全部搞透彻)。

●证实子群：尽管子群的证实定理有两个，但假如考证实子群的话，一般是第二个定理，即设是群，S是G的非空子集，假如关于S中的恣意元素a和b有a*b-1是的子群。

关于有限子群，则可考虑榜首个定理。

●证实规范子群：若是一个子群，H是G的一个子集，即要证实关于恣意的aG，有aH=Ha，或许关于恣意的hH，有a-1 *h*aH。

这是最常见的标题中所使用的办法。

●证实格和子格：子格没有条件，因而和证实格相同，证实调集中恣意两个元素的最大元和最小元都在调集中。

2017离散数学答案(1--5)02任务_0001试卷总分：100 测试时间：0单项选择题一、单项选择题（共10 道试题，共100 分。

）1. 设集合A = {1, a }，则P(A) = ( )．A. {{1}, {a}}B. {,{1}, {a}}C. {{1}, {a}, {1, a }}D. {,{1}, {a}, {1, a }}2. 集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, y A}，则R的性质为（）．A. 不是自反的B. 不是对称的C. 传递的D. 反自反3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )．A. {a，{a}}AB. {1，2}AC. {a}AD. A4.设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1,3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）．A. f◦gB. g◦fC. f◦fD. g◦g5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包．A. 自反B. 传递C. 对称D. 自反和传递6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )．A. A B，且A BB. B A，且A BC. A B，且A BD. A B，且A B7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集<A，≤>上的元素5是集合A的（）．A. 最大元B. 最小元C. 极大元D. 极小元8. 若集合A的元素个数为10，则其幂集的元素个数为（）．A. 1024B. 10C. 100D. 19. 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A. 0B. 2C. 1D. 310. 设集合A={a}，则A的幂集为( )．A. {{a}}B. {a，{a}}C. {，{a}}D. {，a}02任务_0002试卷总分：100 测试时间：0单项选择题一、单项选择题（共10 道试题，共100 分。

02任务_0001试卷总分：100 测试时间：0单项选择题一、单项选择题（共10 道试题，共100 分。

）1. 设集合A = {1, a }，则P(A) = ( )．A. {{1}, {a}}B. {,{1}, {a}}C. {{1}, {a}, {1, a }}D. {,{1}, {a}, {1, a }}2. 集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, y A}，则R的性质为（）．A. 不是自反的B. 不是对称的C. 传递的D. 反自反3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )．A. {a，{a}}AB. {1，2}AC. {a}AD. A4.设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1,3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）．A. f◦gB. g◦fC. f◦fD. g◦g5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包．A. 自反B. 传递C. 对称D. 自反和传递6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )．A. A B，且A BB. B A，且A BC. A B，且A BD. A B，且A B7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集<A，≤>上的元素5是集合A的（）．A. 最大元B. 最小元C. 极大元D. 极小元8. 若集合A的元素个数为10，则其幂集的元素个数为（）．A. 1024B. 10C. 100D. 19. 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A. 0B. 2C. 1D. 310. 设集合A={a}，则A的幂集为( )．A. {{a}}B. {a，{a}}C. {，{a}}D. {，a}02任务_0002试卷总分：100 测试时间：0单项选择题一、单项选择题（共10 道试题，共100 分。