/姓名：姓名：學(xué)號：得分：教師簽名：離散數(shù)學(xué)作業(yè)3離散數(shù)學(xué)集合論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次.內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí).基本上是按照考試的題型〔除單項選擇題外安排練習(xí)題目.目的是通過綜合性書面作業(yè).使同學(xué)自己檢驗學(xué)習(xí)成果.找出掌握的薄弱知識點.重點復(fù)習(xí).爭取盡快掌握。本次形考書面作業(yè)是第一次作業(yè).大家要認(rèn)真及時地完成集合論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來.手工書寫答題.字跡工整.解答題要有解答過程.要求20XX11月7日前完成并上交任課教師〔不收電子稿。并在03任務(wù)界面下方點擊"保存"和"交卷"按鈕.完成并上交任課教師。一、填空題1．設(shè)集合.則P<A>-P<B>={{3}.{1,3}.{2,3}.{1,2,3}}.AB={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>}．2．設(shè)集合A有10個元素.那么A的冪集合P<A>的元素個數(shù)為1024．3．設(shè)集合A={0,1,2,3}.B={2,3,4,5}.R是A到B的二元關(guān)系.則R的有序?qū)蠟閧<2,2>.<2,3>.<3,2>}.<3,3>．4．設(shè)集合A={1,2,3,4}.B={6,8,12}.A到B的二元關(guān)系R＝那么R－1＝{<6,3>,<8,4>}5．設(shè)集合A=｛a,b,c,d｝.A上的二元關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}.則R具有的性質(zhì)是沒有任何性質(zhì)．6．設(shè)集合A=｛a,b,c,d｝.A上的二元關(guān)系R={<a,a>,<b,b>,<b,c>,<c,d>}.若在R中再增加兩個元素{<c,b>,<d,c>}.則新得到的關(guān)系就具有對稱性．7．如果R1和R2是A上的自反關(guān)系.則R1∪R2.R1∩R2.R1-R2中自反關(guān)系有2個．8．設(shè)A={1,2}上的二元關(guān)系為R={<x,y>|xA.yA,x+y=10}.則R的自反閉包為{<1,1>,<2,2>}．9．設(shè)R是集合A上的等價關(guān)系.且1,2,3是A中的元素.則R中至少包含<1,1>,<2,2>,<3,3>等元素．10．設(shè)A={1.2}.B={a.b}.C={3.4.5}.從A到B的函數(shù)f={<1,a>,<2,b>}.從B到C的函數(shù)g={<a.4>,<b.3>}.則Ran<gf>={3,4}．二、判斷說明題〔判斷下列各題.并說明理由．1．若集合A={1.2.3}上的二元關(guān)系R={<1,1>.<2,2>.<1,2>}.則<1>R是自反的關(guān)系；<2>R是對稱的關(guān)系．錯誤。R不具有自反的關(guān)系.因為<3,3>不屬于R。錯誤。R不具有對稱的關(guān)系.因為<2,1>不屬于R。2．設(shè)A={1.2.3}.R={<1.1>,<2.2>,<1.2>.<2.1>}.則R是等價關(guān)系．a(chǎn)bcd圖一abcd圖一gefh3．若偏序集<A.R>的哈斯圖如圖一所示.則集合A的最大元為a.最小元不存在．解：錯誤．集合A的最大元不存在.a是極大元．4．設(shè)集合A={1,2,3,4}.B={2,4,6,8}..判斷下列關(guān)系f是否構(gòu)成函數(shù)f：.并說明理由．<1>f={<1,4>,<2,2,>,<4,6>,<1,8>}；<2>f={<1,6>,<3,4>,<2,2>}；<3>f={<1,8>,<2,6>,<3,4>,<4,2,>}．〔1不構(gòu)成函數(shù)。因為對于3屬于A.在B中沒有元素與之對應(yīng)?！?不構(gòu)成函數(shù)。因為對于4屬于A.在B中沒有元素與之對應(yīng)。〔3構(gòu)成函數(shù)。因為A中任意一個元素都有A中唯一的元素相對應(yīng)。三、計算題1．設(shè).求：<1><AB>~C；<2><AB>-<BA><3>P<A>－P<C>；<4>AB．解：〔1<AB>~C={1} 〔3〔4AB=<AB>－〔AB=〔2={1.2,4,5}-{1}={2,4,5}2．設(shè)A={{1},{2},1,2}.B={1,2,{1,2}}.試計算〔1〔AB；〔2〔A∩B；〔3A×B．解：〔1AB={{1},{2}}〔2A∩B={1,2}〔3A×B={<{1},1>.<{1},2>.<{1},{1,2}>.<{2},1>.<{2},2>.<{2},{1,2}>.<1,1>.<1,2>.<1,{1,2}>.<2,1>.<2,2>,<2,{1,2}>}3．設(shè)A={1.2.3.4.5}.R={<x.y>|xA.yA且x+y4}.S={<x.y>|xA.yA且x+y<0}.試求R.S.RS.SR.R-1.S-1.r<S>.s<R>．解：R={<1,1>,<1,2>,<1,3><2,1><2,2><3,1>}S=空集R*S=空集S*R=空集R-1={<1,1>,<2,1><3,1><1,2><2,2><1,3>}S-1=空集r<S>={<1,1><2,2><3,3><4,4><5,5>}s<R>={<1,1><1,2><1,3><2,1><2,2><3,1>}4．設(shè)A={1,2,3,4,5,6,7,8}.R是A上的整除關(guān)系.B={2,4,6}．<1>寫出關(guān)系R的表示式；<2>畫出關(guān)系R的哈斯圖；<3>求出集合B的最大元、最小元．R={<1,1><1,2><1,3><1,4><1,5><1,6><1,7><1,8><2,2><2,4><2,6><2,8><3,3><3,6><4,4><4,8><5,5><6,6><7,7><8,8>}哈斯圖如下：112486357<3>集合B沒有最大元.最小元是2四、證明題1．試證明集合等式：A<BC>=<AB><AC>．1．證明：設(shè).若x∈A<BC>.則x∈A或x∈BC.即x∈A或x∈B且x∈A或x∈C．即x∈AB且x∈AC.即x∈T=<AB><AC>.所以A<BC><AB><AC>．反之.若x∈<AB><AC>.則x∈AB且x∈AC.即x∈A或x∈B且x∈A或x∈C.即x∈A或x∈BC.即x∈A<BC>.所以<AB><AC>A<BC>．因此．A<BC>=<AB><AC>．2．試證明集合等式A<BC>=<AB><AC>．2．證明：設(shè)S=A∩<B∪C>.T=<A∩B>∪<A∩C>.若x∈S.則x∈A且x∈B∪C.即x∈A且x∈B或x∈A且x∈C.也即x∈A∩B或x∈A∩C.即x∈T.所以ST．反之.若x∈T.則x∈A∩B或x∈A∩C.即x∈A且x∈B或x∈A且x∈C也即x∈A且x∈B∪C.即x∈S.所以TS．因此T=S．3．對任意三個集合A,B和C.試證明：若AB=AC.且A.則B=C．對于任意<a.b>∈A×B.其中a∈A.b∈B,因為A×B=A×C.必有<a,b>∈A×C,其中b∈C因此BC〔2同理.對于任意<a,c>∈A×C,其中.a∈A.c∈C.因為A×B=A×C必有<a,c>∈A×B.其中c∈B.因此CB有〔1〔2得B=C4．試證明：若R與S是集合A上的自反關(guān)系.則R∩S也是集合A上的自反關(guān)系．若R與S是集合A上的自反關(guān)系.則任意x∈A,＜x,x＞∈R,＜x,x＞∈S,從而＜x,x＞∈R∩S,注意x是A的任意元素.所以R∩S也是集合A上的自反關(guān)系．姓名：姓名：學(xué)號：得分：教師簽名：離散數(shù)學(xué)作業(yè)5離散數(shù)學(xué)圖論部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次.內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí).基本上是按照考試的題型〔除單項選擇題外安排練習(xí)題目.目的是通過綜合性書面作業(yè).使同學(xué)自己檢驗學(xué)習(xí)成果.找出掌握的薄弱知識點.重點復(fù)習(xí).爭取盡快掌握。本次形考書面作業(yè)是第二次作業(yè).大家要認(rèn)真及時地完成圖論部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來.手工書寫答題.字跡工整.解答題要有解答過程.要求20XX12月5日前完成并上交任課教師〔不收電子稿。并在05任務(wù)界面下方點擊"保存"和"交卷"按鈕.以便教師評分。一、填空題1．已知圖G中有1個1度結(jié)點.2個2度結(jié)點.3個3度結(jié)點.4個4度結(jié)點.則G的邊數(shù)是15．2．設(shè)給定圖G<如右由圖所示>.則圖G的點割集是{f}．3．設(shè)G是一個圖.結(jié)點集合為V.邊集合為E.則G的結(jié)點度數(shù)之和等于邊數(shù)的兩倍．4．無向圖G存在歐拉回路.當(dāng)且僅當(dāng)G連通且等于出度．5．設(shè)G=<V.E>是具有n個結(jié)點的簡單圖.若在G中每一對結(jié)點度數(shù)之和大于等于n-1.則在G中存在一條漢密爾頓路．6．若圖G=<V,E>中具有一條漢密爾頓回路.則對于結(jié)點集V的每個非空子集S.在G中刪除S中的所有結(jié)點得到的連通分支數(shù)為W.則S中結(jié)點數(shù)|S|與W滿足的關(guān)系式為W<G-V1>V1．7．設(shè)完全圖K有n個結(jié)點<n2>.m條邊.當(dāng)n為奇數(shù)時.K中存在歐拉回路．8．結(jié)點數(shù)v與邊數(shù)e滿足e=v-1關(guān)系的無向連通圖就是樹．9．設(shè)圖G是有6個結(jié)點的連通圖.結(jié)點的總度數(shù)為18.則可從G中刪去4條邊后使之變成樹．10．設(shè)正則5叉樹的樹葉數(shù)為17.則分支數(shù)為i=5．二、判斷說明題〔判斷下列各題.并說明理由．1．如果圖G是無向圖.且其結(jié)點度數(shù)均為偶數(shù).則圖G存在一條歐拉回路．．<1>不正確.缺了一個條件.圖G應(yīng)該是連通圖.可以找出一個反例.比如圖G是一個有孤立結(jié)點的圖。2．如下圖所示的圖G存在一條歐拉回路．<2>不正確.圖中有奇數(shù)度結(jié)點.所以不存在是歐拉回路。3．如下圖所示的圖G不是歐拉圖而是漢密爾頓圖．GG解：正確因為圖中結(jié)點a.b.d.f的度數(shù)都為奇數(shù).所以不是歐拉圖。如果我們沿著<a,d,g,f,e,b,c,a>.這樣除起點和終點是a外.我們經(jīng)過每個點一次僅一次.所以存在一條漢密爾頓回路.是漢密爾頓圖4．設(shè)G是一個有7個結(jié)點16條邊的連通圖.則G為平面圖．解：<1>錯誤假設(shè)圖G是連通的平面圖.根據(jù)定理.結(jié)點數(shù)v.邊數(shù)為e.應(yīng)滿足e小于等于3v-6.但現(xiàn)在16小于等于3*7-6.顯示不成立。所以假設(shè)錯誤。5．設(shè)G是一個連通平面圖.且有6個結(jié)點11條邊.則G有7個面．<2>正確根據(jù)歐拉定理.有v-e+r=2.邊數(shù)v=11.結(jié)點數(shù)e=6.代入公式求出面數(shù)r=7三、計算題1．設(shè)G=<V.E>.V={v1.v2.v3.v4.v5}.E={<v1,v3>.<v2,v3>.<v2,v4>.<v3,v4>.<v3,v5>.<v4,v5>}.試<1>給出G的圖形表示；<2>寫出其鄰接矩陣；<3>求出每個結(jié)點的度數(shù)；<4>畫出其補(bǔ)圖的圖形．解：<1>v1v5v2v3v4<2>鄰接矩陣為<3>v1結(jié)點度數(shù)為1.v2結(jié)點度數(shù)為2.v3結(jié)點度數(shù)為3.v4結(jié)點度數(shù)為2.v5結(jié)點度數(shù)為2<4>補(bǔ)圖圖形為v1v5v2v3v42．圖G=<V,E>.其中V={a,b,c,d,e}.E={<a,b>,<a,c>,<a,e>,<b,d>,<b,e>,<c,e>,<c,d>,<d,e>}.對應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5.試〔1畫出G的圖形；〔2寫出G的鄰接矩陣；〔3求出G權(quán)最小的生成樹及其權(quán)值．〔1G的圖形如下：〔2寫出G的鄰接矩陣〔3G權(quán)最小的生成樹及其權(quán)值3．已知帶權(quán)圖G如右圖所示．<1>求圖G的最小生成樹；<2>計算該生成樹的權(quán)值．解：<1>最小生成樹為112357<2>該生成樹的權(quán)值為<1+2+3+5+7>=184．設(shè)有一組權(quán)為2,3,5,7,17,31.試畫出相應(yīng)的最優(yōu)二叉樹.計算該最優(yōu)二叉樹的權(quán)．335251071731173465權(quán)為2*5+3*5+5*4+7*3+17*2+31=131四、證明題1．設(shè)G是一個n階無向簡單圖.n是大于等于3的奇數(shù)．證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點個數(shù)相等．證明：設(shè).．則是由n階無向完全圖的邊刪去E所得到的．所以對于任意結(jié)點.u在G和中的度數(shù)之和等于u在中的度數(shù)．由于n是大于等于3的奇數(shù).從而的每個結(jié)點都是偶數(shù)度的〔度.于是若在G中是奇數(shù)度結(jié)點.則它在中也是奇數(shù)度結(jié)點．故圖G與它的補(bǔ)圖中的奇數(shù)度結(jié)點個數(shù)相等．2．設(shè)連通圖G有k個奇數(shù)度的結(jié)點.證明在圖G中至少要添加條邊才能使其成為歐拉圖．證明.任何圖中度數(shù)為奇數(shù)的結(jié)點必是偶數(shù).可知k是偶數(shù)．又根據(jù)定理4.1.1的推論.圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點．因此只要在每對奇數(shù)度結(jié)點之間各加一條邊.使圖G的所有結(jié)點的度數(shù)變?yōu)榕紨?shù).成為歐拉圖．故最少要加條邊到圖G才能使其成為歐拉圖．姓名：姓名：學(xué)號：得分：教師簽名：離散數(shù)學(xué)作業(yè)7離散數(shù)學(xué)數(shù)理邏輯部分形成性考核書面作業(yè)本課程形成性考核書面作業(yè)共3次.內(nèi)容主要分別是集合論部分、圖論部分、數(shù)理邏輯部分的綜合練習(xí).基本上是按照考試的題型〔除單項選擇題外安排練習(xí)題目.目的是通過綜合性書面作業(yè).使同學(xué)自己檢驗學(xué)習(xí)成果.找出掌握的薄弱知識點.重點復(fù)習(xí).爭取盡快掌握。本次形考書面作業(yè)是第三次作業(yè).大家要認(rèn)真及時地完成數(shù)理邏輯部分的綜合練習(xí)作業(yè)。要求：將此作業(yè)用A4紙打印出來.手工書寫答題.字跡工整.解答題要有解答過程.要求本學(xué)期第17周末前完成并上交任課教師〔不收電子稿。并在07任務(wù)界面下方點擊"保存"和"交卷"按鈕.以便教師評分。一、填空題1．命題公式的真值是1或T．2．設(shè)P：他生病了.Q：他出差了．R：我同意他不參加學(xué)習(xí).則命題"如果他生病或出差了.我就同意他不參加學(xué)習(xí)"符號化的結(jié)果為〔PQR．3．含有三個命題變項P.Q.R的命題公式PQ的主析取范式是<PQR><PQR>．4．設(shè)P<x>：x是人.Q<x>：x去上課.則命題"有人去上課．"可符號化為x<P<x>Q<x>>．5．設(shè)個體域D＝{a,b},那么謂詞公式消去量詞后的等值式為<A<a>A<b>><<B<a>B<b>>．6．設(shè)個體域D＝{1,2,3}.A<x>為"x大于3".則謂詞公式<x>A<x>的真值為0<F>．7．謂詞命題公式<x><<A<x>B<x>>C<y>>中的自由變元為y．8．謂詞命題公式<x><P<x>Q<x>R<x.y>>中的約束變元為x．三、公式翻譯題1．請將語句"今天是天晴"翻譯成命題公式．設(shè)P：今天是晴天。則P2．請將語句"小王去旅游.小李也去旅游．"翻譯成命題公式．設(shè)P：小王去旅游。Q：小李去旅游。則PQ3．請將語句"他去旅游.僅當(dāng)他有時間．"翻譯成命題公式．設(shè)P：他去旅游。Q：他有時間。則PQ4.將語句"41次列車下午五點開或者六點開"翻譯成命題公式。5．請將語句"有人不去工作"翻譯成謂詞公式．設(shè)A〔x：x是人B〔x：去工作x<A<x>B<x>>6．請將語句"所有人都努力工作．"翻譯成謂詞公式．設(shè)A〔x：x是人B〔x：努力工作x<A<x>B<x>>四、判斷說明題〔判斷下列各題.并說明理由．1．命題公式PP的真值是1．解：錯。因為P和P的否不能同時為真。2．<x><P<x>→Q<y>∧R<z>>中的約束變元為y．解：錯。<x><P<x>→Q<y>∧R<z>>中的約束變元為。3．謂詞公式中x量詞的轄域為．解：錯。因為緊接于量詞之后最小的子公式稱為量詞的轄域.所以x的轄域p<x,y>。4．下面的推理是否正確.請給予說明． <1><x>A<x>B<x>前提引入 <2>A<y>B<y>