《離散數(shù)學(xué)》試題及答案

1、《離散數(shù)學(xué)》試題及答案第1頁(yè)共13頁(yè)一、填空題一、填空題1設(shè)集合AB，其中A＝123B=12則AB＝3?(A)?(B)＝31323123.2.設(shè)有限集合A|A|=n則|?(AA)|=.22n3.設(shè)集合A=abB=12則從A到B的所有映射是?1=(a1)(b1)?2=(a2)(b2)?3=(a1)(b2)?4=(a2)(b1)其中雙射的是?3?4.4.已知命題公式G＝?(P?Q)∧R，則G的主析取范式是(P∧?Q∧R)5.設(shè)G是完全二叉樹

2、，G有7個(gè)點(diǎn)，其中4個(gè)葉點(diǎn)，則G的總度數(shù)為12，分枝點(diǎn)數(shù)為3.6設(shè)A、B為兩個(gè)集合A=124B=34則從A?B＝4A?B＝1234A－B＝12.7.設(shè)R是集合A上的等價(jià)關(guān)系，則R所具有的關(guān)系的三個(gè)特性是自反性對(duì)稱性傳遞性.8.設(shè)命題公式G＝?(P?(Q?R))，則使公式G為真的解釋有(100)(101)(110)9.設(shè)集合A＝1234A上的關(guān)系R1=(14)(23)(32)R2=(21)(32)(43)則R1?R2=(13)(22)(3

3、1)R2?R1=(24)(33)(42)_R12=(22)(33).10.設(shè)有限集AB，|A|=m|B|=n則||?(A?B)|=.nm?211設(shè)ABR是三個(gè)集合，其中R是實(shí)數(shù)集，A=x|1≤x≤1x?RB=x|0≤x2x?R則AB=1=x0BA=x|1x2x?RA∩B=x|0≤x≤1x?R.13.設(shè)集合A＝23456，R是A上的整除關(guān)系，則R以集合形式(列舉法)記為(22)(24)(26)(33)(36)(44)(55)(66).14

4、.設(shè)一階邏輯公式G=?xP(x)??xQ(x)，則G的前束范式是?x(?P(x)∨Q(x)).15.設(shè)G是具有8個(gè)頂點(diǎn)的樹，則G中增加21條邊才能把G變成完全圖。(完全圖的完全圖的邊數(shù)邊數(shù)，樹的邊數(shù)為，樹的邊數(shù)為n1)2)1(?nn16.設(shè)謂詞的定義域?yàn)閍b將表達(dá)式?xR(x)→?xS(x)中量詞消除，寫成與之對(duì)應(yīng)的命題公式是_(R(a)∧R(b))→(S(a)∨S(b))_.《離散數(shù)學(xué)》試題及答案第3頁(yè)共13頁(yè)(A)45(B)56(C

5、)410(D)58.三、計(jì)算證明題三、計(jì)算證明題1.設(shè)集合A＝123468912，R為整除關(guān)系。(1)畫出半序集(AR)的哈斯圖；(2)寫出A的子集B=36912的上界，下界，最小上界，最大下界；(3)寫出A的最大元，最小元，極大元，極小元。解：（解：（1）124836129124836129（2）B無(wú)上界，也無(wú)最小上界。下界13最大下界是3（3）A無(wú)最大元，最小元是1，極大元8129極小元是12.設(shè)集合A＝1234，A上的關(guān)系R＝(x

6、y)|xy?A且x?y求(1)畫出R的關(guān)系圖；(2)寫出R的關(guān)系矩陣.解：（解：（1）（2）12341000110011101111RM?????????????3.設(shè)R是實(shí)數(shù)集合，???是R上的三個(gè)映射，?(x)=x3?(x)=2x?(x)＝x4試求復(fù)合映射???，?????????，?????.解：解：(1)???＝?(?(x))＝?(x)3＝2x3＝2x3.(2)???＝?(?(x))＝?(x)3＝(x3)3＝x6(3)???＝?