《2022年2022年离散数学 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学 .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学综合复习资料一、判断题1如果有限集合 A 有 n 个元素，则其幂集p(A)有 2n 个元素。2R1，R2 是集合 A 上的二元关系，若 R1 和 R2 都是反自反的，则 R1 R2 也是反自反的。3“这朵玫瑰花多美丽呀！”是一个命题。4A、B、C 是任意集合，如果AB 及 BC，则 AC。5“中国有四大发明”是一个命题。6对任意集合 A，A。7集合 A 的一个划分确定 A 的元素间的一个等价关系。8含有幺元的半群为独异点。9每个图中，边数等于结点度数总和两倍。二、基本题1.将下列命题符号化：（1）4 是偶数和合数。（2）如果天不下雨，王荣就去图书馆。（3）所有人都是要死的。2.求命题公
2、式 P(PQ)的主合取范式。3.举出 A=a,b,c 上的二元关系 R 和 S满足：（1）R 是自反的、对称的；（2）S 是对称的、传递的。4.已知图 G 的邻接矩阵 M 如下，结点集为 v1,v2,v3,v4,v5，试画出该图，并求V2 的入度 d-(V2)和出度 d+(V2)。M=5.将下列命题符号化：（1）如果张三和李四都不去，她就去。（2）今天要么是晴天，要么是雨天。0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -（3）每一个有理数都是实数。6.求命题公式(PQ)
3、的主析取范式。7.举出 A=a,b,c 上的二元关系 R 和 S满足：（1）R 既不是自反的又不是反自反的；（2）S 既不是对称的又不是反对称的。8.已知图 G 的邻接矩阵 M 如下，结点集为 v1,v2,v3,v4,v5，试画出该图，并求V2 的入度 d-(V2)和出度 d+(V2)。M=9.举出 A=a,b,c 上的二元关系 R 和 S满足：（1）R 是自反的、传递的；（2）S 是反自反的、传递的。10.设集合为 A=1，3，4，12，24，其上的偏序关系为整除，试列出相应的关系并画出哈斯图。11.二元运算 a*b=a+b-ab 在实数集 R 上是否满足交换律和结合律?12.设集合为 A=
4、1，2，5，10，20，其上的偏序关系为整除，试列出相应的关系并画出哈斯图。13.二元运算 a*b=a+b-3 在实数集 R 上是否满足交换律和结合律?三、证明题1.试证明：AB,(B C)A 2.设 R,S 是 A 上的等价关系，证明R S 也是 A 上的等价关系。3.设,*G是一群，Gx。定义：bxaba*，Gba,。证明,G也是一群。4.试证明：A(BC),D A,B DC 5.在任何有向图中，所有结点的入度之和等于所有结点的出度之和。6.试证明：A B,CBAC 7.设 R，S 是 A 上的相容关系，证明RS也是 A 上的相容关系。8.设 G=有 11 个结点，m 条边，证明 G 或者
5、其补图 G 是非平面图。9.设 f 是从 A 到 B 的一个函数，定义A 上的关系 R：aRb当且仅当 f(a)=f(b)，证明 R是 A 上的等价关系。0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -10.试证明代数系统 为群，已知*运算满足结合律，运算表如下表所示。*a b c d a a b c d b b a d c c c d a b d d c b a 11.在有 6 个结点 12 条边的连通简单平面图中，每个面由3 条边围成。名师资料总结-精品资料欢迎下载-
6、名师精心整理-第 3 页，共 9 页 -离散数学综合复习资料参考答案一、判断题题目1 2 3 4 5 6 7 8 9 答案错误正确错误正确正确错误正确正确错误二、基本题1.答案：（1）（pq）（2）（pq）（3（(x)(R(x)Q(x)）2.答案：解：原式P(P Q)(P (Q Q)(P Q)(PQ)(P Q)(P Q)3.答案：解：此题答案不唯一（1）R=,（2）S=,4.答案：解：该矩阵不对称，所以G 是有向图，如右图。d-(V2)=2，d+(V2)=1 5.答案：（1）（PQ）R）（2）（P Q）（3）(x)(R(x)Q(x)6.答案：解：(PQ)名师资料总结-精品资料欢迎下载-名师精心
7、整理-第 4 页，共 9 页 -(P Q)PQ 7.答案：解：此题答案不唯一（1）R=,（2）S=,8.答案：解：该矩阵不对称，所以G 是有向图，如右图。d-(V2)=1，d+(V2)=2 9.答案：解：此题答案不唯一（1）R=,（2）S=,10.答案：解：RA=,11.答案：解：1）交换律：a*b=a+b-ab=b+a-ba=b*a所以满足交换律2）结合律：(a*b)*c=(a+b-ab)*c=a+b-ab+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc a*(b*c)=a*(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ac-ab-bc+abc 所以(a*
8、b)*c=a*(b*c)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -所以满足结合律。12.答案：解：RA=,13.答案：解：1）交换律：a*b=a+b-3=b+a-3=b*a 所以满足交换律2）结合律：(a*b)*c=(a+b-3)+c 3=a+b+c-6 a*(b*c)=a+(b+c-3)-3=a+b+c-6 所以(a*b)*c=a*(b*c)所以*满足结合律。三、证明题1.答案：证明：(1)AB P(2)A P(附加前提)(3)B T(1),(2)I(4)(B C)P(5)BC T(4)E(6)B T(6)I(7)BB(矛盾)T(3),(6)I 2.答案：证明：
9、a)自反性：对任意 a A，因为 A,S，所以 RS，即 RS具有自反性。b)对称性：对任意 a,b A，如果有 RS，则 R 且 S。因为 R,S 是等价关系，所以具有对称性，所以 R 且 S。所以 RS，即 R S具有对称性。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -c)传递性：对任意 a,b,c A，若有,RS 则,R 且,S 则因为 R,S 是等价关系，所以具有传递性，所以 R 且 S 所以 RS，即 RS 具有传递性。所以 RS 是 A 上的等价关系。3.答案：证明：显然是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有幺元，每个元素有
10、逆元。（1）Gcba,，有)()*(*)*()(cbacxbxacxbxacba所以运算是可结合的。（2）1x是,G的幺元。事实上，Ga，有axxaxa11*；aaxxax*11（3）Ga，111*xax是a在,G中的逆元。事实上，1111111*)*(xxaxxaxaxa1111111*)*(xaxxaxaxax由以上证明，,G是群。4.答案：证明：(1)D P（附加前提）(2)D A P(3)A T(1)(2)I(4)A(BC)P(5)(BC)T(3)(4)I(6)B P(7)C T(5)(6)I(8)DC CP 5.答案：证明：因为有向图中，每条有向边必对应一个入度和一个出度，所以，结点
11、入度之和等于边数，出度之和也等于边数，名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -因此，所有有入度之和等于出度之和。6.答案：证明：(1)A B P(2)AB T(1)E(3)CB P(4)CB T(3)E(5)BC T(4)E(6)BC T(5)E(7)AC T(2)(6)I 7.答案：证明：a)自反性：对任意 a A，因为 A,S，所以 RS，即 RS具有自反性。b)对称性：对任意 a,b A，如果有 RS，则 R 并且 S。因为 R,S 是相容关系，所以具有对称性，所以 R 并且 S。所以 RS，即 R S具有对称性。所以 RS 是 A 上的相容关系。8.答案
12、：证明：设 G 中有 m 条边，则 m+m =11*(11-1)/2=55。若 G,G 均为平面图，则 m=3*11-6=27，m=3*11-6=27 则 m+m=27+27=54 与上矛盾，所以 G 或 G 是非平面图。9.答案：证明：a)自反性：对任意 a A，f(a)=f(a)，所以 aRa，即 R 是自反的。b)对称性：对任意 a，b A，若 aRb，即 f(a)=f(b)，即 f(b)=f(a)，故 bRa，即 R 是对称的。c)传递性：对任意 a，b，c A，若 aRb，bRc，即 f(a)=f(b)，f(b)=f(c)即 f(a)=f(b)=f(c)，故 aRc，即 R 是传递的。所以 R 是 A 上的等价关系。10.答案：名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -证明：由运算表可知*运算满足封闭性；由运算表可知 a 为幺元，每个元素有逆元是其本身；所以为群11.答案：证明：由欧拉公式v-e+r=2 知：6-12+r=2 解得 r=8。又每个面至少由三条边围成，所以2*12=3r 得 r=8。因此每个面恰由三条边围成。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -