离散数学A卷及答案.doc

课程考试试题

学期

学年

2011-2012 2 离散数学（A卷）
拟题人:

校对人:
拟题学院（系）:

适 用 专 业:

高密校区

2011级计专、软专

（答案写在答题纸上，写在试题纸上无效）

一、单项选择题（每小题2分，共20分）
1．下列为两个命题变元ｐ，ｑ的最小项的是（　　　）
A．ｐ∧ｑ∧ù ｐ B．ù ｐ∨ｑ
C．ù ｐ∧ｑ D．ù ｐ∨ｐ∨ｑ
2．下列语句中是真命题的是（　　　）
A．我正在说谎 B．严禁吸烟
C．如果1+2=3，那么雪是黑的 D．如果1+2=5，那么雪是黑的
3．在公式F（x，y）→ yG（x，y）中变元x是（　　　）
A．自由变元 B．约束变元
C．既是自由变元又是约束变元 D．既不是自由变元，又不是约束变元
4．集合A={1，2，…，10}上的关系R={（x，y）|x+y=10，x∈A，y∈A}，则R的性质是（　　　）
A．自反的 B．对称的
C．传递的、对称的 D．反自反的、传递的
5．设论域为{l，2}，与公式等价的是( )
A.A(1)A(2) B. A(1)A(2)
C.A(1) D. A(2)A(1)
6. 下列关系矩阵所对应的关系具有反自反性的是（　　　）
A． B．
C． D．
7. 在自然数集N上，下列运算是可结合的是（　　　）
A B． C D
8．.设A是奇数集合，下列构成独异点的是( )
A. B. C. D.
9. 右图的最大入度是( )
A．0 B．1 C．2 D．3
第9题图
10. 设G为有n个结点的简单图，则有（　　　）
A．Δ(G)＜n B．Δ(G)≤n C．Δ(G)＞n D．Δ(G)≥n
二、填空题(每空2分，共20分)
1．设A={1，2，3，4}，B={2，4，6}，则A-B=________，AB=
2．设S是非空有限集，代数结构（P（S），∪）中，其中P（S）为集合S的幂集，则P（S）对∪运算的单位元是________，零元是________。
3．设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数,
。
4．设有向图G=（V, E）,V={v1,v2,v3,v4},若G的邻接矩阵，则deg-(v1)=_ ________,deg+(v4)=____________。
5．给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={（1,2）,（3,4）,（2,2）},
S={（4,2）,（2,5），（3,1）,（1,3）}，则，。
三、解答题（6个小题，共60分）
1．（10分）设A={１,２,３,６,９,１８}，≤为整除关系。
（１）画出（A，≤）的哈斯图；
（２）求子集Ｂ＝｛３，６，９｝的极大元、极小元、最大元、最小元。
2．（10分）构造命题公式（（P∧Q）→P）∨R的真值表。
3．（10分）求命题公式A=P→（（Q→P）∧（ùP∧Q））的主析取范式和主合取范式。
4．（10分）证明：ù(A∧B)，B∨C, ùC ùA.
5．（10分）设图G有n个结点，n+1条边，证明：G中至少有一个节点度数≥3。　
6．（10分）用矩阵的方法求下图中节点u1，u5之间长度为2的路的数目。

2011－2012 学年 2学期 离散数学 （A卷） 试题标准答案
拟 题 人：

书写标准答案人：

拟题学院（系）： 高密校区

适用专业： 2011级计专、软专

（答案要注明各个要点的评分标准）
一、单项选择题（每小题2分，共20分）1．（Ｃ）2． (Ｄ)；3．（C）；4．（Ｂ）；5. (A) 6．（Ｃ）7． (Ｂ)；8．（Ｃ）；9．（Ｄ）；10. (Ａ).
二、填空题(每空2分，共20分)
1．{1，３}，{1，３，６}； 2．, Ｓ； 3．2x+７, 2x+４； 4．3,1； 5．{(1,5),(3,2), (2,5)}，{(4,2),(3,2), (1,4)}
三、解答题（6个小题，共60分）
1.解：（１） 哈斯图：
……5分
（２）Ｂ＝｛３，６，９｝的极大元：６，９。极小元：３。最大元：无。最小元：３　　　　　　　　　　
　……10分

2. 解：
P
Q

P∧Q
P∧Q→P
（（P∧Q）→P）∨R
1
1
1
１
１
1
1
１
０
１
１
1
１
０
1
0
１
1
１
0
0
０
1
1
０
１
１
０
１
１
０
１
０
０
１
１
０
０
１
０
１
１
０
０
０
０
１
１
　　　　　　………10分
3.解：A= P→（（Q→P）∧（ùP∧Q））
=ùP∨（（ùQ∨P）∧（ùP∧Q））
=ùP∨（（ùQ∧ùP∧Q）∨（P∧ùP∧Q））
=ùP∨（0∨0）
=ùP　　　　　　　　　　　　　　　　　　　　　　　　　　………5分
所以A的主析取范式Ａ＝ùP∧（Q∨ùQ）＝（ùP∧Q）∨（ùP∧ùQ）　………7分　
　A的主合取范式Ａ＝ùP∨（Q∧ùQ）＝（ùP∨Q）∧（ùP∨ùQ）　　　………10分

4．证明：　（１）B∨C 　 　Ｐ 　　　　　　………１分
（２）ùC 　 P（１） 　　　 　………３分
（３）B 　 T (1) (2)I 　………5分
　　　　　（４）ù(A∧B)　　　 P　　　　　 　　　………６分
　　　　　（５）ùA∨ùB　　　　　　 Ｔ（４）E　　　 　　　………8分
　　　　　（６）ùA　　　　　　　 T (3) (5)I　　　　　　　　………10分
5.证明： 设图有n个节点边数为n+1 ………1分
假设任意节点其度数，则 ………5分
又因为节点度数总和等于边数两倍，即 ………8分
所以，这是个矛盾。故不可能每个节点度数小于等于2，即至少有一节点度数大于等于3 ………10分
6.解： 邻接矩阵
　　　　　　　 　　　　　　　　………4分
　 　………8分
所以，图中节点u1，u5之间长度为2的路有３条。　　　　　　　　　　………10分