2022年2022年离散数学题库证明题 .pdf

《2022年2022年离散数学题库证明题 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学题库证明题 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编号题目答案题型分值大纲难度1用 先 求 主 范 式 的 方 法 证 明 (P Q)(PR) (P （Q R）答：先求出左右两个公式的主合取范式(PQ)(PR) (PQ)(PR) (PQ (RR)(P(QQ)R) (PQ R)(PQR)(PQ R)(PQ R) (PQR)(PQ R)(PQ R) (P （QR）) (P（QR ）) (PQ)(PR) (PQ (RR)(P(QQ)R) (PQ R)(PQR)(PQ R)(PQ R) (PQR)(PQ R)(PQ R) 它们有一样的主合取范式，所以它们等价。证明题10 2.3 ；2.4 3 2给 定 连通 简 单 平 面图G=， 且 |V|=6,

2、|E|=12, 则对于任意 fF, d(f)=3。答：因为|V|=63，且 G= V,E,F 是一个连通简单无向平面图，所以对任一 fF，deg(f)3。由欧拉公式 |V|-|E|+|F|=2可得|F|=8 。证明题10 6.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 再由公式Ffdeg(f)=2|E|，Ffdeg(f)=24 。因为对任一 fF，deg(f)3，故要使上述等式成立，对任一 fF，deg(f)=3

3、。3证明对于连通无向简单平面图，当边数 e30 时， 必存在度数 4 的顶点。答：若结点个数小于等于3 时，结论显然成立。当结点多于 3 个时，用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得Vvdeg(v)=2|E| 得 5n2m 。又因为 G= V,E,F是一个连通简单无向平面图，所以对每个面 f,deg(f)3。由公式Ffdeg(f)=2|E|可得， 2m 3k。再由欧拉公式|V|-|E|+|F|=2可得252m-m+32m=151m 从而 30m,这与已知矛盾。证明题10 6.4 3 4在一个连通简单无向平面图G= V，E，F中若

4、 |V|3，则 |E|3|V| 6。答：|V|3，且 G= V，E，F是一个连通简单无向平面图，d(f) 3，fF。由公式Ffdeg (f)=2|E|可得， 2|E|3|F| 。再由欧拉公式|V|-|E|+|F|=2可得证明题10 6.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - |V|-|E|+32|E|2。|E|3|V| 6。5设 G= 是连通的简单平面图，|V|=n3，面数为 k, 则 k 2n-4。答：记|E

5、|=m。因为 G= 是连通的简单平面图， 故每个面的度数都不小于3。从而由公式Ffdeg(f)=2|E|可得 3k2m 再由欧拉公式 |V|-|E|+|F|=2有 m=n+k-2 及23kn+k-2 故 k2n-4。证明题10 6.4 3 6在 半 群 中 ， 若 对a,bG， 方 程a*x=b 和y*a=b 都有惟一解，则 是一个群。答：任意取定 aG ， 记方程 a*x=a 的惟一解为 eR。 即 a*eR=a。下证 eR为关于运算 *的右单位元。对bG ，记方程 y*a=b 的惟一解为 y。是半群，运算*满足结合律。b*eR=(y*a)*eR=y*(a*eR)=y*a=b 。类似地，记方

6、程 y*a=a 的唯一解为 eL。 即 eL*a=a。下证 eL为关于运算 *的左单位元。对bG ，记方程 a*x=b 的惟一解为 x。是半群，运算*满足结合律。eL*b=eL*(a*x)=(eL*a)*x=a*x=b 。从而在半群 中, 关于运算 *存在单位元，记为e。证明题10 8.3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 现证 G中每个元素关于运算 *存在逆元。对bG ， 记 c 为方程 b*x=e 的惟一

7、解。下证 c为b关 于 运 算 的 逆 元 。 记d=c*b 。则b*d=(b*c)*b=e*b=b 。b*e=b, 且方程 b*x=b 有惟一解，d=e。b*c=c*b=e 。从而 c 为 b 关于运算的逆元。综上所述， 是一个群。7设是一个群， H、K是其子群。定义 G上的关系 R：对任意 a,bG ，aRb 存 在h H,k K, 使 得b=h*a*k ，则 R是 G上的等价关系。答：aG ，因为 H、K是 G的子群，所以 eH且 eK。令 h=k=e,则 a=e*a*a=h*e*k, 从而 aRa 。即 R是自反的。a,b G ，若 aRb ，则存在 h H，kK, 使得 b=h*a*

8、k 。因为 H 、 K是 G的子群， 所以 h-1H且 k-1K。 故 a=h-1*a*k-1,从而 bRa 。即 R是对称的。a,b,c G ，若 aRb,bRc,则存在 h,g H，k,l K, 使得b=h*a*k，c=g*b*l。所以c=g*b*l=g*(h*a*k)*l=(g*h)*a*(k*l)。因为H、K 是 G的子群，所以 g*hH且 k*l K。从而 aRc。即 R是传递的。综上所述， R是 G上的等价关系。证明题10 4.4 3 8设 h 是从群 到的群同答：(1) 因为 h(e1)h(e1)=h(e1e1)= h(e1)= e2h(e1),所以 h(e1)=e2。证明题10

9、 8.2 ；8.3 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 态， G1和 G2的单位元分别为e1和 e2，则（1）h(e1)=e2；（2）a G1，h(a-1)=h(a)-1；（3）若 H G1，则 h(H)G2；（4） 若 h 为单一同态，则a G1，|h(a)|=|a|。(2) aG1，h(a)h(a-1)=h(aa-1)= h(e1)= e2, h(a-1)h(a)=h(a-1a)= h(e1)= e2, 故

10、 h(a-1)=h(a)-1。(3) c,d h(H),a,b H，使得 c=h(a),d=h(b)。故cd=h(a)h(b)=h(ab)。因为 H G ，所以 ab H ，故 cdh(H) 。又 c-1=(h(a)-1=h(a-1)且 a-1H ，故 c-1h(H)。由定理 5.3.2 知 h(H)G2。(4) 若|a|=n, 则 an=e1。故(h(a)n=h(an)=h(e1)=e2。从而 h(a) 的阶也有限，且 |h(a)|n。设|h(a)|=m,则 h(am)= (h(a)m= h(e1)=e2。因为 h 是单一同态，所以 am=e1。即|a|m 。故|h(a)|=|a|。若 a

11、的阶是无限的，则类似于上述证明过程可以得出，h(a) 的阶也是无限的。故结论成立。9设*是集合 A上可结合的二元运算，且a,bA,若 a*b=b*a，则 a=b。试证明：（1）a A,a*a=a，即 a 是等幂元；答：（1）aA, 记 b=a*a。因为 * 是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。（2）a,bA,因为由（1） ，a*(a*b*a)=(a*a)*(b*a)=a*(b*a), (a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故 a*(a*b*a)=(a*b*a)*a，从而 a*b*a=a。证明题10 8.

12、1 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - （2）a,bA,a*b*a=a; （3）a,b,cA,a*b*c=a*c 。（3）a,b,cA, （a*b*c ）*（a*c）=（ （a*b*c ）*a ）*c=(a*(b*c)*a)*c 且(a*c)*(a*b*c)=a*(c*(a*b*c)=a*(c*(a*b)*c)。由（2）可知 a*(b*c)*a=a且 c*(a*b)*c=c，故（a*b*c ）*（a*c）=(a

13、*(b*c)*a)*c=a*c 且(a*c)*(a*b*c)= a*(c*(a*b)*c)= a*c，即（a*b*c ）*（a*c）=(a*c)*(a*b*c)。从而由已知条件知， a*b*c=a*c 。10I 上的二元运算 *定义为：a,bI ，a*b=a+b-2。试证： 为群。答 ：（ 1）a,b,cI ，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c) =a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。 故 (a*b)*c= a*(b*c) ，从而 *满足结合律。（2）记 e=2。对aI ，a*2=a+2-2=a=2+a-2=2*a

14、. 。故e=2是 I 关于运算 *的单位元。（3 ）对aI，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故 4-a 是 a 关于运算 *的逆元。综上所述， 为群。证明题10 8.3 4 11R 是集合 X 上的一个自反关系，求证：R 是对称和传递的，当且仅当 和在 R 中有在 R 中。答： “”Xcba,若Rc, ab,a由 R对称性知Ra, ca,bc,bb,ac,ac,ba, ab,aa,bb, acb,ab,c, a即 R 是传递的。12f 和 g 都是群 到 的同态映射， 证明 是 的 一 个 子 群 。 其 中C=)()(|1xgxfGxx且1、 答：

15、证Cba,，有)()(),()(bgbfagaf，又)()(,)()(1111bgbgbfbf)()()()(1111bgbgbfbfaf (agbgagbfafb()(*)()(*)()111)1baCb1 是 的子群。证明题10 8.2 ；8.3 4 13设 R 是 A 上一个二元关系，,(),(|,RbcRcaAcAbabaS且有对于某一个试证明若 R 是 A 上一个等价关系，则S 也是 A上的一个等价关系。答：（1）S 自反的Aa，由R 自反，),(),(RaaRaa，Saa,（2）S 对称的证明题10 4.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - -

16、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - 传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,S 传递的定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,由（1） 、 （2） 、 （3）得； S 是等价关系。141）用反证法证明RSSQRPQP)()()(。2）用 CP 规则证明)()(),(SQPSQRRQP答： 1 证明：)(RSP（附加前提）RSTE QPP QPTE SQP SPTE

17、 PSTE )()(RPRSTI RPTI 证明题10 2.4 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - RPP RPTE )(RPTE FTI 2、证明PP（附加前提）)(RQPP RQTI )(SQRP )(SQQTI SQTE )(SQPCP 15设 ， 是 半 群 ， e是 左 幺 元 且AxAx?,，使得exx*?，则 是群。答： （1）cbcabaAcba则若*,cbcebecaabaacaabaaaca

18、ba:*,*)*?(*)*?()*(*?)*(*?*:即使事实上(2) e 是之幺元。事实上：由于e 是左幺元，现证e 是右幺元。证明题10 8.1 ；8.3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 为右幺元即由使exexxxeeeexxexxxAexAx,*) 1(*?*)*?()*(*?,*,（3）AxAx1,则xxexxxxexxxexexxxxxxxAx?*?*)*?(*) ?*(:有逆元故有事实上由（2）

19、 ， （3）知： 为群。16设9,3,2,1A，在AA上定义关系RdcbaR,:当且仅当cbda，证明R是AA上的等价关系，并求出?5,2R答：证明： 1） ：,RbabaabbaAAba即 R 自反。2） ：,bcadcbdaRdcba则即Rbadcadbc, 从而，即 R 对称。3） ：cedfedfccbdaRfedcRdcba,则从而ebcecbcedafa，,Rfeba即 R 传递。综上得出， R 是等价关系。且证明题10 4.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

20、 - 第 10 页，共 14 页 - - - - - - - - - 9 ,6,8 ,5,7,4,6, 3,5, 2,4, 13,25,5 ,2baAAbababaAAbabaR17试证明若,G是群，GH，且任意的Ha，对每一个Gx，有axxa，则,H是,G的子群。答 ： 证 明 ：（ 1） 设 群,G的 幺 元 为e， 则Gx有xeex，He即 H 非空。（2）Hba,，则Gx有bxxbaxxa,，从而Hbabaxbxabxbbabbxbaxba11111111,)()()()()()(故,H是,G的子群。证明题10 8.1 ；8.3 5 18证明: 1)PQ ，Q R，R，S P= S 2

21、)A(BC)，C(D E)，F(DE),A=BF 答：证明1)：(1) R 前提(2) Q R 前提(3) Q （1） ， （2）(4) P Q 前提(5) P （3） ， （4）(6) SP 前提证明题10 2.4 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - (7) S （5） ， （6）证明2)： (1) A 前提(2) A(BC) 前提 (3) BC （1） ， （2）(4) B 附加前提(5) C （3） ，

22、 （4）(6) C(D E) 前提(7) D E （5） ， （6）(8) F(DE) 前提(9) F （7） ， （8） B F CP 19证明: 1) 、P Q ， PR, QS = RS 2) 、(PQ)(RS)，(QW) (SX)，(W X)，PR = P 答: 证明 1) ：(1) R 附加前提(2) P R 前提(3) P （1） ， （2）(4) PQ 前提(5) Q （3） ， （4）(6) QS 前提(7) S （5） ， （6）证明题10 2.4 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

23、理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - (8) RS CP， （1） ， （8）证明 2)：（1） P 假设前提（2） P R 前提（3） R （1） ， （2）（4） (P Q)(RS) 前提（5） P Q （4）（6） R S （5）（7） Q （1） ， （5）（8） S （3） ， （6）（9） (Q W)(SX) 前提（10） QW （9）（11） SX （10）（12） W （7） ， （10）（13） X （8） ， （11）（14） WX （12） ， （13）（15）(W X) 前提（16）(W X)(W X) （14）

24、 ， （15）20证明: 答：证明 1)：证明10 2.4 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 1) 、 (UV) (MN), UP, P (QS)，QS =M 2) 、 B D， (EF)D， E= B(1) QS 附加前提（2）P(QS) 前提（3）P （1） ， （2）（4） UP 前提（5） U （3） ， （4）（6） UV （5）（7）(UV)(MN) 前提（8） MN (6),(7) （9） M （8）证明 2)：(1) B 附加前提(2) B D 前提(3) D （1） ， （2）(4) (EF)D 前提(5) (EF) （3） ， （4）(6) EF （5）(7) E （6）(8) E 前提(9) EE （7） ， （8）题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -