离散数学(第1次)
- 格式：doc
- 大小：83.50 KB
- 文档页数：15
第1次作业一、单项选择题（本大题共30分，共 15 小题，每小题 2 分）1.图G所示平面图deg(R3)为A.4B.5C.6D.32. 在完全m叉树中，若树叶数为t，分枝点数为i，则有（）。
A.(m-1)i<t-1B.(m-1)i>t-1C.(m-1)i=t-1D.(m-1)i≤t-13.命题a）：如果天下雨，我不去。
写出命题a）的逆换式。
A.如果我不去，天下雨。
B.如果我去，天下雨。
C.如果天下雨，我去。
D.如果天不下雨，我去。
4. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点（）A.5B.4C.2D.65. 假设A={a,b,c,d},考虑子集S={{a,b},{b,c},{d}}，则下列选项正确的是（）。
A.S是A的覆盖B.S是A的划分C.S既不是划分也不是覆盖D.以上选项都不正确6. 没有不犯错误的人。
M(x)：x为人。
F（x）：x犯错误。
则命题可表示为（）。
A.(∀x)(M(x)→F(x)B.(∃x)(M(x)⋀F(x)C.（∀x）(M(x)⋀F(x))D.(∃x)(M(x)→F(x)7. 命题逻辑演绎的CP规则为（）A.在推演过程中可随便使用前提B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果C.如果要演绎出的公式为B→C形式，那么将B作为前提，演绎出CD.设∅(A)是含公式A的命题公式，B<=>A，则可以用B替换∅(A)中的A8. 设G是有6个结点的完全图，从G中删去（）条边，则得到树。
A.6B.9C.10D.159. 设A、B两个集合，当（）时A-B=B。
A.A=BB.A⊆BC.B⊆AD.A=B=ϕ10. 设U={1，2，3，4，5}，A={2，4}，B={4，3，5}，C={2，5，3}，确定集合(A-C)-B = （）。
A.{1,4}B.{2,3,4,5}C.{4}D.ϕ11. 下图的最小生成树的权为（）。
A.40B.44C.48D.5212.对偶式为P↑Q表达式是。
A.P∧QB.P↓QC.P∨QD.P→Q13. 下列语句是命题，并且真值为0的是（）A. 雪式白的。
B.1+2>4。
C.天气真好啊！D.我正在说谎。
14. 如果有限个数的乘积为零，那么至少有一个因子等于零。
N(x)：x是有限个数的乘积。
Z(y)：y为0。
P（x）：x的乘积为0 。
F（y）：y为乘积中的一个因子则命题可表示为（）。
A.(∃x)(N(x)→P(x)∧(∃y)(F(y)⋀(Z(y)))B.(∃x)(N(x)⋀P(x))→(∃y)(F(y)⋀(Z(y)))C.(∃x)(N(x)→P(x)∧(∃y)(F(y)→(Z(y)))D.(∀x)(N(x)→P(x)∧(∃y)(F(y)⋀(Z(y)))15. 设A、B、C是任意集合，判断下述论断是否正确，并将正确的题号填入括号内（）。
A.若A∪B=A∪C，则 B=CB.若A∩B=A∩C ，则 B=CC.若A-B=A-C，则 B=CD.若∼A=∼B，则 A=B二、多项选择题（本大题共20分，共 5 小题，每小题 4 分）1.两个命题变元P和Q生成的4个小项为：。
A.P∧QB.┐P∧QC.P∧┐QD.┐P∧┐Q2.下图是（）。
A.是强连通的B.是弱连通的C.是单侧连通的D.是不连通的3.下列说法正确的是（）A.设<Z,+>是整数加法群，令f: n→-n,∀ n∈Z，则f是Z的一个自同构映射。
B.设G是一个Abel群，令 f: a〖→a〗^(-1) (∀ a∈G)，则f是G的一个自同构映射。
C.设<R^ ,∙>是实数乘法群，<R,+>是实数加法群，令f: x→5x，则f是R 的一个满同态映射D.A、B、C都是正确的。
4.函数f：R×R→R×R,f(<x，y>)=<x+y，x-y>是( )函数。
A.入射B.满射C.双射D.以上答案都不对5.设A={1,2,3}，则集合A上的关系R={<1,1>,<1,3>,<2,1>,<2,3>}是（）关系；A.自反B.反自反C.不是自反D.不是反自反三、判断题（本大题共20分，共 10 小题，每小题 2 分）1. 判断对错：集合{2,3,4，•••}是无限集（）。
2. 设G是一个联结词的集合，若任意一个命题公式都可用G中联结词构成的公式来表示，则称G为最小联结词组。
3. 公式∀xP(x)→∃yQ(x,y)的前束范式是∀x∀y(P(x)→Q(x,y)。
4. 判断对错。
一个谓词公式wff A,如果在一种赋值下为假，则称该wff A 为不可满足的。
5. 下图中（c）和（d）是根树6. 设f∶{x,y}→{1,3,5} 定义为f(x)=1,f(y)=5，则这个函数是入射函数。
7. 设集合A={216，243，357，648}.定义A上的关系 R={〈x,y〉|x,y∈A，且x与y中至少有一个相同数字}。
则R是A上的一个相容关系，R 不是等价关系。
8. 自反（对称、传递）闭包是包含R的最小自反（对称、传递）关系。
（）9. 设X={1,2,3,4},Y={1,2,3,4,5},Z={1,2,3}, f:X→Y,f={,,,},g:Y→Z,g={,,,,}，则g°f={,,,}。
10. 设R是由A={1,2,3,4} 到B={2,3,4} 的关系，S是由B到C={3,5,6}的关系，分别定义为：R={│a+b=6}={,,} S={│b整除c}={,,} 于是复合关系R°S={,,}。
四、计算题（本大题共20分，共 4 小题，每小题 5 分）1.设f,g均为实函数，f(x)=2x+1 , g(x)=x^2+1。
求f°g , g°f , f°f , g°g 。
2.设集合A={1,2,3,4}，A上的二元关系R={(x,y)|x,y∈A,且x≥y},求R的关系图与关系矩阵3.试将公式P∧（P→Q）化为析取范式和合取范式：4.设全集合E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求下列集合：(1)A∩～B；（2）（A∩B）∪～C；（3）～A∪（B－C）；（4）ρ(A)∩ρ(B)五、证明题（本大题共10分，共 2 小题，每小题 5 分）1.符号化下列命题并推证其结论：科学家都是勤奋的。
每个勤奋又身体健康的人在事业中都会获得成功。
存在着身体健康的科学家。
所以存在着事业获得成功的人或事业半途而废的人。
2.设整数集Z上的二元关系R定义如下：R={<x,y>|x,y∈Z,(x-y)/2是整数，证明R在Z上是自反的。
答案：一、单项选择题（30分，共 15 题，每小题 2 分）1. B2. C3. A4. B5. A6. A7. C8. C9. D 10. D 11. C 12. B 13.B 14. B 15. D二、多项选择题（20分，共 5 题，每小题 4 分）1. ABCD2. BC3. AB4. ABC5. CD三、判断题（20分，共 10 题，每小题 2 分）1. √2. ×3. ×4. ×5. √6. √7. √8. √9. √ 10. √四、计算题（20分，共 4 题，每小题 5 分）1.参考答案：f°g(x)=2(x^2+1)=2x^2+3g°f(x)=〖(x^2+1)〗^2+1=4x^2+4x+2f°f(x)=2(2x+1)+1=4x+3g°g(x)=〖(x^2+1)〗^2+1=x^4+2x^2+2所以f°g={<x,2x^2+3>|x∈R}g°f={<x,4x^2+4x+2>|x∈Rf°f={<x,4x+3>│x∈R}g°g={<x,x^4+2x^2+2>|x∈R}解题方案：评分标准：2.参考答案：R={(x,y)│x,y∈A,且x≥y}={(1,1),(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(3,3),(4,3),(4,4) R的关系图如图3-1所示。
解题方案：评分标准：3.参考答案：┐（P∨Q）↔（P∧Q）=(﹁（P∨Q）→（P∧Q）)∧(（P∧Q）→┐（P∨Q）)(等值律)=(（P∨Q）∨（P∧Q）) ∧(┐（P∧Q）∨┐（P∨Q）) (蕴涵律) =（P∨Q）∧(┐P∨┐Q) (分配律) 合取范式=(┐P∨P) ∨(┐P∨Q)∨(┐Q∧P)∨(┐Q∧Q) (分配律)析取范式解题方案：评分标准：4.参考答案：（1）A∩～B={a，d}∩{c，d}={d}.(2) （A∩B）∪～C={a}∪{a,c,e}={a,c,e}.（3）～A∪（B－C）={b,c,e}∪{a,e}={a,b,c,e}.（4）ρ(A)={ϕ,{a},{d},{a,d}}.ρ(B)={ϕ,{a},{b},{e},{a,b},{a,e},{b,e},{a,b,e}}故ρ(A)∩ρ(B)={ϕ,{a}}解题方案：评分标准：五、证明题（10分，共 2 题，每小题 5 分）1.参考答案：解题方案：评分标准：2.参考答案：证明: ∀x∈Z,(x-x)/2=0,，即<x,x>∈R，故R是自反的。
解题方案：评分标准：。
