安工大离散数学试卷.doc

2010---2011学年第一学期期末考试《离散数学B》试卷（A）
一．单项选择题(每题2分，共30分)
1、设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩ ({3，4，6}×{2，3，4})=（ ）.
A． O/ B．{<3，3>}
C．{<3，3>，<6，2>} D．{<3，3>，<3，4>，<6，2>}
2、设有A={a,b,c}上的关系R={<a,a>,<b,b>,<a,b>,<b,a>,<c,a>，<c,b>}，则R具有( )
A. 自反性 B. 对称性
C. 传递性 D. 反对称性
3、若A-B=Ф，则下列哪个结论不可能正确？( )
(A) A=Ф (B) B=Ф　(C) AB (D) BA
4、判断下列命题哪个正确？(　　　　　)
(A) 若A∪B＝A∪C，则B＝C
(B) {a,b}={b,a}
(C) P(A∩B)P(A)∩P(B) （P(S)表示S的幂集）
(D) 若A为非空集，则AA∪A成立。
5、设A={a,{a}}，下列命题错误的是（ ）。
(A) {a}P(A)　(B) {a}P(A)　(C) {{a}}P(A)　(D) {{a}}P(A)
6、集合的以下运算律不成立的是( ).
A. A∩B=B∩A B. A∪B=B∪A
C. AB=BA D. A-B=B-A
7、下述不是命题的是( ).
A. 今天天气真好啊! B. 明天下雨.
C. 2是偶数. D. 这朵花是红色的
8、设P,Q,R是命题公式,则（P→R）( ).
A. P B. P→R
C. R D. ┐R
9、设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( )
A.(x)A(x)→B B. (x)A(x)→B C. A(x)→B D.(x)A(x)→(x)B
10、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中的x( ).
A.只是约束变元
B.只是自由变元
C.既非约束变元又非自由变元
D.既是约束变元又是自由变元
11、设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（　　　）.
A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))
C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)

12、设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）.
A．满射函数 B．入射函数
C．双射函数 D．非入射非满射
13、下列运算中关于整数集不能构成半群的是（　　　）.
A．ab=max{a, b} B．ab=b
C．ab=2ab D．ab=|a-b|
14、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）.
A．2个面 B．3个面 C．4个面 D．5个面
15、给定n个结点的一个图，它还是一个树的下列说法中，（　　　）是不对的。
A.无回路的连通图
B.无回路但若增加一条新边就会形成回路
C.连通且e=v-1，其中e是边数，v是结点数
D.所有结点的度数≥2

二、填空题（每空1分，共20分）
1、命题P：若3+2＞5，则三角形有3条边。P 的真值为_______。
2、命题“存在一些人是大学生”的否定是_________________________。
3、使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x.
4、A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m14= ____________
5、设A={1，2，3}，则A上的二元关系有 个，若R是集合A上的全域关系，则集合A关于R的商集为 。
6、设X={1，2，3}，函数f：X→X，函数g：X→X，f={<1, 2>,<2,3>,<3,1>},
g={<1,2>,<2,3>,<3,3>}，则fg=_____________________________________，
gf=___________________________________.
7、当f:X→Y是_____函数时，f有逆函数，且f -1。f=_____。
8、设A={1,5,8}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点<A,*>中，幺元是____________，零元是____________。
9、设〈B,∧,∨,′，0，1〉是布尔代数，其中′代表补运算，对任意的a∈B,有a∨a′=____,a∧a′=______.
10、设图G1=<V1,E1>, G2=<V2,E2>,且E2E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。
11、下图的点连通度为 ，边连通度为_________.

12、在一棵有2个2度顶点，3个3度顶点，其余顶点都是树叶的无向树中应该有_________片树叶。

三、计算题（每5分，共20分）
1、给定个体域D={a,b},A(a,a)=T,A(a,b)=F,A(b,a)=F,A(b,b)=T,试求(x)(y)A(x,y)的真值。

2、设A={a,b,c,d}, R={〈a,c〉，〈c,b〉，〈b,b〉，〈a,d〉}，求r(R)，s(R) ，t(R)。

3、已知集合A={2,3,4,6,8}，B={2,3,6}，R是A上的整除关系，求盖住集，画出R的哈斯图，并求B的最大元、最小元，极大元、极小元，上界、上确界，下界、下确界。

4、求命题公式(P→Q)(RP)的主析取范式和主合取范式。

四、证明题（每题10分，共30分）
1、将下列推理符号化并给出形式证明：
每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。
设P(x)：x是大学生，Q(x)：x是文科生，S(x)：x是理科生，T(x)：x是优等生，c：小张。

2、设<G，*>为群。若在G上定义二元运算о,使得对任何元素x，yÎG，有xоy = y*x。证明<G，о>也是群。

3、若R和S都是非空集A上的等价关系，证明RS是A上的等价关系。