离散数学试卷五试题与答案

试卷五试题与答案一、填空．给定命题公式A、B，若，则称A和B是逻辑相等的。2．命题公式)(QP的主析取范式为，主合取范式的编码表示为。3．设E为全集，，称为A的绝对补，记作～A，且～（～A）=，～E=，～=。4．设},,{cbaA考虑下列子集}},{},,{{1cbbaS，}},{},,{},{{2cabaaS，}},{},{{3cbaS，}},,{{4cbaS}}{},{},{{5cbaS，}},{},{{6caaS则A的覆盖有，A的划分有。5．设S是非空有限集，代数系统＜P（S），，＞中，P（S）对的幺元为，零元为。P（S）对的幺元为，零元为。6．若EVG,为汉密尔顿图，则对于结点集V的每个非空子集S，均有W(G-S)S成立，其中W(G-S)是。7、n阶完全图结点v的度数d(v)=。8、设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk=。9、如图给出格L，则e的补元是。10、一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是。二、选择1、设S={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，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（）时，[A，+，·]是整环。A、},2|{Znnxx；B、},12|{Znnxx；C、},0|{Zxxx且；D、},,5|{4Rbabaxx。6．任意具有多个等幂元的半群，它（）。A、不能构成群；B、不一定能构成群；C、不能构成交换群；D、能构成交换群。7．设,A是一个有界格，它也是有补格，只要满足（）。A、每个元素都有一个补元；B、每个元素都至少有一个补元；C、每个元素都无补元；D、每个元素都有多个补元。8．设EVG,为无向图，23,7EV，则G一定是（）。A、完全图；B、树；C、简单图；D、多重图。9．给定无向图EVG,，如下图所示，下面哪个边集不是其边割集（）。A、},,,{4341vvvv；B、},,,{6451vvvv；C、},,,{8474vvvv；D、},,,{3221vvvv。10．有n个结点)3(n，m条边的连通简单图是平面图的必要条件（）。A、63mn；B、63mn；C、63nm；D、63nm。三、证明1、设G是（n,m）简单二部图，则42nm。（10分）2、设G为具有n个结点的简单图，且)2)(1(21nnm，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：+01·01001000110101证明它是一个环，并且是一个域。（14分）4、用推理规则证明：CAFEFDEBDCBA,)(,)()(,)()(├A5、有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种药品？四、如下图所示的赋权图表示某七个城市721,,,vvv及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。答案一、填空1．对于A，B中原子变元nPPP,,,21任意一组真值指派，A和B的真值相同。2．110100,MMMQP。3．集A关于E的补集E–A；A；Φ；E。4．54354321,,,,SSSSSSSS，，；。5．；；；SS。6．SG；的连通分支数。7、n-1；8、n(k+1)-2m；9、0；10臂力小者二、选择题号12345678910答案DCAADABDBD二、证明1、证：设G=（V，E）nnnnYnXYXV2121,,,对完全二部图有4)2()(2211211121nnnnnnnnnnnm当21nn时，完全二部图),(mn的边数m有最大值42n故对任意简单二部图),(mn有42nm。2、证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然nnn2111112121nnnnnn2)2)(1(2)2)(1(2)1(2)1(212211nnnnnnnnnm与假设矛盾。所以G连通。3、（1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。群：（0+0）+0=0+（0+0）=0；（0+0）+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}，·]是半群乘：由“·”运算表知封闭群：（0·0）·0=0·（0·0）=0；（0·0）·1=0·（0·1）=0；（0·1）·0=0·（1·0）=0；（0·1）·1=0·（1·1）=0；（1·1）·1=1·（1·1）=0。③·对+的分配律}1,0{,yxⅠ0·（x+y）=0=0+0=(0·x)+(0·y)；Ⅱ1·（x+y）当x=y(x+y)=0则)1()1()11()11()01()01(1100001)(1yxyx；当yx（1yx）则)1()1()11()01()01()11(1001111)(1yxyx所以}1,0{,,zyx均有)()()(yzxzyxz同理可证：)()()(zyzxzyx所以·对+是可分配的。由①②③得，[{0，1}，+，·]是环。（2）[{0，1}，+，·]是域因为[{0，1}，+，·]是有限环，故只需证明是整环即可。①乘交环：由乘法运算表的对称性知，乘法可交换。②含幺环：乘法的幺元是1③无零因子：1·1=1≠0因此[{0，1}，+，·]是整环，故它是域。4、证明：（1）AP（附加前提）（2）CAP（3）CT（1）（2）I（4）)()(DCBAP（5）DCT（4）I（6）DT（3）（5）I（7）)()(FDEBP（8）)()(FDEBT（7）E（9）FDT（8）I（10）FT（6）（9）I（11）BAT（4）I（12）BT（1）（11）I（13）EBT（8）I（14）ET（12）（13）I（15）FET（10）（14）I（16）)(FEP（17）)()(FEFET（15）（16）I∴结论有效。5、解：用n个结点表示n个药箱，当两种药箱放一种相同药时，则对应的两点连一条边，则得到一个无向完全图，因而所求药品数即为该图边数=)1(21nn。四、解：用库斯克（Kruskal）算法求产生的最优树。算法为：61615454434337337272277117123),(17),(3),(9),(4),(1),(vvevvwvvevvwvvevvwvvevvwvvevvwvvevvw选选选选选选结果如图：树权C(T)=23+1+4+9+3+17=57（万元）即为总造价