離散數(shù)學(xué)試題1

《離散數(shù)學(xué)》模擬試卷1一、選擇1．設(shè)集合A={a，b，c，d，e}，偏序關(guān)系R的哈斯圖下圖所示，假設(shè)A的子集B={c，d，e}，則元素c為B的（）A．下界

B．最大下界

C．最小上界

D．以上答案都不對2．已知│A│=15，│B│=10，│A∪B│=20，則│A∩B│=

（）A．10

B．5

C．20

D．133．下圖中哪個是歐拉圖（）A

B

C

D4．下列式子中正確的是（）A．=0

B．

C．{a，b}

D．{}5．在下圖所示的哈斯圖中的偏序集不是格的是（）6．下圖中是一個從X到Y(jié)的映射f，其中X={a，b，c，d，e}，Y={1，2，3，4}，則映射f是（）

A雙射

B滿射

C入射

D以上都不是7．下面不是命題的句子是

（

）。A．雖然李明很累，他還是去上課。B．請不要抽煙！C．北京是中國的首都。D．李明不是老師。8．設(shè)R1，R2是集合A={1，2，3，4}上的兩個關(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．對稱

C．傳遞

D．以上都不對9．設(shè)集合S={1，2，3}，S上的關(guān)系R={<1，1>，<1，2>，<2，1>，<3，3>}，如果1）自反性2）反自反性3）對稱性4）反對稱性5）傳遞性則R具有性質(zhì)：（）A．1）3）5）

B．1）2）

C．2）4）

D．3）10．下列式子中正確的是（）A．=0

B．

C．{a，b}

D．{}11．下面的有向圖G為（）A．弱連通

B．單向連通

C．強連通

D．以上都不是12．下圖中是一個從X到Y(jié)的映射f，其中X={a，b，c，d}，Y={1，2，3}，則映射f是（）A雙射

B滿射

C入射

D以上都不是13．下面不是命題的句子是

（

）。A．雖然李明很累，他還是去上課。B．請不要抽煙！C．北京是中國的首都。D．李明不是老師。14．已知│A│=15，│B│=10，│A∪B│=20，則│A∩B│=

（）A．10

B．5

C．20

D．1315．設(shè)R1，R2是集合A={1，2，3，4}上的兩個關(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．對稱

C．傳遞

D．以上都不對16．設(shè)集合S={1，2，3}，S上的關(guān)系R={<1，1>，<1，2>，<2，1>，<3，3>}，如果1）自反性2）反自反性3）對稱性4）反對稱性5）傳遞性則R具有性質(zhì)：（）A．1）3）5）

B．1）2）

C．2）4）

D．3）17．下列式子中正確的是（）A．=0

B．

C．{a，b}

D．{}18．下面的有向圖G為（）A．弱連通

B．單向連通

C．強連通

D．以上都不是19．下圖中是一個從X到Y(jié)的映射f，其中X={a，b，c，d}，Y={1，2，3}，則映射f是（）A雙射

B滿射

C入射

D以上都不是20．一個代數(shù)系統(tǒng)<S，*>，其中S是非空集合，*是S上的一個二元運算，如果運算*是封閉的，可結(jié)合的，則代數(shù)系統(tǒng)<S，*>為（）A

半群

B

群

C

獨異點

D

以上都不是21．一個代數(shù)系統(tǒng)<S，*>，其中S是非空集合，*是S上的一個二元運算，如果運算*是封閉的，可結(jié)合的，則代數(shù)系統(tǒng)<S，*>為（）A

半群

B

群

C

獨異點

D

以上都不是22．一個代數(shù)系統(tǒng)<S，*>，其中S是非空集合，*是S上的一個二元運算，如果運算*是封閉的，可結(jié)合的，則代數(shù)系統(tǒng)<S，*>為（）A

半群

B

群

C

獨異點

D

以上都不是23．一個代數(shù)系統(tǒng)<S，*>，其中S是非空集合，*是S上的一個二元運算，如果運算*是封閉的，可結(jié)合的，則代數(shù)系統(tǒng)<S，*>為（）A

半群

B

群

C

獨異點

D

以上都不是24．已知集合A={1，2，3}，則A的冪集合(A)=____________________________________。25．設(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=____________________________________________________。26．設(shè)集合A={1，2，3，4，5}，A上偏序關(guān)系R的哈斯圖如下圖所示，則A的極大元是________，極小元是________________。27．已知集合A={，1，2}，則A的冪集合(A)=________28．設(shè)K6是有6個點的完全圖，則K6共有____________條邊。29．設(shè)A，B是兩集合，其中A={a，b，c}，B={a，b}，則A-B=_______________，AB=_______________________________________30．設(shè)A={a，b}，B＝｛1，2，3｝，則AB=31．已知集合A={1，2，3}，則A的冪集合(A)=____________________________________。32．設(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=____________________________________________________。33．設(shè)集合A={1，2，3，4，5}，A上偏序關(guān)系R的哈斯圖如下圖所示，則A的極大元是________，極小元是________________。二、計算或證明題1．利用推理規(guī)則證明：┒（P∧┒Q），┒Q∨R，┒R┒P（10分）2．利用推理規(guī)則證明：（x）（┒A（x）→B（x）），（x）┒B（x）（x）A（x）（10分）3．如果關(guān)系R和S為X上的等價關(guān)系，證明：RS也是X上的等價關(guān)系。（10分）4．設(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的自反閉包和對稱閉包。2）用Warshall算法求出R的傳遞閉包5．設(shè)<R，*>是一個代數(shù)系統(tǒng)，*是R上的一個二元運算，使得對于R中的任意元素x，y都有x*y=xyxy，證明0是幺元而且<R，*>是獨異點（其中，R為實數(shù)集，為普通加法，為普通乘法）（10分）6．設(shè)f1，f2都是一從代數(shù)系統(tǒng)<A，*>到代數(shù)系統(tǒng)<B，>的同態(tài)。設(shè)g是從A到B的一個映射，使得對任意aA，都有g(shù)(a)=f1(a)f2(a)；證明：如果<B，>為一個可交換半群，那么g是一個由<A，*>到<B，>的同態(tài)。（10分）7．假設(shè)給定了正整數(shù)的序偶集合A，在A上定義二元關(guān)系R如下：<<x，y>，<u，v>>R，當(dāng)且僅當(dāng)xv=yu，證明：R為等價關(guān)系。（10分）8．利用推理規(guī)則證明：P∨Q，P→R，Q→SR∨S

（10分）9．利用推理規(guī)則證明：?x(A(x)→B(x)),?x(C(x)→┓B(x))??x(C(x)→┓A(x))

10．下列均為集合A={1，2，3，4}上的偏序關(guān)系，分別畫出它們的哈斯圖，找出集合A相應(yīng)的最大、最小元，極大、極小元。

（10分）11．A={0，1，2，3，4}，式子{<x，y>2<x∧y<3}，寫出該式所給出的A上的二元關(guān)系，并畫出關(guān)系圖。

（10分）12．證明：設(shè)*是定義在集合A上的一個二元運算，且在A中有