離散數(shù)學(xué) 練習(xí)題及答案[重要知識(shí)]

1、例3 給出下列公式的真值表 PRQP)( RQPQP RQP A 000 100 010 110 001 101 011 111 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 成真指派：100，101，110，111 1重點(diǎn)輔導(dǎo) 例4 試求下面公式的主析?。ㄖ骱先。┓妒?，并寫(xiě) 出成真指派和成假指派。 ()()PQQP ()()PQQP ()PQQP ()()()PQQPPPQQ ()()()PQPQPQ 0,2,3 1 ()PQ 成真指派：00，10，11 成假指派：01 2重點(diǎn)輔導(dǎo) 例5 試證 PQQPPQ)( ()()QPPPQ 證明證明

2、)(QPPQ )()(QQPPQ )(QPPQ PQ PQ ()QPPQ 3重點(diǎn)輔導(dǎo) 例1 符號(hào)化下列命題 a)不是所有的男人都比女人高。 M(x):x是男人，W(x):x是女人，H(x,y):x比y高。 ),()()(yxHyWyxMx 4重點(diǎn)輔導(dǎo) 例2 證明 )( )( ),( )( )axA xB xx B xxA x 1)( )( ) 2)( )( ) 1) 3)( ) 4)( ) 3) 5)( ) 2)4) 6)( ) 5) xA xB xP A uB uUS xB xP B uUS A uT xA xEG 證明證明 5重點(diǎn)輔導(dǎo) 例1 求集合的冪集 )(xxP )(P ) ,(P ,

3、 , , 6重點(diǎn)輔導(dǎo) 例2 n 個(gè)元素的集合上，可以定義多少個(gè)關(guān)系？ 設(shè)集合X,Y, |X|=m, |Y|=n，可以定義多少個(gè) 從X到Y(jié)的函數(shù)？ )2( 2 n nm (|Y|X| ) 7重點(diǎn)輔導(dǎo) 例例3 對(duì)任意兩個(gè)集合對(duì)任意兩個(gè)集合A, B,試證試證 BABAA)( 證明證明 對(duì)于任意的x )(BAAx )(BxAxAxxx )(BAxAxxx )(BAxAxxx )(BxAxAxxx BxAxxx BAx 因?yàn)?x 是任意的,所以有 )()(BAxBAAxx的真值為T(mén), BABAA)(因此 8重點(diǎn)輔導(dǎo) 例4 判斷關(guān)系的性質(zhì) 100 010 011 1 R M a bc 1 R R1 是自反

4、的、反對(duì)稱、傳遞的。 , 1 ccbbbaaaR 9重點(diǎn)輔導(dǎo) 例5 求關(guān)系的閉包 ,cbaX ,ccbbaaR X IRRr)( ,cbbaR ,cbba,ccbbaa C RRRs)( ,bcabcbba 解： 10重點(diǎn)輔導(dǎo) 例5（續(xù)） ,cbaX ,cbbaR )3()2( )(RRRRt ,cacbba ,cacbba , )2( caR )3( R 11重點(diǎn)輔導(dǎo) 例7 設(shè) A=1,2,3, 求出A上所有的等價(jià)關(guān)系 解：先求A的各種劃分： 1 2 3 5 1 2 3 2 1 2 3 3 1 2 3 4 1 2 3 1 設(shè)對(duì)應(yīng)于 i 的等價(jià)關(guān)系為Ri ,則： R1=, = = IA R2=

5、, IA R3=, IA R4=, IA R5=, , IA 12重點(diǎn)輔導(dǎo) 例8 畫(huà)出哈斯圖 RcbaP, a b c ,ca ,cb ,cba ,ba 13重點(diǎn)輔導(dǎo) 例9 求極大（?。┰?，最大（?。┰?、上（下） 界，上（下）確界 a b c d e f g h i jk 極大元：j,k 極小元:a,b,e 最大元：無(wú) 最小元：無(wú) B=a,b,c,d,e,f,g 上界： h,i,j,k 下界：無(wú) 無(wú)上（下）確界 14重點(diǎn)輔導(dǎo) 例10 判斷函數(shù)的類(lèi)型 1 x 1 y 2 y 3 y 2 x 3 x 2 x 3 x 1 x 3 y 2 y 1 y 4 x 入 射 映射函數(shù) 雙(入、滿)射滿射 4

6、y 1 y 2 x 3 x 1 x 2 y 3 y 4 y 1 x 2 x 3 x 1 y 2 y 3 y 15重點(diǎn)輔導(dǎo) 例11 求復(fù)合函數(shù) ,3 , 2 , 1qpYX , baZ , 3, 2, 1qppf fg 求 ,bqbpg , 3, 2, 1bbbfg 16重點(diǎn)輔導(dǎo) 例12 求復(fù)合函數(shù) ,3 , 2 , 1qpYX ,baZ , 3, 2, 1qppf fg 求 ,bqbpg , 3, 2, 1bbbfg 17重點(diǎn)輔導(dǎo) 例: 求幺元、零元、逆元 N, I, Q, R上的普通加法 + 和乘法 * +：幺元 0，a-1 = -a； *：幺元 1，零元 0， a-1 = 1/a； 命題公

7、式集合上的 和 ：幺元F，零元T ：幺元T，零元F 冪集P(S)上的和 ：幺元 ，零元S ：幺元S，零元 18重點(diǎn)輔導(dǎo) 例1 G 是一個(gè)有是一個(gè)有 15 條邊的簡(jiǎn)單圖，條邊的簡(jiǎn)單圖， 有有 13 條邊，請(qǐng)問(wèn)條邊，請(qǐng)問(wèn) G 中有多少個(gè)結(jié)點(diǎn)中有多少個(gè)結(jié)點(diǎn)? G 解： 共有共有 15 + 13 = 28 條邊，條邊，GG 是一個(gè)完全圖，它的是一個(gè)完全圖，它的 結(jié)點(diǎn)數(shù)與結(jié)點(diǎn)數(shù)與 G 相同，設(shè)為相同，設(shè)為 n，根，根 據(jù)定理?yè)?jù)定理4， GG n(n-1)/2 = 28 n = 8 19重點(diǎn)輔導(dǎo) 例3 請(qǐng)畫(huà)出請(qǐng)畫(huà)出 4 個(gè)頂點(diǎn)個(gè)頂點(diǎn) 3 條邊的所有可能不同構(gòu)條邊的所有可能不同構(gòu) 的無(wú)向簡(jiǎn)單圖？的無(wú)向簡(jiǎn)單圖

8、？ 20重點(diǎn)輔導(dǎo) 例4 若無(wú)向圖若無(wú)向圖 G 中恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則中恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則 這兩個(gè)結(jié)點(diǎn)必是連通的。這兩個(gè)結(jié)點(diǎn)必是連通的。 設(shè) G 中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為 u ,v。 若 u 與 v 不連通,則至少有兩個(gè)連通 分支 G1 和 G2，u G1,v G2。 于是 G1 和 G2 各含一個(gè)奇數(shù)度結(jié)點(diǎn)， 這與握手原理的推論矛盾， 因此 u 與 v 必是連通的。 證明 試證試證 21重點(diǎn)輔導(dǎo) 例6 判斷下列圖哪些是 E 圖、H圖？ E E非 HH非 22重點(diǎn)輔導(dǎo) 例7 證明 設(shè)設(shè) G 有有 r 個(gè)面，個(gè)面， 當(dāng)當(dāng)v = 3, e = 2時(shí)，時(shí)， 3v-6 顯然成立。顯然成立。 若若 e 3, 則每一個(gè)面至少由則每一個(gè)面至少由 3 條邊圍成，所以條邊圍成，所以 re32 er 3 2 eevrev 3 2 2 3 2 e v ev 3663 ve 設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn), e 條邊的連通簡(jiǎn)單平面 圖，若 v 3，則有 v。 證 明 23重點(diǎn)輔導(dǎo) 例10 求圖的最小生成樹(shù) A C B D E 1 2 3 4 5 6 7 A B CD E 12 46 24重點(diǎn)