DOWNLOADING-教學(xué)講解課件

離散數(shù)學(xué)(7)陳斌2011.10.29離散數(shù)學(xué)(7)陳斌1目錄數(shù)理邏輯集合論圖論抽象代數(shù)目錄數(shù)理邏輯2集合論集合代數(shù)集合的基本概念集合運(yùn)算集合的歸納定義關(guān)系有序組和集合的笛卡兒積二元關(guān)系、等價(jià)關(guān)系、序關(guān)系函數(shù)函數(shù)及函數(shù)的合成特殊函數(shù)類(lèi)函數(shù)的逆集合論集合代數(shù)3集合的歸納定義回顧：列舉定義、描述定義歸納定義(inductivedefinition)基礎(chǔ)條款規(guī)定某些元素為待定義集合成員，集合其它元素可以從基本元素出發(fā)逐步確定歸納條款規(guī)定由已確定的集合元素去進(jìn)一步確定其它元素的規(guī)則終極條款規(guī)定待定義集合只含有基礎(chǔ)條款和歸納條款所確定的成員基礎(chǔ)條款和歸納條款稱作“完備性條款”，必須保證毫無(wú)遺漏產(chǎn)生集合中所有成員終極條款又稱“純粹性條款”，保證集合中僅包含滿足完備性條款的那些對(duì)象集合的歸納定義回顧：列舉定義、描述定義4集合的歸納定義歸納定義“圣誕節(jié)”基礎(chǔ)條款耶穌基督降生的那天是圣誕節(jié)歸納條款如果某天是圣誕節(jié)，則這一天后的第365天也是圣誕節(jié)（不考慮閏年）終極條款除了上面兩條所包括的日子，其它日子都不是圣誕節(jié)集合的歸納定義歸納定義“圣誕節(jié)”5集合的歸納定義設(shè)個(gè)體域U為整數(shù)集，歸納定義偶數(shù)集E基礎(chǔ)條款：0∈E歸納條款：若x∈E，則x+2∈E，x-2∈E終極條款：除了有限次使用上述條款確定的元素以外，E中沒(méi)有別的元素奇數(shù)集O的定義？集合的歸納定義設(shè)個(gè)體域U為整數(shù)集，歸納定義偶數(shù)集E6集合的歸納定義歸納定義“程序”基礎(chǔ)條款：v:=e是程序（其中v是變?cè)?，e是算術(shù)表達(dá)式）歸納條款：若p1,p2是程序，則ifcthenp1elsep2endif也是程序（其中c是條件表達(dá)式）；若p是程序，則whilecdopendwhile也是程序；若p1,p2是程序，則p1;p2也是程序終極條款（略）集合的歸納定義歸納定義“程序”7自然數(shù)的定義數(shù)學(xué)中“數(shù)”是最基本的原始概念，在集合論創(chuàng)立之后，采用集合來(lái)定義自然數(shù)，使得數(shù)學(xué)建立在更為簡(jiǎn)單的概念“集合”基礎(chǔ)之上在算術(shù)公理化系統(tǒng)中，皮亞諾(Peano)的5大公理刻畫(huà)了自然數(shù)的概念P1：至少有一個(gè)對(duì)象是自然數(shù)，記做0；P2：如果n是自然數(shù)，那么n必定恰有一個(gè)直接后繼，記做n’P3：0不是任何自然數(shù)的直接后繼P4：如果自然數(shù)m,n的直接后繼m’,n’相同，那么m=nP5：沒(méi)有不滿足上述條件的對(duì)象是自然數(shù)自然數(shù)的定義數(shù)學(xué)中“數(shù)”是最基本的原始概念，在集合論創(chuàng)立之后8自然數(shù)的定義利用集合定義自然數(shù)要考慮的幾個(gè)問(wèn)題找一個(gè)最簡(jiǎn)單的集合作為0找一種集合運(yùn)算定義“直接后繼”∪?∩？－？這種集合運(yùn)算不可能得到0對(duì)應(yīng)的那個(gè)集合可以通過(guò)集合關(guān)系反應(yīng)自然數(shù)的順序性質(zhì)、自然數(shù)的定義利用集合定義自然數(shù)要考慮的幾個(gè)問(wèn)題9自然數(shù)的定義自然數(shù)集N的歸納定義基礎(chǔ)條款：∈N歸納條款：如果x∈N，則x’=x∪{x}∈N終極條款（略）自然數(shù)集的列舉定義{,{},{,{}},{,{},{,{}}},…}實(shí)際上有：1={0},2={0,1},3={0,1,2}0∈1∈2∈3…同時(shí)也有0∈3還有0123…12，410，1010體現(xiàn)了順序關(guān)系，而且子集關(guān)系具有傳遞性自然數(shù)的定義自然數(shù)集N的歸納定義10自然數(shù)的定義如果我們用x’={x}∈N作直接后繼會(huì)如何？{,{},{{}},{{{}}},….}0∈1∈2∈3但是沒(méi)有1∈3遞歸定義自然數(shù)的運(yùn)算：＋、×x＋0＝xx＋y’＝(x＋y)’如：3+2=(3+1)‘=((3+0)’)‘=(3’)‘=4’=5自然數(shù)的定義如果我們用x’={x}∈N作直接后繼會(huì)如何？11自然數(shù)的定義⊙遞歸定義自然數(shù)的運(yùn)算：＋、×x×0＝0x×y’＝(x×y)＋x例子如：3×2＝(3×1)+3=((3×0)+3)+3=(0+3)+3=(0+2)‘+3=((0+1)’)‘＋3=(((0+0)‘)’)‘+3=((0’)‘)’+3=3+3=……=……=6自然數(shù)的定義⊙遞歸定義自然數(shù)的運(yùn)算：＋、×12⊙歸納原理設(shè)集合A是歸納定義的集合，要證明A中所有元素具有性質(zhì)P，即：x(x∈A→P(x))，可以進(jìn)行如下的證明：（歸納基礎(chǔ)）針對(duì)歸納定義的基礎(chǔ)條款，證明基礎(chǔ)條款中的所有元素均使P(x0)真（歸納推理）證明歸納條款是“保持性質(zhì)P的”，即在假設(shè)歸納條款中已確定元素x使P(x)真的前提下，證明用歸納條款中的操作g所生成的g(x)依然有性質(zhì)P，即P(g(x))為真⊙歸納原理設(shè)集合A是歸納定義的集合，要證明A中所有元素具有性13歸納原理證明：命題公式中左括號(hào)的數(shù)量等于右括號(hào)的數(shù)量設(shè)L[A],R[A]分別表示公式A的左括號(hào)數(shù)量和右括號(hào)的數(shù)量（歸納基礎(chǔ)）：對(duì)于命題變?cè)?或常元)p，L[p]=R[p]=0（歸納推理）：設(shè)L[A]=R[A],L[B]=R[B]，那么L[(?A)]=L[A]+1=R[A]+1=R[(?A)]L[(A→B)]=L[A]+L[B]+1=R[A]+R[B]+1=R[(A→B)]所以對(duì)于一切命題公式，左括號(hào)數(shù)量等于右括號(hào)數(shù)量歸納原理證明：命題公式中左括號(hào)的數(shù)量等于右括號(hào)的數(shù)量14歸納原理既然自然數(shù)集合也是歸納定義的，對(duì)于自然數(shù)的一些性質(zhì)，也可以通過(guò)歸納原理來(lái)證明即我們通常用的“數(shù)學(xué)歸納法”第一數(shù)學(xué)歸納法歸納基礎(chǔ)：證明P(0)為真歸納過(guò)程：對(duì)于任意k≥0假設(shè)P(k)為真時(shí)，推出P(k+1)也為真結(jié)論：所有自然數(shù)n都使P(n)為真歸納原理既然自然數(shù)集合也是歸納定義的，對(duì)于自然數(shù)的一些性質(zhì)，15歸納原理證明對(duì)任意自然數(shù)有(0+1+2+…+n)2=03+13+23+…+n3歸納基礎(chǔ)：當(dāng)n=0，02=03歸納過(guò)程設(shè)當(dāng)n=k時(shí)，(0+1+2+…+k)2=03+13+23+…+k3成立，當(dāng)n=k+1時(shí)，(0+1+2+…+k+(k+1))2=03+13+23+…+k3+(k+1)2+2(0+1+2+…+k)(k+1)=03+13+23+…+k3+(k+1)2+k(k+1)2=03+13+23+…+k3+(k+1)3歸納完成，命題得證※歸納原理證明對(duì)任意自然數(shù)有(0+1+2+…+n)2=03+116歸納原理起始于任意自然數(shù)n0的數(shù)學(xué)歸納法證明所有大于等于n0的自然數(shù)都具有性質(zhì)P起始于多個(gè)自然數(shù)的數(shù)學(xué)歸納法歸納基礎(chǔ)：證明P(0),P(1)真歸納過(guò)程：對(duì)于任意k≥0假設(shè)P(k)為真時(shí)，推出P(k+2)也為真結(jié)論：所有自然數(shù)具有性質(zhì)P推廣到起始于多個(gè)自然數(shù)歸納原理起始于任意自然數(shù)n0的數(shù)學(xué)歸納法17歸納原理證明：3分幣和5分幣可以組成8分以上任何幣值8=3+5;9=3+3+3;10=5+5假設(shè)k可以用3分和5分幣組成，需要證明k+3時(shí)命題真，這是顯然的，只要再加一個(gè)3分幣即可允許有參變量的數(shù)學(xué)歸納法對(duì)于二元謂詞P(m,n)，證明對(duì)于一切自然數(shù)m,n都為真，可以只對(duì)一個(gè)變量進(jìn)行歸納，另一個(gè)作為參數(shù)歸納原理證明：3分幣和5分幣可以組成8分以上任何幣值18歸納原理數(shù)學(xué)歸納法的正確性證明假設(shè)我們已經(jīng)完成下面的推理歸納基礎(chǔ)：P(0)真；歸納推理：k(P(k)→P(k+1))但是還并非所有自然數(shù)都有性質(zhì)P將這些不滿足性質(zhì)P的自然數(shù)構(gòu)成一個(gè)非空自然數(shù)子集，這樣，子集中必定有一個(gè)最小的自然數(shù)，設(shè)為m顯然m>0，記做n+1，這樣n一定具有性質(zhì)P，即P(n)為真n(P(n)∧?P(n+1))╞╡?k(?P(k)∨P(k+1))╞╡?k(P(k)→P(k+1))假設(shè)推理結(jié)果與已經(jīng)完成的歸納推理矛盾，所以假設(shè)錯(cuò)誤所有自然數(shù)都有性質(zhì)P歸納原理數(shù)學(xué)歸納法的正確性證明19關(guān)于課程教材[O158/75]計(jì)算機(jī)科學(xué)中的離散結(jié)構(gòu)王元元,張桂蕓編著，機(jī)械工業(yè)出版社2019[O158/60]離散數(shù)學(xué)導(dǎo)論王元元,張桂蕓編著，科學(xué)出版社2019[O158/36]離散數(shù)學(xué)王元元,李尚奮編著，科學(xué)出版社1994關(guān)于課程教材[O158/75]計(jì)算機(jī)科學(xué)中的離散結(jié)構(gòu)20END特殊符號(hào)表∴,∵,╞═╡,╞═,∈,≠,∑,↓,∪,∩,╞,┠PCαΑ,βΒ,γΓ,δΔ,εΕ,ζΖ,ηΗ,θΘ,ιΙ,κΚ,λΛ,μΜ,νΝ,ξΞ,οΟ,πΠ,ρΡ,??,σΣ,τΤ,υΥ,φΦ,χΧ,ψΨ,ωΩ{?,∧,∨,→,?}≦≧≠≤?END特殊符號(hào)表21離散數(shù)學(xué)(7)陳斌2011.10.29離散數(shù)學(xué)(7)陳斌22目錄數(shù)理邏輯集合論圖論抽象代數(shù)目錄數(shù)理邏輯23集合論集合代數(shù)集合的基本概念集合運(yùn)算集合的歸納定義關(guān)系有序組和集合的笛卡兒積二元關(guān)系、等價(jià)關(guān)系、序關(guān)系函數(shù)函數(shù)及函數(shù)的合成特殊函數(shù)類(lèi)函數(shù)的逆集合論集合代數(shù)24集合的歸納定義回顧：列舉定義、描述定義歸納定義(inductivedefinition)基礎(chǔ)條款規(guī)定某些元素為待定義集合成員，集合其它元素可以從基本元素出發(fā)逐步確定歸納條款規(guī)定由已確定的集合元素去進(jìn)一步確定其它元素的規(guī)則終極條款規(guī)定待定義集合只含有基礎(chǔ)條款和歸納條款所確定的成員基礎(chǔ)條款和歸納條款稱作“完備性條款”，必須保證毫無(wú)遺漏產(chǎn)生集合中所有成員終極條款又稱“純粹性條款”，保證集合中僅包含滿足完備性條款的那些對(duì)象集合的歸納定義回顧：列舉定義、描述定義25集合的歸納定義歸納定義“圣誕節(jié)”基礎(chǔ)條款耶穌基督降生的那天是圣誕節(jié)歸納條款如果某天是圣誕節(jié)，則這一天后的第365天也是圣誕節(jié)（不考慮閏年）終極條款除了上面兩條所包括的日子，其它日子都不是圣誕節(jié)集合的歸納定義歸納定義“圣誕節(jié)”26集合的歸納定義設(shè)個(gè)體域U為整數(shù)集，歸納定義偶數(shù)集E基礎(chǔ)條款：0∈E歸納條款：若x∈E，則x+2∈E，x-2∈E終極條款：除了有限次使用上述條款確定的元素以外，E中沒(méi)有別的元素奇數(shù)集O的定義？集合的歸納定義設(shè)個(gè)體域U為整數(shù)集，歸納定義偶數(shù)集E27集合的歸納定義歸納定義“程序”基礎(chǔ)條款：v:=e是程序（其中v是變?cè)琫是算術(shù)表達(dá)式）歸納條款：若p1,p2是程序，則ifcthenp1elsep2endif也是程序（其中c是條件表達(dá)式）；若p是程序，則whilecdopendwhile也是程序；若p1,p2是程序，則p1;p2也是程序終極條款（略）集合的歸納定義歸納定義“程序”28自然數(shù)的定義數(shù)學(xué)中“數(shù)”是最基本的原始概念，在集合論創(chuàng)立之后，采用集合來(lái)定義自然數(shù)，使得數(shù)學(xué)建立在更為簡(jiǎn)單的概念“集合”基礎(chǔ)之上在算術(shù)公理化系統(tǒng)中，皮亞諾(Peano)的5大公理刻畫(huà)了自然數(shù)的概念P1：至少有一個(gè)對(duì)象是自然數(shù)，記做0；P2：如果n是自然數(shù)，那么n必定恰有一個(gè)直接后繼，記做n’P3：0不是任何自然數(shù)的直接后繼P4：如果自然數(shù)m,n的直接后繼m’,n’相同，那么m=nP5：沒(méi)有不滿足上述條件的對(duì)象是自然數(shù)自然數(shù)的定義數(shù)學(xué)中“數(shù)”是最基本的原始概念，在集合論創(chuàng)立之后29自然數(shù)的定義利用集合定義自然數(shù)要考慮的幾個(gè)問(wèn)題找一個(gè)最簡(jiǎn)單的集合作為0找一種集合運(yùn)算定義“直接后繼”∪?∩？－？這種集合運(yùn)算不可能得到0對(duì)應(yīng)的那個(gè)集合可以通過(guò)集合關(guān)系反應(yīng)自然數(shù)的順序性質(zhì)、自然數(shù)的定義利用集合定義自然數(shù)要考慮的幾個(gè)問(wèn)題30自然數(shù)的定義自然數(shù)集N的歸納定義基礎(chǔ)條款：∈N歸納條款：如果x∈N，則x’=x∪{x}∈N終極條款（略）自然數(shù)集的列舉定義{,{},{,{}},{,{},{,{}}},…}實(shí)際上有：1={0},2={0,1},3={0,1,2}0∈1∈2∈3…同時(shí)也有0∈3還有0123…12，410，1010體現(xiàn)了順序關(guān)系，而且子集關(guān)系具有傳遞性自然數(shù)的定義自然數(shù)集N的歸納定義31自然數(shù)的定義如果我們用x’={x}∈N作直接后繼會(huì)如何？{,{},{{}},{{{}}},….}0∈1∈2∈3但是沒(méi)有1∈3遞歸定義自然數(shù)的運(yùn)算：＋、×x＋0＝xx＋y’＝(x＋y)’如：3+2=(3+1)‘=((3+0)’)‘=(3’)‘=4’=5自然數(shù)的定義如果我們用x’={x}∈N作直接后繼會(huì)如何？32自然數(shù)的定義⊙遞歸定義自然數(shù)的運(yùn)算：＋、×x×0＝0x×y’＝(x×y)＋x例子如：3×2＝(3×1)+3=((3×0)+3)+3=(0+3)+3=(0+2)‘+3=((0+1)’)‘＋3=(((0+0)‘)’)‘+3=((0’)‘)’+3=3+3=……=……=6自然數(shù)的定義⊙遞歸定義自然數(shù)的運(yùn)算：＋、×33⊙歸納原理設(shè)集合A是歸納定義的集合，要證明A中所有元素具有性質(zhì)P，即：x(x∈A→P(x))，可以進(jìn)行如下的證明：（歸納基礎(chǔ)）針對(duì)歸納定義的基礎(chǔ)條款，證明基礎(chǔ)條款中的所有元素均使P(x0)真（歸納推理）證明歸納條款是“保持性質(zhì)P的”，即在假設(shè)歸納條款中已確定元素x使P(x)真的前提下，證明用歸納條款中的操作g所生成的g(x)依然有性質(zhì)P，即P(g(x))為真⊙歸納原理設(shè)集合A是歸納定義的集合，要證明A中所有元素具有性34歸納原理證明：命題公式中左括號(hào)的數(shù)量等于右括號(hào)的數(shù)量設(shè)L[A],R[A]分別表示公式A的左括號(hào)數(shù)量和右括號(hào)的數(shù)量（歸納基礎(chǔ)）：對(duì)于命題變?cè)?或常元)p，L[p]=R[p]=0（歸納推理）：設(shè)L[A]=R[A],L[B]=R[B]，那么L[(?A)]=L[A]+1=R[A]+1=R[(?A)]L[(A→B)]=L[A]+L[B]+1=R[A]+R[B]+1=R[(A→B)]所以對(duì)于一切命題公式，左括號(hào)數(shù)量等于右括號(hào)數(shù)量歸納原理證明：命題公式中左括號(hào)的數(shù)量等于右括號(hào)的數(shù)量35歸納原理既然自然數(shù)集合也是歸納定義的，對(duì)于自然數(shù)的一些性質(zhì)，也可以通過(guò)歸納原理來(lái)證明即我們通常用的“數(shù)學(xué)歸納法”第一數(shù)學(xué)歸納法歸納基礎(chǔ)：證明P(0)為真歸納過(guò)程：對(duì)于任意k≥0假設(shè)P(k)為真時(shí)，推出P(k+1)也為真結(jié)論：所有自然數(shù)n都使P(n)為真歸納原理既然自然數(shù)集合也是歸納定義的，對(duì)于自然數(shù)的一些性質(zhì)，36歸納原理證明對(duì)任意自然數(shù)有(0+1+2+…+n)2=03+13+23+…+n3歸納基礎(chǔ)：當(dāng)n=0，02=03歸納過(guò)程設(shè)當(dāng)n=k時(shí)，(0+1+2+…+k)2=03+13+23+…+k3成立，當(dāng)n=k+1時(shí)，(0+1+2+…+k+(k+1))2=03+13+23+…+k3+(k+1)2+2(0+1+2+…+k)(k+1)=03+13+23+…+k3+(k+1)2+k(k+1)2=03+13+23+…+k3+(k+1)3歸納完成，命題得證※歸納原理證明對(duì)任意自然數(shù)有(0+1+2+…+n)2=03+137歸納原理起始于任意自然數(shù)n0的數(shù)學(xué)歸納法證明所有大于等于n0的自然數(shù)都具有性質(zhì)P起始于多個(gè)自然數(shù)的數(shù)學(xué)歸納法歸納基礎(chǔ)：證明P(0),P(1)真歸納過(guò)程：對(duì)于任意k≥0假設(shè)P(k)為真時(shí)，推出P(k+2)也為真結(jié)論：所有自然數(shù)具有性質(zhì)P推廣到起始于多個(gè)自然數(shù)歸納原理起始于任意自然數(shù)n0的數(shù)學(xué)歸納法38歸納原理證明：3分幣和5分幣可以組成8分以上任何幣值8=3+5;9