離散數(shù)學(xué)及其應(yīng)用(課后習(xí)題)

(圓滿版)失散數(shù)學(xué)及其應(yīng)用(課后習(xí)題)(圓滿版)失散數(shù)學(xué)及其應(yīng)用(課后習(xí)題)(圓滿版)失散數(shù)學(xué)及其應(yīng)用(課后習(xí)題)習(xí)題指出以下命題是原子命題仍是復(fù)合命題?！?〕大雁北回，春季來了。4〕不是東風(fēng)壓倒西風(fēng)，就是西風(fēng)壓倒東風(fēng)。5〕張三和李四在吵嘴。解：〔3〕和〔4〕是復(fù)合命題，〔5〕是原子命題。習(xí)題指出以下命題的真值：〔1〕假定224，那么太陽從西方升起。解：該命題真值為T〔由于命題的前件為假〕?！?〕胎生動(dòng)物當(dāng)且僅當(dāng)是哺乳動(dòng)物。解：該命題真值為F〔如鴨嘴獸雖是哺乳動(dòng)物，但不是胎生動(dòng)物〕。令P：天氣好。Q：我去公園。請將以下命題符號(hào)化?！?〕只需天氣好，我就去公園?！?〕只有天氣好，我才去公園?！?〕天氣好，我去公園。解：〔2〕PQ?！?〕QP?！?〕PQ。習(xí)題2.將以下命題符號(hào)化〔句中括號(hào)內(nèi)提示的是相應(yīng)的原子命題的符號(hào)表示〕：1〕我去新華書店〔P〕，僅當(dāng)我有時(shí)間〔Q〕。3〕只需努力學(xué)習(xí)〔P〕，成績就會(huì)好的〔Q〕。6〕我今日進(jìn)城〔P〕，除非下雨〔Q〕。10〕人不犯我〔P〕，我不罪犯〔Q〕；人假定犯我，我必罪犯。解：〔1〕PQ?！?〕PQ?！?〕QP?！?0〕(PQ)(PQ)。習(xí)題寫出以下公式的真值表：〔2〕P(QR)。1解：該公式的真值表以下表：PQRQRP(QR)0001100111010000111110011101111100111111證明以低等價(jià)公式：〔2〕(PQ)(PQ)(PQ)。證明：(PQ)((PQ)(PQ))(PQ)(PQ))(PQ)(PQ)(PQ)(PQ)〔4〕(PQ)(PR)P(QR)。證明：(PQ)(PR)(PQ)(PR)P(QR)(QR)甲、乙、丙、丁4人參加考試后，有人問他們誰的成績最好，甲說，不是我。乙說：是丁。丙說：是乙。丁說：不是我。4個(gè)人的回復(fù)只有一個(gè)人符合實(shí)質(zhì)，問成績最好的是誰？解：設(shè)A：甲成績最好。B：乙成績最好。C：丙成績最好。D：丁成績最好。四個(gè)人所說的命題分別用P、Q、R、S表示，那么PA；QABCD；RABCD；SD。那么只有一人符合實(shí)質(zhì)的命題K符號(hào)化為K(PQRS)(PQRS)(PQRS)(PQRS)2PQRSA(ABCD)(ABCD)DA(ABCD)(ABCD)D(AD)(ABCD)(ABCD)(ABCD)(ABD)(ABCD)(ACD)0;同理，PQRSAABCD(ABCD)D0;PQRSA(ABCD)ABCDD0;PQRSA(ABCD)(ABCD)DA(ABCD)(ABCD)DAD.所以，當(dāng)K為真時(shí)，AD為真，即甲的成績最好。習(xí)題證明以下各包括式：〔3〕P(QR)(PQ)(PR)。證明：方法一：真值表法〔列出命題公式(P(QR))((PQ)(PR))的真值表〕。PQRPQ

