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

例3給出下列公式的真值表成真指派：100，101，110，1112022-10-19總復(fù)習(xí)1

of

65例4試求下面公式的主析?。ㄖ骱先。┓妒剑懗龀烧嬷概珊统杉僦概?。成真指派：00，10，11成假指派：012022-10-19總復(fù)習(xí)2

of

65例5試證證明2022-10-19總復(fù)習(xí)3

of

65例1符號(hào)化下列命題a)不是所有的男人都比女人高。M(x):x是男人，W(x):x是女人，H(x,y):x比y高。2022-10-19總復(fù)習(xí)4

of

65例2證明證明2022-10-19總復(fù)習(xí)5

of

65例1求集合的冪集2022-10-19總復(fù)習(xí)6

of

65例2n個(gè)元素的集合上，可以定義多少個(gè)關(guān)系？

設(shè)集合X,Y,|X|=m,|Y|=n，可以定義多少個(gè)從X到Y(jié)的函數(shù)？nm

(|Y||X|

)2022-10-19總復(fù)習(xí)7

of

65例3對(duì)任意兩個(gè)集合A,B,試證證明對(duì)于任意的x因?yàn)閤是任意的,所以有的真值為T,因此2022-10-19總復(fù)習(xí)8

of

65例4判斷關(guān)系的性質(zhì)R1

是自反的、反對(duì)稱、傳遞的。2022-10-19總復(fù)習(xí)9

of

65例5求關(guān)系的閉包解：2022-10-19總復(fù)習(xí)10

of

65例5（續(xù)）2022-10-19總復(fù)習(xí)11

of

65例7設(shè)A={1,2,3},求出A上所有的等價(jià)關(guān)系解：先求A的各種劃分：2135123221321341

3設(shè)對(duì)應(yīng)于

i

的等價(jià)關(guān)系為Ri

,則：213R1={<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>}

∪

IA2022-10-19總復(fù)習(xí)12

of

65例8畫出哈斯圖2022-10-19總復(fù)習(xí)13

of

65例9求極大（?。┰?，最大（?。┰?、上（下）界，上（下）確界極大元：j,k極小元:a,b,e最大元：無最小元：無B={a,b,c,d,e,f,g}上界：h,i,j,k

下界：無無上（下）確界2022-10-19總復(fù)習(xí)14

of

652022-10-19總復(fù)習(xí)15

of

65例10判斷函數(shù)的類型入

射映射函數(shù)雙(入、滿)射滿射例11求復(fù)合函數(shù)2022-10-19總復(fù)習(xí)16

of

65例12求復(fù)合函數(shù)2022-10-19總復(fù)習(xí)17

of

652022-10-19總復(fù)習(xí)18

of

65例:求幺元、零元、逆元N,I,Q,R上的普通加法+和乘法*+：幺元0，a-1

=-a；*：幺元1，零元0，a-1

=1/a；命題公式集合上的

和：幺元F，零元T：幺元T，零元F冪集P(S)上的∪和∩∪：幺元

，零元S∩：幺元S，零元例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

=

82022-10-19總復(fù)習(xí)19

of

65例3請(qǐng)畫出4個(gè)頂點(diǎn)3條邊的所有可能不同構(gòu)的無向簡單圖？2022-10-19總復(fù)習(xí)20

of

65例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必是連通的。證明試證2022-10-19總復(fù)習(xí)21

of

65例6判斷下列圖哪些是E

圖、H圖？2022-10-19總復(fù)習(xí)22

of

65例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－６。證明2022-10-19總復(fù)習(xí)23

of

65例10求圖的最小生成樹2022-10-19總復(fù)習(xí)24

of

652022-10-19總復(fù)習(xí)25

of

65例11

無向樹T