离散数学补充习题

《离散数学补充习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、填空题：（每空1分，本大题共15分）1．设，，请在下列每对集合中填入适当的符号：。（1）,(2)。2．设，N为自然数集，若，则是射的，若，则是射的。3．设图G=中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有条边，根据。4．两个重言式的析取是，一个重言式和一个矛盾式的合取是。5．设个体域为自然数集，命题“不存在最大自然数”符号化为。6．7．设P、Q为两个命题，其De-Morden律可表示为；8．二、单项选择题：（每小题1分，本大题共15分）1．设，下面哪个命题为假（）。A、；B、；C、；D、。2．设，则B－A是（）

2、。A、；B、；C、；D、。3．下图描述的偏序集中，子集的上界为（）。A、；B、；C、；D、。4．设和都是X上的双射函数，则为（c）。A、；B、；C、；D、。5．6．7．8．9．设，，则有向图是（）。A、强连通的；B、单侧连通的；C、弱连通的；D、不连通的。10．下面那一个图可一笔画出（）。11．在任何图中必定有偶数个（）。A、度数为偶数的结点；B、入度为奇数的结点；C、度数为奇数的结点；D、出度为奇数的结点。12．含有3个命题变元的具有不同真值的命题公式的个数为（）。A、；B、；C、；D、。13．下列集合中哪个是最小联结词集（）。A、；B、；C、；

3、D、。14．下面哪个命题公式是重言式（b）。A、；B、；C、；D、。15．在谓词演算中，下列各式哪个是正确的（）。A、；B、；C、；D、。三、判断改正题：（每小题2分，本大题共20分）1．设，，则。（其中为P（A））()2．设，，则。（）3．集合A上的恒等关系是一个双射函数。（）4．（）5．（）6．（）7．能一笔画出的图不一定是欧拉图。（）8．设P，Q是两个命题，当且仅当P，Q的真值均为T时，的值为T。（）9．命题公式是重言式。（）10．设命题“所有的研究生都读过大学”符号化为：。（）四、简答题：（25分）1．2．集合上的偏序关系为整除关系。设，，

4、试画出的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。34．5．五、证明题：（25分）1．如果集合A上的关系R和S是反自反的、对称的和传递的，证明：是A上的等价关系。2．用推理规则证明是的有效结论。3．若有n个人，每个人都恰有三个朋友，则n必为偶数。4．一、填空题1．（1），（2）。2．双射，满射。3．14，。4．重言式，矛盾式。5．，6．7．；8．二、单项选择题题号123456789101112131415答案ACBCCACCABA三、判断改正题1．×。2．×3．√。4．。5．6．7．√。8．×当且仅当P，Q的真值相同时，的真值为T。

5、9．√。10．×。四、简答案题1．2．解：的哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无63．4．五、证明题1．证明：（1）自反。（2），若，则由R，S对称，所以，，所以对称。（3），若则由R，S传递性知，从而所以，传递。综上所述，是A上的等价关系。2．证明：（1）P（2）US(1)(3)P(4)T(2)(3)I(5)P(6)US(5)(7)T(6)E,I(8)P(9)T(7)(8)I(10)T(4)(9)I所以，结论有效。3．证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图。因

6、为每个人恰有三个朋友，所以，，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是偶数。4．