PRQRP(QR)(PQ)(PR)(P(QR))((PQ)(PR))0001111110011111110101101110111111111000011111010111111101000011111111113方法二：等值演算法(P(QR))((PQ)(PR))(P(QR))((PQ)(PR))(P(QR))(PQ)(PR)(PQR)(PQ)(PR)(PQR)((PPR)(QPR))(PQR)(QPR)(PQPR)(QQPR)(RQPR)1.方法三：分析法〔1〕直接分析法：假定前件P(QR)為真，分兩種狀況：〔I〕P為假，那么PQ為真，PR為真，(PQ)(PR)為真?！睮I〕P為真，那么QR為真，此時(shí)假定Q為真，那么R為真，那么PQ為真，PR為真，(PQ)(PR)為真；假定Q為假，那么PR為假，(PQ)(PR)為真。綜上，假定前件為真，后件必為真，故該包括式建立。(2〕間接分析法：假定后件(PQ)(PR)為假，那么PQ為真，PR為假。由PR為假可知，P為真，R為假。再由PQ可知，Q為真。此時(shí)QR為假，(QR)為假，即前件為假。故包括式建立。表達(dá)以下各個(gè)命題的逆換式和逆反式，并以符號(hào)寫出?！?〕假以下雨，我不去。解：設(shè)P：天下雨。Q：我去。逆換式：假如我不去，天就下雨。符號(hào)表示為QP。逆反式：假如我去，天就不下雨。符號(hào)表示為QP。〔2〕僅當(dāng)你走我將留下。解：設(shè)P：我留下。Q：你走。逆換式：假如你走，我就留下。符號(hào)表示為：QP。逆反式：假如你不走，我就不留下。符號(hào)表示為：QP。4習(xí)題2.將以下命題公式用只含和的等價(jià)式表達(dá)，并要求盡可能簡單。〔1〕(PQ)P.解：(PQ)P(PP)Q0Q0.〔2〕(P(QR))PQ.解：(P(QR))PQ(P(QR))PQ(PQR)PQ(PPQ)(PQQ)(PQR)(PQ)(PQ)(PQR)(PQ)(PQR)(PQ)(PQR)PQ(PQ).〔3〕PQ(RP).解：PQ(RP)PQ(RP)(PQR)(PQP)(PQR)0PQR(PQR).習(xí)題6．求以下命題公式的主析取范式和主合取范式：〔1〕((PQ)R)P.解：((PQ)R)P((PQ)R)P((PQ)R)P(PQP)(PR)(PQ)(PR)(PQ(RR))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)M0M1M3〔主合取范式〕m2m4m5m6m7.〔主析取范式〕5習(xí)題1.證明(PQ)(PR)(RS)SQ.證明：〔1〕SP〔附帶前提〕〔2〕RSP〔3〕SRT〔2〕E〔4〕RT〔1〕〔3〕I〔5〕PRP〔6〕RPT〔5〕E〔7〕PT〔4〕〔6〕I〔8〕PQP〔9〕QT〔7〕〔8〕I〔10〕SQCP2．用間接證法證明P(QR)，QP，SR，PS.證明：〔1〕SP〔附帶前提〕〔2〕SRP〔3〕RT〔1〕〔2〕I〔4〕PP(5)P(QR)P(6)QRT(4)((5)I(7)QT(3)(6)I(8)QPP(9)PT(7)(8)I(10)PP(矛盾式)T(4)(9)I由〔10〕得出了矛盾，依據(jù)歸謬法說明原推理正確。5.“假以下雨，春游就會(huì)更期；假如沒有球賽，春游就不會(huì)更期。結(jié)果沒有球賽，所以沒有下雨。〞證明上述論斷正確。解：設(shè)P：下雨。Q：有球賽。R：春游更期。那么上述論斷轉(zhuǎn)變?yōu)橐C明PR，QR，P.證：〔1〕QP〔2〕QRP6〔3〕RT〔1〕〔2〕I〔4〕PRP〔5〕PT〔3〕〔4〕I所以，上述推理正確。7.證明RS是前提CD，CR，DS的有效結(jié)論。證明：〔1〕CDP〔2〕CDT〔1〕E〔3〕DSP〔4〕CST〔2〕〔3〕I〔5〕CRP〔6〕RCT〔5〕E〔7〕RST〔4〕〔6〕I〔8〕RST〔7〕E習(xí)題用謂詞表達(dá)式寫出以下命題：〔5〕每個(gè)有理數(shù)是實(shí)數(shù)。解：x(Q(x)R(x))，此中Q(x)：x是有理數(shù)。R(x)：x是實(shí)數(shù)?！?〕有的函數(shù)連續(xù)。解：x(F(x)C(x))，此中F(x)：x是函數(shù)。C(x)：x連續(xù)。習(xí)題將以下命題符號(hào)化：〔3〕沒有人登上過木星。解：設(shè)M(x)：x是人。A(x)：x登上過木星。那么命題可表示為(x)M(x)A(x).符號(hào)化以下命題：〔2〕只管有人聰慧，但未必全部人都聰慧。解：設(shè)M(x)：x是人。C(x)：x聰慧。那么命題可表示為x(M(x)C(x))x(M(x)C(x)).習(xí)題對以下謂詞公式中拘束變元進(jìn)行換名：〔1〕xy(P(x,z)Q(y))S(x,y)〔2〕(x(P(x)(R(x)Q(x)))xR(x))zS(x,z)7解：〔1〕uv(P(u,z)Q(v))S(x,y)〔2〕(u(P(u)(R(u)Q(u)))vR(v))zS(x,z)對以下謂詞公式中自由變元進(jìn)行代入：〔1〕(yA(x,y)xB(x,z))xzC(x,y,z)〔2〕(yP(x,y)zQ(x,z))xR(x,y)解：〔1〕(yA(s,y)xB(x,w))xzC(x,t,z)〔2〕(yP(s,y)zQ(s,z))xR(x,t)習(xí)題證明以低等價(jià)式：〔1〕x(P(x)Q(x))x(P(x)Q(x)).證明：x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))〔2〕x(P(x)Q(x))x(P(x)Q(x)).證明：x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))x(P(x)Q(x))習(xí)題求以下謂詞公式的前束析取范式和前束合取范式：〔1〕(x)P(x)(x)Q(x).解：(x)P(x)(x)Q(x)8(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x))〔前束析取范式、前束合取范式〕〔2〕(x)(y)((z)(P(x,z)P(y,z))(u)Q(x,y,u)).證明：(x)(y)((z)(P(x,z)P(y,z))(u)Q(x,y,u))(x)(y)(z)((P(x,z)P(y,z))(u)Q(x,y,u))(x)(y)(z)(u)((P(x,z)P(y,z))Q(x,y,u))

