最新安工大离散数学试卷

200 9-2010 学年第一学期期末考试《离散数学B》试卷（A）一．单项选择题(每题2分，共30分)1．下列命题公式中不．是重言式的是（）A. (┐P∧Q)→(Q→⌝R)B. P→(Q→Q)C. (P∧Q)→PD. P→(P∨Q)2．在0（）Φ之间写上正确的符号。

A. =B. ⊆C. ∈D. ∉3．设个体域是整数集，则下列命题的真值为真的是（）A.∀x∃y (xy=y)B. ∃x∀y(x+y=y)C.∃x∀y(x+y=x)D. ∀x∃y(y=2x)4．关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误．．的是（）A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）B．z是该谓词公式的约束变元C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元5．设论域D={a,b}，与公式(x)A（x）等价的命题公式是（）A．A（a）∧A（b）B．A（a）→A（b）C．A（a）∨A（b）D．A（b）→A（a）6．集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,y∈A}，则R 的性质（）。

A.自反的B.对称的C.传递的，对称的D. 传递的7．设A={a,{a}}，下列命题错误的是（）。

A. {a}∈P(A)B. {a}⊆P(A)C. {{a}}∈P(A)D. {{a}}⊆P(A)8．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，则f（）A．仅是满射B．仅是入射C．是双射D．无逆函数9．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1 R-1的运算结果是（）A．{〈4，1〉，〈2，3〉，〈4，2〉} B．{〈2，4〉，〈2，3〉，〈4，2〉}C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉} 10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A．矛盾式B．重言式C．可满足式D．公式p∧q11．在自然数集N上，下列哪种运算是可结合的？（）A. a*b=a-bB. a*b=max{a,b}C.a*b=a+2bD. a*b=|a-b|12．、有限布尔代数的元素的个数一定等于（）。

A . 偶数 B. 奇数 C. 4的倍数 D. 2的正整数次幂13．设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

A. 10B.4C. 8D. 1214．设无向图G的边数为m，结点数为n，则G是树等价于（）A．G连通且m=n+1 B．G连通且n=m+1C．G连通且m=2n D．每对结点之间至少有一条通路15．设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )A. 自然数B.实数 C .复数 D . (A)--(C)均成立二、填空题（每题2分，共20分）1．公式(⌝P∧Q)∨(⌝P∧⌝Q)化简为，公式 Q→(P∨(P∧Q))可化简为。

2．命题“存在一些人是大学生”的否定是________________________。

3．公式（∀x）((A(x)→B(y，x))∧（∃z）（ C(m，z))→D(n)）中，自由变元是，约束变元是。

4．若集合S的基数|S|=5，则S的幂集的基数|P(S)|= 。

5．设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，则R= 。

6．设A={a,b,c,d}, R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，则r(R)= ,s(R)= ,t( R)= 。

7．设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点<A,*>中，单位元是，零元是。

8．有n个结点的树，其结点度数之和是。

9..群<G,*>的等幂元是，有个。

10.n阶无向完全图K的边数是，每个结点的度数n是。

三．（6分）求命题公式(P∧R)∨(Q∧R)∨⌝P的主析取范式和主合取范式。

四．（6分）证明：A→(B→C)，C→(⌝D∨E)，⌝F→(D∧⌝E),A=>B→F 五．（5分）证明：(A－B)⋃(A－C)=A－(B⋂C)六．（10分）设A=｛1，2，3｝，P（A）是A的幂集，⊆是集合的包含关系，证明：〈P（A），⊆〉偏序集，画出它的哈斯图，并证明该偏序集为格。

七．（10分）设A={1,2,…,10}。

下列哪个是A的划分？若是划分，则写出它们诱导的等价关系。

（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}八．（8分）I上的二元运算*定义为：∀a,b∈I，a*b=a+b-2。

试证：<I,*>为群。

九．（5分）设无向图G=<V,E>，|E|=12。

已知有6个3度顶点，其他顶点的度数均小于3。

问G中至少有多少个顶点？2009~2010学年第一学期期末考试《离散数学B》试卷（A）一．单项选择题(15×2=30分)1．（A）；2．（D）；3.(D)；4．(B)；5．(A) ；6.(B)；7.(B)；8.(C);9.(A)；10. (B)；11.(B) 12.(D) 13.(D); 14.(B);15.(A)二．填空题(17×1=17分)1．⌝P Q→P;2．所有人都不是大学生；3．y,m,n x,z;4. 32;5．R={<1,1>,<4,2>}6．r(R)={<a,a>,<b,b>,<c,c><d,d>,〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉} S(R)= {〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉,<c,a>,<b,c>,<a,b>,<d,a>}t(R)= {〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉,<a,b>,<c,a>,<b,d>.<a,a>,<c,d>,<b,b>，<b,c><c,c>}7．2,68.2(n-1)9.e,110．n(n-1)/2,(n-1)三．(6分)其中主析取范式和主合取范式各占4分(P∧R)∨(Q∧R)∨⌝P（析取范式）⇔(P∧(Q∨⌝Q)∧R)∨((P∨⌝P)∧Q∧R)∨(⌝P∧(Q∨⌝Q)∧(R∨⌝R))⇔(P∧Q∧R)∨(P∧⌝Q∧R)∨(P∧Q∧R)∨(⌝P∧Q∧R)∨( ⌝P∧Q∧R)∨( ⌝P∧Q∧⌝R)∨(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)⇔(P∧Q∧R)∨(P∧⌝Q∧R)∨(⌝P∧Q∧R)∨(⌝P∧Q∧⌝R) ∨ (⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R) (主析取范式)⌝（(P∧R)∨(Q∧R)∨⌝P）⇔(P∧⌝Q∧⌝R)∨(P∧Q∧⌝R）（原公式否定的主析取范式）(P∧R)∨(Q∧R)∨⌝P ⇔(⌝P∨Q∨R)∧(⌝P∨⌝Q∨R)（主合取范式）四．(8分)(1) A P（附加前提）(2) A→(B→C) P(3) B→C T（1），（2）(4) B P(附加前提)(5) C T（3），（4）(6) C→(⌝D∨E) P(7) ⌝D∨E T（5），（6）(8) ⌝F→(D∧⌝E) P(9) F T（7），（8）(10) B→F CP证明方法不唯一，只要遵循逻辑规则即可。

五．(6分)解(A-B)⋃(A-C)=(A⋂～B)⋃(A⋂～C) =A⋂((～B)⋃(～C))=A⋂(～(B⋂C))= A-(B⋂C)六．（10分）证明:验证P（A）中运算⊆满足自反，反对称，传递；从哈斯图中证明任意两个元素都有上确界和下确界即可。

七．(10分)（1）和（2）都不是A的划分。

（3）是A的划分。

其诱导的等价关系是I⋃A{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。

八．(8分)证明：（1）∀a,b ∈I，a+b-2∈I，*满足封闭律。

（2）∀a,b,c∈I，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c) =a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。

故(a*b)*c= a*(b*c)，从而*满足结合律。

（3）记e=2。

对∀a∈I，a*2=a+2-2=a=2+a-2=2*a.。

故e=2是I关于运算*的单位元。

（4）对∀a∈I，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。

故4-a是a关于运算*的逆元。

综上所述，<I,*>为群。

九．（5分）解：设G中度数小于3的顶点有k个，由握手定理24=∑∈Vvv) deg(知，度数小于3 的顶点度数之和为6。

故当其余的顶点度数都为2时，G的顶点最少。

即G中至少有9个顶点。