《离散数学》课程试题(A)卷
课程代码： 080800111
本试卷适用理学系数学与应用数学专业和信息与计算科学专业
（时量：120分钟；总分为100分）
注 意： 1、所有答案和解答均应写在答题纸上，答在试卷上不记分
2、答案必须写明题目序号，并按题号顺序答题
3、请保持行距，保持卷面整洁
一、填空题：（每题3分，本大题共24分）
1．设}4,}3{,,2{a A =，}1,4,3,}{{a B =，请在下列每对集合中填入适当的符号：⊆∈,。
（1）}{a B , (2) }}3{,4,{a A 。
2．设}1,0{=A ，N 为自然数集，⎩⎨⎧=是偶数。
，是奇数，
，x x x f 10)( 若A A f →：
，则f 是 射的，若A N f →：
，则f 是 射的。
3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，
则G 中有 条边，根据 。
4．两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。
5．在一阶逻辑中将命题：凡对顶角都相等，符号化为_____________________。
6.集合A 有n 个元素，则A 上共有_____________________个既是对称又是反对称的的关系。
7. 连通简单无向图有17条边。
则该图至少有_____________________个结点。
8. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没得优，那么两次考试都得优的学生的人数是_____________________。
二、单项选择题：（每小题3分，本大题共30分）
1．设}16{2<=x x x A 是整数且，下面哪个命题为假（ ）。
A 、A ⊆}4,2,1,0{ ； B 、A ⊆---}1,2,3{ ；
C 、A ⊆Φ ；
D 、A x x x ⊆<}4{是整数且。
2．设}}{,{,ΦΦ=Φ=B A ，则B －A 是（ ）。
A 、}}{{Φ ；
B 、}{Φ ；
C 、}}{,{ΦΦ ；
D 、Φ。
3．设f 和g 都是X 上的双射函数，则1)(-g f 为（ ）。
A 、11--g f ；
B 、1)(-f g ；
C 、11--f g ；
D 、1-f g 。
4．设R 和S 是P 上的关系，P 是所有人的集合，},|,{的父亲是y x P y x y x R ∧∈><=，},|,{的母亲是y x P y x y x S ∧∈><= 则R S 1-表示关系 （ ）。
A 、},|,{的丈夫是y x P y x y x ∧∈><；
B 、},|,{的孙子或孙女是y x P y x y x ∧∈><；
C 、 Φ；
D 、},|,{的祖父或祖母是y x P y x y x ∧∈><
5. 在如下的有向图中，长度为3 的通路有（ ）条。
A ．6；
B ．7；
C ．8； 4．9
6．设G 是n 个结点、m 条边和r 个面的连通平面图，则m 等于（ ）。
A 、n+r-2 ；
B 、n-r+2 ；
C 、n-r-2 ；
D 、n+r+2 。
7．给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（
）。
A 、},,,{4341><><v v v v ；
B 、},,,{6454><><v v v v ；
C 、},,,{8474><><v v v v ；
D 、},,,{3221><><v v v v 。
8．下面那一个图可一笔画出（ ）。
9．在任何图中必定有偶数个（ ）。
A 、度数为偶数的结点 ；
B 、入度为奇数的结点 ；
C 、度数为奇数的结点 ；
D 、出度为奇数的结点 。
10．下列集合中哪个是最小联结词集（ ）。
A 、},{→⌝ ；
B 、},{↔⌝ ；
C 、},{↔→ ；
D 、},,{∨∧⌝ 。
三、证明题：（１6分）
1、用命题逻辑证明这是有效的论断，“如果下雨，春游就改期，如果没有球赛，春游就不改期。
结果没有球赛，所以没有下雨”。
２、若有n 个人，每个人都恰有三个朋友，则n 必为偶数。
四、 简答题：（30分）
1、设个体域},,{c b a D =，消去下列各公式中的量词。
（10分）
（１）))()((y yG x F x ∃∧∀；
（２）),(y x yH x ∀∃。
2、集合}36,24,12,6,3,2{=A 上的偏序关系R 为整除关系。
设}12,6{=B ，}6,3,2{=C ，试画出R 的哈斯图，并求A ，B ，C 的最大元素、极大元素、下界、上确界。
(１０分)
五、 设N 是自然数集合，定义N 上的二元关系R ：},,|,{是偶数y x N y x y x R +∈><=
（１）证明Ｒ是个等价关系；（２）求关系Ｒ的等价类；（３）设计一个从Ｎ到Ｎ的函数ｆ，使得由ｆ所诱导的等价关系是关系Ｒ.（10分）。