《離散數(shù)學(xué)》模擬試卷A及答案

PAGEPAGE2《離散數(shù)學(xué)》模擬試卷A及答案一、選擇dbeac設(shè)集合A={a，b，c，d，e}，偏序關(guān)系R的哈斯圖下圖所示，假設(shè)A的子集B={c，ddbeacA．下界B．最大下界C．最小上界D．以上答案都不對(duì)已知│A│=15，│B│=10，│A∪B│=20，則│A∩B│=（）A．10B．5C．20D．13下圖中哪個(gè)是歐拉圖（）ABCD下列式子中正確的是（）A．?=0B．???C．??{a，b}D．??{?}在下圖所示的哈斯圖中的偏序集不是格的是（）下圖中是一個(gè)從X到Y(jié)的映射f，其中X={a，b，c，d，e}，Y={1，2，3，4}，則映射f是（）acacbd1243e已知集合A={?，1，2}，則A的冪集合r(A)=________設(shè)K6是有6個(gè)點(diǎn)的完全圖，則K6共有____________條邊。設(shè)A，B是兩集合，其中A={a，b，c}，B={a，b}，則A-B=_______________，A?B=_______________________________________設(shè)A={a，b}，B＝｛1，2，3｝，則AB=二、計(jì)算或證明題利用推理規(guī)則證明：┒（P∧┒Q），┒Q∨R，┒R┒P（10分）利用推理規(guī)則證明：（x）（┒A（x）→B（x）），（x）┒B（x）（x）A（x）（10分）如果關(guān)系R和S為X上的等價(jià)關(guān)系，證明：RS也是X上的等價(jià)關(guān)系。（10分）設(shè)集合A={a，b，c，d}，A上的關(guān)系R={<a，a>，<a，b>，<b，a>，<c，d>，<b，c>}（10分）求：1）畫出R的關(guān)系圖，并用作圖法分別求出R的自反閉包和對(duì)稱閉包。2）用Warshall算法求出R的傳遞閉包設(shè)<R，*>是一個(gè)代數(shù)系統(tǒng)，*是R上的一個(gè)二元運(yùn)算，使得對(duì)于R中的任意元素x，y都有x*y=x+y+xy，證明0是幺元而且<R，*>是獨(dú)異點(diǎn)（其中，R為實(shí)數(shù)集，+為普通加法，為普通乘法）（10分）設(shè)f1，f2都是一從代數(shù)系統(tǒng)<A，*>到代數(shù)系統(tǒng)<B，>的同態(tài)。設(shè)g是從A到B的一個(gè)映射，使得對(duì)任意aA，都有g(shù)(a)=f1(a)f2(a)；證明：如果<B，>為一個(gè)可交換半群，那么g是一個(gè)由<A，*>到<B，>的同態(tài)。（10分）假設(shè)給定了正整數(shù)的序偶集合A，在A上定義二元關(guān)系R如下：<<x，y>，<u，v>>R，當(dāng)且僅當(dāng)xv=yu，證明：R為等價(jià)關(guān)系。（10分）答題紙姓名：學(xué)號(hào)：成績(jī)選擇填空題選擇題答案：題號(hào)123456答案CBCDBB填空題答案：7）?，{1}，{2}，{?}，{1，2}，{?，1}，{?，2}，{?，1，2}8）159）{c}，{a,b}10）{<a，1>，<a，2>，<a，3>，<b，1>，<b，2>，<b，3>}計(jì)算證明題證明：┒（P∧┒Q）P┒P∨QT（1）EP→QT（2）E┒Q∨RPQ→RT（4）EP→RT（3）（5）I┒R→┒PT（6）E┒RP┒PT（7）（8）I證明：（x）（┒A（x）→B（x））P（x）┒B（x）P┒B（a）US（2）┒A（a）→B（a）US（1）┒B（a）→A（a）T（4）EA（a）T（3）（5）I（x）A（x）EG（6）如果關(guān)系R和S為X上的等價(jià)關(guān)系，證明：RS也是X上的等價(jià)關(guān)系。證明：1）設(shè)任意xX，∵R和S為等價(jià)關(guān)系，滿足自反性質(zhì)∴有<x，x>R，<x，x>S∴<x，x>RS，∴RS在X上自反。2）設(shè)任意<x，y>RS，則，<x，y>R且<x，y>S∵R和S為等價(jià)關(guān)系，滿足對(duì)稱性質(zhì)，∴必有<y，x>R且<y，x>S∴<y，x>RS∴RS滿足對(duì)稱性質(zhì)3）設(shè)任意<x，y>，<y，z>RS則<x，y>，<y，z>R，∵R傳遞，∴<x，z>R同理，由<x，y>，<y，z>S，∵S傳遞，∴<x，z>S∴<x，z>RS∴RS傳遞綜上，RS滿足自反、對(duì)稱和可傳遞的性質(zhì)，為X上的等價(jià)關(guān)系。設(shè)集合A={a，b，c，d}，A上的關(guān)系R={<a，a>，<a，b>，<b，a>，<c，d>，<d，c>}求：1）畫出R的關(guān)系圖，并用作圖法分別求出R的自反閉包和對(duì)稱閉包。2）用Warshall算法求出R的傳遞閉包略。參考書上例題。5、設(shè)<R，*>是一個(gè)代數(shù)系統(tǒng)，*是R上的一個(gè)二元運(yùn)算，使得對(duì)于R中的任意元素x，y都有x*y=x+y+xy，證明0是幺元而且<R，*>是獨(dú)異點(diǎn)（其中，R為實(shí)數(shù)集，+為普通加法，為普通乘法）（10分）證明：對(duì)于任意x，yR，x*y=x+y+xy，因?yàn)?和在實(shí)數(shù)集合上封閉，所以x*yR；對(duì)于任意x，y，zR，x*（y*z）=x+（y+z+yz）+x（y+z+yz）=x+y+z+xy+xz+yz+xyz（x*y）*z=（x+y+xy）+z+（x+y+xy）z=x+y+z+xy+xz+yz+xyz所以x*（y*z）=（x*y）*z，所以*在R上可結(jié)合。對(duì)于任意xR，因?yàn)閤*0=x+0+x0=x，0*x=0+x+0x=x，所以x*0=0*x=x，所以0為幺元。綜上，<R，*>是獨(dú)異點(diǎn)。6、設(shè)f1，f2都是一從代數(shù)系統(tǒng)<A，*>到代數(shù)系統(tǒng)<B，>的同態(tài)。設(shè)g是從A到B的一個(gè)映射，使得對(duì)任意aA，都有g(shù)(a)=f1(a)f2(a)；證明：如果<B，>為一個(gè)可交換半群，那么g是一個(gè)由<A，*>到<B，>的同態(tài)。證明：設(shè)任意x，y∈A，因?yàn)閒1，f2為<A，*>到<B，>的同態(tài)，所以f1（x*y）=f1（x）f1（y），f2（x*y）=f2（x）f2（y）g（x*y）=f1（x*y）f2(x*y)=（f1（x）f1（y））（f2（x）f2（y））因?yàn)檫\(yùn)算可結(jié)合，可交換，所以（f1（x）f1（y））（f2（x）f2（y））=f1（x）f2（x）f1（y）f2（y）=（f1（x）f2（x））（f1（y）f2（y））=g（x）g（y）所以g（x*y）=g（x）g（y）所以g為<A，*>到<B，>的同態(tài)。7、證明：設(shè)A上定義的二元關(guān)系R為：＜＜x,y＞,＜u,v＞＞∈Rx/y=u/v對(duì)任意＜x,y＞∈A,因?yàn)閤/y=x/y,所以＜＜x,y＞,＜x,y＞＞∈R即R是自反的。設(shè)＜x,y＞∈A，＜u,v＞∈A,若＜＜x,y＞,＜u,v＞＞∈R=>x/y=u/v=>u/v=x/y＜＜u,v＞,＜x,y＞＞∈R即R是對(duì)稱的。設(shè)任意＜x,y＞∈A，＜u,v＞∈A,＜w,s＞∈A,對(duì)＜＜x,y＞,＜u,v＞＞∈R∧＜＜u,v＞,＜w,s＞＞∈R=>(x/y=u/v)∧(u/v=w/s)=>x/y=w/s=>＜＜x,y＞,＜w,s＞＞∈R故R是傳遞的，于是R是A上的等價(jià)關(guān)系。《離散數(shù)學(xué)》模擬試卷B喻琇瑛一、選擇下面不是命題的句子是（）。雖然李明很累，他還是去上課。請(qǐng)不要抽煙！北京是中國(guó)的首都。李明不是老師。已知│A│=15，│B│=10，│A∪B│=20，則│A∩B│=（）A．10B．5C．20D．13設(shè)R1，R2是集合A={1，2，3，4}上的兩個(gè)關(guān)系，其中：R1={<1，1>，<2，2>，<2，3>，<4，4>}，R2={<1，1>，<2，2>，<2，3>，<3，2>，<4，4>}，則R2是R1的（）閉包。A．自反B．對(duì)稱C．傳遞D．以上都不對(duì)設(shè)集合S={1，2，3}，S上的關(guān)系R={<1，1>，<1，2>，<2，1>，<3，3>}，如果1）自反性2）反自反性3）對(duì)稱性4）反對(duì)稱性5）傳遞性則R具有性質(zhì)：（）A．1）3）5）B．1）2）C．2）4）D．3）下列式子中正確的是（）A．?=0B．???C．??{a，b}D．??{?}下面的有向圖G為（）A．弱連通B．單向連通C．強(qiáng)連通D．以上都不是下圖中是一個(gè)從X到Y(jié)的映射f，其中X={a，b，c，d}，Y={1，2，3}，則映射f是（）A雙射B滿射C入射D以上都不是aacbd123一個(gè)代數(shù)系統(tǒng)<S，*>，其中S是非空集合，*是S上的一個(gè)二元運(yùn)算，如果運(yùn)算*是封閉的，可結(jié)合的，則代數(shù)系統(tǒng)<S，*>為（）A半群B群C獨(dú)異點(diǎn)D以上都不是一個(gè)代數(shù)系統(tǒng)<S，*>，其中S是非空集合，*是S上的一個(gè)二元運(yùn)算，如果運(yùn)算*是封閉的，可結(jié)合的，則代數(shù)系統(tǒng)<S，*>為（）A半群B群C獨(dú)異點(diǎn)D以上都不是已知集合A={1，2，3}，則A的冪集合r(A)=____________________________________。設(shè)集合A={a，b，c，d}，A上的關(guān)系R={<a，a><a，c>，<b，d>}，S={<a，b>，<d，c>，<a，d>}則關(guān)系R2=________________________________。逆關(guān)系RC=________________________________________________________。復(fù)合關(guān)系R○S=____________________________________________________。設(shè)集合A={1，2，3，4，5}，A上偏序關(guān)系R的哈斯圖如下圖所示，則A的極大元是________，極小元是________________。445213二、計(jì)算或證明題利用推理規(guī)則證明：P∨Q，P→R，Q→SR∨S（10分）利用推理規(guī)則證明：?x(A(x)→B(x)),?x(C(x)→┓B(x))??x(C(x)→┓A(x))下列均為集合A={1，2，3，4}上的偏序關(guān)系，分別畫出它們的哈斯圖，找出集合A相應(yīng)的最大、最小元，極大、極小元。（10分）1212341243A={0，1，2，3，4}，式子{<x，y>2<x∧y<3}，寫出該式所給出的A上的二元關(guān)系，并畫出關(guān)系圖。（10分）證明：設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，且在A中有關(guān)于運(yùn)算*的左零元θl和右零元θr，那么θl=θr=θ，且A中的零元是唯一的。（10分）設(shè)A={a，b，c，d，e}，A上有一個(gè)劃分H={{a，b}，{c，d}，{e}}，求由劃分H所確定的A上的一個(gè)等價(jià)關(guān)系。（10分）證明：集合X上的二元關(guān)系S是傳遞的，當(dāng)且僅當(dāng)SSS（10分）求出下圖的鄰接矩陣，并求出可達(dá)性矩陣。V4V4V3V2V1答題紙姓名：學(xué)號(hào)：成績(jī)選擇填空題選擇題答案：題號(hào)123456789答案BBBDDBBAA填空題答案：10）?，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}11）R2={<a，a><a，c>}，RC={<a，a><c，a>，<d，b>}，R○S={<a，b><a，d>，<b，c>}12）極大元是_4，5_______，極小元是_1，2，3___________計(jì)算證明題1、利用推理規(guī)則證明：P∨Q，P→R，Q→SR∨S1）P∨QP2）┒P→QT（1）E3）P→RP4）┒R→┒PT（3）E5）┒R→QT（1）（4）I6）Q→SP7）┒R→ST（5）（6）I8）R∨ST（7）E2、?x(A(x)→B(x)),?x(C(x)→┓B(x))??x(C(x)→┓A(x))證明：(1)?x(A(x)→B(x))P(2)┓B(a)→┓A(a)US（1）(3)?x(C(x)→┓B(x))P(4)C(a)→┓B(a)US（3）(5)┓B(a)→┓A(a)T（2）E(6)C(a)→┓A(a)T(5),(4),I(7)?x(C(x)→┓A(x))UG(6)3、３４３４１２圖1：極大元：2，3極小元：4最大元：無(wú)最小元：4圖2：極大元：4極小元：3最大元：4最小元：3A={0，1，2，3，4}，式子{<x，y>2<x∧y<3}，寫出該式所給出的A上的二元關(guān)系，并畫出關(guān)系圖。（10分）R={<3，0>，<3，1>，<3，2>，<3，0>，<3，1>，<3，2>，<4，0>，<4，1>，<4，2>}關(guān)系圖略5、證明：設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，且在A中有關(guān)于運(yùn)算*的左零元θl和右零元θr，那么θl=θr=θ，且A中的零元是唯一的。證明：因?yàn)棣萳=θl*θr=θr，所以θl=θr=θ。又設(shè)另有一零元θ’，則θ’=θ’*θ=θ所以θ’=θ。所以零元唯一。6、設(shè)A={a，b，c，d，e}，A上有一個(gè)劃分H={{a，b}，{c，d}，{e}}，求由劃分H所確定的A上的一個(gè)等價(jià)關(guān)系。R1={a，b}{a，b}={<a，a>，<a，b>，<b，a>，<b，b>}R2={c，d}{c，d}={<c，c>，<c，d>，<d，c>，<d，d>}R3={e}{e}={<e，e>}所以R=R1∪R2∪R3={<a，a>，<a，b>，<b，a>，<b，b>，<c，c>，<c，d>，<d，c>，<d，d>，<e，e>}證明：集合X上的二元關(guān)系S是傳遞的，當(dāng)且僅當(dāng)SSS（10分）證明：1）設(shè)S是傳遞的，設(shè)任意＜x,z＞∈S°S,由復(fù)合定義，則存在某個(gè)y∈X，使得＜x,y＞∈S，且＜y,z＞∈S。因?yàn)镾是傳遞的，所以＜x,z＞∈S，所以S°SS。2）反之，設(shè)S°SS，假定＜x,y＞∈S且＜y,z＞∈S，則＜x,z＞∈S°S。因?yàn)镾°SS，故＜x,z＞∈S，得到S是傳遞的。綜上，S是傳遞的，當(dāng)且僅當(dāng)SSS。求出下圖的鄰接矩陣，并求出可達(dá)性矩陣。V4V4V3V2V101100110000101001010AR=