〔轄域擴(kuò)大〕〔轄域擴(kuò)大〕〔前束析取范式〕(x)(y)(z)(u)((P(x,z)Q(x,y,u))(P(y,z)Q(x,y,u)))〔前束合取范式〕習(xí)題1.證明以下各式?！?〕x(A(x)B(x)),x(B(x)C(x)),xC(x)xA(x).證明：〔1〕xC(x)P〔2〕C(a)US〔1〕〔3〕x(B(x)C(x))P〔4〕B(a)C(a)US〔3〕〔5〕B(a)T(2)(4)I〔6〕x(A(x)B(x))P〔7〕A(a)B(a)US〔6〕〔8〕A(a)T〔5〕〔7〕I〔9〕xA(x)UG〔8〕符號(hào)化以下命題并推證其結(jié)論。〔3〕全部有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，所以，某些實(shí)數(shù)是整數(shù)。解：設(shè)Q(x)：x是有理數(shù)。R(x)：x是實(shí)數(shù)。Z(x)：x是整數(shù)。那么命題可符號(hào)化為：9x(Q(x)R(x))，x(Q(x)Z(x))x(R(x)Z(x))。證明以下：〔1〕x(Q(x)Z(x))P〔2〕Q(c)Z(c)ES〔1〕〔3〕x(Q(x)R(x))P〔4〕Q(c)R(c)US〔3〕〔5〕Q(c)T〔2〕I〔6〕R(c)T〔4〕〔5〕I〔7〕Z(c)T〔2〕I〔8〕R(c)Z(c)T〔6〕〔7〕I〔9〕x(R(x)Z(x))EG〔8〕4〕每個(gè)大學(xué)生不是文科生就是理科生，有的大學(xué)生是優(yōu)等生，小張不是理科生，但他是優(yōu)等生，所以假如小張是大學(xué)生，他就是文科生。解：設(shè)S(x)：x是大學(xué)生。A(x)：x是文科生。B(x)：x是理科生。C(x)：x是優(yōu)等生。a：小張。該命題可符號(hào)化為：x(S(x)A(x)B(x))，x(S(x)C(x))，B(a)，C(a)S(a)A(a)。證明以下：〔1〕x(S(x)A(x)B(x))P〔2〕S(a)A(a)B(a)US〔3〕〔3〕S(a)附帶前提〔6〕A(a)B(a)T〔4〕〔5〕I〔7〕B(a)P〔8〕A(a)T〔6〕〔7〕I〔9〕S(a)A(a)CP10習(xí)題確立以下命題是真仍是假，并簡要說明為何?！?〕〔2〕〔3〕{}〔4〕{}解：〔1〕該命題為真，由于是任何會(huì)合的子集。〔2〕該命題為假，由于不包括任何元素。〔3〕該命題為真，由于屬于會(huì)合{}?！?〕該命題為真，由于是任何會(huì)合的子集。6.求以下會(huì)合的冪集：〔2〕{1,}〔3〕{,{}}解：〔2〕該會(huì)合的冪集為{,{1},{},{1,}}。〔3〕該會(huì)合的冪集為{,{},{{}},{,{}}}習(xí)題證明以低等式：〔4〕A(BC)(AB)(AC)。證明：A(BC)=A(BC)=A(BC)=A(BC)=(AB)(AC)=(AB)(AC)所以，A(BC)(AB)(AC)?！?〕A(BC)(AB)(AC)。證明：A(BC)=A(BC)A(BC)=(AB)(AC)=(AB)(AC)。所以，A(BC)(AB)(AC)。〔8〕(AB)(AC)(AC)(AB)。證明：(AB)(AC)((AB)A)((AB)C)11(AA)(AB)(AC)(BC)(AB)(AC)(BC)(AC)(AB)[(BC)(AA)](AC)(AB)(BCA)(BCA)[(AC)(ABC)][(AB)(ABC)](AC)(AB)所以，(AB)(AC)(AC)(AB)。習(xí)題以低等式能否建立？〔3〕(BC)A(BA)(CA)。解：該等式建立。證明以下：設(shè)x,y(BC)AxBCyAxBxCyA(xByA)(xCyA)x,yBAx,yCAx,y(BA)(CA)所以，(BC)A(BA)(CA)?！?〕(BC)A(BA)(CA)。解：該等式建立。證明以下：設(shè)x,y(BC)AxBCyA(xBxC)yA(xByA)(xCyA)x,yBAx,yCA12x,y(BA)(CA)所以，(BC)A(BA)(CA)。習(xí)題關(guān)于以下各樣狀況，用列舉法求出X到Y(jié)的關(guān)系S、domS、ranS，畫出S的關(guān)系圖，寫出S的關(guān)系矩陣?！?〕X{0,1,2}，Y{0,2,4}，S{x,y|x,yXY}。解：S{0,0,0,2,2,0,2,2}，domS{0,2}，ranS{0,2}。關(guān)系圖以下：001224關(guān)系矩陣為110MS000。110習(xí)題5.設(shè)X{a,b,c,d}，X上的關(guān)系R的關(guān)系矩陣以下，試問R是不是自反的、反自反的、對稱的、反對稱的和傳達(dá)的？0101101100000101〔1〕00〔4〕10111101001111解：〔1〕R是反自反的、反對稱的、非傳達(dá)的。由于r121,r311,但r320?！?〕R是自反的、對稱的、非傳達(dá)的。由于r341,r421,但r320。13習(xí)題5.〔1〕設(shè)X{a,b,c}，X上關(guān)系R的關(guān)系矩陣是101MR110111試求出MRoR、MRoRoR。101101111解：MRoR110o110111，111111111111101111MRoRoR111o110111。111111111習(xí)題4.設(shè)X{1,2,3,4,5}，試依據(jù)以下X的區(qū)分求X上相應(yīng)的等價(jià)關(guān)系，并畫出關(guān)系圖。3〕{{1},{2},{3,4,5}}解：R1{1}{1}{1,1}R2{2}{2}{2,2}R3{3,4,5}{3,4,5}{3,3,3,4,3,5,4,3,4,4,4,5,5,3,5,4,5,5}RR1R2R3{1,1,2,2,3,3,3,4,3,5,4,3,4,4,4,5,5,3,5,4,5,5}關(guān)系圖以下：1425314習(xí)題關(guān)于以下會(huì)合上的“整除〞關(guān)系，畫出其哈斯圖。〔1〕{1,2,3,4,6,8,12,24}解：該整除關(guān)系的哈斯圖以下：2481246231習(xí)題1.指出以下各關(guān)系能否為X到Y(jié)的函數(shù)：〔1〕XYN，R{x,y|(xX)(yY)(xy100)}.〔3〕X{1,2,3,4}，YXX，R1{1,2,3,2,3,4,3,1,4,4,2,3}，R2{1,2,3,2,3,4,3,2,3}.解：〔1〕R不是從X到Y(jié)的函數(shù)；〔2〕R1是從X到Y(jié)的函數(shù)，R2不是從X到Y(jié)的函數(shù)。習(xí)題設(shè)Z，Z，R，C分別表示正整數(shù)集、整數(shù)集、實(shí)數(shù)集、復(fù)數(shù)集，試指出以下照耀中哪些是單射、滿射、雙射，并寫出定義域和值域。〔1〕f:ZZ為f(x)2x1。〔2〕f:RR為f(x)cosx?！?〕f:[0,][1,1]為f(x)cosx。215解：〔1〕為一般照耀，定義域?yàn)閆，值域?yàn)閧y|y2k1,kN}?！?〕為一般照耀，定義域?yàn)镽，值域?yàn)閇1,1]?！?〕為單射，定義域?yàn)閇0,]，值域?yàn)閇0,1]。2習(xí)題設(shè)X{1,2,3,4}?！?〕能否找到另一gIX的單射g:XX，有g(shù)ogIX？解：能。比方g{1,2,2,1,3,4,4,3}?！?〕試定義一個(gè)照耀f:XX使f2f且fIX。解：比方f{1,2,2,2,3,3,4,4}。習(xí)題1.設(shè)無向圖GV,E,，V{v1,v2,L,v6}，E{e1,e2,L,e6}，(e1)(v1,v2)，(e2)(v2,v2)，(e3)(v2,v4)，(e4)(v4,v5)，(e5)(v3,v4)，(e6)(v1,v3)。1〕畫出G的圖形。2〕求G的各節(jié)點(diǎn)的度數(shù)，并考證握手定理。3〕G是不是簡單圖？解：〔1〕v3v5v1v2v4v6〔2〕deg(v)2，deg(v)4，deg(v)2，deg(v)3deg(v)1，deg(v)0。123456166deg(vi)12，2E12，握手定理建立。13〕圖G中存在環(huán)，故G不是簡單圖。4.下邊各圖有幾個(gè)節(jié)點(diǎn)？〔2〕21條邊，3個(gè)度為4的節(jié)點(diǎn)，其他都是度為3的節(jié)點(diǎn)。解：設(shè)度數(shù)為3的節(jié)點(diǎn)個(gè)數(shù)為x，由握手定理，解得故該圖有13個(gè)節(jié)點(diǎn)。

