《2022年2022年离散数学练习题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学练习题及答案 .pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、填空题1、集合的表示方法有两种：法和法。请把“奇整数集合”表示出来 。1、列举；描述；12|Zkkxx，2、无向连通图G 含有欧拉回路的充分必要条件是不含有奇数度结点.2*、 连通有向图D 含有欧拉回路的充分必要条件是D 中每个结点的入度出度.3、设 R 是集合 A 上的等价关系，则R 所具有的关系的三个特性是、自反性、对称性、传递性.4、有限图G 是树的一个等价定义是：连通无回路（或任一等价定义）.5、设 N(x)：x 是自然数， Z(y)；y 是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为x(N(x)Z(x)x(Z(x)N(x)6、在有向图的邻接矩阵中，第i 行元素之和
2、 ,第 j 列元素之和分别为、结点 vi的出度和结点vj的入度 7、设 A，B 为任意命题公式，C 为重言式，若CBCA，那么命题BA是重言式的真值是1 8、命题公式)(QP的主析取范式为PQ9、 设图G 和 G ,若，则G 是 G 的真子图，若V =V,EE，则 G 是 G 的生成子图 .EEVVEEVV,;或10、在平面图EVG,中,则riir1)deg(2 E ,其中 ri(i=1,2,r)是 G 的面11、设2 ,1,BbaA，则从 A 到 B 的所有映射是11、1= （a， 1） ， （b，1）；2= （a，2） ， （b，2）；3= （a，1） ， （b，2） ；4= （ a，2）
3、 ， （b，1） 12、表达式x yL（x，y）中谓词的定义域是a，b，c，将其中的量词消除，写成与之等价的命题公式为12、 （L（a，a）L（a，b）L（a，c） ）（L（b，a）L（b，b） L（b，c） ） （L（c，a）L（c，b） L（c，c） ）12*、设个体域D a,b, 公式),()(yxyHxGx消去量词化为(G(a)(H(a,a) H(a,b) (G(b)(H(b,a) H(b,b) 13、含有三个命题变项P，Q，R 的命题公式P Q 的主析取范式是14、设 R，S都是集合A 上的等价关系，则对称闭包s(RS)= RS15、设 G 是连通平面图， v,e,r 分别表示 G
4、的结点数， 边数和面数，则v,e 和 r 满足的关系式是erv16、 设 G 是 n 个结点的简单图，若G 中每对结点的度数之和n，则 G 一定是哈密顿图. 17、 一个有向树T 称为根树，若，其中，称为树根，称为树叶 . 若有向图 T 恰有一个结点的入度为0，其余结点入度为 1；入度为 0 的结点；出度为0 的结点 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 18、图的通路中边的数目称为. 结点不重复的通路是通路 .
5、 边不重复的通路是通路 . 通路长度；初级；简单. 19、设 A和 B为有限集， |A|=m，|B|=n ，则有个从 A到 B的关系，有个从A到 B的函数，其中当m n 时有个入射，当m=n时，有个双射。19、*2,!,!m nmmnnCmm20、集合2|AnnN（是 / 不是）可数的。是21 、设上的整除关系在L上定义两个二元运算和：对任意,a bL，( , )abglb a b，( , )ablub a b。请填空（在横线上填是或不是）：是是是不是代数系统, ,L格。代数系统,L有界格。代数系统, ,L有补格。代数系统,L分配格。二、单项选择题（选择一个正确答案的代号，填入括号中）1、设命
6、题公式G= （PQ） ，H=P（QP） ，则 G 与 H 的关系是（A ） 。A GHB HGCG=HD以上都不是2、下列命题公式等值的是( C ) BBAAQPQQPQBAABAAQPQP),()D(),()C()(),()B(,)A(3、设 Va,b,c,d,与 V 能构成强连通图的边集E( A ) (A) , (B) , (C) , (D) , 4、设 L(x)：x 是演员， J(x)：x 是老师， A(x,y)：x 佩服 y. 那么命题“所有演员都佩服某些老师”符号化为 ( B ) (A) ),()(yxAxxL(B) ),()()(yxAyJyxLx(C) ),()()(yxAyJx
7、Lyx(D) ),()()(yxAyJxLyx5、在由 3 个元素组成的集合上，可以有( D ) 种不同的关系。(A)3 (B)8 (C) 9 (D) 512 6、设 S1=,S2=,S3=P(),S4=P()则命题为假的是( A )(A)42SS(B) 31SS(C) 42SS(D) 34SS7、设 G 是连通平面图，有v 个结点， e 条边， r 个面，则r= ( A )(A) ev2 (B)ve2 (C) ev2 (D) ev28、下列命题正确的是（A ） 。A =B =C a a，b，c Da， b，c 1,2,3,4,12L121212,a aa aL aa整除名师资料总结 - -
8、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 9、设 A, B, C 都是集合，如果ACBC，则有 ( C ) (A) AB(B) A B(C) 当 A CBC 时,有 A=B(D) 当 C=U 时, 有 A B10、 设)1 , 0,(B是布尔代数，baBba,，则下式不成立的是( D ) 1)D()C(1)B(0)A(baabababa11、下面给出的一阶逻辑等价式中，（A ）是错的。Ax（A（x）B（x） ）=xA（x）xB（x）B AxB
9、（x）=x （ AB（x） ）Cx（A（x）B（ x） ） = xA（ x）xB（x）DxA（x）= x（A（x） ）三、多重选择题 (每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1、 命题公式(P( PQ ) Q是_式。(1) 重言 (2) 矛盾 (3) 可满足 (4) 非永真的可满足2、给定解释I =(D,CI)=( 整数集， f ( x, y): f ( x, y)=x-y；g( x, y): g( x, y)=x+y；P( x, y): xy) ，下列公式中 _在解释 I 下为真。(1) P(f ( x, y), g( x,
10、y) (2) xy P(f ( x, y), g(x, y) (3) xy( P( x, y) P( f ( x, y), x) (4) xy P( f (x, y), g( x, y) 3、是集合， A =10，则)(AP=_。(1) 100 (2) 99 (3) 2048 (4) 1024 (5) 512 4、集合 =x| x 是整数，2x30，=x| x 是质数， x20，C=1,3,5，则CBA)(=_; CAB)(=_; )()(ABAC=_; ACB)(=_。(1) 1,2,3,5 (2) (3) 0 (4) 1,3,5,7,11,13,17,19 (5) 1,3,5,7 (6)
11、7,11,13,17,19 5、设 A、B、C是集合，下列四个命题中，_在任何情况下都是正确的。(1) 若 AB且 BC，则 AC (2) 若 AB 且 BC，则 AC(3) 若 AB且 BC，则 AC (4) 若 AB 且 BC，则 AC6、 设集合 =a, b, c, d, e, f , g ，的一个划分= a, b, c, d, e, f , g ， 则所对应的等价关系有 _个二元组。(1) 14 (2) 15 (3) 16 (4) 17 (5) 8 (6) 49 (7) 512 7、S =1,2,3,4,5,6,7,8,9,10,11,12，是 S 上的整除关系。 S 的子集 名师资料
12、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 2,4,6 ，则在 中，的最大元是 _；的最小元是 _；的上确界是 _；的下确界是 _。(1) 不存在的 (2) 36 (3) 24 (4) 12 (5) 6 (6) 1 (7) 2 8、设有有限布尔代数 (B,+,*,0,1) ，则 B =_能成立。(1) 1 (2) 2 (3) 3 (4) 4 (5) 5 (6) 8 (7) 9 9、G =0,1,2, n ，n N，定义为模 n 加
13、法，即 xy =(x+y) mod n，则代数系统 (G ，)_。(1) 是半群但不是群 (2) 是无限群 (3) 是循环群 (4) 是变换群(5) 是交换群10、仅有一个结点的图称为( )，当然也是 ( ) (1) 零图(2) 平凡图(3) 补图(4) 子图1. 1 、3。2. 4 。3. 4 。4. 1 ；4；2；2。5. 4 。6. 4 。7. 1 ；7；4；7。8. 2 、4、6。9. 3 、4。10. 2 ；1。四、化简解答题1、(1) 图 G 的嵌入图，如第12 题答案图 . 故图 G 为平面图(4 分 ) (2)在具有 n 个顶点的完全图Kn中删去多少条边才能得到树？解： n 个
14、顶点的完全图Kn中共有2)1(nn条边， n 个顶点的树应有1n条边，于是，删去的边有：2)2() 1() 1(2)1(nnnnn。2、判别谓词公式),(),(yxxFyyxyFx的类型 . 2、 设 I 为任意一个解释， D 为 I 的个体域 . 若在解释 I 下， 该公式的前件为0， 无论),(yxxFy如何取值，),(),(yxxFyyxyFx为 1；若在解释I 下，该公式的前件为1，则,0Dx使得),(yxyF为1，它蕴含着),(,0yxFDy为 1),(yxxF为 1，由y 的任意性，必有),(yxxFy为1，于是),(),(yxxFyyxyFx为 1. 所以，),(),(yxxFy
15、yxyFx是永真式3、化简集合表达式：(ABC)(AC)(C(CB)A) 3、(ABC)(AC) (C(CB)A) (AC)（ CA）(两次用吸收律 ) =( AC)(CA) 第 1 题图1、(1)设图 G(如第 1 题图 )，作图 G的嵌入图，说明图G 是平面图 . 第 12 题答案图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - =(AC)(CC)A(AC) =(AC)A=A4、判断下列哪些运算结果是对的？哪些是错的？请将
16、错误的运算结果更正过来(1) (2) (3) ,(4) , ,（5）ABBA)(（ 6）ABBA)(（7）AAA（8）ABA)(4、(1) 对(2) 错应为(3) 对(4) 错应为 （5）错应为BA（6）错应为BA(或BA或 AAB) （7）错应为，即AAAAAA（8）对5、将命题公式)(PRQP化为只含和的尽可能简单的等值式5、)(PRQP)()(PRQP（优先级有误）)()(RPQP不惟一 . 6、设图 G 如右图 .已知通路(1) v1e5 v5e7 v2e2 v3 (2) v5e6 v2e2 v3e3 v4e8 v2e7 v5(3) v2e7 v5e6 v2(4) v1e1 v2e2
17、v3e3 v4e8 v2e6 v5试回答它们各是简单通路、简单回路、初级通路还是初级回路? 6、(1) 初级通路； (2) 简单回路； (3) 初级回路； (4) 简单通路 . 7、试问 n 取何值时，无向完全图Kn，存在一条欧拉回路？7、由于 Kn有 n 个结点，并且每个结点的度数均为n1，于是，当n 为奇数时， Kn的每个结点的度数都是偶数，所以存在一条欧拉回路8、已知 (L， *， )是格，且二元运算*和 满足分配律，a,b,c L，化简表达式(a* b) (a* c)* ( a* b) (b* c) 解答： (a* b) (a*c)*( a*b) (b*c) (a*b) ( (a* c
18、)* ( b* c)(分配律 ) =(a*b) (a*b)*c) (幂等律 ) =a*b(吸收律 ) 9、化简)()()(RPRQRQP。9、)()()(RPRQRQP=RPQQP)(= =RPQP)(=R10、试将一阶逻辑公式xRyyQyxyPx,化成前束范式。解：v1e1 e5v2e6v5e7 e4 e2 e8v3 v4e3 vev名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - xRzQyxPzyxxRzQzyxyPxxR
19、yQyyxyPxxRyyQyxyPxG,11、指出有向图D(如下图 )中各图是强连通，单侧连通还是弱连通？12、找出无向图G（如右图所示）中的一个点割集，三条边和四条边的边割集各一个11、强连通图为：图(1),(4),(5) ；单侧连通图为：如图(1),(2),(4),(5) ；弱连通图为：图(1)(5). 3. 点割集： a,c,d( 不惟一 )三条边的边割集：(b,c),(c,e),(c,d)( 不惟一 ) 四条边的边割集：(a,b),(a,d),(d,e),(c,e)( 不惟一 ) 13、答案图如下图的虚线图. 13、求图 13 图 G 的对偶图. 14、给定三个图如下图所示，试判断它们
20、是否为欧拉图、哈密顿图、或平面图？并说明理由abcdefg图 G1 图 G2图 G3 14、图 G1是欧拉图，因为每个结点度数均为偶数图 G2是哈密顿图，存在哈密顿回路，如cdgfebac (不惟一 ) 图 G3是平面图可以改画成可平面图，(1)(2)(3)(4)(5) abced图 67 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 如图五、计算题1、设 R 和 S是集合4, 3,2, 1A上的关系，其中4,4,4, 2,
21、3,2,2 , 14,3,3 ,2,3 , 1,1 , 1SR，试求：（1）写出 R 和 S 的关系矩阵； （2）计算111,RSRSRSR。1、解：（1）1000000011000010,0000100001000101SRMM（2）SR=， SR=， ， 1R=， 11RS=， 2、 设 A= a，b，c，d ，R1，R2是 A 上的关系，其中R1= （ a，a） ， （a，b） ， （b， a） ， （b，b） ， （c，c） ， （c，d） ， （d，c） ， （d，d），R2= （a，b） ， （b，a） ， （a，c） ， （c，a） ， （b，c） ， （c，b） ， （a，a）
22、 ， （b，b） ， （c，c）。（1）画出 R1和 R2的关系图；（2）判断它们是否为等价关系，是等价关系的求A 中各元素的等价类。2、解：R1和 R2的关系图如下： （略）由关系图可知，R1是等价关系。 R1不同的等价类有两个，即a，b 和c，d 。由于 R2不是自反的，所以R2不是等价关系。3、设集合 A1, 2, 3, 4, 6, 8, 12 ，R 是 A 上的整除关系，a)画出偏序集 (A, R)的哈斯图；b)写出 A 的子集 2, 4, 6, 8 的上界，下界，最小上界，最大下界；(3) 写出集合 A 的最大元，最小元，极大元，极小元。3、 集合 A1, 2, 3, 4, 6, 8
23、, 12(1) 半序集 (A, R) 的哈斯图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - (2) 子集2, 4, 6, 8 无上界，下界是1,2，无最小上界，最大下界是2. (3) A 无最大元，最小元是1，极大元是8, 12，极小元是1。4、用迪克斯特拉算法求下面有限权图中从A 到 B 的最短路，要求用图示给出求解过程，并计算它们的权值。4、 (本题 12 分) 求有限权图的最短路A B 1 4 2 2 4 1 6 3
24、1 8 9 2 1 2 4 8 3 6 12 2 A B 1 4 A B 1 2 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - A 到 B 的最短路的权值为6. 5、已知带权图G，如图 5所示试求图G 的最小生成树，并计算该生成树的权6、设简单连通无向图G 有 12 条边， G 中有 1 度结点 2 个，2 度结点 2 个， 4 度结点 3 个，其余结点度数不超过3求 G 中至少有多少个结点试作一个满足该条件的简单无向图
25、图 5 5、做法如下：选边 1； 选边 2；选边 3； 选边 5；选边 7 最小生成树为 1,2,3,5,7 如图 4 中粗线所示权数为 18图 4 6、设图 G 有 x 个结点，有握手定理2 1+2 2+3 43 （x 2 2 3） 12 2 271821243xx 9 图 G 至少有 9 个结点满足条件的图如图所示7、求命题公式)()(QPPQP的主合取范式 .7、)()(QPPQP分）（分）（分）（分8)()()(6)00(4)()()2()()(QPQPQQPPQPPQPQPQPPQP7*、求 (PQ)(P Q)的主合取范式并给出所有使命题为真的赋值。解答：原式(PQ)(P Q)(P
26、Q) (PQ) (PQ)(P Q)(P Q) (PQ) (PQ PQ)(P Q) (P Q) (P Q)(P Q) (P Q)(PQ) 1 4 5 8 9 2 10 6 7 3 A B 1 4 2 2 1 2 1 4 5 8 9 2 10 6 7 3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - P (Q Q) P (Q Q) (P Q)(PQ) 命题为真的赋值是P=1,Q=0 和 P=1,Q=1 8、求格的表达式)()()
27、(cbacbacba的对偶式，并计算当 a,b,c 的真值分别为0,1,1 时对偶式的真值8、)()()(cbacbacba的对偶式为)()()(cbacbacba对偶式的真值为)110()110()110(11119、设1,12344321,13424321,4,3 ,2, 1试计算M9、231443211, 12344321, 13241432110、重新排列1，2，3，4，5，6，7，8，9 使得有 4 个数在原来位置上，其它5 个数不在原来位置上，有多少种排法？解答：这是有4 个数不动， 5 个数的错位排列问题。4 个数没有预先指定，故有49种可能。5 个数的错位排列，为!1)1(!
28、21! 111!nnn)5(n! 51! 41! 312111! 544152060所求为554444126444911、试画所有不同构的四阶无向树(四个结点 )12. 求从 1 到 500 的整数中，能被 3 或 5 除尽的数的个数。12. 解：设 A为从 1 到 500 的整数中，能被3 除尽的数的集合。 B为从 1 到 500 的整数中，能被5 除尽的数的集合。则 |A|=500/3=166 （x 表示不超过x 的最大整数）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10
29、页，共 17 页 - - - - - - - - - |B|=500/5=100 |AB|=500/ （3*5）=33 （ 1 分）由包含排斥原理：|A B|=|A|+|B|-|AB|=166+100-33=233 即从 1 到 500 的整数中，能被3或 5 除尽的数有233 个。（ 2 分）13、画图。 对于下图，利用克鲁斯克尔算法求一棵最小生成树。13、 最小生成树为14、 求带权 2、3、5、7、11、 13 的最优二叉树。14、 解 2 3 5 7 11 13 所求最优二叉树为 5 5 7 11 13 10 7 11 13 17 11 13 17 24 41 六、证明题1、试构造推理
30、证明QPSSRRQP,)(. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - 1.R S 前提引入 S 前提引入 R ，析取三段论 ( P Q)R 前提引入 ( P Q) ,拒取式 QP置换 2、证明命题公式)()(QRQP与QRP)(有相同的主析取范式2、方法 1)()(QRQP)()(QRQPQRP)(QRP)(因为两命题公式等值，由主合取范式的惟一性，可知两命题公式的主合取范式是相同方法 2)()(QRQP)()(QR
31、QPRQPQRPRQPQRPQRP)(因为它们的主合取范式相同，可知它们的主析取范式也相同3、设 G 为 9 个结点的无向图，每个结点的度数不是5 就是 6，试证明 G 中至少有 5 个度数为 6 的结点，或者至少有6 个度数为 5 的结点。证明：由握手定理的推论，G 中度数为 5 的结点个数只能是0,2,4,6,8 五种情况；此时，相应的结点度数为6 的结点个数分别为9，7，5，3， 1 个，以上五种对应情况(0,9),(2,7),(4,5),(6,3),(8,1) ，每对情况，两数之和为9，且满足第2 个数大于或等于5，或者第 1 个数大于或等于6，意即满足至少有度数为6 的结点 5 个，
32、或者至少有度数为5的结点 6 个。4、试证明（ AB）（AB）=（ AB）（AB）证明：BABABABABBBAABAABBAABABABA5、设,3.QbabaQ，其中 Q 是有理数集，证明(Q.，+， )是域，和分别是数的加法和乘法. 证明)3(3)()()3()3(),3(3, 3111111112211QbbaababaQbaba且惟一，故运算是Q(3)上的二元运算，加法满足结合律、交换律. . Q(3)的 0 元是 003. 300)3()3(),3(3babaQba有,即存在逆元 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -
33、- - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 所以 (Q(3),)是交换群 . )3(3)()3()3()3(),3(3,31221111111112211QbababbaababaQbaba且惟一，故是 Q(3)上的二元运算 . 容易验证在Q(3)上满足交换律、结合律 . Q(3)的单位元是 103. 任给非 0 元)3(3Qba(a,b 至少一个不为0)，)3(33331)3(22221Qbabbaababa运算在 Q(3)上非 0 元存在逆元 . 所以 (Q(3)0 ， )是交换群 . 可以验证，运算对满足分配律
34、. 所以 (Q(3)， )是域 . 6、设 G 是图，无回路，但若外加任意一条边于G 后，就形成一回路. 试证明 G 必为树 . 证明由树的定义可知，只需证G 连通即可 . 任取不相邻两点u,v, 由题设，加上边就形成一回路，于是去掉边,从 u 到 v 仍有路 u,v，即 u,v 连通，由u,v 的任意性可知， G 是连通的，故G 必是树 . 7、设 G 是平面图，并且G 的所有面的次数均为3，证明ve其中 e是 G 的边数 . v 是 G 的结点数 . 7、因为 G 的所有面的次数为3，因此对 G 的任意面r，有deg(r)=3 从而，)()deg(的面的个数表示的面是GrrrGr又根据定理
35、6，G 的所有面的次数之和等于其边数的2倍，即erGr的面是)deg(即er代入欧拉公式rev，eevve8、设 G 是连通简单平面图，则G 至少有一个度数不超过5 的结点（提示：用反证法）8、因为 G 是连通简单平面图，它的每个面至少有3条边，所以有er23，即32er（其中 r，e 分别为图G 的面数和边数）假设结论不成立，则每个结点的度数都大于等于6则有ev26，即有3ev（其中 v 是图 G 的结点数）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 -
36、 - - - - - - - - 由欧拉公式： 2=eeeerv323=0 矛盾所以G 中至少有一个结点的度数小于或等于59、证明：偶数阶群中阶为2 的元素的个数一定是奇数。证：由群的元素的阶的有关知识， 任一个群中阶为 1 的就只有单位元一个， 阶大于 2 的元素是成双成对出现的，其余的元素就是阶为2 的元素。故阶大于2 的元素有偶数个。 由于这是一个偶数阶群， 而奇数加上一个偶数还是奇数，一个偶数减去一个奇数仍是奇数，故阶为2 的元素一定是奇数。我们用综合法得出了整个推理过程。10、设群 除单位元外每个元素的阶均为2，则是交换群。10、 设为一群。证明：若对任意aG有 a2 =e，e 为幺
37、元，则G为阿贝尔群。证明：对任一 aG ，由已知可得 a*a=e，即 a-1=a。对任意 a,bG ，因为 a*b=(a*b)-1=b-1*a-1=b*a，所以运算 *满足交换律。从而 G,*是交换群。10*、设 为一群。证明：若对任意a，b G 有(a b)2 =a2b2，则 G 为阿贝尔群。10*、证：对任意a,bG ，(a*b)2=(a*b)*(a*b)=a*(b*a)*b 又由题设 (a*b)2=a2*b2=(a*a)*(b*b)=a*(a*b)*b （ 2 分）从而 a*(b*a)*b=a*(a*b)*b。两边同时左乘a-1，右乘 b- 1得： a*b=b*a （ 3 分）因此， *
38、运算满足交换律，故 为阿贝尔群。11、在一个群 中，若 A和 B 都是 G的子群。若 AB=G ，则 A=G或 B=G 。证明：用反证法证明。若AG且 BG ，则有 aA,aB且 bB,bA。因为 A，B都是 G的子群，故 a,bG ，从而 a*bG 。因为 aA,所以 a1A。若 a*bA,则 b= a1*(a*b)A，这与 aB矛盾。从而 a*bA。同理可证 a*bB。综合可得 a*bAB=G ，这与已知矛盾。从而假设错误，得证A=G或 B=G 。12、任一有限半群一定在等幂元。证明：设 是一个有限半群。任取aS，由于 *满足结合律，我们有 a,a2,a3, ,an, S 因为 S 是有限
39、集合， 故 a,a2,a3,an,不可能两两不同。从而一定存在正整数k,m,1km名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - 使得 ak=am令 p=m-k，则由于 *满足结合律， ak=am= ap* ak。对任意正整数 qk，有aq= ak * akq =（ap* ak）*akq= ap* aq（#）若 p=q， 则元素 ap就是一个等幂元。 否则因为 p1， 故存在正整数 n 满足 np k。故利用（ #）可得an
40、p= ap* anp= ap* (ap* anp)=ap2* anp= ap2*( ap* anp) =ap3* anp= anp* anp故 anp就是 S的一个等幂元。13、设V是有限字母表，给定代数系统*,V，其中是串的连接运算。对于任一串*V，建立*V到N的映射f，()|f。证明f是*,V到,N的一个满同态，且当| 1V时，f是同构映射。13、 证明对于*V中任意两字符串和，因为| |，所以()|()()fff( )0f， 对于任一正整数nN， 取aV，则|naaan，所以，()nf aaan，f是*,V到,N的一个满同态。当| 1V时，设 Va，()nf aaan，( )0f，f是双
41、射，因此，f是一个同构映射。14、设 R ，S为 A上的两个等价关系，且R S。定义 A/R 上的关系 R/S： R/S 当且仅当 S 证明： R/S 为 A/R 上的等价关系。14、证明： S为 A上的等价关系，那么对任意x 有S，所以 R/S，R/S 是自反的；（ 2 分）若R/S，则 S，由 S 对称知 S，所以 R/S，R/S 是对称的；（ 3 分）若R/S，R/S，则 S，S，由 S 传递知 S，所以 R/S，R/S 是传递的。（ 3 分）故 R/S 为 A/R 上的等价关系。15、设 N4 =0，1，2, 3 ，f：N4N4定义如下：名师资料总结 - - -精品资料欢迎下载 - -
42、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 410411)(xxxxf当当令 F = f0,f1,f2,f3 ，其中f0为 N4上恒等函数。给定一代数结构，且jijifff4（这里 为函数合成运算， +4为模 4 加运算） 。试证与同构。15、证建立双射 h：FN4，使 h（f i） i（ i=0，l，2，3） ；（ 6 分）由于对任何fi，fj F，)()()()(444jijijifhfhjifhffh故 h 为一同构映射 ,与同构得证。16、在边长为 1 的正方
43、形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8 （5 分） 。证明：把边长为1 的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8 。七、综合题1、假设下列陈述都是正确的：(1) 学生会的每个成员都是学生并且是班干部；(2) 有些成员是女生。问是否有成员是女班干部？请将上述陈述和你的结论符号化，并给出你的结论的形式证明。1、解：有成员是女班干部。将命题符号化，个体域为全总个体域。xM：x是学生会的成员。xS：x是学生xG：x是班干部xW：x是女性前提：xGxSxMx
44、，xSxWxMx结论：xGxWxMx证明：xSxWxMx P eSeWeM ES， e为额外变元xGxSxMx P eGeSeM T名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - eM TeS TeG TeW TeGeWeM TxGxWxMx EG2、已知A，证明 (P(A)，A)是布尔代数。S P(A)，求 S 的余元，说明理由2、证明因为集合A 非空，故 P(A)至少有两个元素，显然，是 P(A)上的二元运算 . 由定理
45、，任给B,C,DP(A), H1BD=DCCD=DCH2B(CD)=(BC)(BD) B(CD)=(BC)(BD) H3P(A)存在和 A，BP(A), 有 BB， BA BH4，BP(A), BA，存在 AB，有BAB)= AB(A B)=所以 (AAP,),()是布尔代数 . 对任意 S， 因为S(AS)=(S A)(S S)=A，S (AS)=S(AS)=故 S的余元为 AS名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -