離散數(shù)學(xué) 練習(xí)題及答案

2 0 2 1 -6 -1 6 1 例 3 給 出 下 列 公 式 的 真 值 表PRQP )(RQP QP RQP A000 100 010 110 001 101 011 111 00000011 11111110 11110000成 真 指 派 ： 1 0 0 ， 1 0 1 ， 1 1 0 ， 1 1 1 2 0 2 1 -6 -1 6 2 例 4 試 求 下 面 公 式 的 主 析 取 （ 主 合 取 ） 范 式 ， 并 寫出 成 真 指 派 和 成 假 指 派 。( ) ( )P Q Q P ( ) ( )P Q Q P ( )P Q Q P ( ) ( ( ) ( ( )P Q Q P P P Q Q ( ) ( ) ( )P Q P Q P Q 0,2,3 1( )P Q 成 真 指 派 ： 00， 10， 11成 假 指 派 ： 01 2 0 2 1 -6 -1 6 3 例 5 試 證 PQQPPQ )( ) ( )Q P P P Q 證明)( QPPQ )()( QQPPQ )( QPPQ PQ PQ ( ( )Q P P Q 2 0 2 1 -6 -1 6 4 例 1 符 號(hào) 化 下 列 命 題a)不 是 所 有 的 男 人 都 比 女 人 高 。 M(x):x是 男 人 ， W(x):x是 女 人 ， H(x,y):x比 y高 。),()()( yxHyWyxMx 2 0 2 1 -6 -1 6 5 例 2 證 明) ( ( ) ( ), ( ) ( )a x A x B x x B x xA x 1) ( ( ) ( ) 2) ( ) ( ) 1)3) ( ) 4) ( ) 3)5) ( ) 2)4) 6) ( ) 5)x A x B x PA u B u USx B x PB u USA u TxA x EG 證 明 2 0 2 1 -6 -1 6 6 例 1 求 集 合 的 冪 集 )( xxP )(P ),( P , , 2 0 2 1 -6 -1 6 7 例 2 n 個(gè) 元 素 的 集 合 上 ， 可 以 定 義 多 少 個(gè) 關(guān) 系 ？ 設(shè) 集 合 X,Y, |X|=m, |Y|=n， 可 以 定 義 多 少 個(gè)從 X到 Y的 函 數(shù) ？)2( 2n nm (|Y|X| ) 2 0 2 1 -6 -1 6 8 例 3 對(duì) 任 意 兩 個(gè) 集 合 A, B,試 證 BABAA )(證明對(duì)于任意的x )( BAAx )( BxAxAxxx )( BAxAxxx )( BAxAxxx )( BxAxAxxx BxAxxx BAx 因?yàn)?x 是任意的,所以有)()( BAxBAAxx 的真值為T,BABAA )(因此 2 0 2 1 -6 -1 6 9 例 4 判 斷 關(guān) 系 的 性 質(zhì) 100 010 011 1RM abc 1RR1 是自反的、反對(duì)稱、傳遞的。 ,1 ccbbbaaaR 2 0 2 1 -6 -1 6 1 0 例 5 求 關(guān) 系 的 閉 包 , cbaX , ccbbaaR XIRRr )( , cbbaR, cbba , ccbbaa CRRRs )( , bcabcbba 解 ： 2 0 2 1 -6 -1 6 1 1 例 5 （ 續(xù) ）, cbaX , cbbaR )3()2()( RRRRt , cacbba , cacbba ,)2( caR )3(R 2 0 2 1 -6 -1 6 1 2 例 7 設(shè) A=1 ,2 ,3 , 求 出 A上 所 有 的 等 價(jià) 關(guān) 系解 ： 先 求 A的 各 種 劃 分 ： 12 3512 32 12 33 12 3412 31設(shè) 對(duì) 應(yīng) 于 i 的 等 價(jià) 關(guān) 系 為 Ri ,則 ：R 1=, = IAR2=, IAR3=, IAR4=, IAR5=, , IA 2 0 2 1 -6 -1 6 1 3 例 8 畫 出 哈 斯 圖 RcbaP , a b c, ca , cb , cba, ba 2 0 2 1 -6 -1 6 1 4 例 9 求 極 大 （ 小 ） 元 ， 最 大 （ 小 ） 元 、 上 （ 下 ）界 ， 上 （ 下 ） 確 界 ab c d ef gh ij k 極 大 元 ： j,k極 小 元 :a,b,e最 大 元 ： 無(wú)最 小 元 ： 無(wú)B=a,b,c,d,e,f,g上 界 ： h,i,j,k下 界 ： 無(wú)無(wú) 上 （ 下 ） 確 界 2 0 2 1 -6 -1 6 1 5 例 1 0 判 斷 函 數(shù) 的 類 型 1x 1y2y3y2x3x2x3x1x 3y2y1y4x 入 射 映 射 函 數(shù) 雙 (入 、 滿 )射滿 射 4y 1y2x3x1x 2y3y4y1x2x3x 1y2y3y 2 0 2 1 -6 -1 6 1 6 例 1 1 求 復(fù) 合 函 數(shù),3,2,1 qpYX , baZ ,3,2,1 qppf fg 求, bqbpg ,3,2,1 bbbfg 2 0 2 1 -6 -1 6 1 7 例 1 2 求 復(fù) 合 函 數(shù),3,2,1 qpYX , baZ ,3,2,1 qppf fg 求, bqbpg ,3,2,1 bbbfg 2 0 2 1 -6 -1 6 1 8 例 : 求 幺 元 、 零 元 、 逆 元 N, I, Q, R上 的 普 通 加 法 + 和 乘 法 *+： 幺 元 0 ， a-1 = -a；*： 幺 元 1 ， 零 元 0 ， a-1 = 1 /a； 命 題 公 式 集 合 上 的 和 ： 幺 元 F， 零 元 T ： 幺 元 T， 零 元 F 冪 集 P(S)上 的 和 ： 幺 元 ， 零 元 S： 幺 元 S， 零 元 2 0 2 1 -6 -1 6 1 9 例 1G 是一個(gè)有 15 條邊的簡(jiǎn)單圖， 有 13 條邊，請(qǐng)問(wèn) G 中有多少個(gè)結(jié)點(diǎn)? G解：共有 15 + 13 = 28 條邊，GG 是一個(gè)完全圖，它的結(jié)點(diǎn)數(shù)與 G 相同，設(shè)為 n，根據(jù)定理4，GG n(n-1)/2 = 28n = 8 2 0 2 1 -6 -1 6 2 0 例 3請(qǐng)畫出 4 個(gè)頂點(diǎn) 3 條邊的所有可能不同構(gòu)的無(wú)向簡(jiǎn)單圖？ 2 0 2 1 -6 -1 6 2 1 例 4若無(wú)向圖 G 中恰有兩個(gè)奇數(shù)度結(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 必 是 連 通 的 。證明試證 2 0 2 1 -6 -1 6 2 2 例 6 判 斷 下 列 圖 哪 些 是 E 圖 、 H圖 ？EE非 H H非 2 0 2 1 -6 -1 6 2 3 例 7 證 明設(shè) G 有 r 個(gè)面，當(dāng)v = 3, e = 2時(shí)， 3v-6 顯然成立。若 e 3, 則每一個(gè)面至少由 3 條邊圍成，所以re 32 er 32 eevrev 322 32 ev ev 36 63 ve 設(shè) G 是 一 個(gè) 有 v 個(gè) 結(jié) 點(diǎn) , e 條 邊 的 連 通 簡(jiǎn) 單 平 面圖 ， 若 v 3， 則 有 v 。證明 2 0 2 1 -6 -1 6 2 4 例 1 0 求 圖 的 最 小 生 成 樹ACB D E1 234 5 67 ABC DE1 24 6 2 0 2 1 -6 -1 6 2 5 例 1 1 無(wú) 向 樹 T有 7 片 樹 葉 , 3 個(gè) 3 度 頂 點(diǎn) ,其 余 的都 是 4 度 頂 點(diǎn) ， 則 T有 幾 個(gè) 4 度 頂 點(diǎn) ？ 解 :設(shè) T有 x個(gè) 4 度 頂 點(diǎn) 頂 點(diǎn) 度 數(shù) 之 和 ： 7 +3 *3 +4 x 由 樹 的 性 質(zhì) 可 得 總 邊 數(shù) ： 7 +3 +x-1 由 握 手 原 理 可 得 ： 7 +3 *3 +4 x=2 (7 +3 +x-1 ) x=1