离散数学试卷（25）
一、填空题：（每空1分，本大题共15分）
1．给定命题公式A、B，若 ，则称A和B是逻辑相等的。 2．命题公式?(P?Q)的主析取范式为 ，主合取范式的编
码表示为 。
3．设E为全集， ，称为A的绝对补，记作～A，
且～（～A）= ，～E = ，～?= 。 4．设A?{a,b,c}考虑下列子集
S1?{{a,b},{b,c}}，S2?{{a},{a,b},{a,c}}，S3?{{a},{b,c}}，S4?{{a,b,c}}
S5?{{a},{b},{c}}，S6?{{a},{a,c}}
则A的覆盖有 ，A的划分有 。
5．设S是非空有限集，代数系统＜?（S），?，?＞中，?（S）对?的幺元为 ， 零元为 。?（S）对?的幺元为 ，零元为 。 6．若G??V,E?为汉密尔顿图，则对于结点集V的每个非空子集S，均有
W(G-S) S成立，其中W(G-S)是 。
二、单项选择题：（每小题1分，本大题共10分）
1．下面命题公式（ ）不是重言式。
A、Q?(P?Q)； B、(P?Q)?P；
C、?(P??Q)?(?P?Q)； D、(P?Q)?(?P?Q)。 2．命题“没有不犯错误的人”符号化为（ ）。 设M(x)：x是人，P(x)：x犯错误。
A、?x(M(x)?P(x))； B、?(?x(M(x)??P(x)))； C、?(?x(M(x)?P(x)))； D、?(?x(M(x)??P(x)))。 3．设A?{?}，B = ?(?(A))，下列各式中哪个是错误的（ ）。
166
离散数学试卷（25）
A、??B； B、{?}?B， C、{{?}}?B； D、{?,{?}}??(A)。
4．对自然数集合N，哪种运算不是可结合的，运算定义为任a,b?N（ ）。
A、a?b?min(a,b)； B、a?b?a?2b； C、a?b?a?b?3； D、a?b?a,b(mod3)。 5．设Z为整数集，下面哪个序偶不够成偏序集（ ）。
A、?Z,??C、?Z,??(?：小于关系)； B、?Z,??(?：小于等于关系)；
(?：等于关系)； D、?Z,?(：整除关系)。
6．任意具有多个等幂元的半群，它（ ）。
A、不能构成群； B、不一定能构成群； C、不能构成交换群； D、能构成交换群。
7．设?A,??是一个有界格，它也是有补格，只要满足（ ）。
A、每个元素都有一个补元； B、每个元素都至少有一个补元； C、每个元素都无补元； D、每个元素都有多个补元。 8．设G??V,E?为无向图，V?7,E?23，则G一定是（ ）。
A、完全图； B、树； C、简单图； D、多重图。
9．给定无向图G??V,E?，如下图所示，下面哪个边集不是其边割集（ ）。
A、{?v1,v4?,?v3,v4?}； B、{?v1,v5?,?v4,v6?}； C、{?v4,v7?,?v4,v8?}； D、{?v1,v2?,?v2,v3?}。
10．有n个结点(n?3)，m条边的连通简单图是平面图的必要条件（ ）。
A、n?3m?6； B、n?3m?6； C、m?3n?6； D、m?3n?6。
167
离散数学试卷（25）
三、判断改正题：（每小题2分，本大题共20分）
1．设A，B为任意集合，不能A?B且A?B。 （ ） 2．设R是集合A上的关系，若R1,R2是对称的，则R1?R2也是对称的。（ ） 3．群中可以有零元（对阶数大于1的群）。 （ ） 4．循环群一定是Abel群。 （ ） 5．每一个链都是分配格。 （ ） 6．不可能有偶数个结点，奇数条边的欧拉图。 （ ） 7．图G中的每条边都是割边，则G必是树。 （ ） 9．公式?x(P(x)?Q(x))?R(y)中?x的辖域为P(x)。 （ ） 10．公式?xP(x)??yQ(x,y)的前束范式为
?x?y(P(x)?Q(x,y))。 （ ）
四、简答题（共20分）
1．用等值演算法求下面公式的主析取范式，并求其成真赋值。
(P?Q)?R
2．集合A?{1,2,3,4}上的关系
R?{?1,1?,?1,3?,?2,2?,?3,3?,?3,1?,?3,4?,?4,3?,?4,4?}，
写出关系矩阵MR，画出关系图并讨论R的性质。
3．有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种
药品？
4．一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。
（1）T中有几个结点；
（2）画出具有上述度数的所有非同构的无向图。
168
离散数学试卷（25）
五、证明题：（35分）
1．符号化下列各题，并说明结论是否有效（用推理规则）。
凡15的倍数都是3的倍数，凡15的倍数都是5的倍数，所以有些5的倍数是3的倍数。 2．用推理规则证明：
(A?B)?(C?D),(?B?E)?(?D?F),?(E?F),A?C├ A
3．设函数f：A?B，g：B?C，若g?f是满射的，则g是满射的。 4．当且仅当G的一条边e不包含在G的闭迹中时，e才是G的割边。
5．设?S,?,??是一个分配格，a?S，令f(x)?x?a，对任意a?S，证明：f是
?S,?,??到自身的格同态映射。
一、填空题
1．对于A，B中原子变元P1,P2,?,Pn任意一组真值指派，A和B的真值相同。 2．P??Q,M00?M01?M11 。
3．集A关于E的补集E – A ；A ；Φ；E 。 4．S1,S2,S3,S4,S5；S3，S4，S5。 5．?；S；S；?。 6．?；G?S的连通分支数。
二、单项选择题
题号 答案
1 C 2 D 3 D 4 B 5 A 6 A 7 B 8 D 9 B 10 D 三、判断改正题
1．× 可能A?B且A?B，如A?{a},B?{1，{1}，2}。
169
相关推荐：
loading