東北大學(xué)考試試卷(A卷)2003-2004學(xué)年第2學(xué)期離散數(shù)學(xué)試卷答案

總分一二三四五六七總分一二三四五六七八2003—2004學(xué)年第2學(xué)期課程名稱：離散數(shù)學(xué)┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄一．將下面命題符號(hào)化(8分) 三．(8分)寫(xiě)出命題公式P((RQ)∧(RQ))的主析取范式。如果天氣好，我將去游樂(lè)場(chǎng)，否則我將呆在家中。 解：P((RQ)∧(RQ))(PQ)(PR) P((RQ)∧(RQ))(PRQ)∧(PRQ)只有計(jì)算機(jī)專業(yè)的學(xué)生和非大一學(xué)生才可以訪問(wèn)校園網(wǎng)。 即命題公式的主合取范式中的大項(xiàng)為M6和M2R(PQ) 所以其主析取范式中的小項(xiàng)有m0,m3,m4,m5,m6,m7即主析取范式為：3．并非所有學(xué)習(xí)好的大學(xué)生都想成為科學(xué)家。 (P∧R∧Q)(P∧R∧Q)(P∧R∧Q)(P∧R∧Q)(P∧R∧Q)(P∧R∧Q)x((A(x)B(x))C(x))4．盡管有人聰明，但未必一切人都聰明。

