离散数学模拟试卷二
西安电子科技大学网络教育 2010学年上学期期末考试试题
课程名称：__离散数学 考试形式： 闭 卷
学习中心：_________ 考试时间： 90分钟
姓 名：_____________ 学 号：
一 填空题（每空2分，合计20分）
1. 一个简单无向图有42条边,有3个结点度为5，3个结点度为3，其余结点度为6。则该图共有 个结点。
2. 设R 为集合A 上的等价关系，对A a ∈?，集合
R a ][= ，称为元素a 形成的R 等价类，Φ≠R a ][，因为 。
3. 设}1,0{=A ，N 为自然数集，??
?=是偶数。
，是奇数，，x x x f 10)( 若
A A f →：，则f 是 射的，若A N f →：，则f 是
射的。 4.
{1,2,3,4}A =上二元关系{2,4,3,3,4,2R =，R 的关
系矩阵R M 中24m =______，34m =______。
5. 若>= S 成立，其中() W G S -是 。 6. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________， A B ⊕=________。 7. 设:,()3f R R f x x →=+, g :,g()21R R x x →=+,则复合函数 ()()____________f g x =, (g )()__________________f x =。 8. 设e 是群G 上的幺元，若a G ∈且2a e =,则1 a -=____ , 2a -=__________。 9. 无向图G 具有一条欧拉回路，当且仅当G 是 ，并且所有结点的度数都是 。 10. 设{2,3,6,12}A =, 是A 上的整除关系，则偏序集,A <>的最大元 是________，极小元是________。 二 选 择（每题2分，合计20分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．设f 和g 都是X 上的双射函数，则1 )(-g f 为（ ）。 A 、11 --g f ； B 、1)(-f g ； C 、1 1 --f g ； D 、1 -f g 。 5．下面集合（ ）关于减法运算是封闭的。 A 、N ； B 、}2{I x x ∈ ； C 、}12{I x x ∈+ ； D 、}{是质数x x 。 6．具有如下定义的代数系统>*<,G ，（ ）不构成群。 A 、}10,1{=G ，*是模11乘 ； B 、}9,5,4,3,1{=G ，*是模11乘 ； C 、Q G =（有理数集），*是普通加法 ； D 、Q G =（有理数集），*是普通乘法。 7．设},32{I n m G n m ∈?=，*为普通乘法。则代数系统>*<,G 的幺元为（ ）。 A 、不存在 ； B 、0 32?=e ； C 、32?=e ； D 、11 32--?=e 。 8．下面集合（ ）关于整除关系构成格。 A 、{2，3，6，12，24，36} ； B 、{1，2，3，4，6，8，12} ； C 、{1，2，3，5，6，15，30} ； D 、{3，6，9，12}。 9．无向图>= A 、},,,{4341><> B 、},,,{6451><> C 、},,,{8474><> D 、},,,{3221><> 10．有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件（ ）。 A 、63-≥m n ； B 、63-≤m n ； C 、63-≥n m ； D 、63-≤n m 。 三 计 算（每题8分， 合计40分） 1．设},,{c b a A =上的关系 },,,,,,,{><><><><=b c c b b a a a ρ，求出 )()(,)(ρρρt s r 和。 2. 集合}36,24,12,6,3,2{=A 上的偏序关系 为整除关系。设 }12,6{=B ，}6,3,2{=C ，试画出 的哈斯图，并求A ，B ，C 的最 大元素、极大元素、下界、上确界。 3. 图给出的赋权图表示五个城市54321v v v v v ，，，，及对应两城镇间 公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。 4. 已知}654321{，，，，，=G ，7?为模7乘法。试说明>?<7， G 是否构成群？是否为循环群？若是，生成元是什么？ 5. 给定命题公式)())((W S R Q P ∨?∨∧?∧，试给出相应的二元树。 四 证明题（每题10分， 合计20分） 1. 试证明若>*<,G 是群，G H ?，且任意的H a ∈，对每一个G x ∈，有a x x a *=*，则>*<,H 是>*<,G 的子群。 2.符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。 西安电子科技大学网络教育 2010学年上学期期末考试答题纸 课程名称：__离散数学 考试形式： 闭 卷 学习中心：_________ 考试时间： 90分钟 姓 名：_____________ 学 号： 一 填空题（每空2分，合计20分） 1 16 2 },{][aRx A x x a R ∈=；R a a ][∈ 3 双射 满射 4 1,0 5 S G -≤；的连通分支数。 6 {1,3}A B -=，{1,3,6}A B ⊕= 7 ()()24f g x x =+，()()27g f x x =+ 8 1a a -=，2a e -= 9 连通，偶数 10： 最大：12，极小：2,3 二 选 择（每题2分，合计20分，在正确答案上划√） 1 A B √ D 2 √ B C D 3 A B √ D 4 A B √ D 5 A √ C D 6 A B C √ 7 A √ C D 8 A B √ D 9 A √ C D 10 A B C √ 三 计 算（每题8分 合计40分） 1．解},,,,,,,,,,,{)(><><><><><><=c c b b b c c b b a a a r ρ， },,,,,,,,,{)(><><><><><=a b b c c b b a a a s ρ， },,,,,,,,,{2 ><><><><><==c c b b c a b a a a ρρρ ， } ,,,,,,,,,,,{23><><><><><><==b c c b b a c a b a a a ρρρ } ,,,,,,,,,,,,,{)(2><><><><><><><=?=∴ b c c b c c b b c a b a a a t ρρρ2．解： 的哈斯图为 集合 最大元 极大元 下界 上确界 A 无 24，36 无 无 B 12 12 6，2，3 12 C 6 6 无 6 3．解：此问题的最优设计方案即要求该图的最小生成树， 由破圈法或避圈法得最小生成树为： 其权数为1+1+3+4 = 9 。 4．解：>?<7， G 既构成群，又构成循环群，其生成元为3，5。因为：7?的运算表为： 7? 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 1）由运算表知，7?封闭； 2）7?可结合（可自证明） 3）1为幺元； 4）11 1 =-，421=-，531=-，241=-，351=-，661=-， 综上所述，>?<7， G 构成群。 由331 =，232 =，633 =，434 =，535 =，136 =。所以，3 为其生成元，3的逆元5也为其生成元。 故>?<7， G 为循环群。 5．解：命题公式对应的二元树见右图。 四 证明题（每题10分 合计20分） 1. （1）设群>*<,G 的幺元为e ，则G x ∈? 有 x e e x *=*，∴H e ∈即H 非空。 （2）H b a ∈?,，则 G x ∈? 有 b x x b a x x a *=**=*,，从而 H b a b a x b x a b x b b a b b x b a x b a ∈*∴**=**=****=****=**--------11111111,)()()()()()( 故 >*<,H 是>*<,G 的子群。 2. 设)(x P ：x 喜欢美术，)(x Q ：x 喜欢体育，)(x R ：x 喜欢音乐。论域：人。 命题形式化为：前提： ))()((x Q x P x ?→?，))()((x R x Q x ∨?，)(x R x ?? 结论：)(x P x ??。 证明：（1）)(x R x ?? P (2) )(a R ? ES(1) (3) ))()((x R x Q x ∨? P (4) )()(a R a Q ∨ US(4) (5) )(a Q T(2)(4)I (6) ))()((x Q x P x ?→? P (7) )()(a Q a P ?→ US(6) (8) )(a P ? T(5)(7)I (9) )(x P x ?? EG(8) ∴ 结论有效。