离散数学考试复习资料(编辑修改稿)

离散数学考试复习资料(编辑修改稿)内容摘要：

三、判断题 1. 空间中的平行六面体是平面图。 （ ） 每个顶点的度都是偶数的无向图一定是欧拉图。 （ ） 顶点数目相同，边数也相同的两个无向图一定同构。 （ ） 函数的逆关系还是函数。 （ ） A， B， C 都是集合，如果 A∪ B=A∪ C，则 B=C。 （ ） 设 R是环， A,B是 R的两个理想，且 B包含于 A,则 A/B是 R/B的理想，并且 R/B /(A/B) 同构于 R/A。 （ ） 7. qp  的对偶是 qp。 （ ） 8. 设 G 是有 r 个面的连通平面图，顶点数和边数分别是 n 和 m，则 nm+r=2。 （ ） 9. n 阶有 向完全图有 n（ n1）条边。 （ ） 10. 在代数系统  ,S 中，若 zxyx  ，则 zy。 （ ） 11. 设无向图 T 是树，则 T 中一定没有简单回路。 （ ） 12. 能够画在一张平面上的图是平面图。 13. 设  ,S 是代数系统， B 是 S 的非空子集，则  ,B 是  ,S 的 子代数。 （ ） 14. 循环群的子群仍然是循环群。 （ ） 15. 格不一定是布尔代数。 （ ） 16． 1+101=110是命题。 （ ） 17．“ 全体立正 是命题”。 （ ） 18．“ 明天是否开大会。 ”是命题。 （ ） 19．“ 如果天气好，那么我去散步 ”是命题。 （ ） 20. 判断 (Z,)是否为格。 其中 是数的小于或等于关系。 （ ） 21． 设 R 是实数集，“＋”为数的加法，“”定义为 baba  . 试问 R对二元运算＋和是否构成环。 （ ） 22. 设集合 A＝ {18的正整数因子 }， 为整除关系，说明 A, 是否是偏序关系。 （ ） 23．  }{ 是对的。 （ ） 24． 是 的子集。 （ ） 25．如果 ST＝ SM，则 T＝ M。 （ ） 26. 已知 S＝ {2,a,{3},4},R={{a},3,4,1},则 {a}S。 （ ） 27. 整数集合 Z和普通的减法运算是封闭的。 （ ） 28．在 R中定义二元运算： * ,a*b=a+b+ab,对于任意 a,b 属于 R，则 R,*是独异点。 （ ） 29． 整数集合 {1,2,3,4,6,12}关于整除关系构成了偏序集，并且该偏序集是格。 （ ） 四、证明题 1. 设 G， *是群，具有幺元 e，如果对 G 的任意元素 a，都有 a178。 =e, 则 G， *是交换群 2. 形式证明 qsprsrqp  , 3. 证明： P(QR)PQR. 4．试证明： RSQPSRQP  )())(( 5．试证明： QRRP  )()( 6. 证明： )()( xxBxxA   ))()(( xBxAx  7． 设 G是图，无回路，但若外加任意一条边于 G后，就形成一回路 . 试证明 G必为树 . 8. 设 B是任意集合，试验证 (P(B),)是群 . P(B)是集合 B的 幂集， 是集合的对称差运算， 9． 给定代数系统 (G,+,*), 二元运算见表一，表二 . 表一 表二 + a b c D * a b c D A a b c D a a a a a B b a d C b a b c d C c D a B c a c d b D d C b A d a d b c 证明 (G,+,*)是域 . 10. 证明如果非空集合 A上的二元关系 R 和 S 是偏序关系，则 SR 也是 A上的偏序关系． 11． 试证 A－ (B－ C)＝ (A－ B)(AC) 12．设非空集合 A，验证 ( AAP ,~,),(  )是布尔代数， 13. 试证明属于关系不满足传递性，即对于任意的集合 A,B,C若 A∈ B且 B∈ C 不一定有 A∈ C 14．设 A,B为两个集合，证明 A— B=A当且仅当 A∩ B= 248。 15. 设 R,S都是非空集合 A上的二元关系，且他们是对称的，证明： RoS具有对称性当且仅当 RoS=SoR. 16. 已知 g： AB,f： BC 1） 已知 fog是单射的且 g是满射的，证明 f是单射的 2） 已知 fog 是满射的且 f是单射的，证明 g是满射的 17．设 A是传递集，证明 A+也是传递集。 18．设 G是 n阶无向简单图，其直径为 d(G)=2, ο (G)=n2，证明 G的边数 m≥ 2n4 19． V=S,*是可交换半群 ,若 a,b ∈ S是 V中得幂等元，证明 a*b也是 V中的幂等元 20．设 L是格，证明对于任意 a,b,c,d∈ L有： ( a∧ b)∨ (c∧ d)≤ (a∨ c)∧ (b∨ d) 五、计算题 1. 无向树 T 有 2 个 2 度顶点， 1 个 3 度顶点， 3 个 4 度顶点，其他的都是树叶，问 T 中有多少片树叶。 2. 设公式    xQxP  ，其中 P(x)： x2， Q(x)： x=0， F 是永假式，个体域是 {1， 2}，求公式 A(x)的真值 3. 设集合 X={1， 2， 3, 4}， X 中的关系为 F={1， 1， 1， 2， 1， 4， 2， 1， 2， 2， 3， 3， 4， 1， 4， 4} 写出 F 的关系矩阵及其关系图， F 有哪些性质。 4. (1) n(n≥ 1)阶无向完全图与有向完全图各有多少条边 ?为什么。 (2)完全二部图 K mn, 中共有多少条边 ?为什么。 (3) 每个顶点的度都为 k 的无向图称为 k 正则图，问： n 阶 k正则图中共有多少条边 ?为什么。 5. 设集合 L={a， b}，在 L 中规定 + 和如下： a+a=a， a+b=b+a=b， b+b=b aa=a， ab=ba=a， bb=b 问 L， +， 能构成代数系统吗。 若可以，写出该代数系统的运算表。 该代数系统有什么特性。 6. 设多重集 A={{ }， { ， 1}， {1， 1，  }}， B={{ ， 1}， {1}}.计算 A B， A B，AB 7. 设集合 M={1， 2， 3， 4， 5}，  和  是 M上的两个置换，  =  12543 54321 ，  =（ 1 4 5）（ 2 3），用轮换的形式写出  ， ， － 1  － 1。 8. 对集合 L，规定对于 x， y∈ L， x≤ y 当且仅当 x是 y 的因子。 问下面哪几个偏序集是格 ?为什么。 (1)L={1, 2, 3, 4, 6, 12} (2)L={1, 2 , 3, 48, 12, 14} (3)L={1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 9． 在全总个体域中符号化下列命题。 （ 1）是金子总是要发光的。 （ 2）并非所有微笑的人都是高兴的。 （ 3）平面图的色数不超过 4 10． 若无向图 G 是欧拉图， G 中是否存在割边 ?为什么 ? 11. 设 集 合 }6,5,4,3,2,1{A ， R 是 定 义 在 A 上 的 二 元 关 系 ，},|,{ 是素数baAbabaR  ，写出 R 的关系矩阵并求 R 的对称闭包。 12. 设集合 A={2， 3， 4， 6， 8， 12， 24}， R 为 A上的整除关系。 （ 1）画出半序集（ A， R）的哈斯图； （ 2）写出集合 A中的最大元、最小元、极大元、极小元； （ 3）写出 A的子集 B={2， 3， 6， 12}的上界、下界、最小上界，最大下界。 13. 令 X={ 1x , 2x ,„ , mx },Y={ 1y , 2y ,„ , ny }。 问 ⑴有多少个不同的由 X 到 Y 的关系。 ⑵有多少个不同的由 X 到 Y 的函数。 ⑶当 n,m 满足什么条件时，存在单射，且有多少个不同的单射。 14．在全总个体域中符号化下列命题。 （ 1）在中国工作的人并非都是中国人。 （ 2）有的人在微笑但内心不高兴。 （ 3）每种金属都可以溶解在某种液体种。 15. 将下列命题符号化： (1) 虽然交通堵塞，但是老王还是准时到达火车站； (2) 张力是三好学生或优秀共青团员 (3) 老李或小刁中有一个人去广州出差 16. 判定公式 PQ与 PQ是否等值 . 17． 用等值演算法判定公式 P(QR)PQR 是永真式。 永假式。 18． 求公式 )()( QPRP  的主合取范式和主析取范式 . 19. 化 简下式： (ABC)(ABC) 20． 设命题 P,Q 的真值为 0，命题 R,S 的真值为 1，求命题公式 )()( SQRP  的真值 . 21． 将下列 命题符号化： （ 1）每个母亲都爱自己的孩子； (2) 所有的人都呼吸； (3) 有某些实数是有理数 . 22． 指出下列公式 ),()),(),(( yxxHzyLyxRyx  中量词的每次出现辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元 . 23． 给定解释 I： ① D＝ {2,3}。 ② D中特定元素 a=2； ③ 函数为 2)3(,3)2(  ff ④ 谓词 F(x)为 F(2)=0,F(3)=1 G(x,y)为 G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1 L(x,y)为 L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0 求在解释 I下各公式的真值 . (1) ),()( axGxxF 。 (2) ),( yxyLx ； 24． 讨论公式 ),(),( yxxFyyxyFx  的类型 . 25． 将公式 F )),()(()),()(( zyzDyyCyxBxAx  化为前束范式 . 26. 判定下面二图是否同构。 27. 设 G＝ (V,E)是一个无向图， },...,{ 821 vvvV  },,,,{ 87434551133221  vvvvvvvvvvvvvvE (1) 画出 G的图解； (2) 指出与 v3邻接的结点 ，以及与 v3关联的边； (3) 指出与 e1关联的结点； (4) 该图是否有孤立结点和孤立边。 (5) 求出各结点的度数，并判断是不是完全图。 (6) G＝ V,E的 V， E各是多少。 28. 给定下列六个图 (如图 )， G1＝ V1,E1,其中 V1={a,b,c,d,e},E1={(a,b） ,(b,c),(c,d),(a,e)} G2＝ V2,E2,其中 V2=V1,E2={(a,b),(b,e),(e,b),(a,e),(d,e)} G3＝ V3,E3,其中 V3=V1,E3={(a,b),(b,e),(e,d),(c,c)} G4＝ V4,E4,其中 V4=V1,E4={a,b,b,c,c,a,a,d,d,a,d,e} G5＝ V5,E5,其中 V5=V1,E5={a,b,b,a,b,c,c,d,d,e,e,a} G6＝ V6,E6,其中 V6=V1,E6={a,a,a,b,b,c,e,c,e,d} 试问： (1) 哪些图是有向图。 哪些图是无向图。 (2) 哪些是简单图。 (3) 哪些是强连通图。 哪些是单侧连 通图。 哪些是弱连通图。 a a  a  a  a  a  b e b e b  e b   e b   e b  e c d c d c  d c d c d c d (G1) (G2) (G3) (G4) (G5) (G6) 图 29. 求图 G的点割集、割点、边割集和割边 . V 1 V 4 V 2 V 1 V 3 V。