離散數(shù)學(xué)習(xí)題解答

pqp→7p001111011010100101110001pqp→q0011111011011110010011100111110011所以公式((p→q)^(q→r))→(p→r)為永真式21、(1)解答：7(p^q)vr真值表如下：111101001111所以成假賦值為：011第二章5、(1)(2)(3)6、(1)(2)(3)7、(1)(2)8、(1)(2)所以00,10,11為成真賦值。所以011,111為成真賦值。排孤pIOM1所以000,001,010,011,100,101,110,111為成真賦的關(guān)系，所以公式的主合取范式為：7pv(7qvq)┐(7rvp)^p?qword資料14、在自然推理系統(tǒng)P中構(gòu)造下面推理的證明證明：①7(q?r)前提引入②1qvr①置換(4)前提：q→p,q.s,sit,t?r前提引入⑩U假言推理前提引入①化簡(jiǎn)前提引入②④假言推理前提引入15、在自然推理系統(tǒng)P中用附加前提法證明下面各推理：word資料證明：①S附加前提引入word資料②S→p前提引入④p→(q→r)前提引入⑦r⑤⑥假言推理(2)證明：附加前提引入①附加前提引入②③假言推理④化簡(jiǎn)⑤附加前提引入⑧u⑥⑦假言推理16、在自然推理系統(tǒng)P中用歸謬法證明下面推理：word資料②p→7q結(jié)論否定引入前提引入①②假言推理前提引入③④析取三段論前提引入⑥化簡(jiǎn)⑧為矛盾式，由歸謬法可知，推理正確。第5、在一階邏輯中將下列命題符號(hào)化：(1)火車(chē)都比輪船快。其中，F(xiàn)(x):x是火車(chē)，G(y):y是輪船，H(x,y):x比y快。(2)xy(F(x)^G(y)^H(x,y)),其中F(x):x是火車(chē)，G(y):y是汽車(chē)，H(x,y):x比y快。(3)不10、給定解釋I如下：(a)個(gè)體域D=N(N為自然數(shù))。上謂詞L(x,y):x=y。.xy((x+2=y)→(y+2=x)),真值為0。word資料11、判斷下列各式的類(lèi)型真，而后件永為假，即公式為(1→0)word資料word資料證明：①7.xG(x)前提引入前提引入②④假言推理⑤化簡(jiǎn)前提引入①置換前提引入③⑤析取三段論(4)前提：x(F(x)vG(y)),x(7G(x)vR(x)),xR(x)結(jié)論：證明：①xR(x)前提引入⑧F(c)⑤⑦析取三段論20、在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：word資料word資料證明：①7xF(x)附加前提③┐F(c)②-④x(F(x)vG(x))前提引入⑤F(c)vG(c)④-23、在自然推理系統(tǒng)F中，證明下面推理：(1)每個(gè)有理數(shù)都是實(shí)數(shù)，有的有理數(shù)是整數(shù)，因此有的實(shí)數(shù)是整數(shù)。word資料word資料(2)有理數(shù)、無(wú)理數(shù)都是實(shí)數(shù)，虛數(shù)不是實(shí)數(shù)，因此虛數(shù)既不是有F(x)^7G(x)))證明：①x((F(x)vG(x)→R(x))前提引入②F(y)vG(y))→R(y)①-③x(H(x)→R(x))⑤┐R(y)→┐(F(y)vG(y))②置換⑥H(y)→(F(y)vG(y))H(y)④⑤假言三段論⑦→(7F(y)^G(y))⑥置換word資料所以原式成立。=AN~(BUC)=A-(BUC)所以原式成立。41、設(shè)A、B、C為任意集合，證明：Aword資料word資料42、設(shè)A、B、C為任意集合，證明：AU因此x∈C綜45、設(shè)A、B為任意任意集合，證明：證明：(1)①先證P(A)NP(B)P(A∩B)所以xA^xB所以xANB所所以xA^xB因此P(A∩B)P(A)NP(B)綜上所述P(A∩B)=P(A)NP(B)顯然P(A)UP(B)=P(AUB)不成立.第七章20、25、32、36、38、40、41、42、48、49、5020、設(shè)R?的R?為A上的關(guān)系，證明：11word資料1R關(guān)系圖deC88t(R)關(guān)系圖32、對(duì)于給的A和R,判斷R是否為A上的等價(jià)關(guān)系。R不是A上的等價(jià)關(guān)系，因?yàn)镽不自反.(3)A=Z?,即正整數(shù)集，x,y∈A,xRyxy是奇數(shù)。36、設(shè)A={1,2,3,4},在A×A上定義二元關(guān)系R(1)證明R是A×A上的等價(jià)關(guān)系。(2)確定由R引起的對(duì)A×A的劃分。word資料word資料所以x+V=u+y再由R的定義知<<x,y>,<u,v>>∈R<u,v>,<x,y>,<s,t>∈A×A,若<<u,v>,<x,y>>∈R再根據(jù)R的定義知<<u,v>,<s,t>>∈R所以R具有傳遞性。綜上所述R為A×A上的等價(jià)關(guān)系。證明：①先證RAR1具有自反性所以<x,x>∈R,再由逆關(guān)系的定義知<x,x>∈R-1所以R具有對(duì)稱(chēng)性。x,y,z∈A,并且<x,y>,<y,z>∈RAR1所以<x,y>∈R并且<x,y>∈R1且<y,z>∈R并且<z,y>∈R由R的傳遞性知<x,z>∈R并且<z,x>∈R40、設(shè)R為N×N上的二元關(guān)系，<a,b>,<c,d>∈N×N(1)證明R為等價(jià)關(guān)系(2)求商集N×N/R證明：(1)①先證R具有自反性由R的定義知<a,b>R<a,b>②再證R具有對(duì)稱(chēng)性由R的定義知b=d再由R的定義知<c,d>R<a,b>③再證R具有傳遞性所以b=f再由R的定義知<a,b>R<e,f>所以R具有傳遞性綜上所述知R為N×N上的等價(jià)關(guān)系。(2)N×N/R={{<0,0>,<1,0>,<2,0>,<3,0>..41、設(shè)A={1,2,3,4},在A×A上定義二元關(guān)系R證明：(1)①先證R具有自反性A由于再根據(jù)R的定義知<<a,b>,<a,b>>∈R所以R具有自反性.②再證R具有對(duì)稱(chēng)性所以c+d=a+b再由R的定義知<<c,d>,<a,b>>∈R所以R具有對(duì)稱(chēng)性.并且<<c,d>,<e,f>>∈R則由R的定義知：a+b=c+d并且c+d=e+f再根據(jù)R的定義知<<a,b>,<e,f>>∈R綜上所述R為A×A上的等價(jià)關(guān)系。42、設(shè)R是A上的自反和傳遞關(guān)系，如下定義A上的關(guān)系T,使得證明：T是A上的等價(jià)關(guān)系。證明：①先證T具有自反性由于R是A上自反關(guān)系所以T具有自反性②再證T具有對(duì)稱(chēng)性即<y,x>∈R^<x,y>∈R所以T具有對(duì)稱(chēng)性③再證T具有傳遞性所以T具有傳遞性。48、設(shè)<A,R>和<B,S>為偏序集，在集合A×B上定義關(guān)系T如下：證明：T為A×B上的偏序關(guān)系證明：①先證T具有自反性所以a?∈A并且b?∈B由于R和S分別是A和B上的偏序關(guān)系，所以R和S具有自反性所以T具有自反性。②再證T具有反對(duì)稱(chēng)性由于R和S是偏序關(guān)系，所以R和S反對(duì)稱(chēng)<a?,b?>=<a?,b?>因此③再證T具有傳遞性49、設(shè)<A,R>為偏序集，在A上定義新的關(guān)系S如下：x,y∈AxSyxRy稱(chēng)S為R的對(duì)偶關(guān)系word資料(1)證明S也是A上的偏序關(guān)系。(2)如果R是整數(shù)集合上的小于或等于關(guān)系，那么S是什么關(guān)系?word資料如果R是正整數(shù)集合上的整除關(guān)系，那么S是什么關(guān)系?(3)偏序集<A,R>和<A,S>中的極大元、極小元、最大元、最小證明：(1)①先證S具有自反性由于R具有自反性，所以<x,x>∈R②再證S具有反對(duì)稱(chēng)性由S的定義知：<y,x>∈R并且<x,y>∈R由于R是偏序關(guān)系，所以R具有反對(duì)稱(chēng)性所以x=y③再證S具有傳遞性x,y,z∈A,若<x,y>∈S并且<y,z>∈S又因R為偏序關(guān)系，所以R具有傳遞性所以<z,x>∈R再由S的定義知：<x,z>∈S綜上所述S為A上的偏序關(guān)系。(2)如果R是整數(shù)集合上的小于或等于關(guān)系，那么S是A上的大于或等于關(guān)系。如果R是正整數(shù)集合上的整除關(guān)系，那么S是(3)偏序集<A,R>極大元是<A,S>中的極小元，偏序集<A,R>極小元是<A,S>中的極大元、偏序集<A,R>最大元是<A,S>中的最小元，偏序集<A,R>最小元是<A,S>中的最大第八章21、22、25、29、30、34、(1)說(shuō)明f是否為單射和滿(mǎn)射并說(shuō)明理由；(2)f的反函數(shù)是否存在，如果存在，求出f的反函數(shù)；(3)<X?,X?+1>=<X?,X?+1>根據(jù)有序?qū)ο嗟鹊母拍钪篨?=X?所以f為單射，但f不是滿(mǎn)射，因?yàn)?lt;0,0>ranf(2)f的反函數(shù)不存在22、設(shè)f:Z→Z,f(x)=(x)modn,在Z上定義等價(jià)關(guān)系R,證明：(1)先證f是單射所以x=u,y=v<u,v>∈R×R存在f<u+v,u-V>=<u,v>所以f為滿(mǎn)射綜上所述f為雙射。29、設(shè)A={a,b,c},B=2^,由定義證明：方法一：如下構(gòu)造雙射函數(shù)ff()=fo,f({a})=f?,f({f({a,b})=f4,f({a,c})=fs,f({b,c根據(jù)等勢(shì)定義有P(A)≈2A方法2證明：構(gòu)造函數(shù)f:P(A)→2A可以證明f為一一映射。word資料不論那種情況，則XA1,XA?至少有一個(gè)元素對(duì)應(yīng)不同。所以f為單射。②再證f為滿(mǎn)射φ∈2^,則為A到{0,1}的函數(shù)，構(gòu)造集合A?={x|x∈A^φx)=1}顯然所以f為滿(mǎn)射。所以f為一一映射，因此P(A)≈2^30、設(shè)[1,2]和[0,1]是實(shí)數(shù)區(qū)間，由定義證明[1,2]≈[0,1]證明：令f:[1,2]→[0,1],f(x)=x-1,而f為雙射函數(shù)(顯然成立)由于B≈D,所以存在一一映射g。構(gòu)造A×B到C×D函數(shù)φ:A×B→C×D顯然<f(x),g(y)>∈C×D,①先證φ為單射所以A×B≈C×D第九章4、11、15、164、判斷下列集合對(duì)所給的二元運(yùn)算是否封閉：(1)整數(shù)集合Z和普通的減法運(yùn)算(2)非零整數(shù)集合Z和普通的除法運(yùn)算(3)全體n×n實(shí)矩陣集合Mn(R)和矩陣加法及乘法運(yùn)算，其中n≥2(4)全體n×n實(shí)可逆矩陣集合關(guān)于矩陣加法和乘法運(yùn)算，其中n≥2(9)S={0,1},S關(guān)于普通的加法和乘法運(yùn)算。(10)S={x|x=2",n∈Z*},S關(guān)于普通的加法和乘法運(yùn)算。解：(1)封閉(2)不封閉(3)封閉(4)不封閉、封閉(5)不封閉(6)封閉(7)封閉(8)不封閉、封閉word資料如果能構(gòu)成代數(shù)系統(tǒng)則說(shuō)明*運(yùn)算是否滿(mǎn)足交換律、結(jié)合律，并求*運(yùn)算(1)x*y=gcd(x,y),gcd(x,y)是x與y的最大公約數(shù)。(2)x*y=大于等于x和y的最小整數(shù)。(4)x*y=質(zhì)數(shù)p的個(gè)數(shù)，其中x≤p≤y.解：(1)能構(gòu)成代數(shù)系統(tǒng)，且*運(yùn)算滿(mǎn)足交換律、結(jié)合律，*運(yùn)算不存在單位元，零元為1。(3)能構(gòu)成代數(shù)系統(tǒng)，且*運(yùn)算滿(mǎn)足交換律、結(jié)合律，*運(yùn)算的單位元為1,零元為10。14、下面各集合都是N的子集，它們能否構(gòu)成代數(shù)系統(tǒng)V=<N,+>的子代數(shù)：(1){x|x∈N^x可以被16整除}(3){x|x∈N^x是40的因子}個(gè)集合確定它是否構(gòu)成V的子代數(shù)，為什么?解：(1)S?不能構(gòu)成V的子代數(shù)，因?yàn)槌朔ǖ膯挝辉辉赟?中。(2)15、設(shè)G為群，若x∈G有x2=e,證明G為交換群所以a2=e,b2=e(ab)2=e,即(ab)(ab)=e所以a1=a,b1=b,ba=a1b1所以ba=ab,即ab=ba,因此G為交換群。word資料word資料18、證明偶數(shù)階群必含2階元證明：設(shè)偶數(shù)階下面按元素的階進(jìn)行劃分：①元素的階為1,只有單位元e,所以個(gè)數(shù)為1。②元素的階為2,設(shè)其構(gòu)成的集合為：A③元素的階大于2,設(shè)其構(gòu)成的集合為：B則B的個(gè)數(shù)一定為偶數(shù)。的元素成對(duì)出現(xiàn)。因此B的個(gè)數(shù)一word資料定為偶數(shù)?？山粨Q的元素構(gòu)成的集合，即N(a)={x|x∈G^xa=ax}證明：N(a)是G的子群在ya=ay兩邊分別乘以a-1,得ya-1=a-1y所以(xy?1)a=a(xy-1)由判定定理知N(a)是G的子群24、設(shè)H和K分別為群G的r,s階子群，若r和s互素，證明：證明：①由于H和K分別為群G的子群，顯然e∈HNK。而H和K的階分別為r,s,且r和s互素所以|<x>|為1,所以x=e,與假設(shè)矛盾。綜上所述HNK={e}27、設(shè)G?為循環(huán)群，f是群G?到G?的同態(tài)，證明f(G?)也是循環(huán)群。證word資料明：由于G?為循環(huán)群，不妨設(shè)G?=<a>,首先由定理群在同態(tài)映射下的像仍是群，word資料所以f(G?)是群。下面證明φ(G?)是是循環(huán)群則y=f(x)=f(a)=f(a)f(a)……f(a)=(f(a))這證明了f(a)為f(G?)的生成元。即f(G?)=<f(a)>所以f(G?)為循環(huán)群。28、設(shè)G=<a>是15階循環(huán)群。(1)求出G的所有的生成元。(2)求出G的所有子群。(2)G的所有子群：共4個(gè)子群121(1)計(jì)算σT,TO,σ1,r1,σ1Tσ(2)將OT,T1,σ1Tσ表成不交的輪換之積。解：(1)u12、對(duì)以下各小題給定的集合和運(yùn)算判斷它們是哪一類(lèi)代數(shù)系統(tǒng)(半群，,4,運(yùn)算為普通乘法。la;,aj∈S?,a;*aj=ai.這里的n是給定的正整數(shù)，且n≥2.(3)S?={0,1},*為普通乘法。(4)S?={1,2,3,6},x,y∈S?,xuy和x*y分別表示求最小公倍數(shù)和最大公約數(shù)運(yùn)算。解：(1)不是代數(shù)系統(tǒng)，對(duì)于乘法不封閉。(2)半群，運(yùn)算封閉，有結(jié)合律，沒(méi)有單位元。(3)半群與獨(dú)異點(diǎn)，乘法封閉，有結(jié)合律，單位元是1,但是0沒(méi)有(4)格與布爾代數(shù)。兩個(gè)運(yùn)算滿(mǎn)足交換、相互分配、同一律、補(bǔ)元(5)環(huán)與域，{0,1}關(guān)于模2加法構(gòu)成交換群、{1}關(guān)于模2乘法構(gòu)成交換群，模2乘法關(guān)于模2加法有分配律。word資料(1)化簡(jiǎn)f.(2)求f的對(duì)偶式f。word資料14、設(shè)B是布爾代數(shù)a,b∈B,證明：證明：①若a≤b所以a?b=a?(avb)=a?(a^b)因此a?b=0^b)=0所以avb=1dword資料易見(jiàn)結(jié)合律成立。由于a0(a所以0為單位元。word資料17、設(shè)B是布爾代數(shù)，a,b,c∈B,若a≤c,則有av(b?c)=(avb)^c稱(chēng)這個(gè)等式為模律，證明布爾代數(shù)適合模律。證明：a,b,c∈B,所以av(b?c)=(avb)^(avc)因此av(b?c)=(avb)^C第十四章6、16、25、29、44、45、50(2)n階非連通的簡(jiǎn)單圖的邊數(shù)最多可為多少?最少呢?n1得到(2)n階非連通的簡(jiǎn)單圖至少有2個(gè)連通分支，邊數(shù)最多的情況是由Kn-1和一個(gè)孤立點(diǎn)構(gòu)成，它的邊數(shù)為(n-1)(n-2)/2.邊數(shù)最少的非連通圖，當(dāng)然是n階零圖，邊數(shù)m=0,由n個(gè)孤立點(diǎn)構(gòu)成的圖16、畫(huà)出無(wú)向完全圖K?的所有非同構(gòu)的子圖，指出哪些是生成子圖，解：下面給出了K?的18個(gè)非同構(gòu)的子圖，其中有11個(gè)生成子圖mn123456Io2245oo30o4o0aa25、畫(huà)出5階3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖解：3條邊產(chǎn)生6度，分配給5個(gè)頂點(diǎn)，按簡(jiǎn)單圖度數(shù)的要求，有下面4種分配方案：在同構(gòu)意義下，每種方案對(duì)應(yīng)一個(gè)簡(jiǎn)單圖，4個(gè)非同構(gòu)的圖如下：29、設(shè)G是n階n+1條邊的無(wú)向圖，證明G中存在頂點(diǎn)v,使得d(v)≥3證明：用反證法，假若不然，v∈V(G),均有d(v)≤2,則由握手定理為邊數(shù)，顯然矛盾。所以結(jié)論成立。44、有向圖D如圖所示。求(1)D中V?到V?長(zhǎng)度為1,2,3,4的通路