離散數(shù)學(xué)復(fù)習(xí)題(請參考課件)_第1頁
離散數(shù)學(xué)復(fù)習(xí)題(請參考課件)_第2頁
離散數(shù)學(xué)復(fù)習(xí)題(請參考課件)_第3頁
離散數(shù)學(xué)復(fù)習(xí)題(請參考課件)_第4頁
離散數(shù)學(xué)復(fù)習(xí)題(請參考課件)_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

離散數(shù)學(xué)Part1_數(shù)理邏輯部分將下列命題符號化。P48豆沙包是由面粉和紅小豆做成的.蘋果樹和梨樹都是落葉喬木.王小紅或李大明是物理組成員.王小紅或李大明中的一人是物理組成員.由于交通阻塞,他遲到了.如果交通不阻塞,他就不會遲到.他沒遲到,所以交通沒阻塞.除非交通阻塞,否則他不會遲到.他遲到當(dāng)且僅當(dāng)交通阻塞.分清復(fù)合命題與簡單命題分清相容或與排斥或分清必要與充分條件及必要充分條件答案:(1)是簡單命題(2)是合取式(3)是析取式(相容或)(4)是析取式(排斥或)請分別寫出(1)—(4)的符號化形式設(shè)p:交通阻塞,q:他遲到pq,(6)pq或qp(7)qp或pq,(8)qp或pq(9)pq或pq可見(5)與(7),(6)與(8)相同(等值)用真值表判斷下面公式的類型P51pr(qp)((pq)(qp))r(pq)(pr)按層次寫真值表,由最后一列判類型答案:(1)為矛盾式,(2)為重言式,(3)為可滿足式例用等值演算法判斷下列公式的類型P59(1)q(pq)(2)(pq)(qp)(3)((pq)(pq))r)解(1)q(pq)q(pq)(蘊涵等值式)q(pq)(德摩根律)p(qq)(交換律,結(jié)合律)p0(矛盾律)0(零律)由最后一步可知,(1)為矛盾式.(2)(pq)(qp)(pq)(qp)(蘊涵等值式)(pq)(pq)(交換律)1由最后一步可知,(2)為重言式.問:最后一步為什么等值于1?說明:(2)的演算步驟可長可短,以上演算最省.(3)((pq)(pq))r)(p(qq))r(分配律)p1r(排中律)pr(同一律)由最后一步可知,(3)不是矛盾式,也不是重言式,它是可滿足式,其實101,111是成真賦值,000,010等是成假賦值.總結(jié):從此例可看出A為矛盾式當(dāng)且僅當(dāng)A0A為重言式當(dāng)且僅當(dāng)A1例求公式A=(pq)r的主析取范式與主合取范式.P71(1)求主析取范式(pq)r(pq)r(析取范式)=1\*GB3①(pq)(pq)(rr)(pqr)(pqr)m6m7=2\*GB3②r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)m1m3m5m7=2\*GB3②,=3\*GB3③代入=1\*GB3①并排序,得(pq)rm1m3m5(2)求A的主合取范式(pq)r(pr)(qr)(合取范式)=1\*GB3①prp(qq)r(pqr)(pqr)M0M2=2\*GB3②qr(pp)qr(pqr)(pqr)M0M4=3\*GB3③=2\*GB3②,=3\*GB3③代入=1\*GB3①并排序,得(pq)rM0M2設(shè)A與B均為含n個命題變項的公式,判斷下列命題是否為真?P85AB當(dāng)且僅當(dāng)A與B有相同的主析取范式若A為重言式,則A的主合取范式為0若A為矛盾式,則A的主析取范式為1任何公式都能等值地化成{,}中的公式任何公式都能等值地化成{,,}中的公式(1)為真,這是顯然的(2)為假.注意,任何公式與它的主范式是等值的,顯然重言式不能與0等值。重言式的主合取范式不含極大項,因而主合取范式為1.(3)的分析類似于(2),矛盾式的主合取范式為0.(4)為假,因為{,}不是完備集,比如矛盾式(pq)q不能化成{,}中的公式.(5)為真,注意{,,}的子集{,}為完備集.2.通過求主范式判公式類型P87(1)(p?q)?(?q??p)(2)?(p?q)ùq(3)(p?q)ù?p(1)重言式,(2)矛盾式,(3)可滿足式解用等值演算法求解(1)(pq)(qp)(pq)(qp)(消去)=1\*GB3①(pq)(qp)(內(nèi)移)=2\*GB3②(pq)(pq)(pq)(pq)=3\*GB3③m2m1m3m0=4\*GB3m0m1m2m31=6\*GB3⑥問由=2\*GB3②如何得=3\*GB3③?=5\*GB3⑤為主析取范式,=6\*GB3⑥為主合取范式結(jié)論:(1)為重言式(2)(pq)q(pq)q=1\*GB3①pqq=2\*GB3②0=3\*GB3③M0M1M2M3問:由=2\*GB3②如何得=3\*GB3③?=3\*GB3③為主析取范式,=4\*GB3④為主合取范式結(jié)論:(2)為矛盾式.(3)(pq)pm0m1=1\*GB3①M2M3=2\*GB3②請自己等值演算得=1\*GB3①與=2\*GB3②結(jié)論:(3)為可滿足式請用真值表再解此題3.已知命題公式A中含3個命題變項p,q,r,并知道它的成真賦值為001,010,111,求A的主析取范式和主合取范式,及A對應(yīng)的真值函數(shù).P90答案A的主析取范式為m1A的主合取范式為M0M3M4設(shè)A對應(yīng)的真值函數(shù)為F,則F(001)=F(010)=F(111)=1F(000)=F(011)=F(100)=F(101)=F(110)=0試說明以上得出答案的理由5.某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國學(xué)習(xí).選派必須滿足以下條件:P94若趙去,錢也去.李、周兩人中必至少有一人去錢、孫兩人中去僅去一人.孫、李兩人同去或同不去.若周去,則趙、錢也去.用等值演算法分析該公司如何選派他們出國?解此類問題的步驟應(yīng)為:eq\o\ac(○,1)將簡單命題符號化eq\o\ac(○,2)寫出各復(fù)合命題eq\o\ac(○,3)寫出由=2\*GB3②中復(fù)合命題組成的合取式eq\o\ac(○,4)將=3\*GB3③中公式化成析取式(最好是主析取范式)解=1\*GB3①設(shè)p:派趙去,q:派錢去,r:派孫去,s:派李去,u:派周去=2\*GB3②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))=3\*GB3③設(shè)(1)—(5)構(gòu)成的合取式為AA=(pq)(su)((qr)(qr))((rs)(rs))(u(pq))=4\*GB3④A(pqrsu)(pqrsu)結(jié)論:由=4\*GB3④可知,A的成真賦值為00110與11001,因而派孫、李去(趙、錢、周不去)或派趙、錢、周去(孫、李不去)例用構(gòu)造證明法構(gòu)造下面推理的證明:P112若明天是星期一或星期三,我就有課.若有課,今天必備課.我今天下午沒備課.所以,說明天是星期一或星期三是不對的.構(gòu)造證明設(shè)p:明天是星期一,q:明天是星期三,r:我有課,s:我備課形式結(jié)構(gòu)前提:(pq)r,rs,s結(jié)論:pq證明=1\*GB3①rs前提引入=2\*GB3②s前提引入=3\*GB3③r=1\*GB3①=2\*GB3②拒取式=4\*GB3④(pq)r前提引入=5\*GB3⑤(pq)=3\*GB3③=4\*GB3④拒取式=6\*GB3⑥pq=5\*GB3⑤置換附加前提證明法欲證:前提:A1,A2,…,Ak結(jié)論:CB(2)等價地證明前提:A1,A2,…,Ak,C結(jié)論:B(3)理由:(A1A2…Ak)(CB(A1A2…Ak)(CB(A1A2…AkC)(A1A2…AkC)B例構(gòu)造下面推理的證明P1152是素數(shù)或合數(shù).若2是素數(shù),則是無理數(shù).若是無理數(shù),則4不是素數(shù).所以,如果4是素數(shù),則2是合數(shù).用附加前提證明法構(gòu)造證明(1)設(shè)p:2是素數(shù),q:2是合數(shù),r:是無理數(shù),s:4是素數(shù)(2)形式結(jié)構(gòu)前提:pq,pr,rs結(jié)論:sq(3)證明=1\*GB3①s附加前提引入=2\*GB3②pr前提引入=3\*GB3③rs前提引入=4\*GB3④ps=2\*GB3②=3\*GB3③假言三段論=5\*GB3⑤p=1\*GB3①=4\*GB3④拒取式=6\*GB3⑥pq前提引入=7\*GB3⑦q=5\*GB3⑤=6\*GB3⑥析取三段論請用直接證明法證明之在P系統(tǒng)中構(gòu)造下面推理的證明:P125如果今天是周六,我們就到頤和園或圓明園玩.如果頤和園游人太多,就不去頤和園.今天是周六,并且頤和園游人太多.所以我們?nèi)A明園或動物園玩.設(shè)p:今天是周六,q:到頤和園玩,r:到圓明園玩,s:頤和園游人太多t:到動物園玩(2)前提:p(qr),sq,p,s結(jié)論:rt(3)證明:=1\*GB3①p(qr)前提引入=2\*GB3②p前提引入=3\*GB3③qr=1\*GB3①=2\*GB3②假言推理=4\*GB3④sq前提引入=5\*GB3⑤s前提引入=6\*GB3⑥q=4\*GB3④=5\*GB3⑤假言推理=7\*GB3⑦r=3\*GB3③=6\*GB3⑥析取三段論=8\*GB3⑧rt=7\*GB3⑦附加 在一階邏輯中將下列命題符號化P150大熊貓都可愛有人愛發(fā)脾氣說所有人都愛吃面包是不對的沒有不愛吃糖的人一切人都不一樣高并不是所有的汽車都比火車快由于沒指出個體域,故用全總個體域(1)x(F(x)G(x))其中,F(xiàn)(x):x為大熊貓,G(x):x可愛(2)x(F(x)G(x))其中,F(xiàn)(x):x是人,G(x):x愛發(fā)脾氣(3)x(F(x)G(x))或x(F(x)G(x))其中,F(xiàn)(x):x是人,G(x):x愛吃面包(4)x(F(x)G(x))或x(F(x)G(x))其中,F(xiàn)(x):x是人,G(x):x愛吃糖(5)x(F(x)y(F(y)H(x,y)L(x,y))),或xy(F(x)F(y)H(x,y)L(x,y))其中,F(xiàn)(x):x是人,H(x,y),x與y相同,L(x,y):x與y一樣高(6)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快幾點說明使用的是全總個體域(1)與(2)是兩個基本公式的使用(3)與(4)是否定式(5)與(6)使用了二元謂詞(3)-(6)的不同符號化形式是等值的離散數(shù)學(xué)Part2_集合論部分2.計數(shù)實例P14例求1到1000之間(包含1和1000在內(nèi))既不能被5和6整除,也不能被8整除的數(shù)有多少個?解方法一方法二令S={x|xZ1x1000},A={x|xSx0(mod5)}B={x|xSx0(mod6)},C={x|xSx0(mod8)}則|S|=1000|A|=1000/5=200,|B|=1000/6=166,|C|=1000/8=125|AB|=1000/lcm(5,6)=1000/33=33|AC|=1000/lcm(5,8)=1000/40=25|BC|=1000/lcm(6,8)=1000/24=41|ABC|=1000/lcm(5,6,8)=1000/120=8=1000(200+166+125)+(33+25+41)8=600.設(shè)A={1,2,3},R={<x,y>|x,yA且x+2y6},P104S={<1,2>,<1,3>,<2,2>},求(1)R的集合表達(dá)式(2)R1(3)domR,ranR,fldR(4)RS,R3(5)r(R),s(R),t(R)(1)R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}(2)R1={<1,1>,<2,1>,<1,2>,<2,2>,<1,3>}(3)domR={1,2,3},ranR={1,2},fldR={1,2,3}(4)RS={<1,2>,<1,3>,<2,2>,<2,3>,<3,2>,<3,3>}R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}(5)r(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,3>}s(R)={<1,1>,<1,2>,<2,1>,<2,2>,<3,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論