離散數(shù)學題庫

———————————閱————卷————密————封————裝————訂————線——————————第36頁/共36頁院（系）班級學號（9位）姓名———————————閱————卷————密————封————裝————訂————線——————————第1頁/共4頁常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫01卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、單項選擇題（每題2分，共20分）下列表達式正確的有()（A） （B） （C） （D）設P：2×2=5，Q：雪是黑的，R：2×4=8，S：太陽從東方升起，下列()命題的真值為真。（A） （B） （C） （D）集合A={1,2,…,10}上的關(guān)系R={<x,y>|x+y=10,x,yA}，則R的性質(zhì)為()（A）自反的（B）對稱的（C）傳遞的，對稱的 （D）傳遞的設，，其中表示模3加法，*表示模2乘法，在集合上定義如下運算：有稱為的積代數(shù)，則的積代數(shù)幺元是()（A）<0，0> （B）<0，1> （C）<1，0> （D）<1，1>下圖中既不是Eular圖，也不是Hamilton圖的圖是()設為無向圖，，則G一定是()（A）完全圖 （B）樹 （C）簡單圖 （D）多重圖設P：我將去鎮(zhèn)上,Q：我有時間。命題“我將去鎮(zhèn)上,僅當我有時間”符號化為（）。（A）PQ （B）QP （C）PQ （D）在有n個結(jié)點的連通圖中,其邊數(shù)（）（A）最多有n-1條（B）最多有n條（C）至少有n-1條（D）至少有n條設A－B＝,則有（）（A）B＝ （B）B （C）AB （D）AB設集合A上有3個元素,則A上的不同的等價關(guān)系的個數(shù)為（）（A）5 （B）7 （C）3 （D）6二、填空題（每題2分，共20分）n個命題變元組成的命題公式共有種不同的等價公式。設〈L，≤〉為有界格，a為L中任意元素，如果存在元素b∈L,使，則稱b是a的補元。設*，Δ是定義在集合A上的兩個可交換二元運算，如果對于任意的x,y∈A,都有,則稱運算*和運算Δ滿足吸收律。設T是一棵樹，則T是一個連通且的圖。一個公式的等價式稱作該公式的主合取范式是指它僅由組成。量詞否定等價式?("x)P(x)?，?($x)P(x)?。二叉樹有5個度為2的結(jié)點，則它的葉子結(jié)點數(shù)為。設<G，*>是一個群，<G，*>是阿貝爾群的充要條件是。集合S={α，β，γ，δ}上的二元運算*為*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代數(shù)系統(tǒng)<S，*>中的幺元是，α的逆元是。設A={<1，2>，<2，4>，<3，3>}，B={<1，3>，<2，4>，<4，2>}=。=。三、判斷題（每題1分，共10分）命題公式是一個矛盾式。（），若，則必有。（）設S為集合X上的二元關(guān)系，則S是傳遞的當且僅當(SS)S。（）任何一棵二叉樹的結(jié)點可對應一個前綴碼。（）代數(shù)系統(tǒng)中一個元素的左逆元一定等于該元素的右逆元。（）一個有限平面圖，面的次數(shù)之和等于該圖的邊數(shù)。（）A′B=B′A（）設*定義在集合A上的一個二元運算，如果A中有關(guān)于運算*的左零元θl和右零θr,則A中有零元。（）一個循環(huán)群的生成元不是唯一的。（）任何一個前綴碼都對應一棵二叉樹。（）四、解答題（5小題，共30分）（5分）什么是歐拉路？如何用歐拉路判定一個圖G是否可一筆畫出？（8分）求公式(P∨Q)R的主析取范式和主合取范式。（5分）已知一棵無向樹中有2個2度頂點、1個3度頂點、3個4度頂點，其余頂點度數(shù)都為1。問它有多少個1度頂點？（7分）權(quán)數(shù)1，4，9，16，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹。（5分）集合上的關(guān)系，，寫出關(guān)系矩陣，畫出關(guān)系圖并討論R的性質(zhì)。五、證明（3小題，共20分）（10分）用推理P,T規(guī)則證明：PQ，P→R,Q→SRS。（5分）設Ａ，Ｂ，Ｃ是三個集合，證明：(A－B)(A－C)=A－(BC)。（5分）設<G,*>是群，aG。令H={xG|a*x=x*a}。試證：H是G的子群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫02卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）下列公式中哪些是永真式？()（A）(┐PQ)→(Q→R) （B）(PQ)→P （C）P→(Q→Q) （D）P→(PQ)下列推導錯在()① P② US①③ ES②④ UG③（A）② （B）④ （C）③ （D）無集合A={1，2，3，4}上的偏序關(guān)系圖為圖(0)，則它的Hass圖為()設R是實數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R，×>不是()（A）群 （B）獨異點 （C）半群 （D）廣群連通非平凡的無向圖G有一條歐拉回路當且僅當圖G()（A）只有一個奇度結(jié)點 （B）只有兩個奇度結(jié)點 （C）只有三個奇度結(jié)點 （D）沒有奇度結(jié)點若一棵完全二元（叉）樹有2n-1個頂點，則它()片樹葉（A）n（B）2n （C）n-1 （D）2在謂詞演算中,是的有效結(jié)論,根據(jù)是（）。（A）US規(guī)則（B）UG規(guī)則（C）ES規(guī)則（D）EG規(guī)則設在上海工作；是上海人。則命題“在上海工作的人未必都是上海人”的符號化為（）。A．（B）（C）（D）集合A上的關(guān)系R是相容關(guān)系的必要條件是（）（A）自反,反對稱的 （B）反自反,對稱的 （C）傳遞,自反的 （D）自反,對稱的下列各式錯誤的是（）（A） （B） （C） （D）二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式：（1）┐(P∨Q)； （2）PQ；若集合A上的關(guān)系R滿足的三個性質(zhì)，則R是偏序關(guān)系。設A，B是兩命題公式，當且僅當。給定無孤立點圖G，若存在一條路滿足，該條路稱為歐拉路。一個稱為布爾格。對于實數(shù)集合R，在下表所列的二元遠算是否具有左邊一列中的性質(zhì)，請在相應位上填寫“Y”或“N”MaxMin+可結(jié)合性可交換性存在幺元存在零元設<A,￡>為偏序集，BíA，記B-={y|y?A且y是B的上界}，若B-有最小元，則稱該最小元為B的。一個公式的等價式稱作該公式的主析取范式是指它僅由組成。由集合A和B的所有共同元素組成的集合稱為A和B的交集，記作A?B，即A?B={}。的圖稱為完全圖。三、判斷題（每題1分，共10分）“北京與天津的距離很近”是復合命題。（）如果A∨CB∨C，則有AB。（）設R1和R2是集合A上的關(guān)系，且R1R2，則有r(R1)r(R2)。（）若平面圖共有v個結(jié)點，e條邊和r個面，則v-e+r=2。（）任何循環(huán)群必定是阿貝爾群，反之亦真。（）命題公式是沒有真假值的。（）格〈L,≤〉所誘導的代數(shù)系統(tǒng)為〈L,∧，∨〉，則運算∧，∨滿足交換律。（）設函數(shù)f:A→B,則f的逆關(guān)系是函數(shù)當且僅當f是入射。（）群<G,*>的運算表中的每一行或每一列不一定是G的元素的一個置換。（）任何一棵二叉樹可對應一個前綴碼。（）四、解答題（3小題，共20分）（5分）簡述二叉樹的定義。如何將任何一棵有序樹（m叉樹）改寫為對應的二叉樹？（8分）求公式(P→Q)R的主析取范式和主合取范式。（7分）如下圖所示的賦權(quán)圖表示某七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。五、證明（4小題，共30分）（10分）用推理P,T規(guī)則證明：P→Q，QR，R，SPS。（10分）若R和S都是非空集A上的等價關(guān)系，則RS是A上的等價關(guān)系。（6分）若圖G不連通，則G的補圖是連通的。（4分）I(整數(shù)集)上的二元運算*定義為：a,bI，a*b=a+b-2。證明<I,*>是群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫03卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、單項選擇題（每題2分，共20分）在下述公式中不是重言式為()（A） （B）（C） （D）設，則B－A是()（A） （B） （C） （D）設A={1，2，…，10}，則下面定義的運算*關(guān)于A封閉的有()（A）x*y=max(x，y) （B）x*y=質(zhì)數(shù)p的個數(shù)使得（C）x*y=gcd(x，y) (gcd(x，y)表示x和y的最大公約數(shù))（D）x*y=lcm(x，y)（lcm(x，y)表示x和y的最小公倍數(shù)）設<A，>是偏序集，“”定義為：，則當集合A=()時，<A，>是格（A）{1,2,3,4,6,12}（B）{1,2,3,4,6,8,12,14}（C）{1,2,3,…,12}（D）{1,2,3,4}在有n個頂點的連通圖中，其邊數(shù)()（A）最多有n-1條（B）至少有n條 （C）最多有n條 （D）至少有n-1條一棵樹有2個2度頂點，1個3度頂點，3個4度頂點，則其1度頂點為()（A）5（B）7 （C）8 （D）9公式G=P￢P,則G是（）（A）永真的（B）永假的（C）可滿足的（D）析取的設P,Q的真值為0,R,S的真值為T,則下面命題公式中真值為T的是（）.（A）RP（B）QS（C）PS（D）QRA={1,2,3}上的關(guān)系R={<1,1><1,2><1,3><3,3>},則R具備（）（A）傳遞性與反對稱性（B）傳遞性與對稱性（C）自反性與對稱性（D）反自反性與對稱性連通圖G是一顆樹,當且僅當滿足下述條件中那一個（）（A）有些邊不是割邊。（B）每條邊都是割邊（C）每條邊都不是割邊（D）無割邊集二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式： （1）P→Q； （2）PQ；若對命題P賦值T，Q賦值F，則命題PQ的真值為。代數(shù)系統(tǒng)<A，*>中，|A|>1，如果分別為<A，*>的幺元和零元，則的關(guān)系為（填相等或不相等）。設集合A={1，2，3，4，5，6，7，8，9，10}，定義A上的二元關(guān)系“≤”為x≤y=x|y，則xy=。公式的根樹表示為。重言式又叫式，其定義為。給定無孤立點圖G，若存在一條回路滿足，該回路稱為歐拉回路。設R為X到Y(jié)的關(guān)系，S為從Y到Z上的關(guān)系，R°S稱為R和S的復合關(guān)系，則R°S=。設<G,*>為群，若在G中存在一個元素a,使得，則稱該群為循環(huán)群。設G是一個連通平面圖，一個面的稱作該面的次數(shù)。三、判斷題（每題1分，共10分）設命題“所有的研究生都讀過大學”符號化為：。（）設P，Q是兩個命題，當且僅當P，Q的真值均為T時，PQ的值為T。（）設A={a，b，c}，RA×A且R={<a，b>，<a，c>}，則R是傳遞的。（）在有向圖中頂點間的相互可達關(guān)系是等價關(guān)系。（）代數(shù)系統(tǒng)中一個元素若有左逆元，則該元素一定也有右逆元。（）合式公式的定義是用一個遞歸形式給出的。（）格〈L,≤〉所誘導的代數(shù)系統(tǒng)為〈L,∧，∨〉，則運算∧，∨滿足分配律。（）設函數(shù)f:A→B,則f的逆關(guān)系是函數(shù)當且僅當f是滿射。（）群<G,*>的運算表中的每一行或每一列都是G的元素的一個置換。（）K3，3不是平面圖。（）四、解答題（4小題，共30分）（5分）請解釋謂詞演算推理理論的US規(guī)則，UG規(guī)則，ES規(guī)則和EG規(guī)則。（8分）求公式(P→Q)(RP)的主析取范式和主合取范式。（10分）集合上的偏序關(guān)系R為整除關(guān)系。設，，試畫出R的哈斯圖，并求A，B，C的最大元素、極大元素、下界、上確界。（7分）假設英文字母，a，e，h，n，p，r，w，y出現(xiàn)的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳輸它們的最佳前綴碼，并給出happynewyear的編碼信息。五、證明（3小題，共20分）（8分）用推理P,T規(guī)則證明：BD，(E→F)→D，EB。（6分）證明在6個結(jié)點12條邊的簡單連通平面圖中，每個面的次數(shù)都是3。（6分）<I,+>是一個群,設IE＝{x|x=2n,n∈I},證明<IE,+>是<I,+>的子群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫04卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）命題“盡管有人聰明，但未必一切人都聰明”的符號化（P(x)：x是聰明的，M(x)：x是人）()（A） （B）（C） （D）謂詞公式中的x是()（A）自由變元 （B）約束變元（C）既不是自由變元又不是約束變元 （D）既是自由變元又是約束變元集合A={1，2，3，4}上的偏序關(guān)系如圖(0)，則它的哈斯圖為()設是布爾代數(shù)，f是從An到A的函數(shù)，則()（A）f是布爾代數(shù)（B）f能表示成析取范式，也能表示成合取范式（C）若A={0，1}，則f一定能表示成析取范式，也能表示成合取范式（D）若f是布爾函數(shù)，它一定能表示成析（合）取范式設，*為普通乘法，則<S，*>是()（A）代數(shù)系統(tǒng) （B）半群 （C）群 （D）都不是設無向圖G有18條邊且每個頂點的度數(shù)都是3，則圖G有()個頂點（A）10 （B）4 （C）8 （D）12一個割邊集與任何生成樹之間()（A）沒有關(guān)系 （B）至少有一條公共邊 （C）有一條公共邊 （D）割邊集誘導子圖是生成樹集合A上的等價關(guān)系R,決定了A的一個劃分,該劃分就是（）（A）商集A/R （B）交集AR （C）差集A-R （D）并集AR公式G=P￢P,則G是（）（A）永真的（B）永假的（C）可滿足的（D）析取的在有n個結(jié)點的連通圖中,其邊數(shù)（）（A）最多有n-1條（B）至少有n-1條（C）最多有n條（D）至少有n條二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式：（1）┐(P∧Q)； （2）PQ；n個命題變元有個互不等價的極小項。設n階圖G中有m條邊，每個結(jié)點的度數(shù)不是k的是k+1，若G中有Nk個k度頂點，Nk+1個k+1度頂點，則Nk=。設集合S={α，β，γ，δ，ζ}，S上的運算*定義為*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ則代數(shù)系統(tǒng)<S，*>中幺元是，β左逆元是。具有的圖稱為歐拉圖。設*是定義在集合A上的一個二元運算，θ為A中的一個元素，如果對于任一x∈A,有，則稱θ為A中關(guān)于運算*的零元。是存在量詞消去規(guī)則，簡稱ES規(guī)則。R在A上是自反的?íR。若偏序集A的每一個非空子集存在最小元，則稱偏序集A為集。設圖G=<V,E>，如果有圖G’=<V’,E’>，使得，則稱圖G’是圖G的子圖。三、判斷題（每題1分，共10分）命題公式是重言式。（）公式中的轄域為。（）不可能有某種關(guān)系，既是對稱的，又是反對稱的。（）在任何有向圖中，所有結(jié)點的入度的平方和等于所有結(jié)點的出度的平方和。（）設S={1，2}，則S在普通加法和乘法運算下都封閉。（）PúQ是一個合取范式。（）格〈L,≤〉所誘導的代數(shù)系統(tǒng)為〈L,∧，∨〉，則運算∧，∨滿足結(jié)合律。（）設函數(shù)f:A→B,則f的逆關(guān)系是函數(shù)當且僅當f是雙射。（）群<G,*>中，除幺元e外，不可能有任何別的等冪元。（）在任意圖中,存在奇數(shù)個度數(shù)為奇數(shù)的結(jié)點。（）四、解答題（5小題，共30分）（5分）簡述Warshall在1962年提出的求傳遞閉包的方法。（8分）求公式Q→(PR)的主析取范式和主合取范式。（4分）設全集U={a,b,c,d,e},A={a,d},B={a,b,c},求P(A)-P(B)。（9分）在二叉樹中（1）求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹T; （2）求T對應的二元前綴碼。（4分）設S=QQ，Q為有理數(shù)集合，*為S上的二元運算：對任意<a,b>，<c,d>S,有<a,b>*<c,d>=<ac,ad+b>,求出S關(guān)于二元運算*的幺元以及當a0時，<a,b>關(guān)于*的逆元。五、證明（2小題，共20分）（10分）用推理P,T規(guī)則證明：P→(Q→R)，R→(Q→S)P→(Q→S)。（10分）設<A,*>是半群,e是左幺元且對每一個,存在,使得。①證明：對于任意的,如果a*b=b*c則b=c。②通過證明e是A中的幺元,證明<A,*>是群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫05卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）下列是真命題的有()（A） （B） （C） （D）下列集合中哪個是最小聯(lián)結(jié)詞集()（A） （B）{,} （C）{,} （D）設，S上關(guān)系R的關(guān)系圖如下，則R具有()性質(zhì)（A）自反性、對稱性、傳遞性 （B）反自反性、反對稱性 （C）反自反性、反對稱性、傳遞性 （D）自反性設，*為普通乘法，則<S，*>是()（A）代數(shù)系統(tǒng) （B）半群 （C）群 （D）都不是如右圖相對于完全圖K5的補圖為()設G是n個結(jié)點、m條邊和r個面的連通平面圖，則m等于()（A）n+r-2 （B）n-r+2 （C）n-r-2 （D）n+r+2連通圖G是一顆樹,當且僅當滿足下述條件中那一個（ ）（A）有些邊不是割邊。（B）每條邊都是割邊（C）每條邊都不是割邊（D）無割邊集設集合A={1,2,3,,10},在集合A上定義運算,不是封閉的為（）（A） （B）（最大公約數(shù)）（C）（最小公倍數(shù)） （D）設R和S是集合A上的等價關(guān)系,則RS的對稱性（）（A）一定不成立（B）一定成立 （C）不一定成立（D）不可能成立圖G和G’的結(jié)點和邊分別存在一一對應關(guān)系是G和G’同構(gòu)的（）（A）必要條件（B）充分條件（C）充要條件（D）既不充分也不必要條件二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式： （1）P→Q； （2）PQ；任意兩個不同小項的合取為，全體小項的析取式為。設S={a1，a2，…，a8}，Bi是S的子集，且設B1={a8},則由B31所表達的子集是。設集合S={α，β，γ，δ，ζ}，S上的運算*定義為*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ則代數(shù)系統(tǒng)<S，*>中幺元是，β左逆元是。n階完全圖Kn的點色數(shù)X(KN)=。無向圖G具有一條歐拉路，當且僅當G是連通的，且。*是定義在A上的一個二元運算，e是A中關(guān)于運算*的幺元。如果對于A中的一個元素a存在著A中的某個元素b,使得，那么就稱b是a的一個逆元。是存在量詞引入規(guī)則，簡稱EG規(guī)則。設X和Y是任意兩個集合，而f是X到Y(jié)的一個關(guān)系，如果，稱關(guān)系f為函數(shù)。設圖G的子圖為G’，如果,則稱該圖G’為G的生成子圖。三、判斷題（每題1分，共10分）命題公式是重言式。（）設命題“所有的研究生都讀過大學”符號化為：。（）AB當且僅當A∩B=A。（）在有向圖中，所有結(jié)點的入度平方之和等于出度平方之和。（）設<S，*>是群<G，*>的子群，則<S，*>中幺元不一定是<G，*>中幺元。（）對于n個結(jié)點的完全圖Kn，有X(Kn)＝n。（）Aè(B′C)=(AèB)′(AèC)（）群中的運算不滿足消去律。（）質(zhì)數(shù)階群必定是循環(huán)群。（）(x)(A(x)∨B(x))?(x)A(x)∨(x)B(x)（）四、解答題（5小題，共30分）（5分）什么是集合的劃分，如何根據(jù)集合A的一個劃分確定A的元素間的一個等價關(guān)系？（8分）求公式┐(P∧R)∧(P∨Q)的主析取范式和主合取范式。（4分）設A={a,d},B={a,b,c},C={b,d}。求集合(A-B)(B-C)。（7分）在通訊中，八進制數(shù)字出現(xiàn)的頻率如下：0：20%、1：30%、2：10%、3：15%、4：10%、5：5%、6：5%、7：5%,求傳輸它們最佳前綴碼（寫出求解過程）。（6分）某年級共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，若以課程表示結(jié)點，有一人同時選兩門課程，則這兩點間有邊（其圖如右），問至少需幾天？五、證明（2小題，共20分）（10分）用推理P,T規(guī)則證明：P→Q，P→R，R→SS→Q。（10分）設，在上定義關(guān)系當且僅當，證明是上的等價關(guān)系，并求出[<2,5>]R。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫06卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、單項選擇題（每題2分，共20分）設是人，犯錯誤,命題“沒有不犯錯誤的人”符號化為()（A） （B） （C） （D）下列公式是重言式的有()（A） （B） （C） （D）設A={}，B=Р(Р(A))下列()表達式不成立（A） （B） （C） （D）下面偏序集()能構(gòu)成格6階有限群的任何子群一定不是()（A）2階 （B）3階 （C）4階 （D）6階一棵無向樹T有7片樹葉，3個3度頂點，其余頂點均為4度。則T有()個4度結(jié)點（A）1 （B）2 （C）3 （D）4設G是一個哈密爾頓圖，則G一定是()（A）歐拉圖 （B）樹 （C）平面圖 （D）連通圖設R和S是集合A上的等價關(guān)系,則RS的對稱性（ ）（A）不一定成立（B）一定不成立（C）一定成立（D）不可能成立設G=<V,E>,|V|=n,|E|=m為連通平面圖且有r個面,則r=（）（A）n-m-2 （B）m-n+2（C）n+m-2（D）m+n+2在0____之間填上正確的符號是（）（A）= （B） （C） （D）二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式：（1）┐(P∧Q)； （2）PQ；若P，Q，為二命題，真值為F當且僅當。設考慮下列子集，，，。，。則是A的覆蓋的子集有，是A的劃分的子集有。設<G，*>是一個群，則（A）若a，b，x∈G，ax=b，則x= 。（B）若a，b，x∈G，ax=ab，則x=。n階無向完全圖Kn的邊數(shù)是，每個結(jié)點的度數(shù)是。無向圖G具有一條歐拉回路，當且僅當G是連通的，且。一般來說，命題公式用聯(lián)結(jié)詞組表示。是反對稱的?R?Rcí。設函數(shù)f:A?B，g:C?D，如果A=C，B=D，且，則稱函數(shù)f和g相等，記作f=g。在無向圖G中，如果結(jié)點u和v之間，則結(jié)點u和v稱為是連通的。三、判斷題（每題1分，共10分）若P為命題變元，P∧P為主合取范式。 （）如果AB，則有￢A￢B。（）設R1和R2是集合A上的關(guān)系，且R1R2，則有t(R1)t(R2)。（）在完全二元樹中，若有片葉子，則邊的總數(shù)。（）獨異點的運算表中任意兩行都是不相同的。（）任意平面圖G最多是5-色的。（）A′B=B′A（）群中的運算不滿足消去律。（）質(zhì)數(shù)階群不一定是循環(huán)群。（）("x)F(x)T($x)F(x)（）四、解答題（5小題，共30分）（5分）已知一個偏序關(guān)系，如何畫出它的哈斯圖？（8分）求公式(P→Q)(RP)的主析取范式和主合取范式。（6分）如右圖給出的賦權(quán)圖表示六個城市及架起城市間直接通訊線路的預測造價。試給出一個設計方案使得各城市間能夠通訊且總造價最小，并計算出最小總造價。（7分）構(gòu)造H、A、P、N、E、W、R、對應的前綴碼，并畫出與該前綴碼對應的二叉樹，寫出英文短語HAPPYNEWYEAR的編碼信息。（4分）設全集U={a,b,c,d,e},A={a,d},B={a,b,c},C={b,d}。求集合(AB)C。五、證明（2小題，共20分）（10分）用推理P,T和CP規(guī)則證明：A∨B→C∧D，D∨E→FA→F。（10分）R是實數(shù)集，<R-{-1},*>是一個代數(shù)系統(tǒng)，*是R-{-1}上的一個二元運算，使得對于R-{-1}中任意元素a,b都有a*b=a+b+ab，證明0是<R-{-1},*>的幺元，而且<R-{-1},*>是群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫07卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）設L(x)：x是演員，J(x)：x是老師，A(x,y)：x欽佩y，命題“所有演員都欽佩某些老師”符號化為()（A） （B） （C） （D）命題邏輯演繹的CP規(guī)則為()（A）在推演過程中可隨便使用前提（B）在推演過程中可隨便使用前面演繹出的某些公式的邏輯結(jié)果（C）設是含公式A的命題公式，，則可用B替換中的A（D）如果要演繹出的公式為形式，那么將B作為前提，演繹出C下列命題正確的是()（A） （B） （C） （D）設<A,>是一個有界格，如果它也是有補格，只要滿足()（A）每個元素都至少有一個補元 （B）每個元素都有多個補元 （C）每個元素都無補元 （D）每個元素都有一個補元設，*為普通乘法。則代數(shù)系統(tǒng)的幺元為()（A）不存在 （B） （C） （D）下列圖中()是根樹（A） （B）（C） （D）左圖(0)相對于完全圖K5的補圖為()集合A上的關(guān)系R是相容關(guān)系的必要條件是（）（A）自反、反對稱的（B）反自反、對稱的（C）傳遞、自反的（D）自反、對稱的公式G=P￢P,則G是（）。（A）永真的（B）永假的（C）可滿足的（D）析取的在圖G=<V,E>中,結(jié)點總度數(shù)與邊數(shù)的關(guān)系是（）（A） （B） （C） （D）二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式： （1）P→Q； （2）PQ；論域D={1，2}，指定謂詞PP(1，1)P(1，2)P(2，1)P(2，2)TTFF則公式真值為。下圖所示的哈斯圖中，是格的為。在一個群〈G，*〉中，若G中的元素a的階是k，則a-1的階是。一個圖的歐拉回路是一條通過圖中的回路。給定圖G，若存在一條路滿足，這條路稱作漢密爾頓路。一個代數(shù)系統(tǒng)<S,*>,如果運算*是和，則稱代數(shù)系統(tǒng)<S,*>為半群。一個命題公式稱為合取范式，當且僅當它具有形式。設*是定義在集合A上的二元運算，如果對于任意的x,y∈A,都有，則稱該二元運算*是可交換的。若圖G=〈V,E〉滿足，則G稱為連通圖。三、判斷題（每題1分，共10分）若命題合式公式A的對偶式是A*，則AA*。（）“今天你吃飯了嗎？”這句話不是命題。（）設S為集合X上的二元關(guān)系，則S是傳遞的當且僅當SSS。（）不可能有偶數(shù)個結(jié)點，奇數(shù)條邊的歐拉圖。（）有最大元和最小元的偏序集并不一定是格。（）連通圖的生成樹是唯一的。（）在任意圖中,存在奇數(shù)個度數(shù)為奇數(shù)的結(jié)點。（）群<G,*>的運算表中的每一行或每一列不一定是G的元素的一個置換。（）設<G,*>是一個群，<S,*>是<G,*>的一個子群，則<G,*>中的幺元e一定是<S,*>中的幺元。（）K5不是平面圖。（）四、解答題（5小題，共30分）（5分）什么是集合的覆蓋，如何根據(jù)集合A的一個覆蓋確定A元素間的一個相容關(guān)系？（3分）設A={0,1,2}，B={0,2,4}，列出二元關(guān)系R={<x,y>|x,y}的所有元素。（8分）求公式(PQ)(PR)的主析取范式和主合取范式。（10分）設集合Ａ＝{a,b,c,d}上的關(guān)系Ｒ＝{<a,b>,<b,a>,<b,c>,<c,d>},寫出它的關(guān)系矩陣和關(guān)系圖，并用矩陣運算方法求出Ｒ的傳遞閉包。（6分）某年級共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，若以課程表示結(jié)點，有一人同時選兩門課程，則這兩點間有邊（其圖如右），問至少需幾天？五、證明（2小題，共20分）（10分）用規(guī)則P,T和CP推證：B∨D,(C→A)→DB→C。（10分）設I+是正整數(shù)集，A={<x,y>|x∈I+∧y∈I+}，R={<<x,y>,<u,v>>|xv=yu∧<x,y>∈A∧<u,v>∈A}，證明R是一個等價關(guān)系。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫08卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）命題“有的人喜歡所有的花”的邏輯符號化為()設D：全總個體域，F(xiàn)（x）：x是花，M(x)：x是人，H(x,y)：x喜歡y（A） （B）（C） （D）給定公式，當D={a,b}時，解釋()使該公式真值為F。（A）P(a)=0、P(b)=0 （B）P(a)=0、P(b)=1 （C）P(a)=1、P(b)=1 （D）P(a)=1、P(b)=0下面集合()關(guān)于整除關(guān)系構(gòu)成格（A）{2,3,6,12,24,36} （B）{1,2,3,4,6,8,12} （C）{1,2,3,5,6,15,30} （D）{3,6,9,12}Q為有理數(shù)集N，Q上定義運算*為a*b=a+b–ab，則<Q，*>的幺元為()（A）a （B）b （C）1 （D）0設n階圖G有m條邊，每個結(jié)點度數(shù)不是k就是k+1，若G中有Nk個k度結(jié)點，則Nk=()（A）n×k （B）n×(k+1) （C）n×(k+1)-m （D）n×(k+1)-2m設G是一棵樹，n,m分別表示頂點數(shù)和邊數(shù)，則()（A）n=m （B）n=m+1 （C）m=n+1 （D）不能確定集合A上的關(guān)系R是相容關(guān)系的必要條件是（）（A）自反、反對稱的（B）反自反、對稱的（C）傳遞、自反的（D）自反、對稱的Z是整數(shù)集合,對于下列*運算,哪個<Z,*>代數(shù)系統(tǒng)是半群（）（A）（B）（C）（D）無向圖G中的邊e是其割邊的充分必要條件是（）（A）邊e是平行邊 （B）邊e不是平行邊（C）邊e不包含在G的任一簡單回路中 （D）邊e不包含在G的某一回路中。設集合A={1,2,3,,10},在集合A上定義運算,不是封閉的為（）（A）（最小公倍數(shù)）（B）（最大公約數(shù)）（C）（D）二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式：（1）┐(P∨Q)； （2）PQ；若解釋I的論域D僅包含一個元素，則在I下真值為。設A={a，b，c，d}，A上二元運算如下：*abcdabcdabcdbcdacdabdabc那么代數(shù)系統(tǒng)<A，*>的幺元是，有逆元的元素為。n個結(jié)點的有向完全圖邊數(shù)是，每個結(jié)點的度數(shù)是。給定圖G，若存在一條回路滿足，這個回路稱作漢密爾頓回路。含有的半群稱為獨異點。要證明AíB，必須證明。設RíA′A且A1?,則r(R)=。設*是定義在集合A上的二元運算，如果對于任意的x,y∈A,都有,則稱二元運算*在A上是封閉的。簡單有向圖G=〈V,E〉中，任意一對結(jié)點間，至少有一個結(jié)點到另一個結(jié)點是可達的，則稱這個圖為連通圖。三、判斷題（每題1分，共10分）關(guān)系R是對稱的，當且僅當關(guān)系矩陣是對稱的，或在關(guān)系圖上，任兩個結(jié)點間若有定向弧線，必是成對出現(xiàn)的。（）“這件作品多有創(chuàng)意！”這句話不是命題。（）設集合S={1，2，3，4}，S上的關(guān)系R={<1，1>，<2，2>，<1，3>}，則R具有自反性。（）無多重邊的圖是簡單圖。（）循環(huán)群的任何子群必定是循環(huán)群。（）連通圖的生成樹是不唯一的。（）A?(B′C)=(A?B)′(A?C)（）群中可以有零元。（）如果〈L,≤〉是格，S是L的子集且〈S,≤〉是格，則〈S,≤〉一定是〈L,≤〉的子格。（）任何一棵有序樹都可以改寫為唯一的一棵二叉樹，同樣，任何一棵二叉樹都對可以改回成唯一的一棵有序樹。（）四、解答題（5小題，共30分）（5分）什么是商集，如何根據(jù)集合A的一個等價關(guān)系R求得A關(guān)于R的一個商集？（8分）求公式(R→Q)P的主析取范式和主合取范式。（10分）設集合Ａ＝{a,b,c,d,e}上的關(guān)系Ｒ＝{<a,b>,<b,c>,<b,d>,<d,e>}寫出它的關(guān)系矩陣和關(guān)系圖，并用矩陣運算方法求出Ｒ的傳遞閉包。（3分）設A={1,2,3,4,5}，B={1,2}，列出二元關(guān)系R={<x,y>|2x+y4且x，yB}的所有元素。（4分）設S={１,２,３,４}，Ａ上的關(guān)系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝，求(1)RR(2)R-1。五、證明（3小題，共20分）（8分）利用規(guī)則P，T或CP推證：（P∧Q）,Q∨R,RP。（6分）求一棵帶權(quán)為1,1,1,2,2,3,4,5的最優(yōu)二叉樹T,并計算W(T)。3．（6分）設<A,*>是半群,e是左幺元且對每一個，存在,使得。證明e是<A,*>中幺元。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫09卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、單項選擇題（每題2分，共20分）公式換名()（A） （B）；（C） （D）。下面蘊涵關(guān)系不成立的是()（A） （B）（C） （D）判斷下列命題哪個為正確？()（A）{Ф}∈{Ф,{{Ф}}} （B）{Ф}{Ф,{{Ф}}}` （C）Ф∈{{Ф}} （D）{a,b}∈{a,b,{a},}下列哪個偏序集構(gòu)成有界格()（A）（N，）（B）（Z，） （C）（{2，3，4，6，12}，|（整除關(guān)系）） （D）(P（A），)6階群的子群的階數(shù)可以是()（A）1，2，5 （B）2，4 （C）3，6，7 （D）2，3一棵樹有7片樹葉，3個3度結(jié)點，其余全是4度結(jié)點，則該樹有()個4度結(jié)點（A）1 （B）2 （C）3 （D）4設G是有n個結(jié)點m條邊的連通平面圖，且有k個面，則k等于()（A）m-n+2 （B）n-m-2 （C）n+m-2 （D）m+n+2設在上海工作；是上海人。則命題“在上海工作的人未必都是上海人”的符號化為（）（A）（B）（C）（D）設V={a,b,c,d},則與V構(gòu)成強連通圖的邊集為（）（A）E1={<a,d>,<b,a>,<b,d>,<c,b>,<d,c>}（B）E2={<a,d>,<b,a>,<b,d>,<b,c>,<d,c>}（C）E3={<a,c>,<b,a>,<b,c>,<d,a>,<d,c>}（D）E4={<a,b>,<a,c>,<a,d>,<b,d>,<c,d>}下列公式中不是合式公式的是（）（A） （B）P（RS）（C） （D）P（RS）二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式： （1）PQ； （2）PQ；一般說來，n個命題變元共有個小項（或大項）。設<G，*>是一個群，a，b，c∈G，則(1)若ca=b，則c=; (2)若ca=ba，則c=。具有的圖稱為漢密爾頓圖。設<G,*>是一個代數(shù)系統(tǒng)，其中G是非空集合，如果，則稱<G,*>是一個群。n個命題變元的析取式，稱為布爾析取或大項，是指：。í的傳遞性是指：。設RíA′A且A1?,則s(R)=。設*是定義在集合A上的二元運算，如果對于任意的x,y,z∈A都有,則稱該二元運算*是可結(jié)合的。簡單有向圖G=〈V,E〉中，如果對于圖G中的任意兩個結(jié)點兩者之間是互相可達的，則稱這個圖為圖。三、判斷題（每題1分，共10分）任意兩個矛盾式的合取還是矛盾式。（）如果￢A￢B，則有AB。（）任意無限集合必含有可數(shù)子集。（）沒T是一棵m叉樹，它有t片樹葉，i個分枝點，則(m-1)i=t-1。（）設Q為有理數(shù)集，Q上運算*定義為，則<Q,*>是群。（）?PúQ是一個合取范式。（）在任意圖中,度數(shù)為奇數(shù)的結(jié)點不一定是偶數(shù)個。（）設*定義在集合A上的一個二元運算，如果A中有關(guān)于運算*的左幺元el和右幺er,則A中有幺元。（）任何一個循環(huán)群必定是阿貝爾群。（）簡單圖除了K5和K3，3外都是平面圖。（）四、解答題（5小題，共30分）（5分）<A,*>是一個代數(shù)系統(tǒng)，*是A上的一個二元運算，如何根據(jù)運算表看出<A,*>是否有=1\*GB3①封閉性；=2\*GB3②可交換性；=3\*GB3③等冪元；=4\*GB3④零元；=5\*GB3⑤幺元。（8分）求公式（PR）Q的主析取范式和主合取范式。（4分）設Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=y2｝，求RR和R-1的關(guān)系矩陣。（8分）求出帶權(quán)為2，3，5，7，8，9的最優(yōu)二叉樹T，并求W（T）。（5分）圖給出的賦權(quán)圖表示五個城市及對應兩城鎮(zhèn)間公路的長度。試給出一個最優(yōu)化的設計方案使得各城市間能夠有公路連通。五、證明（2小題，共20分）（10分）用推理P,T規(guī)則證明：（PQ）,（QR）,（RS）（PS）。（10分）設集合A＝{a,b,c,d}，A上的關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}（1）寫出關(guān)系R的關(guān)系矩陣；（2）求R的自反閉包,對稱閉包和傳遞閉包；（3）求包含R的最小的等價關(guān)系。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫10卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）下列哪個公式為永真式？()（A）QQ→P （B）QP→Q （C）PP→Q （D）P(PQ)P設，則有()（A）{{1,2}} （B）{1,2} （C）{1} （D）{2}下列結(jié)果正確的是()（A） （B） （C） （D）設I為整數(shù)集合，m是任意正整數(shù)，是由模m的同余類組成的同余類集合，在上定義運算，則代數(shù)系統(tǒng)最確切的性質(zhì)是()（A）封閉的代數(shù)系統(tǒng) （B）半群 （C）獨異點 （D）群一棵無向樹T有4度、3度、2度的分枝點各1個，其余頂點均為樹葉，則T中有()片樹葉（A）3 （B）4 （C）6 （D）5設，，則有向圖是()（A）強連通的 （B）單側(cè)連通的 （C）弱連通的 （D）不連通的設有33盞燈,擬公用一個電源,則至少需有五插頭的接線板數(shù)（）（A）7 （B）8 （C）9 （D）14下列代數(shù)系統(tǒng)<G,*>中,其中*是加法運算,（）不是群。（A）G為整數(shù)集合（B）G為偶數(shù)集合 （C）G為有理數(shù)集合 （D）G為自然數(shù)集合謂詞公式中量詞的轄域是（）。（A）（B） （C） （D）無向圖G是歐拉圖,當且僅當（）（A）G中所有結(jié)點的度數(shù)全為偶數(shù)（B）G連通且所有結(jié)點度數(shù)全為偶數(shù)（C）G的所有結(jié)點的度數(shù)全為奇數(shù)（D）G連通且所有結(jié)點度數(shù)全為奇數(shù)二、填空題（每題2分，共20分）設P、Q是命題公式，填寫如下的基本等價關(guān)系式：（1）┐(P∧Q)； （2）PQ；設<{a，b，c}，*>為代數(shù)系統(tǒng)，*運算如下：*abcaabcbbaccccc則它的幺元為；a、b的逆元分別為。當時，群只能有階非平凡子群，平凡子群為。樹T的邊數(shù)e與點數(shù)v有關(guān)系。設G＝〈V，E〉是一個無向圖，如果能夠在平面上把G畫成，就稱G是一個平面圖。設<G,Δ>是群，S是G的非空子集，如果對于S中的任意元素a和b有,則<S,Δ>是<G,Δ>的子群。設P（x）：x是素數(shù)，E(x)：x是偶數(shù)，O(x)：x是奇數(shù)N(x，y)：x可以整數(shù)y。則謂詞的自然語言是。設RíA′A且A1?,則t(R)=。設*，Δ是定義在集合A上的兩個二元運算，如果對于任意的x,y,z∈A都有,則稱運算*對于運算Δ是可分配的。簡單有向圖G=〈V,E〉中，如果在圖G中略去方向，將它看成是無向圖，圖是連通的，則稱該有向圖為。三、判斷題（每題1分，共10分）“北京到天津的距離很近”是復合命題。（）一個有限平面圖，面的次數(shù)之和等于該圖的結(jié)點度數(shù)。（）有人能夠證明存在一個無限集，其基數(shù)是嚴格介于之間的。（）一條回路和任何一棵生成樹至少有一條公共邊。（）循環(huán)群不一定是Abel群。（）?PúQ不是一個析取范式。（）K5不是平面圖。（）設*定義在集合A上的一個二元運算，如果A中有關(guān)于運算*的左零元θl和右零θr,且θl=θr,則A中有零元。（）x(F(y)→G(x))F(y)→xG(x)。（）設<G,Δ>是群，S是G的非空子集，如果對于S中的任意元素a和b有aΔb-1∈S,則<S,Δ>是<G,Δ>的子群。（）四、解答題（5小題，共30分）（5分）請敘述群的定義。（8分）求公式（PQ）R的主析取范式和主合取范式。（4分）設A={a,b}，P(A)為A的冪集，求集合P(A)A。（5分）設Ａ＝｛1,2,3,4,5,6｝，B={0,1,2,3}，從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=2y｝，求：(1)RR；(2)R-1。（8分）若傳遞a，b，c，d，e，f的頻率分別為2%，3%，5%，7%，8%，9%，求傳輸它的最佳前綴碼，要求寫出詳細的求解過程。五、證明（3小題，共20分）（8分）用推理P,T,CP規(guī)則證明：A→(B→C),(C∧D)→E,G→(D∧E)A→(B→G)。（8分）設<G，*>是一個群，證明<G，*>是阿貝爾群的充要條件是對于任意的a，b∈G有(a*b)*(a*b)=(a*a)*(b*b)。（4分）設A={a,b,c,d,e,f},R=IA∪{<a,b>,<b,a><f,e><e,f>},則R是A上的等價關(guān)系。(1)求a的等價類[a]R； (2)求商集A/R。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫11卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、單項選擇題（每題2分，共20分）下列等價關(guān)系正確的是()（A） （B）（C） （D）設R,S是集合A上的關(guān)系，則下列說法正確的是()（A）若R,S是自反的，則RS是自反的 （B）若R,S是反自反的，則RS是反自反的（C）若R,S是對稱的，則RS是對稱的 （D）若R,S是傳遞的，則RS是傳遞的設f，g是函數(shù)，當()時，f=g（A） （B）（C） （D）在Peterson圖中，至少填加()條邊才能構(gòu)成Euler圖（A）1 （B）2 （C）4 （D）5在有理數(shù)集Q上定義的二元運算*，有， 則Q中滿足()（A）只有唯一逆元 （B）時有逆元 （C）所有元素都有逆元 （D）所有元素都無逆元下面給出的符號串集合中,哪一個不是前綴碼（）（A）｛1,10,110,1111｝（B）｛01,001,000,1｝（C）｛b,c,aa,ac,aba,abc｝ （D）｛0011,01,101,11,100｝在自然數(shù)集合N上定義的二元運算,滿足結(jié)合律的運算是（）（A）ab=a-b（B）ab=a+4b（C）ab=min{a,b}（D）ab=|a-b|設集合A={1,2,3,,10},在集合A上定義如下運算,不是封閉的有（）（A）（最小公倍數(shù)）（B）（最大公約數(shù)）（C）（D）設S={0，1}，*為普通乘法，則<S，*>是()（A）半群，但不是獨異點 （B）群 （C）環(huán)，但不是群 （D）只是獨異點，但不是群在0____之間填上正確的符號是（）（A）=（B）（C）（D）二、填空題（每題2分，共20分）由集合A的組成的集合,稱為A的冪集，記作P(A)，即P(A)={x|xíA}。若一個集合A的若干個非空子集S1,S2,…,Sm滿足，則這些非空子集的全體叫做A的一個覆蓋。設<A,￡>為偏序集，BíA，若y?A滿足，稱y為B的下界。如果群<G,*>中的運算*是的，則稱該群為阿貝爾群。的圖稱為簡單圖。設G是一個連通平面圖，由圖中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含圖的，也不包含圖的，這樣的區(qū)域稱為圖G的一個面。設P、Q是命題公式，填寫如下的基本等價關(guān)系式：（1）P→Q； （2）PQ；給定集合A的一個覆蓋S={S1,S2,…,Sm}，若，則S稱作是A的一個劃分。圖的補圖為。n個結(jié)點的無向完全圖Kn的邊數(shù)為。三、判斷題（每題1分，共10分）("x)(A(x)∧B(x))?("x)A(x)∧("x)B(x)（）使命題公式的真值為F的真值指派的P、Q、R值分別是T、T、F。（）集合A上的恒等關(guān)系是一個雙射函數(shù)。（）任一簡單圖G的最大度數(shù)Δ（G）不一定小于G的頂點數(shù)。（）設是布爾代數(shù)，則一定為有補分配格。（）命題公式是有真假值的。（）設〈L,≤〉是一個格，那么對L中任何元素a,b,c,d,若a≤b，則a∨c≤b∨c，a∧c≤b∧c。（）存在基數(shù)嚴格介于其之間的無限集。（）群中的運算不滿足消去律。（）K3，3不是平面圖。（）四、解答題（5小題，共30分）（5分）什么是偏序關(guān)系？如何確定偏序集〈L，≤〉中最大元，極大元。（8分）求公式(PR)(QR)P的主析取范式和主合取范式。（7分）權(quán)數(shù)1，2，3，4，5，6，7，8，9，10構(gòu)造一棵最優(yōu)二叉樹。（5）集合上的關(guān)系，寫出關(guān)系矩陣MR，畫出關(guān)系圖并討論R的性質(zhì)。（5分）已知一棵無向樹中有3個2度頂點、1個3度頂點、2個4度頂點，其余頂點度數(shù)都為1。問它有多少個1度頂點？五、證明（3小題，共20分）（10分）用推理P,T規(guī)則證明：PQ，P→R,Q→SRS。（5分）證明對集合A、B和C,有（A∩B）∪C=A∩(B∪C)當且僅當CA。（5分）設<G,·>是群，aG。令H={xG|a·x=x·a}。試證：H是G的子群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫12卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、選擇題（每題2分，共20分）下列推理步驟錯在()① P② US①③ P④ ES③⑤ T②④I⑥ EG⑤（A）② （B）⑤ （C）④ （D）⑥設A={1，2，3，4}，P(A)（P(A)是A的冪集）上規(guī)定二元系則P(A)/R=()（A）A （B）P（A） （C）{[]R,[{1}]R,[{1,2}]R,[{1,2,3}]R,[{1,2,3,4}]R}（D）{[]R,[2]R,[2,3]R,[2,3,4]R,[A]R}Ａ，Ｂ，Ｃ是三個集合，則下列哪幾個推理正確()（A）AB，BC則AC （B）AB，BC則A∈B （C）A∈B，B∈C則A∈C （D）A∈B，B∈C則AC下圖中是哈密頓圖的為()在有n個頂點的連通圖中，其邊數(shù)()（A）最多有n-1條（B）至少有n條 （C）最多有n條 （D）至少有n-1條在自然數(shù)集合N上定義的二元運算,滿足結(jié)合律的是（）（A）ab=a-b（B）ab=min{a,b}（C）ab=a+4b（D）ab=|a-b|連通圖G是一棵樹當且僅當G中（）（A）有些邊不是割邊（B）每條邊都是割邊（C）無割邊集（D）每條邊都不是割邊集合A上的關(guān)系R是相容關(guān)系的必要條件是（）（A）自反,反對稱的（B）反自反,對稱的（C）傳遞,自反的（D）自反,對稱的具有6個結(jié)點的樹的邊數(shù)為（）（A）4（B）6（C）5（D）8集合A上的一個覆蓋確定A的元素間的關(guān)系為：（）（A）相容關(guān)系（B）全序關(guān)系（C）等價關(guān)系（D）偏序關(guān)系二、填空題（每題2分，共20分）設S={a，b，c}若S1={c},則S6的集合表示為。若是集合A的一個劃分，則它應滿足。設S是非空有限集，代數(shù)系統(tǒng)＜P（S），?，è＞中，P（S）對?的幺元為，零元為。P(S）對è的幺元為，零元為。n階完全圖結(jié)點v的度數(shù)deg(v)=。設*是定義在集合A上的一個二元運算，如果對于任意的x∈A,都有,則稱運算*是等冪的。集合A={，{}}的冪集P(A)=。證明ATB，即證A?B是重言式，有兩種證法：（1），（2）。R在A上被稱為傳遞的?。設<G,*>是一個群，<G,*>是阿貝爾群的充要條件是對任意的a,b∈G,有。設G是一個連通平面圖，包圍一個面的稱為這個面的邊界。三、判斷題（每題1分，共10分）(x)(F(x)→G(y))(x)F(x)→G(y)。（）如果f是函數(shù)，則其逆關(guān)系fc也是函數(shù)。（）對任意集合A，B，C有(A－B)－C=A－(B∩C)。（）任何有向圖中各結(jié)點入度之和等于邊數(shù)。（）在有幺元e的代數(shù)系統(tǒng)<S,*>中，如果*是可結(jié)合的運算，且每個元素都有左逆元,那么這個代數(shù)系統(tǒng)中任何一個元素的左逆元必定也是該元素的右逆元，且每個元素的逆元是唯一的。（）一個有限平面圖，面的次數(shù)之和等于該圖的邊數(shù)的二倍。（）(A′B)′C=A′(B′C)（）設<A,*>是一個代數(shù)系統(tǒng)，且集合A中元素的個數(shù)大于1。如果該代數(shù)系統(tǒng)中存在幺元e和零元θ,則θ≠e。（）一個循環(huán)群的生成元是唯一的。（）謂詞公式的前束范式是。（）四、解答題（3小題，共20分）（5分）請簡述“哥尼斯堡七橋問題”，該問題是否有解？為什么？（8分）求公式(P∧R)∧(P∨Q)的主析取范式和主合取范式。（7分）如下圖所示的賦權(quán)圖表示某七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。五、證明（4小題，共30分）（10分）用推理P,T規(guī)則證明：P→Q，QR，R，SPS。（10分）若R和S都是非空集A上的等價關(guān)系，則RS是A上的等價關(guān)系。（4分）設Ａ，Ｂ，Ｃ是三個集合，證明：A(B－C)＝(AB)－(AC)。（6分）I(整數(shù)集)上的二元運算*定義為：a,bI，a*b=a+b-2。證明<I,*>是群。常熟理工學院20～20學年第學期《離散數(shù)學》考試試卷（試卷庫13卷）試題總分：100分考試時限：120分鐘題號一二三四五總分閱卷人得分一、單項選擇題（每題2分，共20分）若公式的主析取范式為則它的主合取范式為()（A） （B）；（C） （D）。下列各式中哪個不成立()（A） （B）（C） （D）設A={，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“”的哈斯圖為()設[{a，b，c}，*]為代數(shù)系統(tǒng)，*運算如下：*abcaabcbbaccccc則零元為()（A）a （B）b （C）沒有 （D）c下面那一個圖可一筆畫出()在任何圖中必定有偶數(shù)個()（A）度數(shù)為偶數(shù)的結(jié)點 （B）入度為奇數(shù)的結(jié)點 （C）度數(shù)為奇數(shù)的結(jié)點 （D）出度為奇數(shù)的結(jié)點下列命題正確的是（）（A）{a}{a,b,c} （B）（A） （C）{a,b,c} （D）{a,b}{a}設集合A上有四個元素,則A上的不同的劃分的個數(shù)為（）（A）11 （B）14 （C）17 （D）15設<A，≤>是偏序集，，下面結(jié)論正確的是()（A）的上確界且唯一 （B）的極大元且不唯一（C）的上界且不唯一 （D）的極大元且唯一無向圖G中的邊e是G的割邊的充要條件為（）（A）e是重邊（B）e不是重邊（C）e不包含在G的任一簡單回路中（D）e不包含在G的某一回路中二、填空題（每題2分，共20分）設A={a,b,c},A上二元關(guān)系R={<a,a>,<a,b>,<a,c>,<c,c>},則s（R）=。設S={a1，a2，…，a8}，Bi是S的子集，則B31=。設I是整數(shù)集合，Z3是由模3的同余類組成的同余類集，在Z3上定義+3如下：，<Z+，+3>是否構(gòu)成群。歐拉圖的充要條件是。設A1?，RíA′A，若R是，則稱R為A上的等價關(guān)系。設*是定義在集合A上的一個二元運算，e為A中的一個元素,如果對于任意x∈A,有，則稱e為Ａ中關(guān)于運算*的幺元。在真值表中，一個公式的真值為T的指派所對應的小項的析取，即為此公式的范式。由所有集合A和B的所有元素組成的集合稱為A和B的并集，記作AèB，即AèB={}。設<A,≤>是偏序集，若有x,y?A，x≤y，且x1y，且不存在