離散數(shù)學(xué)導(dǎo)論_第1頁(yè)
離散數(shù)學(xué)導(dǎo)論_第2頁(yè)
離散數(shù)學(xué)導(dǎo)論_第3頁(yè)
離散數(shù)學(xué)導(dǎo)論_第4頁(yè)
離散數(shù)學(xué)導(dǎo)論_第5頁(yè)
已閱讀5頁(yè),還剩16頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

離散數(shù)學(xué)導(dǎo)論王元元張桂蕓科學(xué)出版社第一、二章2、命題及其真值的判定.3、命題公式的符號(hào)化1、命題邏輯的五個(gè)聯(lián)結(jié)詞┐,∨,∧,,及真值表.4、命題公式的類型:(1)永真式;(2)可滿足式;(3)永假式.很顯然,永真式是可滿足式,非永真式未必是永假式,而當(dāng)A是永真式(永假式)時(shí),┐A必為永假式(永真式).命題公式的類型可用以下方法判定:(1)真值表的方法(2)利用已知永真式及代入、替換原理進(jìn)行等價(jià)推演的方法.(3)利用主析取范式和主合取范式的方法.5、命題公式的范式(主析取范式、主合取范式),求命題公式的范式的方法:(1)利用真值表的方法.(2)等價(jià)推演的方法.例.命題公式的范式.設(shè)命題公式為(1).求出該公式的真值表.(2).求該公式的主析取范式和主合取范式.(3).判斷該公式的類型.解(1).公式A的真值表為(2).公式A的主析取范式為:pqrA00000011010001111001101111011110(3).由真值表可知,公式A為可滿足式.主合取范式為:pqrA000000110100011110011011110111105、謂詞公式的符號(hào)化.準(zhǔn)確地從語句中提取謂詞,表示性質(zhì)的謂語用一元謂詞表示,表示關(guān)系的謂語用二元或更多元數(shù)的謂詞來表示,準(zhǔn)確地使用量詞和適當(dāng)?shù)倪壿嬄?lián)結(jié)詞把原語句表示為謂詞公式.例:設(shè)N(x):x是自然數(shù).I(x):x是整數(shù).則語句:“所有的自然數(shù)都是整數(shù)”可表示為謂詞公式:

設(shè)N(x):x是自然數(shù).E(x):x是奇數(shù).則語句:“有些自然數(shù)是奇數(shù)”可表示為謂詞公式:

當(dāng)個(gè)體域D是有限集合時(shí),利用下列等價(jià)式可以消去謂詞公式中的量詞例:設(shè)個(gè)體域D={0,1},p(0)=1,p(1)=0,確定謂詞公式的真值解:第四章例:設(shè)集合A={1、2、3},則{1}∈ρ

(A)(√)設(shè)集合A={1、2、3},則1∈ρ

(A)(×)2、集合的運(yùn)算(并、交、差、補(bǔ)、冪集運(yùn)算)及運(yùn)算律.1、元素和集合的關(guān)系為屬于關(guān)系∈,集合和集合間的關(guān)系為包含關(guān)系第五章1、關(guān)系及其運(yùn)算.(1)集合的笛卡兒積.(2)關(guān)系的基本運(yùn)算(并、交、差、補(bǔ)、合成)及運(yùn)算律.(3)關(guān)系的基本特性(自反、反自反、對(duì)稱、反對(duì)稱、傳遞).例(3)設(shè)集合A={0,1,2,3,4},R,S均為A上二元關(guān)系,且

R={<x,y>x+y=4}={<0,4>,<4,0>,<1,3>,<3,1>,<2,2>}

S={<x,y>y–x=1}={<0,1>,<1,2>,<2,3>,<3,4>}那么

R?S={<4,l>,<1,4>,<3,2>,<2,3>}={<x,z>x+z=5}S?R={<0,3>,<1,2>,<2,1>,<3,0>}={<x,z>x+z=3}例

設(shè)A={1,2,3}以下各關(guān)系Ri(i=1,2,…,8)均為A上二元關(guān)系.(1)R1={<1,1>,<1,3>,<2,2>,<3,3>}是自反的,而R2={<1,3>,<3,1>}不是自反的,是反自反的,存在既不自反也不反自反的二元關(guān)系,例如R3={<1,1>}.顯然非空集合A上的關(guān)系是反自反的,不是自反的.可是值得注意的是,當(dāng)A=時(shí)(這時(shí)A上只有一個(gè)關(guān)系),A上空關(guān)系既是自反的,又是反自反的,因?yàn)锳=使兩者定義的前提恒假.(2)R4={<1,3>,<3,1>,<1,2>,<1,1>}不是對(duì)稱的;R5={<1,2>,<2,1>}是對(duì)稱的;

R6={<1,2>,<1,3>}是反對(duì)稱的.其實(shí)R4既不是對(duì)稱的,也不是反對(duì)稱的.特別有意思的是,存在既對(duì)稱又反對(duì)稱的二元關(guān)系,例如A上的相等關(guān)系EA.(3)R7={<1,2>,<2,3>,<1,3>,<3,3>}是傳遞的,但R7–{<1,3>}便不是傳遞的了.應(yīng)當(dāng)注意,A上的空關(guān)系,R8={<1,2>}等是傳遞的,因?yàn)閭鬟f性定義的前提對(duì)它們而言均為假.2、等價(jià)關(guān)系及偏序關(guān)系(1)等價(jià)關(guān)系的判定判定該關(guān)系是否滿足自反性、對(duì)稱性、傳遞性.(2)序關(guān)系的判定判定該關(guān)系是否滿足自反性、反對(duì)稱性、傳遞性.整數(shù)集合上的等價(jià)關(guān)系:模n的相等關(guān)系(模n的同余關(guān)系),確定由模n的相等關(guān)系確定的等價(jià)類的元素.第六章1、函數(shù)的概念及運(yùn)算2、特殊函數(shù):?jiǎn)紊洹M射、雙射的判定.例:設(shè)R是集合A={1,2,….10}上的模3同余關(guān)系,則1、握手定理及應(yīng)用.2、歐拉圖、哈密爾頓圖的判定3、二分圖、完全二分圖的判定第八章例.n個(gè)人參加一個(gè)集會(huì),已知每個(gè)人恰有5個(gè)朋友,問n是奇數(shù)還是偶數(shù)?解:用n個(gè)結(jié)點(diǎn)代表n個(gè)人,兩個(gè)朋友對(duì)應(yīng)的結(jié)點(diǎn)之間連接一邊,如此得到一個(gè)5-正則圖G的數(shù)學(xué)模型。于是由握手定理,假如n為奇數(shù),則所有結(jié)點(diǎn)度數(shù)之和也為奇數(shù),這與握手定理相違,故n必為偶數(shù)。第九章樹1、樹的定義及等價(jià)定義問題:設(shè)是具有個(gè)頂點(diǎn)的樹,問其頂點(diǎn)度數(shù)之和等于多少?2、生成樹的概念任一連通圖都至少有一顆生成樹

溫馨提示

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

評(píng)論

0/150

提交評(píng)論