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

试卷五试题与答案一、 填空给定命题公式A、B，若 ，则称A和B是逻辑相等的。2命题公式的主析取范式为 ，主合取范式的编码表示为 。3设E为全集， ，称为A的绝对补，记作A，且（A）= ，E = ，= 。4设考虑下列子集，则A的覆盖有 ，A的划分有 。5设S是非空有限集，代数系统P（S），中，P（S）对的幺元为 ， 零元为 。P（S）对的幺元为 ，零元为 。6若为汉密尔顿图，则对于结点集V的每个非空子集S，均有W(G-S) 成立，其中W(G-S)是 。7、 n阶完全图结点v的度数d(v) = 。8、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则N k = 。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、； B、；C、； D、。6任意具有多个等幂元的半群，它（ ）。A、不能构成群； B、不一定能构成群；C、不能构成交换群； D、能构成交换群。7设是一个有界格，它也是有补格，只要满足（ ）。A、每个元素都有一个补元； B、每个元素都至少有一个补元；C、每个元素都无补元； D、每个元素都有多个补元。8设为无向图，则G一定是（ ）。A、完全图； B、树； C、简单图； D、多重图。9给定无向图，如下图所示，下面哪个边集不是其边割集（ ）。A、； B、；C、；D、。10有n个结点，条边的连通简单图是平面图的必要条件（ ）。A、； B、； C、； D、。三、证明 1、设G是（n,m）简单二部图，则。（10分）2、设G为具有n个结点的简单图，且，则G是连通图。（10分）3、记“开”为1，“关”为0，反映电路规律的代数系统0，1，+，的加法运算和乘法运算。如下：+0101001000110101证明它是一个环，并且是一个域。（14分）4、用推理规则证明： A5、有个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种药品？四、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。答 案一、填空 1对于A，B中原子变元任意一组真值指派，A和B的真值相同。2。3集A关于E的补集E A ；A ；E 。4。5。6的连通分支数。7、n-1；8、n(k+1)-2m；9、0 ；10臂力小者二、选择 题号12345678910答案DCAADABDBD二、 证明1、 证：设G=（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）+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（x+y）=0=0+0=(0x)+(0y)； 1（x+y）当x=y (x+y)=0 则；当（）则所以均有同理可证：所以对+ 是可分配的。由得，0，1，+，是环。（2）0，1，+，是域因为0，1，+，是有限环，故只需证明是整环即可。乘交环： 由乘法运算表的对称性知，乘法可交换。含幺环：乘法的幺元是1无零因子：11=10因此0，1，+，是整环，故它是域。4、证明：（1）A P（附加前提） （2） P （3）C T（1）（2）I （4） P （5） T（4）I（6）D T（3）（5）I（7） P（8） T（7）E（9） T（8）I（10）F T（6）（9）I（11） T（4）I（12）B T（1）（11）I（13） T（8）I（14）E T（12）（13）I（15） T（10）（14）I（16） P（17） T（15）（16）I结论有效。5、解：用个结点表示个药箱，当两种药箱放一种相同药