离散数学试卷与解析〔25〕.doc

一、填空题：（每空1分，本大题共15分） 1．给定命题公式A、B，若 ，则称A和B是逻辑相等的。 2．命题公式的主析取范式为 ，主合取范式的编码表示为 。 3．设E为全集， ，称为A的绝对补，记作～A， 且～（～A）= ，～E = ，～= 。 4．设考虑下列子集 ，，， ， 则A的覆盖有 ，A的划分有 。 5．设S是非空有限集，代数系统＜?（S），?，?＞中，?（S）对?的幺元为 ， 零元为 。?（S）对?的幺元为 ，零元为 。 6．若为汉密尔顿图，则对于结点集V的每个非空子集S，均有 W(G-S) 成立，其中W(G-S)是 。 二、单项选择题：（每小题1分，本大题共10分） 1．下面命题公式（ ）不是重言式。 A、； B、； C、； D、。 2．命题“没有不犯错误的人”符号化为（ ）。 设是人，犯错误。 A、； B、； C、； D、。 3．设，B = ?(?(A))，下列各式中哪个是错误的（ ）。 A、； B、， C、； D、?(A)。 4．对自然数集合N，哪种运算不是可结合的，运算定义为任（ ）。 A、； B、； C、； D、。 5．设Z为整数集，下面哪个序偶不够成偏序集（ ）。 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、。 三、判断改正题：（每小题2分，本大题共20分） 1．设A，B为任意集合，不能。 （ ） 2．设R是集合A上的关系，若是对称的，则也是对称的。（ ） 3．群中可以有零元（对阶数大于1的群）。 （ ） 4．循环群一定是Abel群。 （ ） 5．每一个链都是分配格。 （ ） 6．不可能有偶数个结点，奇数条边的欧拉图。 （ ） 7．图G中的每条边都是割边，则G必是树。 （ ） 9．公式中的辖域为。 （ ） 10．公式的前束范式为 。 （ ） 四、简答题（共20分） 1．用等值演算法求下面公式的主析取范式，并求其成真赋值。 2．集合上的关系 ，写出关系矩阵，画出关系图并讨论R的性质。 3．有个药箱，若每两个药箱里有一种相同的药，而每种药