离散数学习题集十五套答案.docx

《离散数学习题集十五套答案.docx》由会员分享，可在线阅读，更多相关《离散数学习题集十五套答案.docx（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、离散数学试题与答案试卷一一、填空 20% （每小题2分）A B C1设 （N：自然数集，E+ 正偶数） 则 。2A，B，C表示三个集合，文图中阴影局部的集合表达式为 。3设P，Q 的真值为0，R，S的真值为1，则的真值= 。4公式的主合取范式为 。5若说明I的论域D仅包含一个元素，则 在I下真值为 。6设1，2，3，4，A上关系图为则 R2 = 。7设a，b，c，d，其上偏序关系R的哈斯图为则 。8图的补图为 。9设a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。1

2、0下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分）1、下列是真命题的有（）A ； B；C ； D 。2、下列集合中相等的有（ ） A4，3；B，3，4；C4，3，3；D 3，4。3、设1，2，3，则A上的二元关系有（ ）个。 A 23 ； B 32 ； C ； D 。4、设R，S是集合A上的关系，则下列说法正确的是（ ） A若R，S 是自反的， 则是自反的； B若R，S 是反自反的， 则是反自反的； C若R，S 是对称的， 则是对称的； D若R，S 是传递的， 则是传递的。5、设1，2，3，4，P（A）（A的幂集）上规定二元系如下则P（A）/ （ ）AA ；BP(A) ；C

3、1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、设，1，1，3，1，2，3则A上包含关系“”的哈斯图为（ ）7、下列函数是双射的为（ ）Af : , f (x) = 2x ； Bf : , f (n) = ；Cf : , f (x) = x ； Df , f (x) = | x | 。（注：I整数集，E偶数集， N自然数集，R实数集）8、图 中 从v1到v3长度为3 的通路有（ ）条。A 0；B 1；C 2；D 3。9、下图中既不是图，也不是图的图是（ ）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。A1；B2；C3；D4 。三、

4、证明 26%、 R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。（8分）、 f和g都是群到的同态映射，证明是的一个子群。其中 (8分)、 ( = v， ) 是每一个面至少由k（k3）条边围成的连通平面图，则， 由此证明彼得森图（）图是非平面图。（11分）四、逻辑推演 16%用规则证明下题（每小题 8分）1、2、五、计算 18%1、设集合a，b，c，d上的关系 , , , 用矩阵运算求出R的传递闭包t (R)。 （9分）2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些干脆通信线路造价，试给出一个设计方案，使得各城市之间可以通信而且总造价最小。（分）试卷

5、二试题与答案一、填空 20% （每小题2分）1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。2、论域1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 。2、 设a1 ，a2 ，a8，是S的子集，则由B31所表达的子集是 。3、 设2，3，4，5，6上的二元关系，则 （列举法）。R的关系矩阵 。5、设1，2，3，则A上既不是对称的又不是反对称的关系 ；A上既是对称的又是反对称的关系 。*a b cabca b cb b cc c b6、设代数系统，其中a，b，c,则幺元是 ；是否有幂等

6、性 ；是否有对称性 。7、4阶群必是 群或 群。8、下面偏序格是安排格的是 。9、n个结点的无向完全图的边数为 ，欧拉图的充要条件是 。10、公式的根树表示为 。二、选择 20% （每小题2分）1、在下述公式中是重言式为（ ）A；B；C； D。2、命题公式 中微小项的个数为（ ），成真赋值的个数为（ ）。A0； B1； C2； D3 。3、设，则 有（ ）个元素。A3； B6； C7； D8 。4、 设，定义上的等价关系则由 R产 生的上一个划分共有（ ）个分块。A4； B5； C6； D9 。5、设，S上关系R的关系图为则R具有（ ）性质。A自反性、对称性、传递性； B反自反性、反对称性；C

7、反自反性、反对称性、传递性； D自反性 。6、设 为一般加法和乘法，则（ ）是域。A BC D= N 。7、下面偏序集（ ）能构成格。8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。A1； B2； C3； D4 。9、在如下各图中（ ）欧拉图。10、设R是实数集合，“”为一般乘法，则代数系统 是（ ）。A群； B独异点； C半群 。三、证明 46%1、 设R是A上一个二元关系，试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）2、 用逻辑推理证明：全部的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）3、 若是从A到B的函数，定义一个函

8、数对随意有，证明：若f是A到B的满射，则g是从B到 的单射。（10分）4、 若无向图G中只有两个奇数度结点，则这两个结点肯定连通。（8分）5、 设G是具有n个结点的无向简洁图，其边数，则G是图（8分）四、计算 14%1、 设是一个群，这里+6是模6加法，Z6=0 ，1，2，3，4，5，试求出的全部子群及其相应左陪集。（7分）2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷二答案：试卷三试题与答案一、 填空 20% （每空 2分）1、 设 f，g是自然数集N上的函数，则 。2、 设a，b，c，A上二元关系 , , , 则s（R）= 。3、 1，2，

9、3，4，5，6，A上二元关系，则用列举法 ；T的关系图为 ；T具有 性质。4、 集合的幂集= 。5、 P，Q真值为0 ；R，S真值为1。则的真值为 。6、 的主合取范式为 。7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N ()：x可以整数y。则谓词的自然语言是 。8、 谓词的前束范式为 。二、 选择 20% （每小题 2分）1、 下述命题公式中，是重言式的为（ ）。A、； B、；C、； D、。2、 的主析取范式中含微小项的个数为（ ）。A 、2； B、 3； C、5； D、0； E、 8 。3、 给定推理PPTI推理过程中错在（ ）。A、-; B、-; C、-;

10、D、-; E、-4、 设S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5，在条件下X与（ ）集合相等。A、 2或S5 ； B、4或S5；C、1，S2或S4； D、X与S1，S5中任何集合都不等。5、 设R和S是P上的关系，P是全部人的集合，则表示关系 （ ）。A、；B、；C、 ； D、。6、 下面函数（ ）是单射而非满射。A、；B、；C、；D、。其中R为实数集，Z为整数集，分别表示正实数与正整数集。7、 设1，2，3，R为S上的关系，其关系图为 则R具有（ ）的性质。A、 自反、对称、传递； B、什么性质也没有；C、反自反、反对称、传递； D

11、、自反、对称、反对称、传递。8、 设，则有（ ）。A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 设1 ,2 ,3 ，则A上有（ ）个二元关系。A、23 ； B、32 ； C、； D、。10、全体小项合取式为（ ）。A、可满意式； B、冲突式； C、永真式； D、A，B，C 都有可能。三、 用规则证明 16% （每小题 8分）1、2、四、（14%） 集合, , , ，,12 = x21 。1、 证明R是X上的等价关系。 （10分）2、 求出X关于R的商集。（4分）五、（10%）设集合 a , c , d 上关系 , , , 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算

12、求出R的传递闭包。（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数。2、（10分）设函数，证明 有一左逆函数当且仅当f是入射函数。答案：一、 填空 20%（每空2分）1、2(1)；2、；3、；4、反对称性、反自反性；4、；5、1；6、；7、随意x，假如x是素数则存在一个y，y是奇数且y整除x ；8、。二、 选择 20%（每小题 2分）题目12345678910答案CCCCABDADC三、 证明 16%(每小题8分)1、P（附加前提）TIPTITITIPTI2、 P（附加前提）TEPTI四、 14%（1） 证明：1、 自反性： 2、 对称性： 3、 传递性：即由（1）（2）（3）

13、知：R是X上的先等价关系。2、五、 10%1、； 关系图2、 t (R)= , , , , , , , , 。 六、 20%1、（1）（2）。2、证明：。试卷四试题与答案一、 填空 10% （每小题 2分）1、 若P，Q，为二命题，真值为0 当且仅当 。2、 命题“对于随意给定的正实数，都存在比它大的实数”令F(x)：x为实数，则命题的逻辑谓词公式为 。3、 谓词合式公式的前束范式为 。4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的局部不变，这种方法称为换名规则。5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为

14、。二、 选择 25% （每小题 2.5分）1、 下列语句是命题的有（ ）。A、 明年中秋节的晚上是晴天； B、；C、当且仅当x和y都大于0； D、我正在说谎。2、 下列各命题中真值为真的命题有（ ）。A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；C、2+24当且仅当3是奇数； D、2+24当且仅当3不是奇数；3、 下列符号串是合式公式的有（ ）A、；B、；C、；D、。4、 下列等价式成立的有（ ）。A、；B、；C、 ； D、。5、 若和B为，且则（ ）。A、称为B的前件； B、称B为的有效结论C、当且仅当；D、当且仅当。6、 A，B为二合式公式，且，则（ ）。A、为重言式

15、； B、；C、； D、； E、为重言式。7、 “人总是要死的”谓词公式表示为（ ）。（论域为全总个体域）M(x)：x是人；(x)：x是要死的。A、； B、C、；D、8、 公式的说明I为：个体域2，P(x)：x3, Q(x)：4则A的真值为（ ）。A、1； B、0； C、可满意式； D、无法断定。9、 下列等价关系正确的是（ ）。A、；B、；C、；D、。10、 下列推理步骤错在（ ）。PPTIA、；B、；C、；D、三、 逻辑推断30% 1、 用等值演算法和真值表法推断公式的类型。（10分）2、 下列问题，若成立请证明，若不成立请举出反例：（10分）（1） 已知，问成立吗？（2） 已知，问成立吗？

16、3、 假如厂方回绝增加工资，那么罢工就不会停顿，除非罢工超过一年并且工厂撤换了厂长。问：若厂方回绝增加工资，面罢工刚开场，罢工是否可以停顿。（10分）四、计算10%1、 设命题A1，A2的真值为1，A3，A4真值为0，求命题的真值。（5分）2、 利用主析取范式，求公式的类型。（5分）五、谓词逻辑推理 15%符号化语句：“有些人喜爱全部的花，但是人们不喜爱杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域a , b , c，求证：。答案：六、 填空 10%（每小题2分）1、P真值为1，Q的真值为0；2、；3、；4、约束变元；5、，y为D的某些元素。七、 选择 25%（每小题2.5分

17、）题目12345678910答案CAB(4)八、 逻辑推断 30%1、（1）等值演算法（2）真值表法P QA1 1111111 0010010 1100010 011111所以A为重言式。2、（1）不成立。若取但A与B不肯定等价，可为随意不等价的公式。（2）成立。 证明：即：所以故 。3、解：设P：厂方回绝增加工资；Q：罢工停顿；R罢工超壶过一年；R：撤换厂长前提： 结论：PPTIPTITETI罢工不会停顿是有效结论。四、计算 10%（1） 解：（2）它无成真赋值，所以为冲突式。五、谓词逻辑推理 15%解： 证明：PTITIPTITETI九、 证明10% 试卷五试题与答案一、填空15%（每空3

18、分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 个5度结点。2、n阶完全图，的点数X () = 。3、有向图 中从v1到v2长度为2的通路有 条。4、设R，+，是代数系统，假如R，+是交换群 R，是半群 则称R，+，为环。5、设是代数系统，则满意幂等律，即对有 。二、选择15%（每小题3分）1、 下面四组数能构成无向简洁图的度数列的有（ ）。A、（2，2，2，2，2）； B、（1，1，2，2，3）；C、（1，1，2，2，2）； D、（0，1，3，3，3）。2、 下图中是哈密顿图的为（ ）。3、 假如一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（ ）A、真； B、假。

19、4、 下列偏序集（ ）能构成格。5、 设，*为一般乘法，则S，*是（）。A、代数系统； B、半群； C、群； D、都不是。三、证明 48%1、（10%）在至少有2个人的人群中，至少有2 个人，他们有一样的挚友数。2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。3、（8%）证明在6个结点12条边的连通平面简洁图中， 每个面的面数都是3。4、（10%）证明循环群的同态像必是循环群。5、（12%）设是布尔代数，定义运算*为，求证B，*是阿贝尔群。四、计算22%1、在二叉树中1） 求带权为2，3，5，7，8的最优二叉树T。（5分）2） 求T对应的二元前缀码。（5分）2、 下图所示带权图中

20、最优投递路途并求出投递路途长度（邮局在D点）。答案：一、填空（15%）每空3 分1、 6；2、n；3、2；4、+对安排且对+安排均成立；5、。二、选择（15%）每小题3分题目12345答案BCD三、证明（48%）1、（10分）证明：用n个顶点v1，表示n个人，构成顶点集v1，设，无向图（V，E）现证G中至少有两个结点度数一样。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2） 若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简洁图，所以每个顶点度数都小于等于1，由于G中n顶点其度数取值只能是1，2，1，由鸽巢原理，必定至少有两个结点

21、度数是一样的。2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理冲突。因此u，v必连通。3（8分）证：612 欧拉公式2知 22-6-12=8由图论根本定理知：，而，所以必有，即每个面用3条边围成。4（10分） 证：设循环群A，的生成元为a，同态映射为f，同态像为f（A），*，于是都有对1有2, 有若1时 有对时，这说明，f(A)中每一个元素均可表示为，所以f(A),*为f(a) 生成的循环群。5、证：（1） 交换律：有 （2） 结合律：有而：（3） 幺：有（4） 逆：

22、 综上所述：B，*是阿贝尔群。四、计算（22%）1、（10分）（1）（5分）由方法,得最佳二叉树为：（2）（5分）最佳前缀码为：000，001，01，10，112、（12分） 图中奇数点为E、F ，d(E)=3(F)=3()=28 复制道路、，得图G，则G是欧拉图。由D开场找一条欧拉回路：。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=281。试卷六试题与答案一、 填空 15% （每小题 3分）1、 n阶完全图结点v的度数d(v) = 。2、 设n阶图G中有m条边，每个结点的度数不是k的是1，若G中有个k度顶点，1个1度顶点，则N k = 。3、 算式 的

23、二叉树表示为 。4、 如图给出格L，则e的补元是 。5、 一组学生，用二二扳腕子竞赛法来测定臂力的大小，则幺元是 。二、选择 15% （每小题 3分）1、设0,1,2,3,为小于等于关系，则S，是（ ）。A、群；B、环；C、域；D、格。2、设a , b , c，*为代数系统，*运算如下：*abcaabcbbaccccc则零元为（ ）。A、a； B、b； C、c； D、没有。3、如右图 相对于完全图K5的补图为（ ）。4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）4度结点。A、1； B、2； C、3； D、4。5、设A，+，是代数系统，其中+，为一般加法和乘法，则（ ）

24、时，A，+，是整环。A、； B、；C、； D、。三、证明 50%1、设G是（）简洁二部图，则。（10分）2、设G为具有n个结点的简洁图，且，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统0，1，+，的加法运算和乘法运算。如下：+0101001000110101证明它是一个环，并且是一个域。（14分）4、 是一代数格，“”为自然偏序，则L，是偏序格。（16分）四、10%设是布尔代数上的一个布尔表达式，试写出的析取范式和合取范式（10分）五、10%如下图所示的赋权图表示某七个城市及预先算出它们之间的一些干脆通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间

25、既可以通信又使总造价最小。答案：一、填空 15%（每小题3分）1、1；2、n(1)-2m；3、如右图；4、0 ；5、臂力小者二、选择 15%（每小题 3分）题目12345答案DCAAD三、证明 50%（1） 证：设（V，E）对完全二部图有当时，完全二部图的边数m有最大值故对随意简洁二部图有。（2） 证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，明显与假设冲突。所以G连通。（3） （1）0，1，+，是环0，1，+是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群： （0+0）+0=0+（0+0）=0 ；（0+0）+

26、1=0+（0+1）=1；（0+1）+0=0+（1+0）=1 ； （0+1）+1=0+（1+1）=0；（1+1）+1=1+（1+1）=0 结合律成立。 幺：幺元为0。逆：0，1逆元均为其本身。0，1，是半群乘：由“ ”运算表知封闭群： （00）0=0（00）=0 ；（00）1=0（01）= 0；（01）0=0（10）=0 ； （01）1=0（11）=0；（11）1=1（11）=0 。对+的安排律 0（）=0=0+0=(0x)+(0y)； 1（）当 ()=0 则；当（）则所以均有同理可证：所以对+ 是可安排的。由得，0，1，+，是环。（2）0，1，+，是域因为0，1，+，是有限环，故只需证明是整环

27、即可。乘交环： 由乘法运算表的对称性知，乘法可交换。含幺环：乘法的幺元是1无零因子：11=10因此0，1，+，是整环，故它是域。4、证：（1 ）“”是偏序关系， 自然偏序 反自反性：由代数格幂等关系：。反对称性： 若 即：，则 传递性：则：（2）在L中存在的下（上）确界设则：事实上：若x , y 有另一下界c，则 是x , y 最大下界，即同理可证上确界状况。四、14%解：函数表为：00000011010001111000101111011111析取范式：合取范式：五、10%解： 用库斯克（）算法求产生的最优树。算法为： 结果如图：树权C(T)=23+1+4+9+3+17=57（万元）即为总造

28、价试卷七试题与答案一、 填空 15% （每小题 3分）1. 任何() 图G = () , 边与顶点数的关系是 。2. 当n为 时,非平凡无向完全图是欧拉图。3. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有 个1度顶点。4. n阶完全图的点色数X()= 。5. 一组学生,用两两扳腕子竞赛来测定臂力大小,则幺元是 。二、 选择 15% （每小题 3分）1、下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。2、图 的邻接矩阵为( )。A、；B、；C、；D、。3、下

29、列几个图是简洁图的有( )。A. G1=(V11), 其中 V1=1=；B. G2=(V22)其中V212=,；C. (V33), 其中V313=；D. (V44),其中V414=（）,（）,（）,（）,（）。4、下列图中是欧拉图的有( )。5、，其中，为集合对称差运算，则方程的解为（ ）。A、； B、； C、； D、。三、 证明 34% 1、 证明：在至少有2 个人的人群中，至少有2 个人，他的有一样的挚友数。（8分）2、 若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）3、 证明：在6个结点12条边的连通平面简洁图中，每个面的面度都是3。（8分）4、 证明循环群的同态像必是循环群。

30、（10分）四、 中国邮递员问题13%求带权图G中的最优投递路途。邮局在v1点。五、 根树的应用 13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。六、 10%设B4=e , a , b , ，运算*如下表，*则是一个群（称作四元群答案：十、 填空 15%（每小题3分）1、；2、奇数；3、5；4、n；5、臂力小者 十一、 选择 15%（每小题 3分）题目12345答案BCBBA十二、 证明 34%1、（10分）证明：用n个顶点v1，表示n个人，构成顶点集v1，设，无向图（V，E

31、）现证G中至少有两个结点度数一样。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2） 若G中有一个孤立点，则G中的至少有3个顶点，现不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简洁图，所以每个顶点度数都小于等于1，由于G中顶点数到值只能是1，2，1这1个数，因此取1个值的n个顶点的度数至少有两个结点度数是一样的。2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理冲突。因此u，v必连通。3、（8分）证：612 欧拉公式2知 22-6-12=8由图论根本定理知：，而，所以必有，即每个面用3条边围成。4、（10分） 证：设循环群A，的生成元为a，同态映射为f，同态像为，于是都有对1有2, 有若1时 有对时，这说明，f(A)中每一个元素均可表示为，所以是以f(a) 生成元的循环群。十三、 中国邮递员问题 14%解：图中有4个奇数结点，（1） 求任两结点的最短路再找两条道路使得它们没有一样的起点和终点，且长度总和最短：（2） 在原图中复制出，设图G，则图G中每个结点度数均为偶数的图G存在欧拉回路，欧拉回路C权长为43