2016离散数学中期大作业

离散数学作业题第2章集合、关系与映射1.A⊆B，A∈B能否同时成立，说明原因求集合A＝{a，{a}}的幂集2.证明：若B⊆C，则P(B)⊆ P(C)3.如果A∪B=A∪C，是否有B=C？如果A⊕B=A⊕C，是否有B=C？4.试求1到10000之间不能被4，5或6整除的整数个数.5.列出所有从A={a,b,c}到B={s}的关系，并指出集合A上的恒等关系和从A到B的全域关系.6.给出A上的关系及其关系图和矩阵表示.{<x,y>|0≤x-y＜3} A={0，1，2，3，4}7.已知S={a,b}. R⊆ ={〈x,y〉|x,y∈A∧x⊆y∧A为集合族ρ(S)}.试写出关系R⊆.8.已知：A={a,b,c}, R={〈a,b〉,〈a,c〉,〈b,c〉}该关系具有什么性质？(自反，反自反，对称，反对称，传递性)9.设A={a,b,c},R={〈a,b〉,〈a,c〉} 计算：r(R)，sr(R)，tr(R)，str(R).10.设A是含有4个元素的集合，试求：(1)在A上可以定义多少种对称关系？(2)在A上可以定义多少种既是自反的，又是对称的关系？(3)在A上可以定义多少种既不是自反的，也不是反自反的二元关系？11.设集合A={0，1，2，3，4}. R={<x,y>|x+y=4,x,y∈A} ，S={<x,y>|y-x=1,x,y∈A}.试求：R◦S，R◦R，(R◦S)◦R，R◦(S◦R).12.证明：R是A上的传递关系⇔R◦R⊆R.13.A={1,2,3,4,5},R={<x,y>|x,y∈A∧x-y可被2整除}，试问R是否是A上的等价关系？如果是，求出R的各等价类.14.A={1,2,3,4,5},A上的划分∏={{1,2},{3,4},{5}}，给出由∏所诱导出的A上的等价关系R的集合表达式.15.试给出一个单射但非满射的函数.(对某一集合而言)16.设f：N→N×N，f(n)=<n,n+1>,则：(1)说明f是否为单射和满射，并说明理由.(2) f的反函数是否存在？并说明理由.(3)求ranf.17.已知如果从无限集合A到集合B存在单射f，则B也是无限集合。

离散数学一、填空题(本大题共48分，共16小题，每小题3分)1.--公式为之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定2.无向图G具有是生成树，当且仅当的，若G为(n,m)连通图，要确定G的一棵生成树必删掉G的条边。

3.一个无向图的欧拉回路要求经过图中一次且仅一次，汉密顿图要求经过图中一次且仅一次。

4.设P：我生病，Q：我去学校(1)命题“我虽然生病但我仍去学校”符号化为o (2)命题“只有生病的时候，我才不去学校”符号化为o (3)命题"如果我生病，那么我不去学校”符号化为o5.设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数6.若HlAH2A-AHn是 ,则称Hl, H2, -Hn是相容的，若HlAH2A-AHn是 ,则称H1.H2, -Hn是不相容的7.设f,g,h 是N 到N上的函数(N 为自然数集合),f(n)=n+l;g(n)=2n;h(n)=0；贝lj(fdg)oh=8.K5的点连通度为 ,边连通度为o9.A={1, 2, 3, 4, 5, 6, 8, 10, 24, 36}, R 是A 上的整除关系。

子B={1, 2, 3, 4},那么B的上界是； B的下界是；：6的上确界是; B的下确界为10.命题公式P-*QAR的对偶式为11.设入={1, {2}, <t>},则A的幕集有元素个。

12.设A={0, 1,2, 3}, B={4,6, 7}, C={8, 9, 12, 14}, R1 是由A 到B 的关系,R2 是由B到C原关系，分别定义为Rl={<2, 6>, <3, 4>, <0, 7>} ;R2={<4, 8>, <4, 12>, <6, 12>,〈7, 14〉},则复合关系RloR2 为：13.设A= {<i)}, B={<t>, (<!>}},贝i]P(A) nP(B)= 。

一、简要回答下列问题：（每小题3分，共30分）1．请给出集合的结合率。