四．(10分)R1R2R1∪R2、R1∩R2、R1-R2、、r((A×A)-R1)中哪些是A上的等價(jià)關(guān)系？如果不是說(shuō)明理由，或舉反例。如果是請(qǐng)給予證明。、1 2 1 x(A(x)B(x))x((A(x)B(x)) 答：(1)R1∪R2不是等價(jià)關(guān)系。設(shè)A＝{1,2,3}1為R12為R2的關(guān)系3R∪R的關(guān)系圖，顯然R∪R不是A（21 2 1 二．(10分)填空(每空1分)1.（3）ABEX={P,Q,R,S,T,U,V,W,Y,Z},素都表示命題，如下所示：

1(2)R∩R21

是A上的等價(jià)關(guān)系。、 P:A－B=AQ:AB=BR:ABS:ABT:BAU:BAV:AB=ΦW:AB=BY:A、 P:A－B=AQ:AB=BR:ABS:ABT:BAU:BAV:AB=ΦW:AB=BY:ABZ:BAR R 又令R是X上的命題等價(jià)關(guān)系,則商集X/R=({{P,S,V,Z},{R,U,W},{Q,T,Y}}) ∩，所以R R 2 1 2

是自反的；(b)設(shè)<x,y>∈R∩R，則有<x,y>∈R

和<x,y>∈R，由于R和R

是對(duì)稱的，1 2 1 1 1 2 2 1 所以有<y,x>∈R1和<y,x>∈R2即<y,x>∈R∩R，可得R∩R2是對(duì)稱的；(c)設(shè)<x,y>∈R∩R，且<y,z>1 2 1 1 1 2 2 1 2.(每空1分)令R和S都是人類(lèi)上的關(guān)系，且 ∩R，則

和R是傳遞的可得<x,z>∈R，<x,z>∈R={<x,y>|xyS={<x,y>|xy的母親}則

2 1 1

2 1 2 11 2 1 2 1 R2<x,z>∈R∩R，所以R∩R∩R是A1 2 1 2 1 SR表示(祖母和孫子 )關(guān)系；RSC表示(夫妻 )關(guān)系。 (3)R1-R2不是等價(jià)關(guān)系設(shè)A＝{1,2,3}反例如下圖所示，圖4為R1的關(guān)系圖，圖5為R2的關(guān)系圖，圖6為R1-R2的關(guān)系圖，顯然R1-R2不是A上的等價(jià)關(guān)系。3.(1<G,*>是群,其中G={a,b,c}ab2=(c),b*c=(a4.(1)A,BP(A)A|A|=3,|P(B)|=64,|P(A∪B)|=256,|B|=(6|A-B|=(2|AB|=(7)。

(4)r((A×A)-R

1)A＝{1,2,3}7為

8為R2的學(xué)班院級(jí)…………○……學(xué)姓號(hào)名………密…學(xué)班院級(jí)…………○……學(xué)姓號(hào)名………密……………○……………封……………○…………線………………Page1of3PagePagePAGE3of3得分分得分分)(按照教材格式寫(xiě)出推理過(guò)程)x(x)(B(x)C(x))), x(x)(C(x)D(x))),x(x)D(x)) x(x)B(x))證明：(1) x(A(x)∧D(x))P得分(2)A(a)∧D(a))ES(1)(3)A(a)T(2)I(4)D(a))T(2)I（2分）(5)x(A(x)→(B(x)→C(x)))P(6)A(a)→(B(a)→C(a))US(5)(7)B(a)→C(a))T(3)(6)I（2分）(8)x(A(x)→(C(x)∨D(x)))P(9)A(a)→(C(a)∨D(a)))US(8)（2分）(10)C(a)∨D(a)T(3)(9)I（2分）(11)C(a)T(4)(10)I(12)B(a)T(7)(11)I（2分）(13)A(a)∧B(a))(14)x(A(x)∧B(x))T(3)(12)EG(13)（2分）得分六．(15分)給定集合Ｇ＝{x|x是有理數(shù)且x≠1}，在Ｇ上定義二元運(yùn)算*如下對(duì)任何a，b∈Ｇ a*b=a+b-ab求證<Ｇ，*>是個(gè)交換群。證明:1)封閉性.任取a,b∈I,a*b=a+b-2∈I,a*b∈I,所以*I上封閉.(32).a,b,c∈I,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=(a+b-2)+c-2=(a*b)*c所以*可結(jié)合.(3分)3).證*可交換.任取a,b∈Ia*b=a+b-2=b+a-2=b*a所以*(34).a∈I,a*2=a+2-2=a2*a=2+a-2=a(35).證可逆性.任取a∈I,4-a∈I,使得a*(4-a)=a+4-a-2=2(4-a)*a=4-a+a-2=a∴a-1=4-a(3所以<I,*>是交換群得分七．.(15得分七．.(15分)設(shè)<G,>是群,a∈G,定義函數(shù)fa:GG為:任何x∈G 有1.求證fa:GG是入射的.2.F={fa:GG|a∈G},FGa定義的函數(shù)構(gòu)成的集合，令“”是函數(shù)的左復(fù)合運(yùn)算,求證<F,>是個(gè)群.x1≠x2，fa(x1)＝fa(x2)a*x1=a*x2由群的消去性可知x1=x2，與x1≠x2相矛盾，fa(x1)≠fa(x2)，即fa:GG（4分）2．證明：(1)fa1，fa2∈F(a1，a2∈G)由已知可知fa1=a1*x，fa2=a2*xfa1fa2(x)=a1*(a2*x)=a1*a2*x由于a1，a2∈G，，由群G的封閉性可知a1*a2∈Gfa1fa2(x)∈F（2分）fa1，fa2，fa3∈F，由運(yùn)算“*”的可結(jié)合性可得fa1(fa2fa3a1*(a2*(a3*x)=(a1*a2)*(a3*x)=fa1fa2)fa3所以運(yùn)算“”是可結(jié)合的。（2分）fe(x)=e*x(eG中的幺元)fefa(x)=e*(a*x)=fafe(x)=a*(e*x)=a*x＝fa(x所以fe是代數(shù)系統(tǒng)<F,>的幺元。（3分） fa-1a的逆元。fafa-1(x)=a*(a-1*x)=(a*a-1)*x=x=a-1*(a*x)=fa-1fa(x)=fa-1為faF（3分）綜上所述，運(yùn)算“所以代數(shù)系統(tǒng)<F,>（1分）得分八．簡(jiǎn)答題(12分)e條邊，tet（3分m:(m-1)i=t-1得分支結(jié)點(diǎn)數(shù)i=t-1又根據(jù)樹(shù)中e=v-1v是結(jié)點(diǎn)數(shù).所以e=(i+t)-1=t-1+t-1=2t-22．請(qǐng)畫(huà)出有5個(gè)結(jié)點(diǎn)的無(wú)向完全圖K5的所有不同構(gòu)的生成樹(shù)。（3分）K5T4，T3可生成樹(shù)，如下： （11114）(11