《离散数学》总复习.pdf

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

1、?离散数学总复习离散数学总复习 1 12 23 34 43 14 14 24 31 2 3 4,ACovA=p11.11.设设是是，上上的的偏偏序序关关系系，则则。.解解 知知识识点点:,.CovAx yyx=p偏偏序序关关系系确确定定元元素素 盖盖住住元元素素1234 3,1,4,2,4,3 A,AA 12.12.设设是是一一个个代代数数系系统统，为为定定义义在在 上上的的二二元元运运算算。若若，则则称称运运算算 为为可可交交换换的的。M若若，则则称称运运算算 为为可可结结合合的的。若若，则则称称运运算算 为为等等幂幂的的。,x yA xyyx=,()()x y zA xyzxyz=,xA

2、xxx=QQ374289236?离散数学总复习离散数学总复习e若若，则则称称 为为幺幺元元。若若，则则称称 为为零零元元。,xA exxex=,xAxx=1S,13.13.设设是是一一个个代代数数系系统统，若若满满足足（），2（），3（），S,则则称称是是一一个个独独异异点点。运运算算封封闭闭结结合合律律成成立立有有幺幺元元G,S,G,SS=14.14.是是一一个个群群，是是的的平平凡凡子子群群，则则或或者者。eGG,G 15.15.群群的的运运算算表表中中每每一一行行或或每每一一列列都都是是 中中元元素素的的。置置换换nnKE=16.16.个个结结点点的的无无向向完完全全图图的的边边数数。1

3、(1)2nn17.17.一一棵棵树树有有一一个个结结点点的的度度数数为为2 2，二二个个结结点点的的度度数数为为3 3，三三个个结结点点的的度度数数为为4 4，则则有有个个结结点点的的度度数数为为1 1。.解解 知知识识点点:树树的的基基本本概概念念及及图图的的基基本本定定理理（握握手手定定理理）x设设有有 个个结结点点的的度度数数为为1 1，1 1 22 33 42123 1)xx+=+=+（则则有有101Tevev=树树 的的边边数数 与与结结点点数数 的的关关系系：.1deg()2viive=QQ374289236?离散数学总复习离散数学总复习()QPQR四四.求求合合式式公公式式的的主

