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

1、例3 給出下列公式的真值表,成真指派：100，101，110，111,1,例4,試求下面公式的主析取（主合?。┓妒?，并寫出成真指派和成假指派。,成真指派：00，10，11 成假指派：01,2,例5 試證,證明,3,例1 符號化下列命題,a)不是所有的男人都比女人高。 M(x):x是男人，W(x):x是女人，H(x,y):x比y高。,4,例2 證明,證明,5,例1 求集合的冪集,6,例2,n 個(gè)元素的集合上，可以定義多少個(gè)關(guān)系？ 設(shè)集合X,Y, |X|=m, |Y|=n，可以定義多少個(gè)從X到Y(jié)的函數(shù)？,nm (|Y|X| ),7,例3 對任意兩個(gè)集合A, B,試證,8,例4 判斷關(guān)系的性質(zhì),9,

2、例5 求關(guān)系的閉包,解：,10,例5（續(xù)）,11,例7 設(shè) A=1,2,3, 求出A上所有的等價(jià)關(guān)系,解：,先求A的各種劃分：,設(shè)對應(yīng)于 i 的等價(jià)關(guān)系為Ri ,則：,R1=, = IA R2=, IA R3=, IA R4=, IA R5=, , IA,12,例8 畫出哈斯圖,13,例9 求極大（?。┰?，最大（?。┰?、上（下）界，上（下）確界,極大元：j,k 極小元:a,b,e 最大元：無 最小元：無,B=a,b,c,d,e,f,g 上界： h,i,j,k 下界：無 無上（下）確界,14,例10 判斷函數(shù)的類型,入 射,映射函數(shù),雙(入、滿)射,滿射,15,例11 求復(fù)合函數(shù),16,例12

3、求復(fù)合函數(shù),17,例: 求幺元、零元、逆元,N, I, Q, R上的普通加法 + 和乘法 * +：幺元 0，a-1 = -a； *：幺元 1，零元 0， a-1 = 1/a； 命題公式集合上的 和 ：幺元F，零元T ：幺元T，零元F 冪集P(S)上的和 ：幺元 ，零元S ：幺元S，零元,18,例1,G 是一個(gè)有 15 條邊的簡單圖， 有 13 條邊，請問 G 中有多少個(gè)結(jié)點(diǎn)?,19,例3,請畫出 4 個(gè)頂點(diǎn) 3 條邊的所有可能不同構(gòu)的無向簡單圖？,20,例4,若無向圖 G 中恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)必是連通的。,設(shè) G 中兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為 u ,v。 若 u 與 v 不連通,則至少

4、有兩個(gè)連通分支 G1 和 G2，u G1,v G2。 于是 G1 和 G2 各含一個(gè)奇數(shù)度結(jié)點(diǎn)，這與握手原理的推論矛盾， 因此 u 與 v 必是連通的。,證明,試證,21,例6 判斷下列圖哪些是 E 圖、H圖？,22,例7 證明,設(shè) G 有 r 個(gè)面， 當(dāng)v = 3, e = 2時(shí)， 3v-6 顯然成立。 若 e 3, 則每一個(gè)面至少由 3 條邊圍成，所以,設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn), e 條邊的連通簡單平面圖，若 v 3，則有 v。,證明,23,例10 求圖的最小生成樹,24,例11,無向樹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+