離散數(shù)學習題與解答

./作業(yè)題與解答第一章19 、4>、6> 21 1、2>、3>19、2>解答: p→┐p→┐q真值表如下:pq┐p┐qp→┐pp→┐p→┐q001111011010100101110001.19、4>所以公式p→┐q→┐q為可滿足式.解答: p→q>→┐q→┐p>真值表如下:pq┐p┐qp→q┐q→┐pp→q→┐q→┐p>0011111011011110010011100111所以公式p→q→┐q→┐p為永真式.19、6解答: p→q∧q→r>>→p→r>真值表如下:pqrp→qq→rp→rp→q∧q→r>p→q∧q→r>>→p→r>0001111100111111010101010111111110001001101011011101000111111111所以公式p→q∧q→r>→<p→r為永真式21、1解答: ┐┐p∧q∨┐r真值表如下:pqr┐p┐r┐p∧q┐┐p∧q>┐┐p∧q∨┐r0001101100110011010111010111010010001011101000111100101111100011所以成假賦值為01.21、2>解答: ┐q∨r∧p→q真值表如下:pqr┐q┐q∨rp→q┐q∨r∧p→q>00011110011111010001001101111001100101110011000101110111所以成假賦值為010101011021、3解答: p→q∧┐<p∧r∨p真值表如下:pqrp→qp∧r┐p∧r>┐p∧r∨pp→q∧┐p∧r∨p>0001011100110111010101110111011110000110101010101101011111111011所以成假賦值為10011.第二章5、1>2>3> 6、1>2>3> 7、1>2> 8、1>2>3>5、求下列公式的主析取范式并求成真賦值1> ┐p→q→┐q∨p>┐┐p→q>∨<┐q∨p>┐┐┐p>∨q>∨┐q∨p>┐p∧┐q>∨┐q∨p>┐p∧┐q>∨p∧┐q∨p∧q>0∨m2∨3,所以00,10,1為成真賦值.2> <┐p→q∧q∧r>┐┐p∨q∧q∧r>p∨q∧q∧r>p∧q∧r∨q∧r>p∧q∧r∨p∧q∧r∨┐p∧q∧r>p∧q∧r∨┐p∧q∧r>3∨m7,所以01,1為成真賦值.3> p∨q∧r>→p∨q∨r>┐p∨q∧r>∨<p∨q∨r>┐p∧┐q∨┐r∨p∨q∨r>┐p∧┐q∨┐p∧┐r∨p∨q∨r>┐p∧┐q∨┐p∧┐r∨p∨q∨r>┐p∧┐q∨┐p∨p∨q∨r∧<┐r∨p∨q∨r>>┐p∧┐q∨1∧1>┐p∧┐q∨1.10∨1∨m2∨3∨4∨5∨m6∨m7,所以000,001,00,01,100,11,10,1為成真賦值.7、求下列公式的主析取范式,再用主析取范式求主合取范式1> p∧q∨r<p∧q∧r∨<p∧q∧┐r∨p∧r∨┐p∧r><p∧q∧r∨<p∧q∧┐r∨p∧r∧q∨p∧r∧┐q>∨┐p∧r∧q>∨┐p∧r∧┐q><p∧q∧r∨<p∧q∧┐r∨p∧┐q∧r∨┐p∧q∧r>∨┐p∧┐q∧r>1∨3∨5∨6∨7由主析取范式和主合取范式之間的關(guān)系,所以公式的主合取范式為：p∧q∨rM0∧M2∧M42><p→q>∧<q→r>┐p∨q∧┐q∨r>┐p∧┐q∨r∨q∧┐q∨r>┐p∧┐q∨┐p∧r∨<q∧┐q∨q∧r>┐p∧┐q∨<┐p∧r∨q∧r>┐p∧┐q∧┐r∨┐p∧┐q∧r>∨┐p∧q∧r>∨┐p∧┐q∧r>∨p∧q∧r∨┐p∧q∧r>┐p∧┐q∧┐r∨┐p∧┐q∧r>∨┐p∧q∧r>∨p∧q∧r>0∨1∨3∨7由主析取范式和主合取范式之間的關(guān)系,所以公式的.主合取范式為：<p→q>∧<q→r>M2∧M4∧M∧M68、求下列公式的主合取范式,再用主合取范式求主析取范式<1><p∧q>→q┐p∧q∨q┐p∨┐q∨q┐p∨┐q∨q>┐p∨11該公式無主合取范式,所以公式的主析取范式為：<p∧q>→q0∨1∨2∨3<2><pq>→r┐┐p∨q∧p∨┐q>∨rp∧┐q>∨┐p∧q∨rp∨┐p∧q>∧<┐q∨┐p∧q>∨rp∨┐p>∧<p∨q∧<┐∨┐p∧<┐q∨∨r<p∨q∧<┐q∨┐p∨r<p∨q∨r∧<┐p∨┐q∨r>M0∧M6由主合取范式和主析取范式之間的關(guān)系,所以公式的主析取范式為：<pq>→r1∨2∨3∨4∨5∨7<3>┐r→p∧p∧q┐┐r∨p∧p∧qr∧┐p∧p∧qr∧┐p∧p∧qr∧0∧q0.M0∧M1∧M2∧M3∧M∧M5∧M6∧M7該公式無主析取范式第三章14 2、4、5> 15 1、2> 16 1>14、在自然推理系統(tǒng)P中構(gòu)造下面推理的證明<2>前提：p→q,┐<q∧r>,r結(jié)論：┐p證明：①┐<q∧r> 前提引入②┐q∨┐r ①置換③r 前提引入④┐q ②③析取三段論⑤p→q 前提引入⑥┐p ④⑤拒取式〔4前提：q→p,q s,s t,t∧r結(jié)論：p∧q證明：①s t 前提引入②<s→t>∧<t→s> ①置換③t→s ②化簡④t∧r 前提引入⑤t ④化簡⑥s ③⑤假言推理⑦q s 前提引入.⑧<s→q>∧<q→s> ⑦置換⑨s→q ⑧化簡⑩q ⑥⑨假言推理q→p 前提引入p ⑩假言推理p∧q ⑩合取〔5前提：p→r,q→s,p∧q結(jié)論：r∧s證明:①p∧q 前提引入②p ①化簡③q ①化簡④p→r 前提引入⑤r ②④假言推理⑥q→s 前提引入⑦s ③⑥假言推理⑧r∧s ⑤⑦合取15、在自然推理系統(tǒng)P中用附加前提法證明下面各推理：<1>前提：p→<q→r>,s→p,q結(jié)論：s→r證明：①s 附加前提引入.②s→p 前提引入③p ①②假言推理④p→<q→r>前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理<2>前提：<p∨q>→<r∧s>,<s∨t>→u結(jié)論：p→u證明：①p 附加前提引入②p∨q ①附加③<p∨q>→<r∧s> 前提引入④r∧s ②③假言推理⑤s ④化簡⑥s∨t ⑤附加⑦<s∨t>→u 前提引入⑧u ⑥⑦假言推理16、在自然推理系統(tǒng)P中用歸謬法證明下面推理：<1>前提：p→┐q,┐r∨q,r∧┐s結(jié)論：┐p證明:.①p 結(jié)論否定引入②p→┐q 前提引入③┐q ①②假言推理④┐r∨q 前提引入⑤┐r ③④析取三段論⑥r(nóng)∧┐s 前提引入⑦r ⑥化簡⑧┐r∧r ⑤⑦合取<矛盾>⑧為矛盾式,由歸謬法可知,推理正確.第四章5、<1><2><3><4> 10、<2><4> 11、<2><6>5、在一階邏輯中將下列命題符號化：<1>火車都比輪船快.xy<F<x>∧G<y>→H<x,y>>,其中,F<x>：x是火車,G<y>：y是輪船,H<x,y>:x比y快.<2>有的火車比有的汽車快.xy<F<x>∧G<y>∧H<x,y>>,其中,F<x>:x是火車,G<y>：y是汽車,H<x,y>:x比y快.<3>不存在比所有火車都快的汽車.┐x<F<x>∧y<G<y>→H<x,y>>>.或x<F<x>→y<G<y>∧┐H<x,y>>>,其中,F<x>:x是汽車,G<y>：y是火車,H<x,y>:x比y快.<4>說凡是汽車就比火車慢是不對的.┐xy<F<x>∧G<y>→H<x,y>>或xy<F<x>∧G<y>∧┐H<x,y>>,其中,F<x>:x是汽車,G<y>：y是火車,H<x,y>:x比y慢.10、給定解釋I如下：〔a個體域D=N〔N為自然數(shù).〔bD中特定元素=2.〔cD上函數(shù)<x,y>=x＋y,<x,y>=x·y.D上謂詞<x,y>：x=y.<2>xy<F<f<x,a>,y>→F<f<y,a>,x>>xy<<x+2=y>→<y+2=x>>,真值為0.<4>xF<f<x,x>,g<x,x>>x<x+x=x·x>,真值為1.11、判斷下列各式的類型<2>x<F<x>→F<x>>→y<G<y>∧┐G<y>>>此謂詞公式前件永為真,而后件永為假,即公式為<1→0>.,此公式為矛盾式,所以原謂詞公式為矛盾式.<6>┐<xF<x>→yG<y>>∧yG<y>此謂詞公式是命題公式┐<p→q>∧q的代換實例而該命題公式是矛盾式,所以此謂詞公式是矛盾式.第五章 15<1><2><3><4> 20<1><2> 23<1><2>15、在自然推理系統(tǒng)F中構(gòu)造下面推理的證明：<1>前提:xF<x>→y<<F<y>∨G<y>>→R<y>>,xF<x>結(jié)論：xR<x>證明：①xF<x>→y<<F<y>∨G<y>>→R<y>><前提引入>②xF<x> <前提引入>③y<<F<y>∨G<y>>→R<y>> <①②假言言推理>④F<c> <②EI規(guī)則>⑤F<c>∨G<c>→R<c> <③UI規(guī)則⑥F<c>∨G<c> <④附加律>⑦R<c> <⑤⑥假言言推理>⑧xR<x> <⑦EG規(guī)則><2>前提：x<F<x>→<G<a>∧R<x>>>,xF<x>.結(jié)論：x<F<x>∧R<x>>證明：①xF<x> 前提引入②F<c> ①-③x<F<x>→<G<a>∧R<x>>> 前提引入④F<c>→<G<a>∧R<c>> ④-⑤G<a>∧R<c> ②④假言推理⑥R<c> ⑤化簡⑦F<c>∧R<c> ②⑥合?、鄕<F<x>∧R<x>> ⑥+<3>前提：x<F<x>∨G<x>>,┐xG<x>結(jié)論：xF<x>證明:①┐xx> 前提引入②x┐x> ①置換③┐c> ②-.④xx∨x>前提引入.⑤c∨c> ④-⑥c> ③⑤析取三段論⑦xx> ⑥+<4>前提:x<F<x>∨G<y>>,x<┐G<x>∨┐R<x>>,xR<x>結(jié)論：xF<x>.證明：①xR<x> 前提引入②R<c> ①-③x<┐G<x>∨┐R<x>> 前提引入④┐G<c>∨┐R<c> ③-⑤┐G<c> ②④析取三段論⑥x<F<x>∨G<y>> 前提引入⑦F<c>∨G<c> ⑥-⑧F<c> ⑤⑦析取三段論⑨xx> ⑧+20、在自然推理系統(tǒng)F中,構(gòu)造下面推理的證明：<可以使用附加前提證明法><1>前提：x<F<x>→G<x>>結(jié)論：xF<x>→xG<x>證明：①xF<x> 附加前提②F<y> ①-③x<F<x>→G<x>> 前提引入④F<y>→G<y> ③-.⑤G<y> ②④假言推理⑥xG<x> ⑤+<2> 前提：x<F<x>∨G<x>>結(jié)論：┐xF<x>→xG<x>證明：①┐xF<x> 附加前提②x┐F<x> ①等值演算③┐F<c> ②-④x<F<x>∨G<x>> 前提引入⑤F<c>∨G<c> ④-⑥G<c> ③⑤析取三段論⑦xG<x> ⑥+23、在自然推理系統(tǒng)F中,證明下面推理：<1>每個有理數(shù)都是實數(shù),有的有理數(shù)是整數(shù),因此有的實數(shù)是整數(shù).設F<x>:x為有理數(shù),R<x>:x為實數(shù),G<x>:x是整數(shù).前提：x<F<x>→R<x>>,x<F<x>∧G<x>>結(jié)論：x<R<x>∧G<x>>證明：①x<F<x>∧G<x>> 提引入②F<c>∧G<c> ①-③F<c> ②化簡.④G<c> ②化簡⑤x<F<x>→R<x>> 前提引入⑥F<c>→R<c> ⑤-⑦R<c> ③⑥假言推理⑧R<c>∧G<c> ④⑦合?、醲<R<x>∧G<x>> ⑧+<2>有理數(shù)、無理數(shù)都是實數(shù),虛數(shù)不是實數(shù),因此虛數(shù)既不是有理數(shù)、也不是無理數(shù).設：F<x>:x為有理數(shù),G<x>:x為無理數(shù),R<x>為實數(shù),H<x>為虛數(shù)前提：x<<F<x>∨G<x>>→R<x>>,x<H<x>→┐R<x>>結(jié)論：x<H<x>→<┐F<x>∧┐G<x>>>證明：①x<<F<x>∨G<x>→R<x>> 前提引入②F<y>∨G<y>>→R<y> ①-③x<H<x>→┐R<x>> 前提引入④H<y>→┐R<y>③-⑤⑥⑦⑧┐R<y>→┐<F<y>∨G<y>>H<y>→┐<F<y>∨G<y>>H<y>→<┐F<y>∧┐G<y>>x<H<x>→<┐F<x>∧┐G<x>>>②置換④⑤假言三段論⑥置換⑦+.第六章31,32、<1><2><3>,41,42,4531、設A、B為任意集合,證明：<A-B>∪<B-A>=<A∪B>-<A∩B>證明：由于<A-B>∪<B-A>=<A∩～B>∪<B∩～A>=<<A∩～B>∪B>∩<<A∩～B>∪～A>=<<A∪B>∩<～B∪B>>∩<<A∪～A>∩<～B∪～A>>=<A∪B>∩<～B∪～A>=<A∪B>∩～<B∩A>=<A∪B>∩～<A∩B>=<A∪B>-<A∩B>所以原式成立.32、設A、B、C為任意集合,證明：〔1<A-B>-C=A-<B∪C>證明：由于<A-B>-C=<A∩～B>∩～C=A∩<～B∩～C>=A∩～<B∪C>=A–<B∪C> 所以原式成立..〔2<A-B>-C=<A-C>-<B-C>證明：由于<A-C>-<B-C>=<A∩～C>∩～<B∩～C>=<A∩～C>∩<～B∪C>=<<A∩～C>∩～B>∪<<A∩～C>∩C>=<A∩～C>∩～B=<A∩～B>∩～C=<A-B>∩～C=<A-B>-C 所以原式成立.〔3<A-B>-C=<A-C>-B證明: 由于<A-B>-C=<A∩～B>∩～C=<A∩～C>∩～B=<A-C>-B所以原式成立.41、設A、B、C為任意集合,證明：A∩CB∩C∧A-CB-C AB證明：x∈A<1>若x∈C.所以x∈B∩C因此x∈B<2>若xC則x∈A-C,而A-CB-C所以x∈B-C因此x∈B綜上所述,AB42、設A、B、C為任意集合,證明：A∪B=A∪C ∧A∩B=A∩C B=C證明：<1>先證BCx∈B①若x∈A則x∈A∩B,而A∩B=A∩C所以x∈A∩C因此x∈C②若xA.所以x∈A∪C因此x∈C綜上所述知BC<2>再證CB 同理可證所以B=C45、設A、B為任意任意集合,證明：<1>P<A>∩P<B>=P<A∩B><2>P<A>∪P<B>P<A∪B><3>針對<2>舉一反例,說明P<A>∪P<B>=P<A∪B>對某些集合A和B是不成立的.證明：<1>①先證P<A>∩P<B>P<A∩B>x∈P<A>∩P<B>則x∈P<A> ∧x∈P<B>所以xA∧xB所以xA∩B所以x∈P<A∩B>因此P<A>∩P<B>P<A∩B>.x∈P<A∩B>則xA∩B所以xA∧xB所以x∈P<A> ∧x∈P<B>所以x∈P<A>∩P<B>因此P<A∩B>P<A>∩P<B>綜上所述P<A∩B>=P<A>∩P<B><2>x∈P<A>∪P<B>則x∈P<A> ∨x∈P<B>所以xA∨xB①若xA則xA∪B所以x∈P<A∪B>②若xB則xA∪B所以x∈P<A∪B>.<3>舉例：令A={1},B={2}則A∪B={1,2}則P<A>={,{1}},P<B>={,{2}}而P<A∪B>={,{1},{2},{1,2}}顯然P<A>∪P<B>=P<A∪B>不成立.第七章 20、25、32、36、38、40、41、42、48、49、5020、設R1的R2為A上的關(guān)系,證明:.2-1<1><R1∪R22-1=R1-∪R-1..-111<><R1∩-111=R1∩R2.-1證明:<1><x,y>∈<R1∪R2-1<y,x>∈R1∪R2<y,x>∈R1∨<y,x>∈R2.2<x,y>∈R12-1∨<x,y>∈R-1..-1-1<x,y>∈-1-1∪R2..-1-11所以<R1∪-1-11=R1∪R2.-1<2><x,y>∈<R1∩R2-1<y,x>∈R1∩R2.<y,x>∈R1∧<y,x>∈R2.2<x,y>∈R12-1∧<x,y>∈R-1..-1-1<x,y>∈-1-1∩R2..-1-11所以<R1∩-1-11=R1∩R2.25設R的關(guān)系圖如圖所示,試給出r<R>,s<R>,t<R>的關(guān)系圖a b d ecR系圖解：a b d ecR>關(guān)圖a b d ecR>關(guān)圖a b d ecR>關(guān)圖.32、對于給的A和R,判斷R是否為A上的等價關(guān)系.<1>A為為實數(shù)集,x,y∈A,xRy x-y=2.解:R不是A上的等價關(guān)系,因為R不自反.<2>A={1,2,3},x,y∈A,xRy x+y≠3解:R不是A上的等價關(guān)系,因為R不傳遞.<3>A=Z+,即正整數(shù)集,x,y∈A,xRy xy是奇數(shù).解:R不是A上的等價關(guān)系,因為R不自反.<4>A=P<X>,|X|≥2,x,y∈A,xRyxy∨yx解:R不是A上的等價關(guān)系,因為R不傳遞.<5>A=P<X>,CX,x,y∈A,xRyx⊕yC解:R是A上的等價關(guān)系.36、設A={1,2,3,4},在A×A上定義二元關(guān)系R<u,v>,<x,y>∈A×A,<u,v>R<x,y>u+y=x+v<1>證明R是A×A上的等價關(guān)系.<2>確定由R引起的對A×A的劃分.證明：<1>①先證R具有自反性<x,y>∈A×A.由于x+y=x+y再根據(jù)R的定義知<<x,y>,<x,y>>∈R所以R具有自反性.②再證R具有對稱性<u,v>,<x,y>∈A×A,若<<u,v>,<x,y>>∈R則由R的定義知：u+y=x+v所以x+v=u+y再由R的定義知<<x,y>,<u,v>>∈R所以R具有對稱性.③再證R具有傳遞性<u,v>,<x,y>,<s,t>∈A×A,若<<u,v>,<x,y>>∈R并且<<x,y>,<s,t>>∈R則由R的定義知：u+y=x+v并且x+t=s+y根據(jù)上述兩式知:u+t=s+v再根據(jù)R的定義知<<u,v>,<s,t>>∈R所以R具有傳遞性.綜上所述R為A×A上的等價關(guān)系..<2>A×A/R={{<1,4>},{<1,3>,<2,4>},{<1,2>,<2,3>,<3,4>},{<1,1>,<2,2>,<3,3>,<4,4>},{<2,1>,<3,2>,<4,3>},{<3,1>,<4,2>},{<4,1>}}38、設R為A上的自反和傳遞的關(guān)系,證明R∩R-1是A上的等價關(guān)系.證明：①先證R∩R-1具有自反性x∈A由于R為A上的自反關(guān)系所以<x,x>∈R,再由逆關(guān)系的定義知<x,x>∈R-1所以<x,x>∈R∩R-1因此R具有自反性.②再證R∩R-1具有對稱性<x,y>∈R∩R-1所以<x,y>∈R并且<x,y>∈R-1由逆關(guān)系的定義知<y,x>∈R-1并且<y,x>∈R所以<y,x>∈R-∩R即<y,x>∈R∩R-1所以R具有對稱性..③再證R具有有傳遞性x,y,z∈A,并且<x,y>,<y,z>∈R∩R-1所以<x,y>∈R并且<x,y>∈R-1并且<y,z>∈R并且<y,z>∈R-1所以<x,y>∈R并且<y,x>∈R并且<y,z>∈R并且<z,y>∈R由R的傳遞性知<x,z>∈R并且<z,x>∈R所以<x,z>∈R并且<x,z>∈R-1所以<x,z>∈R∩R-1所以R∩R-1具有傳遞性.綜上所述知R∩R-1為A上的等價關(guān)系.40、設R為N×N上的二元關(guān)系,<a,b>,<c,d>∈N×N<a,b>R<c,d>b=d<1>證明R為等價關(guān)系<2>求商集N×N/R證明：<1>①先證R具有自反性<a,b>∈N×N因為b=b.由R的定義知<a,b>R<a,b>所以R具有自反性.②再證R具有對稱性<a,b>,<c,d>∈N×N,若<a,b>R<c,d>由R的定義知b=d再由R的定義知<c,d>R<a,b>所以R具有對稱性.③再證R具有傳遞性<a,b>,<c,d>,<e,f>∈N×N,若<a,b>R<c,d>并且<c,d>R<e,f>由R的定義知b=d,d=f所以b=f再由R的定義知<a,b>R<e,f>所以R具有傳遞性綜上所述知R為N×N上的等價關(guān)系.<2>N×N/R={{<0,0>,<1,0>,<2,0>,<3,0>…},{<0,1>,<1,1>,<2,1>,<3,1>…},.{<0,2>,<1,2>,<2,2>,<3,2>…},…………………}41、設A={1,2,3,4},在A×A上定義二元關(guān)系R<a,b>,<c,d>∈A×A,<a,b>R<c,d>a+b=c+d<1>證明R為等價關(guān)系.<2>求R導出的劃分.證明：<1>①先證R具有自反性<a,b>∈A×A由于a+b=a+b再根據(jù)R的定義知<<a,b>,<a,b>>∈R所以R具有自反性.②再證R具有對稱性<a,b>,<c,d>∈A×A,若<<a,b>,<c,d>>∈R則由R的定義知：a+b=c+d所以c+d=a+b再由R的定義知<<c,d>,<a,b>>∈R所以R具有對稱性..<a,b>,<c,d>,<e,f>∈A×A,若<<a,b>,<c,d>>∈R并且<<c,d>,<e,f>>∈R則由R的定義知：a+b=c+d并且c+d=e+f根據(jù)上述兩式知:a+b=e+f再根據(jù)R的定義知<<a,b>,<e,f>>∈R所以R具有傳遞性.綜上所述R為A×A上的等價關(guān)系.<2>A×A/R={{<1,1>},{<2,1>,<1,2>},{<3,1>,<2,2>,<1,3>},{<4,1>,<3,2>,<2,3>,<1,4>},{<4,2>,<3,3>,<2,4>},{<4,3>,<3,4>},{<4,4>}}42、設R是A上的自反和傳遞關(guān)系,如下定義A上的關(guān)系T,使得x,y∈A <x,y>∈T<x,y>∈R∧<y,x>∈R證明：T是A上的等價關(guān)系.證明：①先證T具有自反性x∈A由于R是A上自反關(guān)系.即<x,x>∈R∧<x,x>∈R由T的定義知：<x,x>∈T所以T具有自反性②再證T具有對稱性x,y∈A,若<x,y>∈T由T的定義知：<x,y>∈R∧<y,x>∈R即<y,x>∈R∧<x,y>∈R再由T的定義知：<y,x>∈T所以T具有對稱性③再證T具有傳遞性x,y,z∈A,若<x,y>∈T∧<y,z>∈T由T的定義知：<x,y>∈R∧<y,x>∈R并且<y,z>∈R∧<z,y>∈R再由R具有傳遞性知:<x,z>∈R∧<z,x>∈R再根據(jù)T的定義知:<x,z>∈T所以T具有傳遞性..綜上所述知T為A上的等價關(guān)系.48、設<A,R>和<B,S>為偏序集,在集合A×B上定義關(guān)系T如下：<a1,b1>,<a2,b2∈A×B,<a1,b1>T<a2,b2>a1Ra2∧b1Sb2證明：T為A×B上的偏序關(guān)系證明：①先證T具有自反性<a1,b1>∈A×B所以a1∈A并且b1∈B由于R和S分別是A和B上的偏序關(guān)系,所以R和S具有自反性所以a1Ra1∧b1Sb1由T的定義知:<a1,b1>T<a1,b1>所以T具有自反性.②再證T具有反對稱性<a1,b1>,<a2,b2>∈A×B,若<a1,b1>T<a2,b2>并且<a2,b2>T<a1,b1>則由T的定義知:a1Ra2∧b1Sb2并且a2Ra1∧b2Sb1.由于R和S是偏序關(guān)系,所以R和S反對稱所以a1=a2并且b1=b2所以<a1,b1>=<a2,b2>因此T具有反對稱性.③再證T具有傳遞性<a1,b1>,<a2,b2>,<a3,b>∈A×B,若<a1,b1>T<a2,b2>并且<a2,b2>T<a3,b3>由T的定義知:a1Ra2∧b1Sb2并且a2Ra3∧b2Sb3由于R和S是偏序關(guān)系,所以R和S具有傳遞性所以a1Ra3∧b1Sb3再由T的定義知:<a1,b1>T<a3,b3>所以T具有傳遞性.綜上所述T為A上的偏序關(guān)系.49、設<A,R>為偏序集,在A上定義新的關(guān)系S如下：x,y∈A xSyxRy 稱S為R的對偶關(guān)系<1>證明S也是A上的偏序關(guān)系.<2>如果R是整數(shù)集合上的小于或等于關(guān)系,那么S是什么關(guān)系？.如果R是正整數(shù)集合上的整除關(guān)系,那么S是什么關(guān)系?<3>偏序集<A,R>和<A,S>中的極大元、極小元、最大元、最小元等之間有什么關(guān)系？證明：<1>①先證S具有自反性x∈A由于R具有自反性,所以<x,x>∈R由S的定義知：<x,x>∈S所以S具有自反性.②再證S具有反對稱性x,y∈A,若<x,y>∈S并且<y,x>∈S那么由S的定義知：<y,x>∈R并且<x,y>∈R由于R是偏序關(guān)系,所以R具有反對稱性所以x=y所以S具有反對稱性.③再證S具有傳遞性x,y,z∈A,若<x,y>∈S并且<y,z>∈S由S的定義知：<y,x>∈R并且<z,y>∈R.又因R為偏序關(guān)系,所以R具有傳遞性所以<z,x>∈R再由S的定義知：<x,z>∈S所以S具有傳遞性.綜上所述S為A上的偏序關(guān)系.<2>如果R是整數(shù)集合上的小于或等于關(guān)系,那么S是A上的大于或等于關(guān)系.如果R是正整數(shù)集合上的整除關(guān)系,那么S是正整數(shù)集合上的倍數(shù)關(guān)系.<3>偏序集<A,R>極大元是<A,S>中的極小元,偏序集<A,R>極小元是<A,S>中的極大元、偏序集<A,R>最大元是<A,S>中的最小元,偏序集<A,R>最小元是<A,S>中的最大元..第八章 21、22、25、29、30、34、3521、設f:N→N×N,f<x>=<x,x+1><1>說明f是否為單射和滿射并說明理由；<2>f的反函數(shù)是否存在,如果存在,求出f的反函數(shù)；<3>求ranf解:<1>f為單射,證明如下：x1,x2∈N,若f<x1>=f<x2>則<x1,x1+1>=<x2,x2+1>根據(jù)有序?qū)ο嗟鹊母拍钪簒1=x2所以f為單射,但f不是滿射,因為<00>ranf<2>f的反函數(shù)不存在<3>ranf={<n,n+1>|n∈N}22、設f:Z→Z,f<x>=<x>modn,在Z上定義等價關(guān)系R,x,y∈Z <xy>∈Rf<x>=f<y><1>計算f<Z>；<2>確定商集Z/R.解:<1>f<Z>={0,1,...,n-1}<2>Z/R={{nk+i|k∈Z}|i=0,1,...n-1}25、設f:R×R→R×R,f<<x,y>>=<<x+y>/2,<x-y>/2>證明f是雙射證明：〔1先證f是單射<x,y>,<u,v>∈R×R,若f<<x,y>>=f<<u,v>>則<<x+y>/2,<x-y>/2>=<<u+v>/2,<u-v>/2>所以<x+y>/2=<u+v>/2<x-y>/2=<u-v>/2所以x=u,y=v所以<x,y>=<u,v>所以f為單射〔2再證f是滿射<u,v>∈R×R存在<u+v,u-v>∈R×R且f<u+v,u-v>=<u,v>所以f為滿射綜上所述f為雙射..29、設A=ab,c}B=2A由定義證明A≈2A證明:方法一:A={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}.2A={f,ff,f,f,f,f,f}.0 1 23 4 5 6 7.0={<a,0>,<b,0>,<c,0>} f1={<a,1>,<b,0>,<c,0>}2={<a,0>,<b,1>,<c,0>} f3={<a,0>,<b,0>,<c,1>}4={<a,1>,<b,1>,<c,0>} f5={<a,1>,<b,0>,<c,1>}f6={<a,0>,<b,1>,<c,1>} f7={<a,1>,<b,1>,<c,1>}如下構(gòu)造雙射函數(shù)ff<>=f0,f<{a}>=f1,f<>=f2,f<{c}>=f3,f<{a,b}>=f4,f<{a,c}>=f5,f<{b,c}>=f6,f<{a,b,c}>=f7,根據(jù)等勢定義有A≈2A方法2證明：構(gòu)造函數(shù)f:P<A>→2AA1∈P<A>,f<A1>=x1可以證明f為一一映射.①先證f為單射.A1,A2 ,若A1≠A2則存在元素x,x∈A1,且xA2或者xA1,且x∈A2不論那種情況,則x1,x2至少有一個元素對應不同.所以1≠2所以f為單射.②再證f為滿射∈2A,則為A到{0,1}的函數(shù),構(gòu)造集合A3={x|x∈A∧<x>=1}顯然A3∈P<A>,且f<A3>=3=φ所以f為滿射.所以f為一一映射,因此P<A>≈2A30、設[1,2]和[0,1]是實數(shù)區(qū)間,由定義證明[1,2]≈[0,1]證明：令f:[1,2]→[0,1],f<x>=x-1,而f為雙射函數(shù)〔顯然成立所以[1,2]≈[0,1]34、設A、B、C、D是集合,且A≈C,B≈D,證明:A×B≈C×D證明:由于A≈C,所以存在一一映射f.由于B≈D,所以存在一一映射g..構(gòu)造A×B到C×D函數(shù)φ：A×B→C×D<x,y>∈A×B, φ<<x,y>>=<f<x>,g<y>>顯然<f<x>,g<y>>∈C×D,下面證明φ為雙射函數(shù)①先證φ為單射<x,y>,<u,v>∈A×B,若φ<<x,y>>=φ<<u,v>>即<f<x>,g<y>>=<f<u>,g<v>>所以f<x>=f<u>且g<y>=g<v>而f,g為一一映射,所以x=u且y=v所以<x,y>=<u,v>所以φ為單射②再證φ為滿射<s,t>∈C×D則s∈C,t∈D由于f,g是一一函數(shù),所以存在x∈A,y∈B,使得f<x>=s,g<y>=t顯然<x,y>∈A×B,且φ<<x,y>>=<s,t>所以φ為滿射.因此φ為雙射函數(shù).所以A×B≈C×D35、找出三個不同的N的真子集,使得它們都與N等勢解:A={2n|n∈N}={2n+1|n∈N}={2n|n∈N}則A,B,C是三個不同的N的真子集,且它們都與N等勢.第九章4、11、15、164、判斷下列集合對所給的二元運算是否封閉：<1>整數(shù)集合Z和普通的減法運算<2>非零整數(shù)集合Z*和普通的除法運算<3>全體n×n實矩陣集合Mn<R>和矩陣加法及乘法運算,其中n≥2<4>全體n×n實可逆矩陣集合關(guān)于矩陣加法和乘法運算,其中n≥2<5>正實數(shù)集合R+和運算,其中運算定義為：ａ,ｂ∈R+,a b=ab-a-b<6>n∈Z+,nZ={nz|z∈Z}.nZ關(guān)于普通的加法和乘法運算.<7>A={a1,a2,...,an},n≥2. 運算定義如下：ai,aj∈A,ai aj=ai.<8>S={2x-1|x∈Z+}關(guān)于普通的加法和乘法運算.<9>S={0,1},S關(guān)于普通的加法和乘法運算.<10>S={x|x=2n,n∈Z+},S關(guān)于普通的加法和乘法運算.解：<1>封閉<2>不封閉<3>封閉<4>不封閉、封閉<5>不封閉<6>封閉<7>封閉<8>不封閉、封閉<9>不封閉、封閉<10>不封閉、封閉.11、設S={1,2,...,10},問下面定義的運算能否與S構(gòu)成代數(shù)系統(tǒng)<S,*>?如果能構(gòu)成代數(shù)系統(tǒng)則說明*運算是否滿足交換律結(jié)合律并求*運算的單位元和零元.<1>x*y=gcd<x,y>,gcd<x,y>是x與y的最大公約數(shù).<2>x*y=lcm<x,y>,lcm<x,y>是x與y的最小公倍數(shù).<3>x*y=大于等于x和y的最小整數(shù).<4>x*y=質(zhì)數(shù)p的個數(shù),其中x≤p≤y.解：<1>能構(gòu)成代數(shù)系統(tǒng),且*運算滿足交換律、結(jié)合律,*運算不存在單位元,零元為1.<2>不能構(gòu)成代數(shù)系統(tǒng).<3>能構(gòu)成代數(shù)系統(tǒng),且*運算滿足交換律、結(jié)合律,*運算的單位元為1,零元為10.<4>不能構(gòu)成代數(shù)系統(tǒng).14、下面各集合都是N的子集,它們能否構(gòu)成代數(shù)系統(tǒng)V=<N,+>的子代數(shù)：<1>{x|x∈N∧x可以被16整除}<2>{x|x∈N∧x與8互質(zhì)}.<3>{x|x∈N∧x是40的因子}<4>{x|x∈N∧x是30的倍數(shù)}解：<1>是<2>不是<3>不是<4>是16、設V=<Z,+,·>,其中+和·分別代表普通加法和乘法,對下面給定的每個集合確定它是否構(gòu)成V的子代數(shù),為什么？<1>S1={2n|n∈Z}<2>S2={2n＋1|n∈Z}<3>S3={－1,0,1}解：<1>S1不能構(gòu)成V的子代數(shù),因為乘法的單位元不在S1中.<2>S2不能構(gòu)成V的子代數(shù),因為加法運算不封閉.<3>S3不能構(gòu)成V的子代數(shù),因為加法運算不封閉..第十章15、17、18、21、22、24、27、28、29.15、設G為群,若x∈G有x2=e,證明G為交換群證明：a,b∈G由條件x∈G有x2=e所以a2=e,b2=e<ab>2=e,即<ab><ab>=e所以a-1=a,b-1=b,ba=a-1b-1所以ba=ab,即ab=ba,因此G為交換群.17、設G為群,a,b,c∈G,證明：|abc|=|bca|=|cab|證明：設|abc|=r,|bca|=t,則<abc>r=e, <bca>t=e由于<abc>t=<abc><abc>……<abc>=a<bca><bca>……<bca>a-1=a<bca>ta-1=aea-1=aa-1=e由定理知：r|t又由于<bca>r=<bca><bca>……<bca>=a-1<abc><abc>……<abc>a.=a-1<abc>ra=a-1ea=a-1a=e由定理知：t|r綜上所述:r=t,即|abc|=|bca|同理可證：|bca|=|cab|所以|abc|=|bca|=|cab|18、證明偶數(shù)階群必含2階元證明：設偶數(shù)階群為G,不妨設|G|=2n下面按元素的階進行劃分：①元素的階為1,只有單位元e,所以個數(shù)為1.②元素的階為2,設其構(gòu)成的集合為：A③元素的階大于2,設其構(gòu)成的集合為：B則B的個數(shù)一定為偶數(shù).因為a∈G,若|a|﹥2則由定理知|a|=|a-1|,且a≠a-1所以階大于2的元素成對出現(xiàn).因此B的個數(shù)一定為偶數(shù).所以|G|=1+|A|+|B|,即|A|=|G|-1-|B|≥1,.所以偶數(shù)階群必含2階元.21、設G為群,a是G中給定元素,a的正規(guī)化子Na表示G中與a可交換的元素構(gòu)成的集合,即Na=x|x∈G∧aax}證明：Na是G的子群證明:1>a∈Na,所以Na非空<因為a∈G∧aa=a>2>xy∈Na>則xa=x yaay在ya=y兩邊分別乘以1得ya1=ay由于y1a=xy1a=xa1y>1=xya1>1=xay1>=xay1=axy1=axy1>所以y1a=axy1>由判定定理知Na是G的子群22、設H是群G的子群,x∈G,令xHx-1={xhx-1|h∈H},證明：xHx-1是G的子群,稱為H的共軛子群.證明：e是xHx-1中的元素,因此xHx-1非空.u,v∈xHx-1.則存在h,k∈H,使得u=xhx-1,v=xkx-1,則有uv-1=<xhx-><xkx-1>-1=<xhx-1<xk-1x1>=x<hk-1>x-1因為H為子群,hk-1屬于H,從而x<hk-1>x-1屬于xHx-1.即uv-1∈xHx-1由判定定理,所以xHx-1是G的子群.24、設H和K分別為群G的r,s階子群,若r和s互素,證明：H∩K={e}證明：①由于H和K分別為群G的子群,顯然e∈H∩K.②假若x∈H∩K,且x≠e則x∈H∧x∈K則<x>≤H,<x>≤K由拉格朗日定理知：|<x>|整除H和K的階.而H和K的階分別為r,s,且r和s互素所以|<x>|為1,所以x=e,與假設矛盾.綜上所述H∩K={e}27、設G1為循環(huán)群,f是群G1到G2的同態(tài),證明f<G>也是循環(huán)群.證明：由于G1為循環(huán)群,不妨設G1=<a>,首先由定理群在同態(tài)映射下的像仍是群,.所以f<G1>是群.下面證明φ<G1>是是循環(huán)群y∈f<G1>,x∈G1,使得f<x>=y.而G1=<a>所以存在r使得x=ar則y=f<x>=f<ar>=f<a>f<a>……f<a>=<f<a>>r這證明了f<a>為f<G1>的生成元.即f<G1>=<<a>>所以f<G1>為循環(huán)群.28、設G=<a>是15階循環(huán)群.<1>求出G的所有的生成元.<2>求出G的所有子群.解：<1>生成元為:a,a2,a4,a7,a,a11,a13,a14<2>G的所有子群:共4個子群<e>, <a3>={e,a3,a6,a9,a12}, <a5>={e,a5,a10}, G29、設σ,τ是5元置換,且.1232144512 3 43 4 51.<1>計算στ,τσ,σ-1,τ-1,σ-1τσ<2>將στ,τ1,σ-1τσ表成不交的輪換之積..<3>將<2>中的置換表示成對換之積,并說明哪些為奇置換,哪些為偶置換.解:<1><2><3>στ為奇置換,τ-1,σ-1τσ為偶置換..第十一章2、6、12、13、14、16、172、下列各集合對于整除關(guān)系都構(gòu)成偏序集,判斷哪些偏序集是格.<1>L={1,2,3,4,5}<2>L={1,2,3,6,12}<3>L={1,2,3,4,6,9,12,18,36}<4>L={1,2,22,...,2n},n∈Z+解：<1>不是格,因為{3,4}無上確界<2>、<3>、<4>都是格.6、設L是格,a,b,c∈L,且a≤b≤c,證明：a∨b=b∧c證明：由于L是格,a,b,c∈L,且a≤b≤c所以a∨b=b,b∧c=b因此a∨b=b∧c12、對以下各小題給定的集合和運算判斷它們是哪一類代數(shù)系統(tǒng)<半群,獨異點,群,環(huán),域,格,布爾代數(shù)>,并說明理由..1 1<1>S=1 11,2,21,3,31,4,運算為普通乘法.4 .<2>S2={a1,a2,...,an}, ai,aj∈S2,ai*aj=ai.這里的n是給定的正整數(shù),.且n≥2.<3>S3={0,1},*為普通乘法.<4>S4={1,2,3,6},x,y∈S4,x y和x*y分別表示求最小公倍數(shù)和最大公約數(shù)運算.<5>S5={0,1},*為模2加法, 為模2乘法.解：<1>不是代數(shù)系統(tǒng),對于乘法不封閉.<2>半群,運算封閉,有結(jié)合律,沒有單位元.<3>半群與獨異點,乘法封閉,有結(jié)合律,單位元是1,但是0沒有逆元.<4>格與布爾代數(shù).兩個運算滿足交換、相互分配、同一律、補元律.<5>環(huán)與域,{0,1}關(guān)于模2加法構(gòu)成交換群、{1}關(guān)于模2乘法構(gòu)成交換群,模2乘法關(guān)于模2加法有分配律.13、設B是布爾代數(shù),B中的表達式f是<a∧b>∨<a∧b∧c>∨<b∧c><1>化簡f.<2>求f的對偶式f*..解：<1>由于<a∧b>∨<a∧b∧c>∨<b∧c>=<a∧b>∨<b∧c>=<b∧a>∨<b∧c>=b∧<a∨c><2>f*=<a∨b>∧<b∨c>14、設B是布爾代數(shù),a,b∈B,證明：≤ba∧b’=0a’∨b=1證明：①若a≤b則a∨b=b所以a∧b’=a∧<a∨b>’=a∧<a’∧b’>=<a∧a’>∧b’=0∧b’=0因此a∧b’=0②若a∧b’=0兩邊分別求補元,即<a∧b’>’=0’所以a’∨b=1③若a’∨b=1則a=a∧1=a∧<a’∨b>=<a∧a’>∨<a∧b>=0∨<a∧b>=a∧b.所以a∧b=a由定理知a≤b16、設<B,∧,∨,＇,0,1>是布爾代數(shù),在B上定義二元運算,x,y∈B有xy=<x∧y＇>∨<x＇∧y>問<B,>能否構(gòu)成代數(shù)系統(tǒng)？如果能,指出是哪一種代數(shù)系統(tǒng).為什么？解：構(gòu)成群,運算封閉.a,b,c∈B<a>c<ab'><a'>c<ab'><a'>c'><ab'><a'>'><ab'c'><a'bc'><ab'>'<a'>'c><ab'c'><a'bc'><a'><a'>c><ab'c'><a'bc'><a'ac><a'b'>bac>bb'c><ab'c'><a'bc'>0<a'b'><abc>0<ab'c'><a'bc'><a'b'c><abc>同理有a>cab>a''>'b'>''>ab>易見結(jié)合律成立.由于a0<a0'><a'><a>0a所以0為單位元..由于aa<aa'><a'a>000所以a的逆元為a.因此<B,>能構(gòu)成群.17、設B是布爾代數(shù),a,b,c∈B,若a≤c,則有a∨<b∧c>=<a∨b>∧c稱這個等式為模律,證明布爾代數(shù)適合模律.證明：a,b,c∈B,若a≤c則a∨c=c所以a∨<b∧c>=<a∨b>∧<a∨c>=<a∨b>∧c因此a∨<b∧c>=<a∨b>∧c第十四章6、16、25、29、44、45、506、<1>設n階圖G中有m條邊,證明:<G>2m/n<G><2>n階非連通的簡單圖的邊數(shù)最多可為多少？最少呢？證明：<1>由G>