離散數(shù)學習題答案-2015

./離散數(shù)學習題答案習題一1、利用邏輯聯(lián)結詞把下列命題翻譯成符號邏輯形式他既是本片的編劇,又是導演 P∧Q銀行利率一降低,股價隨之上揚 P→Q盡管銀行利率降低,股價卻沒有上揚 P∧Q占據(jù)空間的、有質量而且不斷變化的對象稱為物質 M<S∧P∧T>他今天不是乘火車去北京,就是隨旅行團去了九寨溝 P▽Q小張身體單薄,但是極少生病,并且頭腦好使 P∧Q∧R不識廬山真面目,只緣身在此山中 P→Q〔解釋：因為身在此山中,所以不識廬山真面目兩個三角形相似,當且僅當他們的對應角相等或者對應邊成比例S<E∨T>如果一個整數(shù)能被6整除,那么它就能被2和3整除.如果一個整數(shù)能被3整除,那么它的各位數(shù)字之和也能被3整除解：設P–一個整數(shù)能被6整除 Q–一個整數(shù)能被2整除 R–一個整數(shù)能被3整除 S–一個整數(shù)各位數(shù)字之和能被3整除 翻譯為：〔P→〔Q∧R∧〔R→S2、判別下面各語句是否命題,如果是命題,說出它的真值〔1BASIC語言是最完美的程序設計語言 Y,T/F〔2這件事大概是小王干的 N〔3x2=64 N〔4可導的實函數(shù)都是連續(xù)函數(shù) Y,T/F〔5我們要發(fā)揚連續(xù)作戰(zhàn)的作風,再接再厲,爭取更大的勝利 N〔6客觀規(guī)律是不以人們意志為轉移的 Y,T〔7到2020年,中國的國民生產(chǎn)總值將趕上和超過美國 Y,N/A〔8凡事都有例外 Y,F3、構造下列公式的真值表,并由此判別哪些公式是永真式、矛盾式或可滿足式〔1〔P∨〔～P∧Q→Q解：PQ～P∧QP∨〔～P∧Q〔P∨〔～P∧Q→Q可滿足式00001011111001011011〔2~〔4表略：〔2可滿足式、〔3永真式、〔4可滿足式4、利用真值表方法驗證下列各式為永真式〔1~〔8略5、證明下列各等價式〔3P→〔Q∨R〔P→Q∨〔P→R證明：左式 ～P∨Q∨R～P∨Q∨～P∨R〔～P∨Q∨〔～P∨R〔P→Q∨〔P→R右式〔4〔P∧Q∨〔R∧Q∨〔R∧P〔P∨Q∧〔R∨Q∧〔R∨P證明：左式 <〔P∨R∧Q∨〔R∧P<〔P∨R∨R>>∧<〔P∨R∨P>>∧〔Q∨R∧〔Q∨P〔P∨Q∧〔R∨Q∧〔R∨P右式6、如果P∨QQ∨R,能否斷定PR？如果P∧QQ∧R,能否斷定PR？如果～P～R,能否斷定PR？解： 〔1如果P∨QQ∨R,不能判斷PR,因為如果Q=P∨R,那么P∨QP∨P∨RQ∨R,但P可以不等價于R. 〔2如果P∧QQ∧R,不能判斷PR,因為如果Q=P∧R,那么P∧QP∧P∧RQ∧R,但P可以不等價于R. 〔3如果～P～R,那么有PR,因為～P～R,則～P<->～R為永真式,及有P<->R為永真式,所以PR.8、把下列各式用↑等價表示出來〔1<P∧Q>∨～P解：原式 <<P↑Q>↑<P↑Q>>∨<P↑P><<<P↑Q>↑<P↑Q>>↑<<P↑Q>↑<P↑Q>>>↑<<P↑P>↑<P↑P>>9、證明：{～→}是最小功能完備集合證明: 因為{～,∨}是最小功能完備集合,所以,如果{～→}能表示出∨,則其是功能完備集合.由于P∨Q<～P>→Q,所以{～→}是功能完備集合.因為～→不能相互表示,所以{～→}是最小功能完備集合；同理可證：{非,條件非}也能將或表示出來：P∨Q～<～P!→Q>8、分別利用真值表法和等價變換法求下列公式的主合取范式及主析取范式:<3>P→<R∧<Q→P>>解：真值表法PQRQ→PR∧<Q→P>P→<R∧<Q→P>>000101001111010001011001100100101111110100111111所以：主合取范式為=<～P∨Q∨R>∧<～P∨～Q∨R>=M4∧M6主析取范式為=<～P∧～Q∧～R>∨<～P∧～Q∧R>∨<～P∧Q∧～R>∨<～P∧Q∧R>∨<P∧～Q∧R>∨<P∧Q∧R>=m0∨m1∨m2∨m3∨m5∨m7等價變換法〔略<4><P→<Q∧R>>∧<～P→<～Q∧～R>>解：真值表法PQRQ∧R～Q∧～RP→<Q∧R>～P→<～Q∧～R><P→<Q∧R>>∧<～P→<～Q∧～R>>0000111100100100010001000111010010001010101000101100001011110111所以：主合取范式為=<P∨Q∨～R>∧<P∨～Q∨R>∧<P∨～Q∨～R>∧<～P∨Q∨R>∧<～P∨Q∨～R>∧<～P∨～Q∨R>=M1∧M2∧M3∧M4∧M5∧M6主析取范式為=<～P∧～Q∧～R>∨<P∧Q∧R>=m0∨m7等價變換法〔略14、從A,B,C,D4個人中派2人出差,要求滿足下列條件：如果A去,則必須在C或D中選一人同去；B和C不能同時去；C和D不能同時去.用構造范式的方法決定選派方案.解：由題設A：A去,B：B去,C：C去,D：D去則滿足條件的選派應滿足如下范式：〔A→〔CD∧～〔B∧C∧～〔C∧D構造和以上范式等價的主析取范式〔A→〔CD∧～〔B∧C∧～〔C∧D〔～A∧～B∧～C∧D∨〔～A∧～B∧～C∧～D∨〔～A∧～B∧C∧～D∨〔～A∧B∧～C∧～D∨〔A∧～B∧C∧～D∨〔A∧～B∧～C∧D∨〔～A∧B∧～C∧D∨〔A∧B∧～C∧D共有八個極小項,但根據(jù)題意,需派兩人出差,所以,只有其中三項滿足要求：〔A∧～B∧C∧～D,〔A∧～B∧～C∧D,〔～A∧B∧～C∧D即有三種方案：A和C去或者A和D去或者B和D去.15、證明下列蘊含試：〔1P→Q=>P→<P∧Q>證明：P→Q～P∨QT∧<～P∨Q><～P∨P>∧<～P∨Q>～P∨<P∧Q>P→<P∧Q>所以,這是個等價式,因此也是個蘊含式〔2<P→Q>→Q=><P∨Q>證明：<P→Q>→Q～<～P∨Q>∨Q<P∧～Q>∨Q<P∨Q>∧<Q∨～Q><P∨Q>∧T<P∨Q>所以,這是個等價式,因此也是個蘊含式〔3P∧～P∧R=>S證明：P∧～P∧RF=>S<F可蘊含任何命題公式>〔4P=>Q∨R∨～R證明：P=>TQ∨R∨～R〔任何公式可蘊含永真式18、一個有錢人生前留下了一筆珍寶,藏在一個隱秘處.在他留下的遺囑中指出尋找珍寶的線索如下：如果藏寶的房子靠近池塘,那么珍寶不會藏在東廂房.如果房子的前院栽有大柏樹,那么珍寶就藏在東廂房.藏寶房子靠近池塘.要么前院栽有大柏樹,要么珍寶埋在花園正中地下.如果后院栽有香樟樹,珍寶藏在附近.請利用蘊含關系找出藏寶處解：根據(jù)給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據(jù)題意,得出：〔Q→～P∧〔R→P∧Q∧〔R∨S∧〔T→M？〔Q→～P∧〔R→P∧Q∧〔R∨S∧〔T→M～P∧〔R→P∧〔R∨S∧〔T→M～R∧〔R∨S∧〔T→MS∧〔T→MS即珍寶藏在花園正中地下20、演繹證明下面各蘊含式：〔4<R→Q>∧<R→S>,<Q→E>∧<S→B>,～<E∧B>,<P→R>～P證明：運用反證方法,將結論的非納入前提,證明步驟如下[1] P p<附加前提>[2] P→R p[3] R T[1,2]I[4] <R→Q>∧<R→S> p[5] Q∧S T[3,4]I[6] <Q→E>∧<S→B> p[7] E∧B T[5,6]I[8] ～<E∧B> p[9] F<矛盾式> T[7,8]E〔5P→<Q→R>,Q→<R→S>P→<Q→S>證明：運用cp法,將結論條件式的前件作為前提,證明步驟如下[1] P p<附加前提>[2] P→<Q→R> p[3] Q→R T[1,2]I[4] Q→<R→S> p[5] R→<Q→S> T[4]E[6] Q→S T[3,5]I[7] P→<Q→S> CP[1,6]21、把下列句子演繹成邏輯形式,并給出證明〔2某公司發(fā)生了一起盜竊案,經(jīng)仔細偵察,掌握了如下一些事實：被盜現(xiàn)場沒有留下任何痕跡失盜時,小花或則小英正在卡拉ok廳如果失竊時小胖正在附近,他就會習慣性地破門而入偷走東西后揚長而去如果失盜時小花正在卡拉ok廳唱歌,那么金剛是最大的嫌疑者如果失盜時小胖不在附近,那么他的女友小英會和他一起外出旅游如果失盜時小英正在卡拉ok廳唱歌,那么瘦子是最大的嫌疑者根據(jù)以上事實,請通過演繹推理找出偷竊者解：根據(jù)給定的條件有下述命題：P：現(xiàn)場無任何痕跡Q：失竊時,小花在OK廳R：失竊時,小英在OK廳S：失竊時,小胖在附近T：金剛是偷竊者M：瘦子是偷竊者則根據(jù)案情有如下命題公式：{P,Q∨R,S→～P,Q→T,～S→～R,R→M}PPS→～PP～ST①②I～S→～RP～RT③④IQ∨RPQT⑤⑥IQ→TPTT⑦⑧I即金剛是偷竊者23、利用消解法證明下列各蘊含式：〔3P→<Q→R>,Q→<R→S>P→<Q→S>證明： P→<Q→R>～P∨～Q∨R Q→<R→S>～Q∨～R∨S ～〔P→<Q→S>P∧Q∧～S因此子句集合={～P∨～Q∨R,～Q∨～R∨S,P,Q,～S}消解過程如下：[1] ～P∨～Q∨R p[2] P p[3] ～Q∨R 由[1,2]歸結[4] Q p[5] R 由[3,4]歸結[6] ～Q∨～R∨S p[7] ～S p[8] ～Q∨～R 由[6,7]歸結[9] ～R 由[4,8]歸結[10] FLASE□由[5,9]歸結 導出空子句習題二1、把下列謂詞翻譯成謂詞公式〔1每個有理數(shù)都是實數(shù),但是并非每個實數(shù)都是有理數(shù),有些實數(shù)是有理數(shù)解： R<x> -- x是實數(shù) Ra<x> -- x是有利數(shù)翻譯如下：<x><Ra<x>→R<x>>∧～<x><R<x>→Ra<x>>∧<x><R<x>>∧Ra<x>〔2直線a和b平行當切僅當a和b不相交解： A<x> -- x是直線 F<x,y> -- x與y平行 G〔x,y> -- ｘ與ｙ相交翻譯如下：<ａ><ｂ>〔A<ａ>∧A<ｂ>→<F<ａ,ｂ>～G〔ａ,ｂ>>〔3除非所有的會員都參加,這個活動才有意義解： A<x> -- ｘ是會員 B<x> -- x有意義ａ -- 這個活動 F<x,y> -- ｘ參加ｙ翻譯如下：B〔ａ→<x>〔A<x>→F<x,ａ>或～<x>〔A<x>→F<x,ａ>→～B〔ａ〔4任何正整數(shù)不是合數(shù)就是質數(shù)解： A<x> -- ｘ是正整數(shù) Ｂ<x> -- ｘ是合數(shù) Ｃ<x> -- ｘ是質數(shù)翻譯如下：<x>〔A<x>→Ｂ<x>Ｃ<x>凡是存錢的人都想有利息,如果沒有利息,人們就不會存錢解： A<x> -- ｘ是存錢的人F<x,y> -- ｘ想有ｙP -- 存錢沒有利息Q: -- 人們不存錢a: -- 利息翻譯如下：<x>〔A<x>→F<x,a>∧〔P→Q2、設論域D={0,1,2},把下列公式用不含量詞的公式表示出來〔3<x>[～P<x>]∨<x>Q<x>解：上式〔～P<0>∧～P<1>∧～P<2>∨Q<0>∨Q<1>∨Q<2>3、指出下列公式中的約束變元和自由變元,并確定公式的轄域解：略5、把下列語句符號化,并確定相應謂詞公式是永真式、可滿足式、還是矛盾式〔1如果兩個數(shù)的積等于0,那么至少其中一個數(shù)為0,數(shù)x-1不等于0,所以數(shù)x-1和x+1的積也不等于0解：設論域在任意數(shù)域集合,運用常規(guī)的數(shù)學符號,翻譯如下<x><y><xy=0→<x=0∨y=0>>∧<<x-1≠0>→<<x-1><x+1>≠0>>這是一個可滿足式,但不是永真式,因為存在x=-1時,謂詞公式不成立,但其它情況均成立,如果論域中不包含-1,為真,包含就不成立〔2誠實的人都講實話.小林不是誠實的,因而小林不講實話解： H<x> -- x誠實 T<x> -- x講真話 a -- 小林翻譯如下： 〔<x><H<x>→T<x>>∧～H<a>→～T<a>這是一個可滿足式,因為否定條件命題前件,不一定后件命題一定為假.及小林雖然不誠實,但也可能講實話6、對于題目給定的解釋,求下列各公式相應的真值〔1A=<x>[P<x>∨Q<x>]∧R<a>,解釋D={1,2,3},P<x>:x2+x=2;Q<x>:x是素數(shù)；R<x>:x<3;a=1解：根據(jù)解釋,A變?yōu)椤睵<1>∨Q<1>∧〔P<2>∨Q<2>∧〔P<3>∨Q<2>∧R<1>,根據(jù)P<x>,Q<x>,R<x>的定義,顯然P<1>∨Q<1>=1,P<2>∨Q<2>=1,P<3>∨Q<2>=1,R<1>=1,所以整個公式解釋為真〔2A=P<a,f<b>>∧P<b,f<a>>,B=<x><y>P<y,x>,C=<y><x>P<y,x>,E=<x><y>[P<x,y>→P<f<x>,f<y>>],解釋：D={2,3},a=3,b=2,f<2>=3,f<3>=2,P<2,2>=0,P<2,3>=0,P<3,2>=P<3,3>=1解：根據(jù)解釋,A變?yōu)镻<3,3>∧P<2,2>=1∧0=0, 真值為假 B變?yōu)?lt;P<2,2>∨P<2,3>>∧<P<3,2>∨P<3,3>>=〔0∨0∧〔1∨1=0, 真值為假 C變?yōu)?lt;P<2,2>∧P<2,3>>∨<P<3,2>∧P<3,3>>=〔0∧0∨〔1∧1=1, 真值為真 E變?yōu)?lt;P<2,2>→P<3,3>>∧<P<2,3>→P<3,2>>∧<P<3,2>→P<2,3>>∧<P<3,3>→P<2,2>>=〔0→1∧〔0→1∧〔1→0∧〔1→0=0, 真值為假7、設論域為整數(shù)集合Z,試判定下面各公式是否是永真式,矛盾式或可滿足式〔1<x>[x>-10∧x2≥0]答：為假命題〔2<x>[2x>8∧x2-6x+5≤0]答：為真命題,當4,5使?jié)M足謂詞公式〔3<x><y>[x+y=1024]答：為真命題,對任意整數(shù)x,y取值為1024-x及可〔4<y><x>[xy<10∨x+y≥2]答：為真命題,y=0及成立9、證明下列各式成立：〔1<x><y>[P<x>→Q<y>]<x>P<x>→<y>Q<y>證明：右式<x><y>[~P<x>∨Q<y>]<x>~P<x>∨<y>Q<y><x>P<x>→<y>Q<y>10、判別<x>[P<x>→Q<x>]<x>P<x>→<x>Q<x>是否成立,如果成立,請給出證明；如果不成立,找一個解釋予以說明解：<x>[P<x>→Q<x>]<x>[～P<x>∨Q<x>]<x>～P<x>∨<x>Q<x><x>P<x>→<x>Q<x>顯然和<x>P<x>→<x>Q<x>不等價,現(xiàn)構造如下解釋設論域為D={a,b},P<a>=0,P<b>=1,Q<a>=0,Q<b>=0,則<x>[P<x>→Q<x>]解釋為真,而<x>P<x>→<x>Q<x>解釋為假,所以不等價11、把下列公式化為等價的前束范式,再求出對應的SKolem范式〔4<x>[～P<x,0>→<<y>P<y,f<x>>∧<z>Q<x,z>>]解：原式<x>[P<x,0>∨<<y>P<y,f<x>>∧<z>Q<x,z>>]<x><y><z>[P<x,0>∨<P<y,f<x>>∧Q<x,z>>]其SKolem范式為：<x><z>[P<x,0>∨<P<g<x>,f<x>>∧Q<x,z>>]13、證明下列各式成立〔1<x><y>[P<x>∧Q<y>]<x>P<x>證明：左式<x>P<x>∧<y>Q<y><x>P<x>〔2~<<x>P<x>∧Q<a>><x>P<x>→~Q<a>證明：左式~<x>P<x>∨~Q<a><x>P<x>→~Q<a>15、下面給出了對<x>[P<x>∨Q<x>]<x>P<x>∨<x>Q<x>]的證明：〔原證明過程略試判斷這個證明是否正確.你能給出一個證明嗎？答：這個證明不正確,因為：如果PQ則~Q~P而~P~Q不一定成立,因此在這個證明過程中,第二步到第三步的蘊含不成立17、判別下面各個推理是否正確,如果不正確,指出錯在什么地方〔題目不再重復〔1答：不正確,全稱指定應該變?yōu)槠渌莤的變元,可修改為：P<y>→Q<x>〔2答：正確〔3答：不正確,全稱指定應該使用相同的個體常量,可修改為：P<a>∨Q<a>〔4答：題目不正確,存在量詞的指導變元應該是另外的變元符號〔5答：不正確,存在量詞的轄域應該包含全部的謂詞,可修改為：<x>[P<x>→Q<x>] 〔6答：不正確,對不同的個體常元應該用不同的變元進行存在指定,可修改為：<x>[P<x>→Q<b>]〔7答：不正確,推理過程中,應該先使用存在指定,然后使用全稱指定習題三4、仔細區(qū)分集合中的關系符號∈和,并判斷下列各蘊含關系的真假〔題目內容,見課本〔1真,根據(jù)子集的定義,任何屬于B集合的元素也屬于C集合〔2假,例如：A={1,2}B={{1,2},2,3}C=B,1屬于A,但并不是C集的元素〔3假,例如：A={1,2}B={1,2,3}C={{1,2,3}},A不是C的元素〔4假,例如：A={1,2}B={1,2,3}C={{1,2,3}},A不是C的子集〔5假,例如：A=1B={1,2,3}C={{1,2,3}},A不是C的元素〔6真,子集關系具有傳遞性9、證明下列各式〔1A∩<B-C>=<A∩B>-<A∩C>證明：左式=A∩<B∩~C>=<A∩B∩~C>∪<A∩B∩~A>=<A∩B>∩<~C∪~A>=<A∩B>∩~<A∩C>=<A∩B>-<A∩C>=右式〔2A-<B∪C>=<A-B>∩<A-C>證明：右式=<A∩~B>∩<A∩~C>=A∩~B∩~C=A∩~<B∪C>=A-<B∪C>=左式〔3<A-B>-C=A-<B∪C>=<A-C>-B證明：<A-B>-C=A∩~B∩~C=A∩~<B∪C>=A-<B∪C>=A∩~C∩~B=<A-C>-B〔4A∩<B∪C>=<A∩B>∪CCA證明：充分性∵A∩<B∪C>=<A∩B>∪C<A∩B>∪<A∩C>=<A∩B>∪C假設C不是A的子集,則C中必存在元素c在C中而不在A中,那么c一定不在等式的左端集合中,而一定在右端集合中,矛盾∴CA必要性∵CA,∴A∩C=C,等式兩端同時并上另一個集合,等式成立∴<A∩B>∪<A∩C>=<A∩B>∪CA∩<B∪C>=<A∩B>∪C〔5A∩<B⊕C>=<A∩B>⊕<A∩C>證明：左式=A∩〔B∪C-B∩C=A∩〔<B∪C>∩<~B∪~C>=A∩<B∪C>∩<~B∪~C>=AB~C+AC~B右式=〔<A∩B>∪<A∩C>-〔<A∩B>∩<A∩C>=〔A∩<B∪C>∩~〔A∩B∩C=A∩<B∪C>∩<~A∪~B∪~C>=AB~C+AC~B所以,左式=右式10、下面三式中,哪個可得出B=C的結論〔1A∪B=A∪C答：不能得出此結論,因為如果B≠C,但B,C都是A的子集,A∪B=A∪C成立〔2A∩B=A∩C答：不能得出此結論,因為B≠C,但A是C∩B子集,A∩B=A∩C成立A⊕B=A⊕C答：能,因為A⊕A=Φ,Φ⊕A=A⊕Φ=A,同時,〔A⊕B⊕C=A⊕〔B⊕C所以,已知等式兩端A⊕A⊕B=A⊕A⊕CΦ⊕B=Φ⊕CB=C16、求A={,a,}的冪集解：2A={,{},{a},{},{,a},{,},{a,},{17、設A,B是任意兩集合,證明〔12A2B2A證明：X2A2BX2AXXAXB =>XABX2A等號成立的條件:AB或BA<因為若A和B沒有子集關系,必有aA–B和bB–A,使{a,b}2AB,但{a,b}2A2〔22A2B=2A證明：X2A2BX2AXXAXBXABX2A附加題：證明等式<A⊕B>⊕C=A⊕<B⊕C>證明：A⊕<B⊕C>=A⊕<<B-C>∪<C-B>>=<A-<<B-C>∪<C-B>>>∪<<<B-C>∪<C-B>>-A> =~AB~C+~A~BC+A~B~C+ABC<A⊕B>⊕C=C⊕<A⊕B>那么按上式的劃簡方式,就是把C替換為A,把A替換為B,將B替換為C,所以C⊕<A⊕B>=~CA~B+~C~AB+C~A~B+CAB=~AB~C+~A~BC+A~B~C+ABC習題四1、設A={1,2,3,4},B={0,1,4,9,12}.分別把下面定義的從集合A到集合B的二元關系R用序偶的集合表示出來〔1xRyx|y解:R={<1,0>,<1,1>,<1,4>,<1,9>,<1,12>,<2,0>,<2,4>,<2,12>,<3,0>,<3,9>,<3,12>,<4,0>,<4,4>,<4,12>}〔2xRyxy<mod3>解:R={<1,1>,<1,4>,<3,0>,<3,9>,<3,12>,<4,1>,<4,4>}〔3xRyy/x∟<y-x>/2」解:R={<3,9>,<3,12>,<4,9>,<4,12>}2、用關系圖和關系矩陣表示第1題中的各個關系解：略6、設在整數(shù)集Z上定義如下二元關系,試填寫下表：解：填表如下R自反性反自反性對稱性反對稱性傳遞性x|y√×××√x≡y<modm>√×√×√xy>0××√×√xy≧0√×√××x=y或|x-y|=1√×√××x2>y2×√×√√因為x|x成立,所以自反性成立；所以反自反性不成立；因為x≠0時,x|0成立,但0|x不成立,所以對稱性不成立,因為1|-1,和-1|1成立,所以反對稱性不成立；但x|y,y|z成立,就一定有x|z成立,所以傳遞性成立因為模m相等是整數(shù)集合上的等價關系,所以具有自反、對稱、傳遞性因為00=0,所以自反性不成立；因為x≠0時必有xx>0,所以反自反性不成立；因為xy>0必有yx>0,所以對稱性成立；因此反對稱性不成立；因為xy>0,yz>0,能得到x,y,z同號且不為0,所以,xz>0,所以傳遞性成立因為xx≧0,所以自反性成立；因此,反自反性不成立；因為xy≧0,所以yx≧0,因此對稱性成立；因此,反對稱性不成立；因為-1*0≧0,0*1≧0,但-1*1<0,所以傳遞性不成立因為x=x,所以自反性成立；因此反自反性不成立；因為|x-y|=1,所以|y-x|=1,因此對稱性成立；所以反對稱性不成立；因為|1-2|=1,|2-3|=1,但|1-3|=2,所以傳遞性不成立因為xx=xx,所以自反性不成立；反自反性成立；因為x2>y2成立,那么y2>x2就不成立,所以對稱性不成立,反對稱性成立；傳遞性成立7、設R是集合A上的一個二元關系,合于xRy∧yRz=>~xRz,稱R是A上的一個反傳遞關系.試舉一個實際的反傳遞關系的例子解：例如在人群集合上,建立父子關系,那么就是一個反傳遞關系,因為如果甲是乙的父親,乙是丙的父親,那么甲和丙就一定不存在父子關系；另外,在正整數(shù)域上建立的倍數(shù)關系,也是一個反傳遞關系,因為如果a是b的2倍,b是c的2倍,那么a一定不是c的2倍8、設R和S都是集合A上的二元關系,它們經(jīng)過關系運算后得到A上的一個新關系.試判別當R和S同時具有下表左列某種指定性質時,經(jīng)過指定的運算后所得到新關系也仍保持這種性質,把所得結論以√,×的形式填在下表中相應的位置上R∩SR∪SR-SR○S-RR-1自反性√√×√×√反自反性√√√××√對稱性√√√×√√反對稱性√×√××√傳遞性√××××√自反性的保持情況說明：因為R,S都具有自反性,所以IAR,IAS,因此IAR∩S,IAR∪S,所以自反性在R∩S,R∪S上保持因為IAS,所以IA不是S補集的子集,因此也不是R∩-S的子集,所以自反性在R-S上不保持因為R,S是自反的,所以對任意的a∈A,〔a,a∈R,S,所以〔a,a∈R○S,因此自反性在R○S上保持因為〔a,a∈R,所以〔a,a不屬于-R,所以-R不具有自反性因為〔a,a∈R,所以〔a,a∈R-1,因此R-1具有自反性反自反性的保持情況說明：因為R,S都具有反自反性,等價于IA∩R=Φ,IA∩S=Φ因為IA∩R∩S=Φ,IA∩〔R∪S=Φ,所以R∩S,R∪S都是反自反的因為IA∩R∩-S=Φ,所以R-S也是自反的對于R○S,假設〔a,b∈R,〔b,a∈S,那么〔a,a∈R○S,所以反自反在R○S上不一定保持因為〔a,a不屬于R,所以〔a,a一定屬于-R,所以-R一定是自反的,一定不是反自反的因為〔a,a不屬于R,所以〔a,a也不屬于R-1,因此R-1一定是反自反的對稱性的保持情況說明：因為R,S是對稱的,所以R=R-1,S=S-1,-R=<-R>-1=-R-1,-S=<-S>-1=-S-1因為〔R∩S-1=R-1∩S-1=R∩S,所以R∩S具有對稱性因為〔R∪S-1=R-1∪S-1=R∪S,所以R∪S具有對稱性因為〔R-S-1=〔R∩-S-1=R-1∩〔-S-1=R-1∩-S-1=R∩-S,所以R-S具有對稱性因為<R○S>-1=S-1○R-1=S○R,但S○R通常情況下與R○S不相同,所以對稱性不一定保持,例如：R={<a,b>,<b,a>},S={<b,c>,<c,b>},則R○S={〔a,c},并不對稱因為〔-R-1=-R-1=-R,所以R的補是對稱的因為R逆的逆就是R,既等于R的逆,所以R的逆是對稱的反對稱性的保持情況說明：因為R,S是反對稱的,所以R∩R-1IAS∩S-1IA因為〔R∩S∩〔R∩S-1=〔R∩R-1∩〔S∩S-1IA,所以R∩S具有反對稱性因為如果R={<a,b>}S={<b,a>},都是反對稱的,但R∪S={<a,b>,<b,a>}是對稱的,所以R∪S不一定再保持對稱性因為R是反對稱的,而R-S在R的基礎上減少集合元素,因此也一定是反對稱的因為如果R={<a,b>,<c,a>},S={<b,c>,<a,a>},那么R○S={〔a,c,〔c,a},變?yōu)閷ΨQ的,所以反對稱性,在復合運算下不一定保持因為如果R={〔a,b,<c,c>}是反對稱的,但-R={〔a,a,<b,b>,<b,a>,<a,c,>,<c,a>,<b,c>,<c,b>},不是反對稱的,所以反對稱性在補集運算上不保持因為R∩R-1IA,有因為R=<R-1>-1,所以R-1是反對稱的傳遞性的保持情況說明：因為R,S是傳遞的,所以R2R,S2S因為〔R∩S2=〔R∩S○〔R∩SR2∩S2∩<R○S>∩<S○R>R∩S,所以傳遞性保持如果R={<a,b>},S={<b,c>},都是傳遞關系,但R∪S={<a,b>,<b,c>}不再是傳遞關系,所以傳遞性在R∪S上不一定保持如果R={<a,b>,<b,c>,<a,c>},S={<a,c>},分別是兩個傳遞關系,但R-S={<a,b>,<b,c>}不再是傳遞關系,所以傳遞性在R-S上不一定保持如果R={<a,b>,<c,d>},S={<b,c>,<d,e>},分別是兩個傳遞關系,但R○S={<a,c>,<c,e>}不再是傳遞關系,所以傳遞性在R○S上不一定保持如果A={a,b,c},R={<a,b>},那么–R=A×A–R,顯然不是傳遞的,所以傳遞性在-R上不一定保持因為R2R,所以〔R2-1R-1,即〔R-12R-1,所以傳遞性在逆運算下保持10、設R是集合A上的一個二元關系,證明〔1R是自反的IAR證明:R是自反的=>IAR因為,R是自反的,所以對任意的A中元素a,有〔a,a∈R,即IA中任意元素都屬于R,所以IARIAR=>R是自反的因為,對任意的A中元素a,有〔a,a∈IA,又IAR,所以〔a,a∈R,所以R是自反的綜上所述,R是自反的IAR〔2R是反自反的IA∩R=Φ證明：R是反自反的=>IA∩R=Φ因為,IA中的任意元素<a,a>,都不屬于R,所以IA∩R=ΦIA∩R=Φ=>R是反自反的因為IA∩R=Φ,所以IA中的任意元素<a,a>,都不屬于R,即對任意的A中元素a,有〔a,a∈IA,都不屬于R,所以R是反自反的綜上所述,R是反自反的IA∩R=Φ〔3R是對稱的R=R-1證明：R是對稱的=>R=R-1因為對R中的任意元素〔a,b,因為R是對稱的,所以〔b,a∈R,那么〔a,b∈R-1,所以RR-1因為對R-1中的任意元素〔a,b,那么〔b,a∈R,因為R是對稱的,那么〔a,b∈R,所以R-1R所以R=R-1R=R-1=>R是對稱的對R中的任意元素〔a,b,因為R=R-1,所以〔a,b也屬于R-1,所以〔b,a∈R,因此R是對稱的綜上所述,R是對稱的R=R-1〔4R是反對稱的R∩R-1IA證明:R是反對稱的=>R∩R-1IA因為對任意<a,b>∈R∩R-1,那么其就同時屬于R和R-1,那么〔b,a也屬于R,根據(jù)反對稱的定義,a=b,所以〔a,b∈IA,所以R∩R-1IAR∩R-1IA=>R是反對稱的假設R不是反對稱的,那么必定存在a≠b∧<a,b>∈R∧<b,a>∈R,那么〔a,b∈R∩R-1,但〔a,b不屬于IA,矛盾；因此R必是反對稱的綜上所述,R是反對稱的R∩R-1IAR是傳遞的R2R證明：R是傳遞的=>R2R因為對任意〔a,b∈R2,必存在c,使得〔a,c,<c,b>屬于R,因為R是傳遞的,所以<a,b>屬于R,因此R2RR2R=>R是傳遞的因為對任意的R中的元素〔a,b,<b,c>,那么<a,c>必定屬于R2,也就屬于R,所以R是傳遞的綜上所述,R是傳遞的R2R11、設A={1,2,3,4},定義A上的關系R={<a,b>|a=b+2},S={<x,y>|y=x+1∨x=2y}求：R.S,R.S-1.R,R2,<S-1>2解：根據(jù)題意,R={<3,1>,<4,2>},S={<4,2>,<1,2>,<2,3>,〔3,4}所以：R.S={〔3,2,〔4,3}S-1={〔2,4,〔2,1,〔3,2,〔4,3}所以：R.S-1={<4,4>,<4,1>} R.S-1.R={<4,2>} R2= <S-1>2 ={<2,3>,<3,4>,<3,1>,<4,2>}12、設A={a,b,c,d,e,f,g,h},A上的二元關系R對應的關系圖4-5所示,求使Rm=Rn的最小整數(shù)m和n<m<n>答：R=R16；簡要說明如下：本關系圖分為兩個部分,R=R1∪R2,因為R1.R2=R2.R1=,所以R2=R12∪R22,同理Rn=R1n∪R2n,又因為I1=R13,I2=R25；3,5的最小公倍數(shù)為15,所以I=R15,所以R=IoR15=RoR15=R1613、設R是集合A上的二元關系,證明：〔1IAn=IA證明：因為單位關系的關系矩陣為單位矩陣,而復合運算就是矩陣的乘法,根據(jù)單位矩陣的性質,IAn=IA〔2IAoR=RoIA=R證明：同上,因為單位矩陣左乘、右乘一個矩陣,結果不變；所以IAoR=RoIA=R〔3<R∪IA>n=IA∪R∪R2∪R3…∪Rn證明：根據(jù)書中并集關系復合的定理〔4.2,展開,并利用上述1,2的結論,及可得證〔嚴格可用歸納法15、寫出第12題中關系圖對應的關系矩陣,并利用warshall算法求這個關系的傳遞閉包解：習題五1、設A={<a,b>|a,bN},定義A上的一個二元關系R={<<a,b>,<c,d>>|ad=bc}證明：R是A上的等價關系證明：〔自反性因為對任意〔a,bA,都有：ab=ba,既<〔a,b,<a,b>>R,所以R是自反的〔對稱性如果〔〔a,b,<c,d>R,那么ad=bc,所以cb=ad,既〔〔c,d,<a,b>R,所以R是對稱的〔傳遞性如果〔〔a,b,<c,d>R,<<c,d>,<e,f>>R,那么ad=bc,cf=ed,因此,adcf=bced<注：如果0?N中>,那么af=eb,所以〔〔a,b,<e,f>R,R具有傳遞性綜上所證,R是A上的等價關系3、集合A={1,2,3,4}的一個分化為S0={{1,2,4},{3}},求由S0導出的A上的一個等價關系R解：等價關系R={1,2,4}×{1,2,4}∪{3}×{3}={〔1,1,〔2,2,〔4,4,〔1,2,〔1,4,〔2,1,〔2,4,〔4,1,<4,2>,<3,3>}4、試確定在4個元素的集合上可以定義的等價關系數(shù)目解：在此集合上可以確定的4分劃個數(shù)為：1在此集合上可以確定的3分劃個數(shù)為：c<4,2>=6在此集合上可以確定的2分劃個數(shù)為：c<4,1>+c<4,2>/2=7在此集合上可以確定的1分劃個數(shù)為：c<4,4>=1所以共可定義15個等價關系6、設R是非空集合A上的一個二元關系,具有對稱性和傳遞性.證明：如果對每一個xA,存在yA使xRy,那么,R是A上的等價關系證明：因為對每一個xA,存在yA使xRy,由于R是對稱的,所以yRx；又因為R是傳遞的,當xRy并且yRx,那么xRx.所以R是自反的.綜上所述,R是自反的,對稱的和傳遞的,因此R是A上的等價關系8、設A是由54的正因子構成的集合,"|"表示整除.畫出偏序集<A,|>對應的Hasse圖解：先求出偏序集,然后求處相應的cover,然后畫出Hasse圖A={1,2,3,6,9,18,27,54}COVER<|>={<1,2>,<1,3>,<2,6>,<3,6>,<3,9>,<6,18>,<9,18>,<9,27>,<18,54>,<27,54>}最大元：54最小元：1有4個包含元素最多的全序子集:L1={54,27,9,3,1}L1={54,18,9,3,1}L1={54,18,6,3,1}L1={54,18,6,2,1}18182639541279、設A={a,b,c},畫出偏序集合對應的Hasse圖.試比較本題與上題Hasse圖的異同解：{{a,b,c}{a,b}{a,c}{b,c}{a}{c}兩圖的相同點：都有最大〔小元不同點：最大線序一個為5,一個為411、設R是集合A上的一個等價關系.現(xiàn)在在等價類之間定義一個新關系S使得R的任何等價類[a]和[b]滿足[a]S[b]aRb,判別S是一個什么關系解:根據(jù)題目信息,猜測是等價關系,說明如下：因為對任意的aA,aRa成立〔R是A上的等價關系,是自反的,所以[a]S[a],S是自反的假設[a]S[b]成立,那么aRb；因為R是對稱的,所以bRa,因此[b]S[a]成立,所以S是對稱的假設[a]S[b],[b]S[c]成立,則aRb,bRc,因為R是傳遞的,所以aRc成立,因此[a]S[c]成立,所以S是傳遞的綜上所述,S是等價類集合上的等價關系習題六1、設A={1,2,3,4},B=A×A,確定下述集合是否為A到B的全函數(shù)或部分函數(shù)〔1{〔1,〔2,3,〔2,〔2,2,〔3,〔1,3,〔4,〔4,3}答：根據(jù)本書全函數(shù)的定義,這是從A到B的全函數(shù)〔2{〔1,〔1,2,〔1,〔2,3,〔3,〔2,4}}答：根據(jù)本書函數(shù)的定義,每個原像只能有一個像,所以此定義不是A到B的函數(shù)〔3{〔1,〔3,3,〔2,〔3,3,〔3,〔2,1,〔4,〔4,1}答：根據(jù)本書全函數(shù)的定義,這是從A到B的全函數(shù)2、判別以下關系中哪些是全函數(shù)〔1{〔n1,n2|n1,n2N,0<2n1-n2<5}答：此關系不滿足全函數(shù)的定義,因為〔3,5,〔3,4,〔3,3,〔3,2,〔3,1都屬于此關系,但它違反了本書函數(shù)是單值的定義〔2{〔n1,n2|n1,n2N,n1是n2的正因子個數(shù)}答：如果N集合中不包含0,那么此關系是全函數(shù),因為任意一個自然數(shù)按正因子個數(shù)的定義,都有確切的值,因此是全函數(shù)〔3{〔S1,S2|S1,S2?{a,b,c,d}且S1∩S2=}答：此關系不滿足全函數(shù)的定義,因為〔,{a},<,>等屬于此關系,但它違反了本書函數(shù)是單值的定義〔4{〔a,b|a,bN,gcd<a,b>=3}答：此關系不滿足全函數(shù)的定義,因為就1,2而言,3不是他們的因數(shù)；同時推論開,所有不是3的質數(shù),3都不是他們的因數(shù),因此他們就沒有像,所以不是全函數(shù)〔5{〔x,y|x,yZ,y=x2}答：此關系是全函數(shù),因為任意一個整數(shù),都能求到唯一的平方數(shù).所以按定義是全函數(shù)7、確定下列映射是否單射、滿射或雙射：f1:N→R,f1<n>=lnn答：如果0不屬于N,那么這是一個單射函數(shù),因為任意一個自然數(shù)都可以求其自然對數(shù),同時ln是單調函數(shù),所以是單射函數(shù).但是并非任意一個實數(shù)其原像都是自然數(shù),所以不是滿射f2:N→N,f2<n>為不超過n的素數(shù)數(shù)目答：這是一個滿射函數(shù),但不是單射.因為f<3>=f<4>=3,及不超過3,4的素數(shù)都是1,2,3,個數(shù)為3；同時因為自然數(shù)中的素數(shù)有無窮多,所以對任意一個自然數(shù)m,都能找到從第m個素數(shù)起到第m+1個素數(shù)〔但不包括第m+1個素數(shù)的所有自然數(shù),其函數(shù)值都等于m,所以是滿射,但不是單射〔注：7是第5個素數(shù),11是第6個素數(shù),所以f<7>=f<8>=f<9>=f<10>=5f3:N×N→N,f3<n1,n2>=<n1+1>n2答：這既不是單射,也不是滿射〔與0是否屬于N無關,以下說明以0不屬于N而言；因為任意兩個自然數(shù),都能求到此函數(shù)值,所以是全函數(shù).因為f<1,2>=f<3,1>=4,所以不是單射函數(shù)；同時1沒有原像,所以不是滿射函數(shù)f4：R→R,f4<x>=x2+2x-15答：一元二次函數(shù),既不是單射,也不是滿射；其幾何圖像為拋物線f5：Z→Z,f5<x>=1+2x3答：這是一個單射函數(shù),但不是滿射；因為3次曲線是單調函數(shù),所以在定義域子集范圍也是單調的,所以是單射函數(shù).但任意一個整數(shù)像的原像卻不一定是整數(shù).所以不是滿射A是集合,f6:2A×2A→2A×2A,f6<x,y>=<x答：假設A=,那么這是一個雙射函數(shù)〔請同學思考假設A不是空集,那么此函數(shù)既不是單射,也不是滿射；因為：對f<x,y>=f<y,x>,所以不是單射；另外對于〔,A,沒有原像；所以不是滿射f7:R×R→R,f7<x,y>=x+y,f8:R×R→R,f8<x,y>=xy答：此兩個函數(shù),都不是單射,但都是滿射函數(shù)8、設X是有限集合,f:X→X,證明：如果f是單射,f必是雙射證明：假設f不是滿射,那么就必定有元素沒有原像,由于X是有限集合,根據(jù)鴿蘢原理：原像元素個數(shù)〔鴿子就比像元素個數(shù)多〔鴿籠,所以必定有多個原像會映射到相同的像上,所以不是單射.矛盾.所以f必定是滿射,即是雙射如果f是滿射,f必是雙射證明：假設f不是單射,那么必定存在多個元素映射到相同的像上.由于X集合是有限的,那么因變量的個數(shù)就少于自變量個數(shù),因此f就不是滿射.與題設矛盾.因此f必是單射,既是雙射9、設f是有限集X上的一個函數(shù),滿足?xX,f2<x>=x；證明：f是雙射證明：因為f2<x>=f.f<x>=x,既是f2=Ix；所以f是自己的逆函數(shù),根據(jù)逆函數(shù)的性質,f必是雙射18、證明下列集合A和B等勢〔1A=<0,1>,B=<-2,2>證明：如果能找到從A到B的雙射函數(shù),就能說明A和B等勢,存在A到B上的這樣的函數(shù)；例如：f<x>=4x-2或f<x>=5x-3〔2A=<-∞,+∞>,B=<0,+∞>證明：如果能找到從A到B的雙射函數(shù),就能說明A和B等勢,存在A到B上的這樣的函數(shù)；例如：f<x>=ex〔3A=<0,1>,B=<1/4,1/2>證明：如果能找到從A到B的雙射函數(shù),就能說明A和B等勢,存在A到B上的這樣的函數(shù)；例如：f<x>=1/4x+1/4〔4A=N,B={<m,n>|m,nN∧m≤n}證明：如果將B集合寫成如下的分化并集形式：B=B1∪B2∪B3……,這樣B成為可數(shù)個集合的并集,其中Bi={〔i,i,<i,i+1>,<i,i+2>……},是一個可數(shù)集合,根據(jù)書中定理,可數(shù)個可數(shù)集合的并集合依然是可數(shù)集,那么就和N等勢,證畢習題八26、證明：在任何人數(shù)不少于2的人群中,至少有2個人在其中有同樣多的熟人證明：設人群人數(shù)為n〔≥,那么每個人有可能有的熟人數(shù)為〔0,1,…n-1n種情況,但是,當有人沒有熟人時,就不可能有人有n-1個熟人；同理,當有人認識其余的所有人時,就不存在有人沒有熟人,因此每個人可能有的熟人數(shù)只有n-1種.而一共有n個人,那么根據(jù)鴿籠原理,必存在至少有2個人在其中有同樣多的熟人的情況習題十1、設G是一個〔n,m簡單圖；證明：m≤C<n,2>等號成立,當且僅當G是完全圖證明：此題有兩個內容,第一方面證明簡單圖滿足m≤C<n,2>,第二證明,m=C<n,2>當且僅當G是完全圖<1>:因為在簡單無向圖中,每個結點的最大度數(shù)為n-1,所以圖的總度數(shù)的上限為n<n-1>,所以邊的上限為n<n-1>/2,因此任意一個簡單無像圖G,其邊數(shù)滿足：m≤n<n-1>/2=C<n,2><2>： m=C<n,2>?G是完全圖因為,當m=C<n,2>時,全圖的總度數(shù)為n<n-1>,因此其平均點度為<n-1>,因為n階簡單無向圖中點度的最大值為〔n-1,所以此時每個點的度數(shù)都相同并為〔n-1,根據(jù)完全圖的定義,此圖為完全圖 G是完全圖?m=C<n,2>當G為完全圖時,既每個結點都和其他結點相鄰,所以全圖的總邊數(shù)m=n<n-1>/2=C<n,2>4、證明：在〔n,m圖中δ≤2m/n≤Δ證明：因為2m/n代表簡單無向圖的平均點度值,所以平均值大于等于最小值,小于等于最大值,結論成立6、設G是〔n,m簡單二部圖,證明：m≤n2/4證明：設G的兩個頂點集合中頂點個數(shù)分別為n1,n2,并有n=n1+n2<1式>；同時,在簡單二部圖中,當其為完全二部圖是,其邊數(shù)最大,及max<m>=n1×n2<2式>；聯(lián)立〔1〔2式,通過高等數(shù)學的知識,當n1=n2=1/2n時,max<m>取得最大值n2/4,所以一般〔n,m簡單二部圖,其邊數(shù)小于等于此最大值既m≤n2/49、如果G≌G’,稱G是自補圖；確定一個圖為自補圖的最低條件：畫出一個自補圖解：因為G和自己的補圖同構,那么G和G’應該有相等條數(shù)的邊,所以m=m’,又因為m+m’=n<n-1>/2,所以G的邊的條數(shù)必須滿足m=n<n-1>/4.因此圖G的階數(shù)或階數(shù)減一必需是4的倍數(shù),這就是最低條件.圖略〔4階或5階這樣的圖都容易畫出10、判斷圖10-29中的兩個圖是否同構,并說明理由答：這兩個圖不同構,因為這兩個圖中,都有唯一的3度點,因此在同構映射中一定相互對應,但一個圖中的3度點連接兩個一度點,而在另一個圖中其3度點只連接了一個一度點,不能相互映射.因此不同構15、如果u和v是圖G中僅有的兩個奇數(shù)度結點,證明u和v必是連通的證明：假設u,v分別在圖G的兩個分中G1,G2中,那么G1,G2各自的總結點度數(shù)就是奇數(shù),與握手定理矛盾.因此,u,v必在一個連通分支中,所以是連通的16、證明：G是二部圖當且僅當G的回路都是偶長回路〔非平凡圖,n>1證明：〔1先證明在二部圖中,所有奇長道路的兩個端點必定分別在兩個頂點集合中使用歸納方法：A當?shù)缆烽L度L<P>=1時,就是圖G的邊和其兩個端點,根據(jù)二部圖的定義,兩個端點分別在兩個頂點集合中B假設道路長度L<P>=2n+1<n>0>時結論成立,及P=V1V2….V2n+2,其中V1,V2n+2分別屬于兩個頂點集合C>當L<P>=2<n+1>+1〔n>0時,P=V1V2….V2n+2V2n+3V2n+4；當我們刪除此道路的最后兩個結點,道路長度變?yōu)長<P’>=2n+1,根據(jù)<B>的假設,那么V1,V2n+2就分別在兩個頂點集合.現(xiàn)在把V2n+3加入到道路中,因為V2n+3是V2n+2的鄰結點,所以V2n+3在V2n+2的對集中,既和V1在一個頂點集合中；同理V2n+4就在V1的對集中,也就是V1,V2n+4在不同的頂點集合中綜上所述,〔1結論成立〔2G是二部圖?G的回路都是偶長的設C是G中的任意回路,那么C=V1…..V1,假設L<C>為奇數(shù),那么根據(jù)〔1的結論,V1,V1應該在不同的集合中,矛盾；所以L<C>必為偶數(shù)G的回路都是偶長的?G是二部圖首先,按如下方式對G的連通分支進行著色,任選一個結點,著紅色,然后將其所有鄰結點著為黑色,〔將紅色結點標記,然后逐一對黑色結點的鄰結點著為紅色并標記黑結點,如此往復,值到全部結點著色標記完成,或遇到已著色的結點被重新著色為相反的顏色〔此圖有奇長度回路.下面說明,如果是偶長的,那么就是二部圖：證明：從染色的順序看,紅點到黑點之間的距離為單數(shù),紅點到紅點的距離為雙數(shù),并且相同顏色的點不會相鄰.所以可以將圖的頂點集合分成兩個集合,每個集合的點的顏色一致.根據(jù)二部圖的定義,這是一個二部圖.如果著色過程中出現(xiàn)已著色點被重新著色成相反顏色,例如：v1是開始的紅點,如果現(xiàn)在有點為u1點為黑色,并且開始對他的鄰結點進行早色,我們發(fā)現(xiàn)w1是u1的鄰結點,但已經(jīng)被著色成黑色,那么,我們就找到得到v1到u1的距離為單數(shù)的道路p1,v1到w1距離為單數(shù)的道路p2,如果p1+u1w1+p1,就形成一個回路,此回路為奇數(shù),與前提矛盾.所以不可能出現(xiàn)這種情況.〔注:對其他分支重復這種方法,如果遇到孤立結點,則交替著紅色和黑色19、設G=<V,E>是點度均為偶數(shù)的連通圖,證明：對任何uV,ω<G-u>≤d<u>/2證明：因為G的點度都為偶數(shù),因此G-u最多形成d<u>個奇數(shù)度點,而奇數(shù)度點必須成對出現(xiàn)在連通分支中,所以ω<G-u>的最大值為d<u>/2,所以ω<G-u>≤d<u>/223、證明：在具有n<n≥2>個結點的簡單無向圖G中,至少有兩個結點度數(shù)相同證明：在n個結點的簡單無向圖中,每個結點的可能度數(shù)為0、1、2…n-1,共n種,但是如果有結點度為0,那么就不存在有結點度數(shù)為n-1；同理,有結點度數(shù)為n-1,那就不存在孤立結點,所以可能的點度只能有n-1種,但有n個結點,所以必有兩個結點度數(shù)要相同30、略習題十一1、設一個樹中度為k的結點數(shù)是nk<2≤k>,求它的葉的數(shù)目解：設T中葉結點數(shù)目為t,那么根據(jù)握手定理,及數(shù)的點邊關系可以得到：n=t+n2+n3+…+nk <1>Σd<v>=2m=t+2n2+3n3+…+knk=2<n-1><2>所以：t+2n2+3n3+…+knk=2〔t+n2+n3+…+nk-2t=n3+2n4+…+<k-2>nk+22、證明：樹T中最長簡單道路的起點和終點必都是T的葉證明:首先證明在T中的任意最長道路P中,其起點u和終點v的所有鄰結點必然在P中,否則此道路可以變長,與最長條件矛盾假設在T中存在最長道路P,其起點u或終點v不是葉結點<假設是u>,那么d<u>>1,及u至少有兩個鄰結點u1,u2,他們都將出現(xiàn)在道路中,既P=uu1…u2…v,因為u2是u的鄰結點,所以在T中就存在C=uu1..u2u的簡單回路,與樹的基本性質矛盾,所以u,v必是葉結點10、設e是連通圖G的一條邊,證明：e是G的割邊當且僅當e含于G的每個生成樹中證明：e是G的割邊?e含于G的每個生成樹中假設e不包含在G的生成樹T’中,那么刪除e邊后,T’依然包含在G-{e}中,因為T’連通,所以G-{e}連通,與e是割邊矛盾,所以e必包含在G的任何生成樹中e含于G的每個生成樹中?e是G的割邊假設e不是割邊,那么G-{e}依然連通,所以存在生成數(shù)T’,當然T’也是G的生成樹,但e不包含在T’中,與題設矛盾,因此e是G的割邊12、略23、略〔參考課堂ppt講解習題十二1、證明：圖12-7中的圖都是平面圖略〔只需要畫處其平面圖的形式即可3、設G是階數(shù)不小于11的圖,證明：G或G’<代表G的補圖>中至少有一個是非平面圖證明：假設G和G’都是平面圖,因為m<G>+m<G’>=n<n-1>/2,因此至少有一圖的邊至少為n<n-1>/4,根據(jù)平面圖邊與點的關系,n<n-1>/4≤3n–6,得到n1-13n+24≤0,因此n≤10,與題設矛盾；因此必有一圖為非平面圖5、證明：少于30條邊的簡單平面圖至少有一個頂點的度不大于4證明：少于30條邊的簡單平面圖所有的定點的度都大于等于5,那么根據(jù)握手定理和平面圖的性質有： 5n≤2m〔1m≤3n–6〔2?5n≤6n–12?n≥12 根據(jù)〔1式,60≤2m,既m≥30與題設矛盾,因此至少有一個頂點的度不大于47、證明：對K3,3的任意一條邊e,K3,3-e是平面圖；同樣,對K5的任何邊e,K5-e也是平面圖證明：因為K3,3的任意一條邊ei,ej,K3,3-ei,K3,3-ej都是同構的,而根據(jù)題1〔a的結論,我們可以平面嵌入它,因此K3,3-e是平面圖；同理,K5-e也是平面圖9、如果一平面圖于其對偶圖同購,則稱這個平面圖為自對偶圖,推導自對偶圖必須滿足的結點數(shù)n與邊數(shù)m的關系,并找出一些自對偶圖解：如果一個圖是平面圖,那么滿足歐拉公式：n–m+f=2〔1其對偶圖也是平面圖,因此也應滿足歐拉公式：n*-m*+f*=2<2>因為對偶關系,因此：n=f* f=n*又因為此二圖同構,因此 n=n*,m=m*所以： n=f,并且2n–m=2據(jù)此可以找到一些自對偶圖：K1,G<2,2>–有兩種圖像,K4習題十三1、構造<n,m>歐拉圖,使其滿足條件：〔1m,n奇偶性相同；〔2m,n奇偶性相反答：略2、設G=〔V,E是一個具有2k<k>0>個奇數(shù)度結點的連通圖.證明：G中必存在k條邊不相重的簡單道路P1,P2,…,Pk,使得E=E<P1>E<P2>…E<Pk>證明：把2k個奇數(shù)度結點分成兩兩一組的k組,然后每組結點新加一條邊,所得圖為歐拉圖,故存在歐拉回路C；然后去掉歐拉回路C中的k條新加入的邊,得到k條互無重復邊的道路P1,P2,…,Pk,即為所求5、在圖13-10中求中國郵遞員問題的解解：v9v9v6v3v1v2v4v5v7v8v1022111133v1134415562如上圖標號：圖中有4個奇數(shù)度結點v1,v6,v9,v3,求兩兩之間最短長度：Pv1v6=3<v1v6>,Pv1v9=7<v1v2v3v4v9>,Pv1v3=4<v1v2v3>,Pv6v9=7<v6v7v8v9>,Pv3v6=6<v3v8v7v6>,Pv3v9=3<v3v4v9>,Pv1v6和Pv3v9滿足最小性要求,復制v1v6和v3v4v9的邊,圖中歐拉回路即為所求解6、設G是有兩個奇數(shù)度點的連通圖,設計一個構造G的歐拉道路的算法解：此算法只要在書中歐拉回路的算法中,添加起點為奇數(shù)結點即可,詳細描述略9、證明：凡有割點的圖都不是哈密頓圖證明：假設e為圖G的割點,根據(jù)割點的定義,ω<G-e>>1,因此不滿足哈圖的必要條件；所以不是哈圖13、假定在n<≥2>個人的團體中,任何2人合起來認識其余的n-2個人,證明：〔1這n個人可以排成一排,使得站在中間的每個人的兩旁都是自己認識的人,站在兩端的人旁邊各有1個認識的人〔2當n≥4時,這n個人可以圍成一個圓圈,使得每個人兩旁都是自己所認識的人證明：如果團體中的個人看成是結點,而人于人的關系看成是邊,那么就構成一個認識與否的圖,對于問題〔1,就轉化為此圖中存在哈道路問題；問題〔2,就轉化為圖中存在哈圈的問題,現(xiàn)說明如下：在此題中,任何2人合起來認識其余的n-2個人蘊含任何人最多只有一人不認識,因為如果a,不認識b和c,那么b和c就不能認識完剩下的全部人,因此在圖既為d<u>≥n-2那么,任意兩個結點u,v,d<u>+d<v>≥n-2+n-2,因為n≥2,所以d<u>+d<v>≥n-1,根據(jù)書中定理,此圖存在哈道路如果n≥4,那么d<u>+d<v>≥n-2+n-2≥n,根據(jù)書中定理,此圖存在哈圈習題十四4、設S={a,b,c},運算"."由表14-2定義；判斷代數(shù)系統(tǒng)<S,.>是否為廣群,半群,含幺半群,群答：由運算表可知："?"封閉,所以是廣群；由表可知：x,yS,x?y=y,所以<x?y>?z=z,x?<y?z>=x?z=z,所以結合律成立,所以是半群；由表可知：a,b,c皆為左幺元,無右幺元,所以<S,?>是半群5、表14-3中所列運算定義在實數(shù)集合R上,請在下表的各欄上填上該運算是否具有指定性質+-×maxmin|x-y|封閉性√√√√√√結合性√×√√√×交換性√×√√√√存在幺元√×√×××存在零元××√×××每元有逆元√×××××答：+：是封閉的,有結合性,可交換,0為幺員,無零元,每個數(shù)的相反數(shù)為其逆元a,-a-:是封閉的,沒有結合性〔3-2-1≠3-〔2-1,不可交換3-2≠2-3,沒有幺〔不可交換,沒有零元,沒有逆元〔無幺×：是封閉的,有結合性,可交換,1為幺元,0為零元,0沒有逆元Max:是封閉的,max<max<a,b>,c>=max<a,max<b,c>>有結合性,max<a,b>=max<b,a>具有交換性,無幺元,無零元,無逆元Min：〔同上|x-y|:是封閉的,||5-3|-2|≠|5-|3-2||沒有結合性,|x-y|=|y-x|可交換,沒有幺|-1-0|≠-1,沒有零,沒有逆習題十五3、在實數(shù)集合R上定義二元運算"*"如下：?a,bR,a*b=a+b+ab；證明：〈R,*〉是含幺半群證明：因為定義運算中只包含初等運算+,×,所以是封閉的；因為對任意實數(shù)a,b,c,〔a*b*c=<a+b+ab>+c+<a+b+ab>c=a*<b*c>具有結合性；0是幺元,a*0=a+b+0.a=a=0*a所以是含幺半群〔注：-1沒有逆元,因此不是群4、設半群<A,?>中任何兩個不同元素關于運算"?"不可交換；證明：對任何aA,a?a=a證明：〔注：應該是非平凡半群,即元素個數(shù)≥2假設存在aA,a?a≠a,設a?a=b,那么<a?a>?a=b?a=a?<a?a>=a?b<運用半群的結合性>,所以a,b,可交換；與題設矛盾,假設不成立；因此原命題結論成立6、證明：群中只有幺元是冪等元證明：假設a是冪等元,那么對任意群中元素b,ba=baa,根據(jù)消去率,b=ba；同理ab=aab,所以b=ab,根據(jù)幺元的定義,a=e；既群中冪等元是幺元9、在整數(shù)集Z上用加法運算+和-定義新運算""如下：a,bZ,ab=a+b-2.證明:<Z,>是群證明：封閉性、結合性證明略.設幺元為e,ea=e+a-2=a,e=2.對a的逆b,有ab=2,即a+b-2=2,可見b=4-a綜上,<Z,>是群11、設<S,*>和<T,*>都是<G,*>的子群,,令ST={x|xSxT},ST={s*t|sStT}.<*可交換>；證明：<ST,*>和<ST,*>也都是<G,*>的子群證明：已知<S,*>和<T,*>都是<G,*>的子群,任取a,bST,所以a*b-1S,a*b-1T,即a*b-1ST,所以<ST,*>是<G,*>的子群對于<ST,*>,已知ST=TS,任取s1*t1,s2*t2ST,<s1*t1>*<s2*t2>-1=<s1*t1>*<t2-1*s2-1>=s1*t3*s2-1 =s1*s2-1*t3=s3*t3ST所以<ST,*>是<G,*>的子群16、證明：每個階數(shù)大于1的群必含有階數(shù)大于1的交換子群證明：因為群G的階數(shù)大于大于1,任取aG∧a≠e,構成S=<a>,那么S及為滿足要求的交換子群；因為<a>是循環(huán)群,所以是交換群,并且是G的子群e,a<a>∧a≠e,所以〔a的階數(shù)大于117、證明：循環(huán)群的子群必是循環(huán)群證明：設G的生成元為a,H為G的子群,并且H中具有最小正冪的元是ak,如果k=1,那么a就是子群的生成元,所以是循環(huán)子群如果k≠1,那么G=<a>,HG,H={e,ak,ak2,ak3,…},設ak是H中具有最小正指數(shù)的元,則amH,令m=tk+r<0r<k>,則am=<ak>tar,由k的選擇知,r=0,