离散数学练习题及答案PPT学习教案

1、会计学1离散数学练习题及答案离散数学练习题及答案2022-5-192()()PQQP ()()PQQP ()PQQP () () ()PQQP PPQ Q ()()()PQPQPQ 0,2,31()PQ成真指派：00，10，11成假指派：01第1页/共25页2022-5-193PQQPPQ)()()QPPPQ 证明证明)(QPPQ)()(QQPPQ)(QPPQPQ PQ ()QPPQ 第2页/共25页2022-5-194),()()(yxHyWyxMx第3页/共25页2022-5-195)( )( ),( )( )axA xB xx B xxA x 1)( )( ) 2)( )( ) 1)3)

2、( ) 4)( ) 3)5)( ) 2)4)6)( ) 5)xA xB xPA uB uUSxB xPB uUSA uTxA xEG 证明证明第4页/共25页2022-5-196)(xxP)(P) ,(P , , ,第5页/共25页2022-5-197)2(2nnm (|Y|X| )第6页/共25页2022-5-198BABAA)(证明证明对于任意的x)(BAAx)(BxAxAxxx)(BAxAxxx)(BAxAxxx)(BxAxAxxxBxAxxxBAx因为 x 是任意的,所以有)()(BAxBAAxx的真值为T,BABAA)(因此第7页/共25页2022-5-1991000100111RM

3、abc1RR1 是自反的、反对称、传递的。,1ccbbbaaaR第8页/共25页2022-5-1910,cbaX ,ccbbaaRXIRRr)(,cbbaR,cbba,ccbbaaCRRRs)(,bcabcbba解：第9页/共25页2022-5-1911,cbaX ,cbbaR) 3()2()(RRRRt,cacbba,cacbba,)2(caR) 3(R第10页/共25页2022-5-1912解：先求A的各种划分：12351232123312341231设对应于 i 的等价关系为Ri ,则：R1=, = = IAR2=, IAR3=, IAR4=, IAR5=, , IA 第11页/共25页

4、2022-5-1913RcbaP,abc,ca, cb,cba,ba第12页/共25页2022-5-1914abcdefghijk极大元：j,k极小元:a,b,e最大元：无最小元：无B=a,b,c,d,e,f,g上界： h,i,j,k下界：无无上（下）确界第13页/共25页2022-5-19151x1y2y3y2x3x2x3x1x3y2y1y4x入 射 映射函数双(入、满)射满射4y1y2x3x1x2y3y4y1x2x3x1y2y3y第14页/共25页2022-5-1916,3 , 2 , 1qpYX, baZ , 3, 2, 1qppffg 求,bqbpg, 3, 2, 1bbbfg第15页

5、/共25页2022-5-1917,3 , 2 , 1qpYX, baZ , 3, 2, 1qppffg 求,bqbpg, 3, 2, 1bbbfg第16页/共25页2022-5-1918：幺元，零元S：幺元S，零元第17页/共25页2022-5-1919G 是一个有是一个有 15 条边的简单图，条边的简单图， 有有 13 条边，请问条边，请问 G 中有多少个结点中有多少个结点? G解：共有共有 15 + 13 = 28 条边条边，GG 是一个完全图，它的是一个完全图，它的结点数与结点数与 G 相同，设为相同，设为 n，根，根据定理据定理4，GG n(n-1)/2 = 28n = 8第18页/共

6、25页2022-5-1920请画出请画出 4 个顶点个顶点 3 条边的所有可能不同构条边的所有可能不同构的无向简单图？的无向简单图？第19页/共25页2022-5-1921若无向图若无向图 G 中恰有两个奇数度结点，则中恰有两个奇数度结点，则这两个结点必是连通的。这两个结点必是连通的。设 G 中两个奇数度结点分别为 u ,v。 若 u 与 v 不连通,则至少有两个连通分支 G1 和 G2，u G1,v G2。 于是 G1 和 G2 各含一个奇数度结点，这与握手原理的推论矛盾，因此 u 与 v 必是连通的。证明试证试证第20页/共25页2022-5-1922EE非HH非第21页/共25页2022-5-1923设设 G 有有 r 个面，个面，当当v = 3, e = 2时，时， 3v-6 显然成立。显然成立。若若 e 3, 则每一个面至少由则每一个面至少由 3 条边围成，所以条边围成，所以re32er32eevrev32232ev ev 3663ve 设 G 是一个有 v