2002年4月至2011年7月历次自考离散数学试题汇总（打印版） - 图文

e9=(v3,v5), e10=(v5,v6) 令ai为ei上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，

T的总权和=1+2+3+4+5=15

31.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2) (换名) ?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2) ??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2) ??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2) 四、证明题

32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的

x?y

?d(vi)=2(x+y-1)。

i?1 又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是

x?y

?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4

i?1 从而2(x+y-1)≥x+2y+2k-4 x≥2k-2

33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

(1)?f,g∈F,因为f和g都是A到A的双射函数，故f?g也是A到A的双射函数，从而集合F关于运算?是封闭的。

(2)?f,g,h∈F,由函数复合运算的结合律有f?(g?h)=(f?g)?h故运算?是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，?〉中的幺元

(4)?f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有f?f-1=f-1?f=IA,因此f-1是f的逆元

由此上知〈F，?〉是群

34.证明(?x)(A(x)→B(x)) ? ?x(┐A(x)∨B(x))

?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨…∨(┐A(an)∨B(an))) ?(┐A(a1)∨A(a2)∨…∨┐A(an)∨(B(a1)∨B(a2)∨…∨(B(an)) ?┐(A(a1)∧A(a2)∧…∧A(an))∨(┐B(a1)∨B(a2)∨…∨(B(an))

5

?┐(?x)A(x)∨(?x)B(x) ? (?x)A(x)→(?x)B(x) 五、应用题

35.令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C++语言 t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t 结论：p→t

证①p P(附加前提) ②p∨q T①I

③(p∨q)→(r∧s) P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I

⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I

36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

?Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2…Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

浙江省2002年7月高等教育自学考试

离散数学试题

课程代码：02324

一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

每小题2分，共30分) 1. 下述不是命题的是( )

A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( )

A. 恒真的 B. 恒假的 C. 可满足的 D. 合取范式 3. 命题公式﹁B→﹁A等价于( )

A. ﹁A∨﹁B B. ﹁(A∨B) C. ﹁A∧﹁B D. A→B

4. 设有A={a,b,c}上的关系R={,,,,}，则R不具有( ) A. 自反性 B. 对称性 C. 传递性 D. 反对称性

5. 设×是定义在所有(-∞，+∞)上的连续函数集合C上的普通乘法运算，则×不满足( ) A. 封闭性 B. 结合律

6

C. 交换律 D. 等幂律 6. 下述集合对所给的二元运算封闭的是( )

A. 集合S={-1,0,1,2…}上规定运算?为 a?b=min{a,b-1}, ?a,b∈S B. 集合S={x|x=2n,n∈N}上的乘法运算 C. 集合S={x|x>0}上的规定运算?为 a?b=

lna?lnba?b ?a,b∈S

D. 集合S={1,3,5,7,…}上的加法运算

7. 如果A∩B=A∩C，则下述结论成立的是( ) A. B=C B. B?A且C?A

C. B∪A=C∪A D. 以上结论都不对 8. 下列哪个式子不是谓词演算的合式公式( ) A. (?x)(A(x,2)∧B(y)) B. (?x)(A(x)∧B(x,y)) C. ((?x)∧(?y))→(A(x,y)∧B(x,y)) D. (?x)(A(x)→B(y)) 9. 谓词公式(?y)(?x)(P(x)→R(x,y))∧?yQ(x,y)中变元y( ) A. 是自由变元但不是约束变元 B. 是约束变元但不是自由变元 C. 既是自由变元又是约束变元 D. 既不是自由变元又不是约束变元 10. 设有一个连通平面图，共有6个结点、11条边，则它的边数为( ) A. 6 B. 7 C. 8 D. 9

11. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>}

B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 12. 设(B，·，+，￣，0，1)是布尔代数，a,b是B中元素，a?b,则下面公式中与a·b等价的是( A. a+b B. a·b C. a D. a+b 13. 下图中是哈密尔顿图的是( )

14. 下列是欧拉图的是( )

15. 下列不是森林是( )

7

)

二、填空题(每空2分，共20分)

1. 设P，Q是二个命题，则命题公式P∧Q的合取范式是______。 2. 公式?xP(x)∧?xQ(x)的前束范式为______。

3. 设S(x)∶x是大学生；K(x)∶x是运动员。则命题：“有些运动员不是大学生”的符号化为______。 4. 设A={a,b,c}，则A的幂集ρ(A)=______。

5. 某公司有销售人员82人，维修人员191人，既做销售又搞维修的人员20人，既非销售人员又非维修人员有912人，则该公司总人数为______。 6. 设A={α，β，γ}，R是A上的二元关系R={<α，β>，<β，γ>，<γ,α>}，则其传递闭包为t(R)=______。 7. 设A={{a,b},{a,c},{a},{b},{c}}，则偏序集的哈斯图为______。 8. 设是一个群，若运算*在G上满足______律，则称为Abel群。 9. 设A={1,2,3}，B=?，则A×B=______。

10. 设有如下的有向图，则结点?7的入度为______。

三、计算题(每小题5分，共35分) 1. 求(﹁P∨﹁Q)→(P←→﹁Q)的主析取范式。

2. 给定个体域D={a,b},F(a,b)=T,F(a,b)=F,F(b,a)=F,F(b,b)=T,试求(?x)( ?y)F(x,y)的真值。 3. 设f(x)=x+2 ［0,1］→R，g(x)=x2+1 R→R，求复合函数g?f(x)的象rang?f。

4. 设集合A={a,b,c}上的二元关系R={,,}求关系R的关系图，并判断R的性质(自反性、对称性、反对称性、传递性)。

5. 已知集合A={1,2,3,4,5,6}，B={2,3,5}，R是A上的整除关系，求R的哈斯图，并求B的最大元、最小元，极大元、极小元，上界、上确界，下界、下确界。 6. 试求下图的可达矩阵。

8