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

2023/7/31離散數(shù)學(xué)練習(xí)題及答案1of65例3給出下列公式的真值表成真指派：100，101，110，1112023/7/31離散數(shù)學(xué)練習(xí)題及答案2of65例4

試求下面公式的主析?。ㄖ骱先。┓妒?，并寫出成真指派和成假指派。成真指派：00，10，11成假指派：012023/7/31離散數(shù)學(xué)練習(xí)題及答案3of65例5試證證明2023/7/31離散數(shù)學(xué)練習(xí)題及答案4of65例1符號(hào)化下列命題a)不是所有的男人都比女人高。

M(x):x是男人，W(x):x是女人，H(x,y):x比y高。2023/7/31離散數(shù)學(xué)練習(xí)題及答案5of65例2證明證明2023/7/31離散數(shù)學(xué)練習(xí)題及答案6of65例1求集合的冪集2023/7/31離散數(shù)學(xué)練習(xí)題及答案7of65例2n個(gè)元素的集合上，可以定義多少個(gè)關(guān)系？設(shè)集合X,Y,|X|=m,|Y|=n，可以定義多少個(gè)從X到Y(jié)的函數(shù)？nm

(|Y||X|)2023/7/31離散數(shù)學(xué)練習(xí)題及答案8of65例3對(duì)任意兩個(gè)集合A,B,試證證明對(duì)于任意的x因?yàn)閤是任意的,所以有的真值為T,因此2023/7/31離散數(shù)學(xué)練習(xí)題及答案9of65例4判斷關(guān)系的性質(zhì)R1是自反的、反對(duì)稱、傳遞的。2023/7/31離散數(shù)學(xué)練習(xí)題及答案10of65例5求關(guān)系的閉包

解：2023/7/31離散數(shù)學(xué)練習(xí)題及答案11of65例5（續(xù)）2023/7/31離散數(shù)學(xué)練習(xí)題及答案12of65例7設(shè)A={1,2,3},求出A上所有的等價(jià)關(guān)系解：先求A的各種劃分：12351232123312341231設(shè)對(duì)應(yīng)于i

的等價(jià)關(guān)系為Ri,則：R1={<1,1>,<2,2>,<3,3>}=

IAR2={<1,2>,<2,1>}∪

IAR3={<1,3>,<3,1>}∪

IAR4={<2,3>,<3,2>}∪

IAR5={<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>}∪

IA2023/7/31離散數(shù)學(xué)練習(xí)題及答案13of65例8畫出哈斯圖2023/7/31離散數(shù)學(xué)練習(xí)題及答案14of65例9求極大（?。┰畲螅ㄐ。┰⑸希ㄏ拢┙?，上（下）確界極大元：j,k極小元:a,b,e最大元：無最小元：無B={a,b,c,d,e,f,g}上界：h,i,j,k下界：無無上（下）確界2023/7/31離散數(shù)學(xué)練習(xí)題及答案15of65例10判斷函數(shù)的類型入射

映射函數(shù)雙(入、滿)射滿射2023/7/31離散數(shù)學(xué)練習(xí)題及答案16of65例11求復(fù)合函數(shù)2023/7/31離散數(shù)學(xué)練習(xí)題及答案17of65例12求復(fù)合函數(shù)2023/7/31離散數(shù)學(xué)練習(xí)題及答案18of65例:求幺元、零元、逆元N,I,Q,R上的普通加法+和乘法*+：幺元0，a-1=-a；*：幺元1，零元0，a-1=1/a；命題公式集合上的和：幺元F，零元T

：幺元T，零元F冪集P(S)上的∪和∩∪：幺元，零元S∩：幺元S，零元2023/7/31離散數(shù)學(xué)練習(xí)題及答案19of65例1G是一個(gè)有15條邊的簡單圖，有13條邊，請(qǐng)問G

中有多少個(gè)結(jié)點(diǎn)?解：共有15+13=28條邊，

是一個(gè)完全圖，它的結(jié)點(diǎn)數(shù)與G相同，設(shè)為n，根據(jù)定理4，n(n-1)/2=28n=82023/7/31離散數(shù)學(xué)練習(xí)題及答案20of65例3請(qǐng)畫出4個(gè)頂點(diǎn)3條邊的所有可能不同構(gòu)的無向簡單圖？2023/7/31離散數(shù)學(xué)練習(xí)題及答案21of65例4若無向圖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

必是連通的。證明試證2023/7/31離散數(shù)學(xué)練習(xí)題及答案22of65例6判斷下列圖哪些是E圖、H圖？2023/7/31離散數(shù)學(xué)練習(xí)題及答案23of65例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－６。證明2023/7/31離散數(shù)學(xué)練習(xí)題及答案24of65例10求圖的最小生成樹2023/7/31離散數(shù)學(xué)練習(xí)題及答案25of65例11無向樹T有7片樹葉,3個(gè)3度頂點(diǎn),其余的都是4度頂點(diǎn)，則T有幾個(gè)4度頂點(diǎn)？解: