離散數(shù)學(xué)平時(shí)作業(yè)

1、第一章假定A是ECNU二年級(jí)的學(xué)生集合，B是ECNU必須學(xué)離散數(shù)學(xué)的學(xué)生的集合。請(qǐng)用 A和B表示ECNU不必學(xué)習(xí)離散數(shù)學(xué)的二年級(jí)的學(xué)生的集合。解：三試求：P() P(P() P(P(P()(1) )(2) , 在1 -200的正整數(shù)中，能被 3或5整除，但不能被15整除的正整數(shù)共有多少個(gè)？能被5整除的有40個(gè)，能被15整除的有13個(gè)，能被3或5整除，但不能被 15整除的正整數(shù)共有66-13+40-13=80個(gè)。第三章下列語(yǔ)句是命題嗎？2是正數(shù)嗎？ 2x+x+1=0。(3)我要上學(xué)。(4)明年2月1日下雨。(5)如果股票漲了，那么我就賺錢。解：)不是)不是)不是)是)是請(qǐng)用自然語(yǔ)言表達(dá)命題 (p

2、Tr)(qTr),其中p、q、r為如下命題:p：你得流感了q：你錯(cuò)過(guò)了最后的考試r：這門課你通過(guò)了解:(1)如果你得流感了，你就不能通過(guò)這門課；或者你錯(cuò)過(guò)了最后的考試，你也不能通過(guò)這 門課。如果你得流感了并且錯(cuò)過(guò)了最后的考試，那么你就不能通過(guò)這門課。通過(guò)真值表求p-HpNqT p)的主析取范式和主合取范式。解：主析取范式：(p q)(p. q) (p. q) (p q)主合取范式不存在給出 (qTSbq,pLg is的形式證明。證明：前提引入附加前提引入(1 ) (2)析取三段 前提引入(3 ) ( 4 )假言推理 前提引入(5 ) ( 6 )假言推理(1 ) p -RP(4 ) p- (q-

3、 s)q-sQS第四章將以(5*)3丫(5丫)干代丫)翻譯成漢語(yǔ)，其中 C(x層示x有電腦，F(xiàn)(x,y)表示x和y是同 班同學(xué)，個(gè)體域是學(xué)校全體學(xué)生的集合。解：學(xué)校的全體學(xué)生要么自己有電腦，要么其同班同學(xué)有電腦。構(gòu)造 Vx(P(x)vQ(x), Vx(Q(xR(x)xR(xV xP(x)的形式證明。解：-xR(x) R(e)-x(Q(x) R(x) Q(e) -R(e)-RQ (e)- x(P(x) Q(x)P(e) Q(e)P(e)-x (P(x)前提引入U(xiǎn)S規(guī)則前提引入U(xiǎn)S規(guī)則析取三段論前提引入U(xiǎn)S規(guī)則析取三段論EG規(guī)則第五章. 設(shè) r、s、t都是X 上的關(guān)系。證明：rsnTRr冶)n(R

4、T), (Rn s)T(r:jt)n (ST)。解：對(duì)x,y三X, R(Sn T)= u( 三R 三 SA T)= u( 三R 三S 三T)= u( 三R 三S 三T 三R)= u( 三R 三S)=u ( 三T 三 R)= ( R S) ( R T)二 三(RS)A (R T)故 R (SA T) (R S)A (R T)對(duì)-x,y三X, (RA S) T= u( 三RC S 三 T)= u( ER S T)= u( 三R S 三T 三T)=u( R T)=lu ( S T)= ( R T) ( ST)二 三(RT)A (S T)故(RA S) T (R T)A (S T).設(shè)X是所有人組成的

5、集合，定義 X上的關(guān)系Ri和R2： aRib當(dāng)且僅當(dāng)a比b高，aR2b 當(dāng)且僅當(dāng)a和b有共同的祖父母。問(wèn)關(guān)系Ri和R2是否是自反、反自反、對(duì)稱、反對(duì)稱、傳遞的？. 設(shè)Ri和R2是X上的關(guān)系。證明t(R2R2)m(Ri)5(R2)。.下列集合關(guān)于整除關(guān)系I構(gòu)成偏序集。請(qǐng)分別畫(huà)出它們的哈斯圖，判斷它們是否是全序集，給出它們的極大元、極小元、最大元、最小元。2,4,8,i6;(4) 2,3,4,5,9/0,80。i.f: XtY,下列命題是否成立?f是一對(duì)一的當(dāng)且僅當(dāng)對(duì)任意f是一對(duì)一的當(dāng)且僅當(dāng)對(duì)任意第六章a,bWX,當(dāng) f(a)=f(b)時(shí),必有 a=b;a,bX,當(dāng) f(a) wf(b),必有 a

6、wbo解：成立不成立，如f(x)=x22.下圖展示了五個(gè)關(guān)系的關(guān)系圖。 哪些是到上的函數(shù)？哪些是一問(wèn)：這些關(guān)系中，哪些是函數(shù)？哪些是一對(duì)一的函數(shù)? 一對(duì)應(yīng)？解：1是函數(shù)，一對(duì)一，但不是到上的;2是函數(shù)，到上的，但不是一對(duì)一;3是函數(shù)， 對(duì)應(yīng)；4是函數(shù)；5不是函數(shù)。第七章6 個(gè)學(xué)生：Alices Bobh Carol、Dean、Santos和 tom,其中，Alice和 Carol不和，Dean和Carol不和，Santos Tom和Alice兩兩不和。請(qǐng)給出表示這種情形的圖模型。設(shè)簡(jiǎn)單無(wú)向圖 G=(V,E)若S (G)k(k1),則G有長(zhǎng)度為k的基本通路。解：證明：我們假設(shè)存在k-1的基本通路

7、，則存在k個(gè)頂點(diǎn)，通路最后一個(gè)頂點(diǎn)與通路上頂點(diǎn)相連的度 數(shù)至多為k-1。因?yàn)镾 (G)k(k1),所以該頂點(diǎn)必定與其他頂點(diǎn)相連，那么存在長(zhǎng)度為K的基本通路。得證。一大學(xué)有5個(gè)專業(yè)委員會(huì)：物理、化學(xué)、數(shù)學(xué)、生物、計(jì)算機(jī)，6位院士： B、C、D、G、S Wo專業(yè)委員會(huì)由院士組成，物理委員會(huì)有院士：C、S和W,化學(xué)委員會(huì)有院士： G D和W;數(shù)學(xué)委員會(huì)有院士：B、G G和S;生物委員會(huì)有院士：B和G;計(jì)算機(jī)委員會(huì)有院士： D和Go每個(gè)專業(yè)委員會(huì)每周開(kāi)一小時(shí)例會(huì)，所有成員都不能缺席。如果某院士同時(shí)是兩個(gè)專業(yè)委員會(huì)的成員，那么這兩個(gè)專業(yè)委員會(huì)的例會(huì)就不能安排在同一個(gè)時(shí)間。現(xiàn)要為這些例會(huì)安排時(shí)間，希望它們

8、的時(shí)間盡可能集中。問(wèn)最少需要 幾個(gè)開(kāi)會(huì)時(shí)間？請(qǐng)給出一種安排。答：頂點(diǎn)表示各個(gè)專業(yè)委員會(huì)，邊表示兩委員會(huì)有共同委員。畫(huà)出如下無(wú)向圖:3個(gè)。一種開(kāi)會(huì)方案為對(duì)該圖著色，可得最少的開(kāi)會(huì)時(shí)間為 數(shù)學(xué)，生物和化學(xué)，物理和計(jì)算機(jī)。第八章解：從圖中刪除所標(biāo)記的 6個(gè)頂點(diǎn)， 所得到白圖由7個(gè)孤立點(diǎn)組成，有 7個(gè)連通分量。所 以，該圖不滿足哈密頓圖的必要條件，因而不是哈密頓圖。2.證明連通圖的割邊一定是每棵生成樹(shù)的邊。解:證明：刪除割邊后的圖一定不連通，其中不存在生成樹(shù)。所以，每課生成樹(shù)都包含割邊第九章.股評(píng)家推薦了 12個(gè)股票，一股民欲購(gòu)買其中的3個(gè)。問(wèn)在下列各種條件下，分別有多少種不同的投資方式？(1)每個(gè)股

9、票各投資 3000元；2) 3個(gè)股票分別投資 5000元、3000元和1000元。解： C123=220(2) P123=1320. 16支互不同顏色的蠟筆平分給4個(gè)孩子，有多少種不同的分法？解：C(16,4) C(12,4) C(8,4) C(4,4).某學(xué)校有2504個(gè)計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生，其中1876人選修了 C語(yǔ)言，999人選修了Fortran語(yǔ)言，345人選修了 JAVA, 876人選彳了 C語(yǔ)言和Fortran語(yǔ)言，231人選修 了 Fortran 和JAVA, 290人選修了 C和JAVA, 189個(gè)學(xué)生同時(shí)選了 C、Fortran 和JAVA。問(wèn)沒(méi)有選這3門程序設(shè)計(jì)語(yǔ)言課中的任

10、何一門的學(xué)生有多少個(gè)？解：A表示選修了 C語(yǔ)言，B表示選修了 Fortran語(yǔ)言，C表示選修了 JAVA|A 一B 一C|=|A|+|B|+|C|-|A- B|-|B C|-|C A|+|A B C|=1876+999+345-876-231-290+189=2012則沒(méi)有選這3門程序設(shè)計(jì)語(yǔ)言課中的任何一門的學(xué)生：2504-2012=492第十章1. 求初值問(wèn)題的通項(xiàng)公式：an=10an-1-25an-2； a0=-7 , a1=15。解：特征方程：r2-10r+25=0 ,特征根：”=門=5通解：an=(a+函)5n由 a0=a50=a=-7 和 a1= (-7+ 951 =15 解得：=-7