221343xx10習(xí)題4.分別指出圖7-32中的3個(gè)圖分別屬于哪一各樣類〔強(qiáng)連通，單側(cè)連通，弱連通〕。〔a〕(b)(c)v1解：〔a〕是強(qiáng)連通的，〔b〕是單側(cè)連通的，(c)是弱連通的。習(xí)題1.圖7-39給出了一個(gè)有向圖，試求v4v2〔1〕毗鄰矩陣。〔2〕A2、A3、A4，并找出從v1到v4長度為1、2、3、4的路各有幾條？v3〔3〕可達(dá)性矩陣。圖7-3901010011解：〔1〕毗鄰矩陣A10。010100010101010111〔2〕A2001100110201,01010101011101000100001117011101010212A302010011012201110101021,2001101000201021201010323A401220011041302120101032.3020101000122從毗鄰矩陣及其冪可知，從v1到v4長度為1的路有1條，從v1到v4長度為2的路有1條，從v1到v4長度為3的路有2條，從v1到v4長度為4的路有3條?！?〕令BAA2A3A4，07470111那么B0747，可達(dá)性矩陣P01110747011。104340111習(xí)題2.確立n取如何的值，圓滿圖Kn有一條歐拉回路。解：圓滿圖Kn有一條歐拉回路的充要條件是每個(gè)節(jié)點(diǎn)的度數(shù)都是偶數(shù)。而在Kn中，每個(gè)節(jié)點(diǎn)的度數(shù)都是n1。故當(dāng)n為奇數(shù)時(shí)，圓滿圖Kn有一條歐拉回路。習(xí)題5.設(shè)G是一個(gè)連通平面圖，它有n個(gè)節(jié)點(diǎn)，m條邊，且每個(gè)面由k條邊圍成。試證mk(n2)。k2證明：設(shè)圖G有r個(gè)面，由平面圖的面的次數(shù)的定理，r2mdeg(Ri)kr.〔1〕i1再由歐拉定理，nmr2.〔2〕由〔1〕得r2m，代入〔2〕式得k18k(n2).k2習(xí)題一棵樹T有5個(gè)度為2的節(jié)點(diǎn)，3個(gè)度為3的節(jié)