4、主析析取取、主主合合取取范范式式。.解解()QPQR()QPQR)QPQR（)PQQR（)PQRPQRPQR（111011010mmm110101100001000MMMMM()()()PQRPQRPQR()()PQRPQR 1,2E=五五.已已知知论论域域ab(1)f(1,1)P1TTF22(2)f1(1,2)P(2,1)P(2,2)PF1.(,()(,()P a f aP b f b求求2.()()(,)(),()xy P x yP f xf yQQ374289236?离散数学总复习离散数学总复习1.(,()(,()P a f aP b f b2.()()(,)(),()xy P x yP

5、 f xf y.解解(1,(1)(2,(2)PfPf(1,2)(2,1)PPTFF()(,1)(),(1)(,2)(),(2)xP xP f xfP xP f xf(1,1)(1),(1)(1,2)(1),(2)PP ffPP ff(2,1)(2),(1)(2,2)(2),(2)PP ffPP ff(1,1)(2,2)(1,2)(2,1)PPPP(2,1)(1,2)(2,2)(1,1)PPPP()()FFTT()()TTFFFTFQQ374289236?离散数学总复习离散数学总复习六六.用用推推理理规规则则证证明明以以下下论论证证：所所有有有有理理数数是是实实数数，某某些些有有理理数数是是整整

6、数数，因因此此某某些些实实数数是是整整数数。.证证明明():():():Q xxxxxxRI设设为为有有理理数数。为为实实数数。为为整整数数。()()(),QRxxx()()()xxQI x()()()xxRI x()()()1(x QIxxP()()()2 Q aI a(1)ES(3)()Q a(2)TI(4)()I a(2)TI()()()5(x QRxxP()()()6 Q aR a(5)US(7)()R a()()()8 R aI a(4)(7)TI(3)(6)TI()()()9(x RIxx(8)EGQQ374289236?离散数学总复习离散数学总复习 ,(),(),()Aa b c

7、 dARa bb ab cc dr R s R t R=七七.设设，上上的的二二元元关关系系为为，试试求求。.解解RM=abcdabcd01001010000100002RRRMMM=o01000100101010100001000100000000=o()Ar RRI=U ,a aa bb ab bb cc cc dd d=()Cs RRR=U ,a bb ab cc bc dd c=1010010100010000=QQ374289236?离散数学总复习离散数学总复习32RRRMMM=o10100100010110100001000100000000=o=01011010000000004

8、3RRRMMM=o01010100101010100000000100000000=o1010010100000000=2,Ra aa cb bb d=3,Ra ba db ab c=4,.Ra aa cb bb d=(),.t Ra aa ba ca db ab bb cb dc d=QQ374289236?离散数学总复习离散数学总复习 2,3,4,5,7,10,12,13,16,17,19,20,21,22,25,29,30,(mod3),ARARx yx yAxyRA=八八.已已知知，是是 上上的的同同余余模模3 3关关系系，即即且且试试求求由由该该等等价价关关系系 所所确确定定的的 的

9、的一一个个划划分分。.解解 ,(mod3),Rx yx yAxyRA=且且是是 上上一一个个等等价价关关系系。,22(mod3)Rx xA x=,23,0,1,2,x xA xk k=L2,5,17,20 29=，,33(mod3)Rx xA x=,33,0,1,2,x xA xk k=L3,12,21 30=，,44(mod3)Rx xA x=,43,0,1,2,x xA xk k=L4,7,10,13,16,19,22 25=，/,234,RRRA R=2,5,17,20,29 3,12,21,30 4,7,10,13,16,19,22,.25=QQ374289236?离散数学总复习离散数

10、学总复习 ,()(),Aa bP AP A=九九.，求求出出上上的的包包含含关关系系，证证明明包包含含关关系系是是偏偏序序关关系系，并并画画出出其其哈哈斯斯图图，问问是是否否为为全全序序集集。.解解 (),P Aaba b=,aba baaaa bbbba ba ba b=，()CovP A=,abaa bba b a b ,a b(),P A 由由哈哈斯斯图图可可以以看看出出不不是是全全序序集集。QQ374289236?离散数学总复习离散数学总复习11,2,3,4AA=十十.设设，上上的的偏偏序序关关系系如如图图，画画出出其其哈哈斯斯图图，说说明明此此偏偏序序关关系系是是否否为为全全序序关关

11、系系。12342,AAp.已已知知偏偏序序集集哈哈斯斯图图如如图图所所示示，求求出出 上上的的偏偏序序关关系系。.解解 1,2,3,4,4,1CovA=3412,Ap由由哈哈斯斯图图可可以以看看出出是是全全序序集集。1324.解解 1,3,1,4,3,2 CovA=Q1,1,2,2,3,3,4,4,1,3,1,4,3,2,1,2 =pQQ374289236?离散数学总复习离散数学总复习十十一一.证证明明以以下下两两个个图图同同构构.证证明明GGabcdabcd,GV EGV E=()()给给图图和和的的结结点点标标上上记记1 1号号如如图图。1 1:,.2aa bb ccVgdVd()()作作

12、的的映映射射(,)(),()ijijeevEggvEvv=且且满满足足若若，则则。,GV EGV EGG=所所以以图图和和同同构构，即即QQ374289236?离散数学总复习离散数学总复习,GKruskal十十二二.对对于于图图利利用用算算法法求求出出一一棵棵最最小小生生成成树树。1124555473644465566.解解11233444560()11234445630C T=+=+=+=QQ374289236?离散数学总复习离散数学总复习,GaGHy yaay yGHG =十十三三.设设是是群群，对对任任一一，令令，试试证证明明是是子子群群。.证证明明HG显显然然。(),.1x yHaGx

13、 aax y aay=有有使使得得()xyaxya=xay=()axy=.xyH(2).HG运运算算 在在 中中显显然然满满足足结结合合律律（在在 中中结结合合律律成成立立）(),.3 Gee aa eaeH=中中的的幺幺元元 使使,.xH exx ex=并并使使(4).xHx aax=有有，11()xxax11()xaxx=11.axxa=1.xH,HG 因因此此，是是子子群群。QQ374289236?离散数学总复习离散数学总复习,()()SSabaaa bbbababab =十十四四.如如果果是是半半群群，且且 是是可可交交换换的的，证证明明：若若 中中有有元元素素，使使得得，则则。.证证

14、明明,()S 封封闭闭，结结合合律律成成立立的的半半群群代代数数系系统统是是，,.abSaaa b bb=，()()abab()abab=()ab ab=()aabb=()()aabb=.ab=410,(,:()()()(),CGx xxCGabi cdiCabicdiacbdadbc iGG=+=+gggg十十五五.设设 是是复复数数集集合合，上上的的二二元元运运算算为为复复数数的的普普通通乘乘法法即即。试试构构造造 关关于于普普通通乘乘法法 运运算算表表，并并证证明明代代数数系系统统是是一一个个群群。QQ374289236?离散数学总复习离散数学总复习410,Gx xxC=.解解 11,i

15、i=，g11ii11ii11ii11iiii11ii11(1)g运运算算 封封闭闭。(2)CG结结合合律律在在 上上成成立立，则则在在 上上自自然然成成立立。(3)g运运算算的的幺幺元元为为1 1，,11.xGxxx=gg使使(4)G中中的的每每个个元元素素有有逆逆元元：111=，111=（），1ii=，1().ii=,Gg因因此此是是一一个个群群。QQ374289236?离散数学总复习离散数学总复习1,GuGGaba ubG=g十十六六.设设是是群群，在在 中中定定义义新新的的运运算算：证证明明：也也是是群群。.证证明明1(),1,a bG aba ubG=ggG关关于于运运算算封封闭闭。1

16、(),()(2)a b cG abca ubc=gg11()a ubuc=gggg11a ub uc=gg gg1()()ab cab uc=gg11()a ub uc=gggg11a ub uc=gg gg()().abcab c=G关关于于运运算算 结结合合律律成成立立。13(),GuaG uau uae aa=ggg关关于于运运算算 的的幺幺元元为为 即即1aua uua ea=ggguaaua=eGg（为为 关关于于运运算算 的的幺幺元元）。11,4()(CaG aau auaa=ggg关关于于运运算算 的的逆逆元元记记为为其其中中为为 关关于于运运算算 的的逆逆元元）,11.Ca a

17、a uu auu=gg ggQQ374289236?离散数学总复习离散数学总复习(),ABCCAABC十十七七.有有、三三人人 这这三三人人中中 一一位位是是经经理理,一一位位是是会会计计,一一位位是是司司机机.已已知知 的的年年龄龄比比会会计计大大,和和司司机机的的年年龄龄不不相相同同,司司机机的的年年龄龄逻逻辑辑小小比比B B小小.试试判判断断、三三人人确确切切问问题题的的身身份份。.解解ABC经经理理会会计计司司机机FFFTFB的的年年龄龄司司机机的的年年龄龄会会计计的的年年龄龄.B是是经经理理TTFFABC因因此此，是是会会计计，是是经经理理，是是司司机机。QQ374289236?离散

18、数学总复习离散数学总复习()61 6十十八八.一一个个六六面面体体的的 个个面面，分分别别标标有有的的六六个个数数字字，它它放放置置的的状状态态不不同同，可可见见到到的的数数字字也也不不同同，请请判判断断出出每每个个相相对对面面的的数数字字分分别别是是与与；逻逻辑辑小小问问题题与与；与与。.解解14与与26与与35与与QQ374289236?离散数学总复习离散数学总复习()十十九九.张张三三、李李四四、王王五五三三位位同同学学中中有有一一人人在在别别人人不不在在时时为为集集体体做做好好事事。事事后后老老师师问问是是谁谁做做的的好好事事。张张三三说说：“是是李李四四”，王王五五说说：“不不是是我我”，李李四四说说：“不不是是我我”。已已知知他他们们三三人人中中有有一一人人说说的的是是真真话话，试试判判断断做做好好事事逻逻辑辑小小问问题题的的是是谁谁？.解解张张三三李李四四王王五五说说话话说说话话说说话话做做好好事事做做好好事事做做好好事事TFFTFFTFFFTFTFFFT判判断断相相容容F李李四四因因此此，说说真真话话的的是是，做做好好事事的的是是王王五五。QQ374289236