答：结合律(AUB)UC=AU(BUC)x∈(AUB)UC，即 x∈AUB 或 x∈C即 x∈A 或 x∈B 或 x∈C 即 x∈A 或 x∈B∪C即 x∈AU(BUC)说明 (AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？答：不同的对称关系有：8种R = ΦR = {<1,1>}R = {<2,2>}R = {<1,1>,<2,2>}R = {<1,2>,<2,1>}R = {<1,1>,<1,2>,<2,1>}R = {<1,2>,<2,1>,<2,2>}R = {<1,1>,<1,2>,<2,1>,<2,2>}4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。

答：m0= ┐p∧┐q∧┐r m4= p∧┐q∧┐r6．什么是图中的简单路？请举一例。

答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。

7．什么是交换群，请举一例。

答：如果群〈G，*〉中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。

如〈I，+〉是交换群。

8．什么是群中右模H合同关系？答：设G是群，H是G的子群，a,b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），记为a≡b（右mod H）。

9．什么是有壹环？请举一例。

答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。

离散数学自考题真题2016年04月(总分100, 做题时间90分钟)第Ⅰ部分选择题一、单项选择题(在每小题列出的四个备选项中只有一个是符合题目要求的)1.下列命题公式为永假式的是______SSS_SINGLE_SELA ﹁(P→Q)B ﹁(P→Q)∧QC (P→Q)∨QD ﹁P∧(P→Q)该问题分值: 1答案:B[解析] 当且仅当P的真值为T，Q的真值为F时，P→Q为F，其余情况P→Q为T。

则选项A的真值可为T也可为F。

同理选项C、选项D可为F亦可为T，只有选项B在任何情况下均为F。

2.偏序关系一定不是______SSS_SINGLE_SELA 自反的B 传递的C 反自反的D 反对称的该问题分值: 1答案:C3.下列语句为复合命题的是______SSS_SINGLE_SELA 今天天气凉爽B 今天天气炎热，有雷阵雨C x+y＞16D 今天天气多好呀，外面景色多美呀该问题分值: 1答案:B[解析] 判断命题有两个条件：(1)语句本身是陈述句；(2)它有唯一的真值。

因此C、D不是命题更不是复合命题；A是简单命题；只有B是复合命题。

4.设R(x)：x是实数，L (x，y)：x＜y，语句“没有最大的实数”可符号化为______A．B．C．D．SSS_SIMPLE_SINA B C D该问题分值: 1答案:A5.下列集合关于数的加法和乘法运算不能构成环的是______SSS_SINGLE_SELA 自然数集合B 整数集合C 有理数集合D 实数集合该问题分值: 1答案:A6.5个结点的非同构的无向树的数目是______SSS_SINGLE_SELA 5B 4C 3D 2该问题分值: 1答案:C[解析] 5个结点的非同构无向树有3个，具体如下：7.设A={1，2，3，4，5，6}，为A上的整除关系，则A的最小元为______ SSS_SINGLE_SELA 1B 3C 4D 6该问题分值: 1答案:A[解析] A={1，2，3，4，5，6}，则其哈斯图为，则其最小元是1。

一．R，S是集合A上的两个关系。

试证明下列等式：（1）(R•S)-1= S-1•R-1（2）(R-1)-1= R答：（1）对∀∈(R。

S)^(-1)∈R。

S∈R ∧∈S∈S^(-1)∧∈R^(-1)∈S^(-1)。

R^(-1)（2）对∀∈(R^(-1))^(-1)∈R^(-1)∈R二、R，S是集合A上的两个关系。

试证明下列等式：（1）(R∪S)-1= R-1∪S-1（2）(R∩S)-1= R-1∩S-1（1）证相互包含:任意<x,y>∈（R∪S）^(-1),<y,x>∈（R∪S）,<y,x>∈R或者),<y,x>∈S<x,y>∈R^(-1),或者<x,y>∈S^(-1),<x,y>∈R^(-1)∪S^(-1),（R∪S）^(-1)包含于R^(-1)∪S^(-1),任意<x,y>∈R^(-1)∪S^(-1),<x,y>∈R^(-1),或者<x,y>∈S^(-1),<y,x>∈R或者,<y,x>∈S<y,x>∈（R∪S）,<x,y>∈（R∪S）^(-1),R^(-1)∪S^(-1)包含于（R∪S）^(-1),所以（R∪S）^(-1)=R^(-1)∪S^(-1),（2）任意<x,y>∈（R∩S）^(-1),<y,x>∈（R∩S）,<y,x>∈R并且,<y,x>∈S<x,y>∈R^(-1),并且<x,y>∈S^(-1),<x,y>∈（R^(-1)∩S^(-1),（R∩S）^(-1)包含于R^(-1)∩S^(-1),任意<x,y>∈R^(-1)∩S^(-1),<x,y>∈R^(-1),并且<x,y>∈S^(-1),<y,x>∈R并且,<y,x>∈S<y,x>∈（R∩S）,<x,y>∈（R∩S）^(-1),R^(-1)∩S^(-1)包含于（R∩S）^(-1),所以（R∩S）^(-1)=R^(-1)∩S^(-1),三、设R是非空集合A上的关系，如果1）对任意a∈A，都有a R a ；2）若aRb，aRc，则bRc ；对称性：已知aRa,对任意b,如果aRb,那么根据条件2有bRa.传递性：对任意a,b,c,如果aRb且bRc,那么根据对称性有bRa,再根据条件2就有aRc.四、若集合A上的关系R，S具有对称性，证明：R•S具有对称性的充要条件为R•S= S•R。

2016年秋国家开放大学《离散数学》形考2试题及答案（答案全部正确）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 分。

离散数学大作业——编程实现最小生成树学院：电子工程学院班级：021051学号：*********名：***一、最小生成树概念：设G=(V,E)是无向连通带权图，即一个网络。

E中每条边(v,w)的权为c[v,w]。

所有生成树G’上各边权的总和最小的生成树称为G的最小生成树。

二、prim算法（贪心思想）设图G =（V，E），其生成树的顶点集合为U。

1.把v0放入U。

2.在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

3.把2找到的边的v加入U集合。

如果U集合已有n个元素，则结束，否则继续执行2其算法的时间复杂度为O(n^2)三、程序源代码# include<stdio.h># include<malloc.h># define m 6# define n 11 typedef struct {int i,tag;char s;}vertice;typedef struct {int a,b,tag;int weight;}edge;vertice v[m];edge e[n];void inititate();void sort();void chuli();int biaoji( edge *s); void print();void main() {inititate();sort();chuli();print();}void inititate() {int i;printf("输入图的%d个顶点:\n",m);for(i=0;i<m;i++) {v[i].i=i+1;v[i].tag=0;scanf("%c",&v[i].s);getchar();}printf("\n输入%d条边的两端顶点及权：\n",n);for(i=0;i<n;i++) {scanf("%d %d %d",&e[i].a,&e[i].b,&e[i].weight);e[i].tag=0;}}int biaoji( edge *s) {int i,j;i=s->a;j=s->b;if(v[i].tag==0 || v[j].tag==0) {v[i].tag=1;v[i].tag=1;s->tag=1;return 1;}return 0;}void print() {int i,j=0;printf("\n最小生成树的边为：\n");for(i=0;i<n&&j<m-1;i++)if(e[i].tag==1) {printf("<%d-%d> ",e[i].a,e[i].b);j++;}printf("\n\n");}void sort() {edge s;int i,j;for(i=0;i<n-1;i++) {for(j=i+1;j<n;j++) {if(e[i].weight>e[j].weight) {s=e[i];e[i]=e[j];e[j]=s;}}}}void chuli() {int i,j=0;edge *s;for(i=0;i<n&&j<m;i++) {s=&e[i];if(biaoji(s)==1)j++;}}四、实验结果输入图的6个顶点:1 2 3 4 5 6输入11条边的权及两端顶点：1 2 11 4 61 6 91 3 112 3 22 4 33 5 83 6 74 5 104 6 45 6 5最小生成树的边为：<1-2> <2-3> <2-4> <4-6> <5-6> Press any key to continue。

离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。

许多应用问题都是一个求无向连通图的最小生成树问题。

例如寻找在城市之间铺设光缆的最好方案问题等等。

解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法。

本文中使用了kruskal算法（避圈法）实现寻找赋权图的最小生成树问题。

概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。

离散数学导论大作业---------最小生成树一 问题描述：求下图的最小生成树二，问题求解 用Kruskal 算法求解上述问题1. Kruskal 的算法描述如下：K r u s k a l 算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。

注意到所选取的边若产生环路则不可能形成一棵生成树。

K r u s k a l 算法分e 步，其中e 是网络中边的数目。

按耗费递增的顺序adf来考虑这e 条边，每次考虑一条边。

当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

2. 代码如下：#include<string.h>#include<stdio.h>#include<stdlib.h>#define name 5//。

顶点名占5个字符#define vertexnum 40 //。

顶点数目最多为40 typedef char Vertex[name];//。

顶点名字串typedef int AdjMatrix[vertexnum][vertexnum];//邻接距阵struct MGraph//。

定义图的结构体类型{Vertex vexs[vertexnum];AdjMatrix arcs;int vexnum,arcnum;};typedef struct{Vertex adjvex;//。

当前点int lowcost;//。

代价}minside[vertexnum];//声明函数原型int LocateVex(MGraph G,Vertex u);void CreateGraph(MGraph&G);int minimum(minside SZ,MGraph G);void MiniSpanTree_PRIM(MGraph G,Vertex u);//主函数int main(){MGraph g;CreateGraph(g);MiniSpanTree_PRIM(g,g.vexs[0]);system("PAUSE");return 0;}int LocateVex(MGraph G,Vertex u)//。

一、请给出一个集合A ，并给出A 上既具有对称性，又具有反对称性的关系。

（10分） A:(A ∩B)∪A=A,(A ∪B)∩A=A.二、请给出一个集合A ，并给出A 上既不具有对称性，又不具有反对称性的关系。

（10分） A:(A ∩B)∪A=A,(A ∪B)∩A=A.三、设A={1，2}，请给出A 上的所有关系。

（10分）{1,2} {2,1}四、设A={1，2，3}，问A 上一共有多少个不同的关系。

（10分）集合中有三个元素,3个元素对,可定义二元关系2^3=8种（3个元素对分别满足或者不满足关系R ）五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。

（10分）证明：设公式G 的合取范式为：G ’=G 1∧G 2∧…∧G n若公式G 恒真，则G ’恒真，即子句G i ；i=1,2,…n 恒真为其充要条件。

G i 恒真则其必然有一个原子和它的否定同时出现在G i 中，也就是说无论一个解释I 使这个原子为1或0 ，G i 都取1值。

若不然，假设G i 恒真，但每个原子和其否定都不同时出现在G i 中。

则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么G i 在解释I 下的取值为0。

这与G i 恒真矛盾。

因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。

六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。

证明：n ≤2m C ，其中2m C 表示m 中取2的组合数。

（10分）证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。

因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)的元数n ≤C m 2 ，其中C m 2 表示m 中取2的组合数。

1．假设p 为假，q 为假，并且r 为假，求下列表达式的真值(要求写出求值过程)：（1）p∧( q r)（2）q∨(p r)2. 用真值表判断下面公式的类型（矛盾式、永真式、非永真式的可满足式）(1) p r(q p)(2) (p q) (p r)3. 设集合A＝{2, 3, 4, 6, 8, 24, 48}，R 是A 上的整除关系，(1) 画出偏序集(A, R)的哈斯图；(2) 写出A 的子集B={2, 3, 4, 6, 8}的最大元，最小元，极大元，极小元。

4. 设集合A＝{a, b, c}，A 上的二元关系R＝{(a, a),(b, c), (b, b),(a, b),(c, c)}，(1)画出R的关系图；(2) 写出R 的关系矩阵.(3) 问R 具有关系的哪几种性质(自反、对称、反对称、传递).5.求解：（1）用ABCDEF 六个字母可以组成多少个不重复的长度为3 的字符串？(2)（1）中有多少个字符串以字母A 开头？(3)（1）中有多少个字符串不以字母A 开头？6.求解以下递推方程a n =6a n- 1 +16a n-2，a0 = 3, a1 =4W(T)7.求带权为 1, 1, 2, 3, 4, 6 的最优树，并给出该树的权值1．在自然推理系统P 中构造下面推理的证明：如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。

所以，当小赵去看电影时，小李也去2.证明等值式：x y(F(x) G(y) H(x,y)) x y(F(x) G(y) H(x,y))3 ．R1 和R2 为A 上的关系，证明：（R1∪R2）-1=R1-1∪R2-14 / 4。

离散数学大作业大作业时间为第1周到第17周，满分100分，由两部分组成。

提交作业方式有以下三种，请务必与辅导教师沟通后选择：1. 将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅。

注意选择此种提交方式时仍然需要在网络课提交作业入口处上传说明文档，文档内注明“作业已由线下提交给辅导老师”。

2. 在线提交word文档．3. 自备答题纸张，将答题过程手工书写，并拍照上传．第一部分一、公式翻译题（每小题2分，共10分）1.将语句“我会英语，并且会德语．”翻译成命题公式．设p.我学英语Q:我学法语则命题公式为:pΛQ2.将语句“如果今天是周三，则昨天是周二．”翻译成命题公式．设P：今天是周三Q：昨天是周二则命题公式为：P→Q3.将语句“小王是个学生，小李是个职员．”翻译成命题公式．设P：小王是个学生Q：小李是个职员则命题公式为：P∧Q4.将语句“如果明天下雨，我们就去图书馆.”翻译成命题公式．设 P 表示“明天下雨”Q 表示“我们就去图书馆”命题公式：P → Q5.将语句“当大家都进入教室后，讨论会开始进行．”翻译成命题公式．设 P ：大家都进入教室后Q ：讨论会开始进行命题公式：P → Q二、计算题（每小题10分，共50分）1．设集合A={1, 2, 3}，B={2, 3, 4}，C={2, {3}}，试计算（1）A-C；（2）A∩B；（3）(A∩B)×C．答：（1）A-C ={1,3}；（2）A∩B={2,3}；（3）(A∩B)×C={<2,2>,<2,{3}>,<3,2>,<3,{3}>}。

2. 设G =<V ，E >，V ={v 1, v 2, v 3, v 4, v 5}，E ={(v 1,v 3) , (v 1,v 5) , (v 2,v 3) , (v 3,v 4) , (v 4,v 5) }，试（1）给出G 的图形表示；（2）求出每个结点的度数；（3）画出其补图的图形．答：（1）G 的图形表示如图所示（2）v1, v2, v3, v4, v5结点的度数依次为2，1，3，2，2（3）补图的图形3．试画一棵带权为1, 2, 3, 3, 4的最优二叉树,并计算该最优二叉树的权．最优二叉树的权为1×3+2×3+3×2+3×2+4×2=294．求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．W(v2,v6)=1,选(v2,v6)W(v4,v5)=1,选(v4,v5)W(v1,v6)=2,选(v1,v6)W(v3,v5)=2,选(v3,v5)W(v2,v3)=4,选(v2,v3)最小生成树，如图生成树的权W(T)=1+1+2+2+4=10 ο ο ο ο ο v 6 v 1 v 2 v 5 v 3 ο v 4 1 6 2 4 5 7 9 3 1 5 2 ο ο ο ο ο v 6 v 1 v 2 v 5 v 3ο v 4 1 6 2 4 57 9 3 1 5 25.求P→(Q∧R) 的析取范式与合取范式.P→(Q∧R)=┐P∨(Q∧R)=（┐P∨Q）∧（┐P∨R）合取范式=（┐P∨Q）∨（R∧┐R）∧（┐P∨R）=（┐P∨Q）∨（R∧┐R）∧（┐P∨R）∨（Q∧┐Q）=（┐P∨Q∨R）∧（┐P∨Q∨┐R）∧（┐P∨┐Q∨R）主合取范式=（┐P∧┐Q∧┐R）∨（┐P∧┐Q∧R）∨（┐P∧┐Q∧┐R）（┐P∧Q∧R）∨（P∧┐Q∧R）∨（P∧Q∧┐R）∨（P∧Q∧R）主析取范式第二部分从下列选题中选择一个感兴趣的主题，自主查阅文献资料进行深入的研究和学习，并形成一份至少一千字的总结报告。

2016年秋国家开放大学《离散数学》形考4试题及答案（答案全部正确）04任务_0001试卷总分：100 测试时间：0单项选择题一、单项选择题（共 10 道试题，共 100 分。

）1. 无向树T有8个结点，则T的边数为( )．A. 6B. 7C. 8D. 92. 图G如图三所示，以下说法正确的是( ) ．A. {(a, d)}是割边B. {(a, d)}是边割集C. {(a, d) ,(b, d)}是边割集D. {(b, d)}是边割集3. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )．A. （a）只是弱连通的B. （b）只是弱连通的C. （c）只是弱连通的D. （d）只是弱连通的4. 如图一所示，以下说法正确的是( ) ．A. {(a, e)}是割边B. {(a, e)}是边割集C. {(a, e) ,(b, c)}是边割集D. {(d, e)}是边割集5. 设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．A. m-n+1B. m-nC. m+n+1D. n-m+16. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A. e－v＋2B. v＋e－2C. e－v－2D. e＋v＋27. 设无向图G的邻接矩阵为，则G的边数为( )．A. 6B. 5C. 4D. 38. 如图所示，以下说法正确的是( )．A. e是割点B. {a,e}是点割集C. {b, e}是点割集D. {d}是点割集9. 无向简单图G是棵树，当且仅当( )．A. G连通且边数比结点数少1B. G连通且结点数比边数少1C. G的边数比结点数少1D. G中没有回路．10. 以下结论正确的是( )．A. 无向完全图都是欧拉图B. 有n个结点n－1条边的无向图都是树C. 无向完全图都是平面图D. 树的每条边都是割边04任务_0002试卷总分：100 测试时间：0单项选择题一、单项选择题（共 10 道试题，共 100 分。

1求命题公式(p∨q)→(r∨q) 的主析取范式、主合取范式及公式的成假赋值。

（只能用等值演算求）
2求谓词公式∃xA(x) →∀xB(x)的前束范式。

3符号化命题，并用构造法证明其结论：
每个喜欢步行的人都不喜欢骑自行车。

每个人或者喜欢骑自行车或者喜欢乘汽车。

有的人不喜欢乘汽车。

所以有的人不喜欢步行。

(个体域为人类集合)
4设A={1,2,3,4}，A上二元关系R定义为：R={<1,2>,<2,3>,<2,4>,<4,2>} 求R的自反闭包、对称闭包和传递闭包。

（传递闭包用矩阵求）5设A = {1, 2, 3 , 4, 5, 6 , 7}, A上的一个划分S= {{ 1, 2 } , {4,5} , {3, 6 , 7}},写出划分S所对应的等价关系。

6若(A, ≤ ) 是偏序集，其中A = {1, 2, 3 , 4, 5, 6 , 7 , 8 , 9, 10 , 12 , 16}，≤为A上的整除关系，画出哈斯图，并求子集{1, 2, 3 , 4}、{2, 3 , 6}、{2, 3 , 5 , 8}的最大元、最小元、极大元、极小元、上界、下界、上确界、下确界。

7设个体域为D={a, b}，P(a,a)=P(b,b)=1，P(a,b)=P(b,a)=0 试求出谓词公式∀y∃x P(x, y)的真值。

= {1，2，3，4，5，6}上关系R 的关系图，试画出R 的传递闭包t (R )的关系图,并用集合表示.2西南大学网络与继续教育学院课程考试试题卷类别：网教专业：计算机教育 2019年12月课程名称【编号】：离散数学【0004】B 卷大作业满分：100分一、大作业题目134563.请给出谓词逻辑的研究对象，并将“任何整数的平方均非负”使用谓词符号化.答：研究对象：个体词，谓词，量词，命题符号化；，1.请给出集合A 到集合B 的映射f 的定义.设R 是实数集合，f :R ×R →R ×R ,f (x ,，y ) = (x +y ,x -y ).证明f 是双射.答：A,B 是两个集合,如果按照某种对应法则f,对于集合A 中的任何一个元素x,在集合B 中都有唯4.利用真值表求命题公式(p →(q →r ))↔(r →(q →p ))的主析取范式和主合取范式.5.求叶赋权分别为2, 3, 5, 7, 8的最优2叉树.一的元素y 和它对应,那么这样的对应叫做集合A 到集合B 的映射.记做f:A →B.并称y 是x 的象,x 是y 答：的原象.对任意的（x,y))∈R*R,f((x,y))=(x+y,x-y),二、大作业要求假设存在另一(x1,y1,)满足f((x1,y1))=(x1+y1,x1-y1)=(x+y,x-y),大作业共需要完成三道题：第1题必做，满分30分；即:x1+y1=x+y,x1-y1=x-y第2-3题选作一题，满分30分；第4-5题选作一题，满分40分.解这个关于x1,y1的线性方程组x1=x,y1=y 对任意的(x,y)∈R*R 存在（a,b)∈R*R,( a=(x+y)/2,b=(x-y)/2 )满足f((a,b))=(x,y),所以f 是满射所以f 是双射2.设R 是集合A 上的关系，请给出R 的传递闭包t (R )的定义.下图给出的是集合A所以f 是入射。

