离散数学补充习题.doc

一、填空题：（每空1分，本大题共15分）1设，请在下列每对集合中填入适当的符号：。 （1） , (2) 。2设，N为自然数集， 若，则是 射的，若，则是 射的。3设图G = 中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有 条边，根据 。4两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。5设个体域为自然数集，命题“不存在最大自然数”符号化为 。67设P、Q为两个命题，其De-Morden律可表示为 ；8二、单项选择题：（每小题1分，本大题共15分）1设，下面哪个命题为假（ ）。 A、 ； B、 ；C、 ； D、。2设，则BA是（ ）。A、 ； B、 ； C、 ； D、。3下图描述的偏序集中，子集的上界为 （ ）。A、 ； B、 ； C、 ； D、。4设和都是X上的双射函数，则为（ c ）。A、 ； B、 ； C、 ； D、。56789设，则有向图是（ ）。A、强连通的 ； B、单侧连通的 ； C、弱连通的 ； D、不连通的。10下面那一个图可一笔画出（ ）。11在任何图中必定有偶数个（ ）。A、度数为偶数的结点 ； B、入度为奇数的结点 ；C、度数为奇数的结点 ； D、出度为奇数的结点 。12含有3个命题变元的具有不同真值的命题公式的个数为（ ）。A、 ； B、 ； C、 ； D、 。13下列集合中哪个是最小联结词集（ ）。A、 ； B、 ； C、 ； 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分）12集合上的偏序关系为整除关系。设，试画出的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。345五、证明题：（25分）1如果集合A上的关系R和S是反自反的、对称的和传递的，证明：是A上的等价关系。2用推理规则证明是 的有效结论。3若有n个人，每个人都恰有三个朋友，则n必为偶数。4一、填空题1（1） ， （2）。 2双射 ， 满射。 314 ， 。4重言式 ，矛盾式 。 5 ， 6 7；8 二、单项选择题题号123456789101112131415答案ACBCCACCABA三、判断改正题1 。2 3 。4 。 56 7 。 8 当且仅当P，Q的真值相同时，的真值为T。 9 。 10 。四、简答案题12解：的哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无634 五、证明题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证明：将每个人用结点表示