離散數(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重點輔導 例4 試求下面公式的主析?。ㄖ骱先。┓妒?，并寫 出成真指派和成假指派。 ()()PQQP ()()PQQP ()PQQP ()()()PQQPPPQQ ()()()PQPQPQ 0,2,3 1 ()PQ 成真指派：00，10，11 成假指派：01 2重點輔導 例5 試證 PQQPPQ)( ()()QPPPQ 證明證明

2、)(QPPQ )()(QQPPQ )(QPPQ PQ PQ ()QPPQ 3重點輔導 例1 符號化下列命題 a)不是所有的男人都比女人高。 M(x):x是男人，W(x):x是女人，H(x,y):x比y高。 ),()()(yxHyWyxMx 4重點輔導 例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重點輔導 例1 求集合的冪集 )(xxP )(P ) ,(P ,

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

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

5、, IA R3=, IA R4=, IA R5=, , IA 12重點輔導 例8 畫出哈斯圖 RcbaP, a b c ,ca ,cb ,cba ,ba 13重點輔導 例9 求極大（?。┰畲螅ㄐ。┰?、上（下） 界，上（下）確界 a b c d e f g h i jk 極大元：j,k 極小元:a,b,e 最大元：無 最小元：無 B=a,b,c,d,e,f,g 上界： h,i,j,k 下界：無 無上（下）確界 14重點輔導 例10 判斷函數(shù)的類型 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重點輔導 例11 求復合函數(shù) ,3 , 2 , 1qpYX , baZ , 3, 2, 1qppf fg 求 ,bqbpg , 3, 2, 1bbbfg 16重點輔導 例12 求復合函數(shù) ,3 , 2 , 1qpYX ,baZ , 3, 2, 1qppf fg 求 ,bqbpg , 3, 2, 1bbbfg 17重點輔導 例: 求幺元、零元、逆元 N, I, Q, R上的普通加法 + 和乘法 * +：幺元 0，a-1 = -a； *：幺元 1，零元 0， a-1 = 1/a； 命題公

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

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