一、简要回答下列问题：（每小题3分，共30分）1．请给出集合运算的等幂率。

答：等幂律 A⋂A=A，A⋃A=A2．请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。

答：设A={1,2,3}, R={（1，1），（2，2），（3，3）} 既对称又反对称。

3．设A={1，2，3}，问全域关系是否具有自反性，对称性？答：是，全域关系具有自反性、对称性4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={4,3}，求M的上界，下界。

答：上界无下界 15．关于P，Q，R请给出使极小项m1，m7为真的解释。

答：P=0,Q=0,R=1, ⌝P∧⌝Q∧R，记为m1 取1值，为真；P=1,Q=1,R=1，P∧Q∧R 记为m7 取1值，为真。

6．什么是图中的回路，请举一例。

设G=(P,L)是图，(v0 ,v1, …, v n)是G中从v0到v n的路，称此路为简单路，如果（1）v0 , …, v n-1互不相同（2）v1 , …, v n互不相同显然，一条简单路(v0 ,v1, …, v n)，除v0与 v n可以相同外，其他任意两点都不相同。

上图中，路(A，B，C，D)，（A，E，D，A）是简单路，而路（A，B，F，C，B）不是简单路。

设G=(P，L)是图，G中从点v到自身的长度不小于3的简单路，称为回路。

上图中，路（A，E，D，A），（A，D，C，F，B，A）是回路。

当简单路的起点和终点重合时，并且从起点再到自身的长度大于等于3时，即为回路。

7．设S是一个非空集合，ρ（S）是S的幂集，⋂，⋃是集合的交，并运算。

求对于⋂的单位元，对⋃的单位元。

答：对于⋂的单位元是S，对于⋃的单位元是空集∅。

8．什么是群中左模H合同关系？答：包含a的左陪集，就是以H的所有元素乘以a所得的集合Ha，定义a合同于b(左模H)，a≡b（左mod H）9．有壹环的子环是否一定是有壹环？答：不一定，可能有，也可能没有10．设R={0，1，2，3，4，5，6，7，8，9，10，11}是模12的整数环，问N1=6R，N2=2R是否为R的极大理想？答：N1=6R={0，6}，不是R的极大理想，是R的主理想。

离散数学试题与答案试卷一一、填空 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 | 。

一、单项选择题1、三个结点最多可以构成__________个非同构的无向简单图。

A ．1B ．2C ．3D ．42. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（ ）A. 1,1,1,3，B.3,2,2,3C. 2,2,2,2，D. 1,2,3,43．无向图的关联矩阵中，每行的元素之和为（ ）。

A ．边数的2倍B ．2C ．顶点数D ．顶点的度数4、二部图（偶图）K 2,3是（ ）。

A ．欧拉图B ．哈密顿图C ．非平面图D ．平面图5．3阶无向完全图（K 3）不是以下哪种图？（ ）A ．欧拉图B ．平面图C ．二部图D ．哈密顿图二、填空题1． 一个无向图有4个结点，4条边，其中的3个顶点度数分别为1，2，3，则第4个结点度数一定是_______。

2、无向完全图K 4要成为欧拉图至少要添加_____________条边。

3．完全二部图K 2,3是平面图，它的平面嵌入共有______________个面。

4. 一棵无向树T 有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T 中有_____________片树叶。

三、设无向图G 有12条边，2个4度顶点，其余顶点度数均为3或2。

（1）计算该图最少有多少个顶点？（2）画出一棵具有最少顶点的无向图。

四、以下是具有结点V 1，V 2，V 3，V 4的有向图的邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1001200010100110 （1）画出该图； （2）求长度为2的通路总数和回路总数；（3）该图是否为欧拉图?五、右图是具有四个结点的有向图：（1）写出该图的邻接矩阵、可达矩阵；（2）求长度为2的通路总数。

（3）判断该图为单向连通还是强连通？六、右下图为无向图：（1）它是否为平面图？若是，请画出它的一个平面嵌入图；否则，说明理由。

（2）判断该图是否为哈密尔顿图？请说明理由。

（3）判断该图是否为二部图？请说明理由。

七. 图G是一个简单的连通的平面图，顶点数为8为四边形（次数为4），计算平面图G的边数和面数。