離散第2講 廣義并交、笛卡爾、歸納定義（優(yōu)選課資）

1、 計(jì)算機(jī)專業(yè)基礎(chǔ)課程計(jì)算機(jī)專業(yè)基礎(chǔ)課程授課人：梁妍授課人：梁妍vPowerPoint Template_Sub 1.1集合的概念與表示集合的概念與表示1.2集合運(yùn)算集合運(yùn)算1.3集合的歸納定義集合的歸納定義-2-優(yōu)制課程優(yōu)制課程v集合運(yùn)算與歸納定義集合運(yùn)算與歸納定義 Page 7 to 13 Page 7 to 13離散數(shù)學(xué)離散數(shù)學(xué)第第2 2講講v內(nèi)容提要內(nèi)容提要集合的運(yùn)算集合的運(yùn)算廣義并、廣義交運(yùn)算廣義并、廣義交運(yùn)算序偶和序偶和n元有序組元有序組笛卡爾積笛卡爾積集合的歸納定義集合的歸納定義集合的歸納定義方法集合的歸納定義方法集合定義的自然數(shù)集合定義的自然數(shù)-4-優(yōu)制課程優(yōu)制課程v集合族的概念

2、集合族的概念 定義定義1.7：稱每個(gè)元素都是集合的集合為稱每個(gè)元素都是集合的集合為集合族集合族（collection）。）。 若集合族若集合族C可表示為可表示為C = Sd | d D ，則稱，則稱D為為集合族集合族C的的標(biāo)志集標(biāo)志集（index set）。）。C = 0, 0, 1, 0, 1, 2, C = Nd | d I+ -5-優(yōu)制課程優(yōu)制課程v集合的廣義并和廣義交集合的廣義并和廣義交定義定義1.8：設(shè)設(shè)C為非空集合族為非空集合族（1）C = x | 存在某個(gè)存在某個(gè)S，滿足，滿足S C并且并且x S C稱為稱為C的的廣義并廣義并 (C中所有集合的并)（2）C = x | 對(duì)任意的對(duì)

3、任意的S，如果，如果S C則一定有則一定有x S C稱為稱為C的的廣義交廣義交(C中所有集合的交)例如例如C = 0, 0, 1, 0, 1, 2, C = N, C = 0C = Nd | d I+，C = , C = 1dddIdNN-6-優(yōu)制課程優(yōu)制課程v廣義并、交運(yùn)算實(shí)例廣義并、交運(yùn)算實(shí)例A, B = A BA, B = A BA, B, C = A B CA, B, C = A B C = = , = , = , A =A , A = -7-優(yōu)制課程優(yōu)制課程v序偶序偶(ordered pairs)(ordered pairs)如何在集合的基礎(chǔ)上定義出如何在集合的基礎(chǔ)上定義出次序次序的

4、概念？的概念？定義定義1.9：設(shè)設(shè)a, b為任意對(duì)象，稱集合為任意對(duì)象，稱集合a, a, b為二元有序組，或?yàn)槎行蚪M，或序偶序偶，簡(jiǎn)記作，簡(jiǎn)記作。其中。其中a稱稱為序偶為序偶的的第一分量第一分量，b稱為序偶的稱為序偶的第二第二分量分量。定理定理1.17：對(duì)任意序偶對(duì)任意序偶, ， =當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a=c且且b=d?？梢允菃蝹€(gè)客體，可以是單個(gè)客體，集合，甚至序偶集合，甚至序偶-8-優(yōu)制課程優(yōu)制課程vn n元有序組元有序組定義定義1.10： n元有序組元有序組可以從二元可以從二元有序組（序偶）出發(fā)，遞歸地定義如下有序組（序偶）出發(fā)，遞歸地定義如下 = a1, a1, a2 = , a3 =

5、, an其中其中ai稱為稱為n元有序組的元有序組的第第i分量分量本質(zhì)上，本質(zhì)上，n元有序組依然是序偶元有序組依然是序偶定理定理1.18：對(duì)任意對(duì)象對(duì)任意對(duì)象a1, a2, , an，b1, b2, , bn， = 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)a1=b1，a2=b2，an=bn-9-優(yōu)制課程優(yōu)制課程v集合的笛卡爾積集合的笛卡爾積 定義定義1.11：對(duì)任意集合對(duì)任意集合A1, A2，A1 A2叫做叫做A1, A2的的笛卡爾積笛卡爾積，定義如下：，定義如下：A1 A2 = | x A1，y A2說(shuō)明說(shuō)明 運(yùn)算是左結(jié)合的運(yùn)算是左結(jié)合的A1 A2 An = (A1 A2 An1) An當(dāng)當(dāng)A1=A2=An=A時(shí)，時(shí)

6、，A1 A2 An記作記作An A1 A2 An = | a1 A1，, an An-10-優(yōu)制課程優(yōu)制課程v笛卡爾積運(yùn)算舉例笛卡爾積運(yùn)算舉例例例1.10 A=1, 2, B=a, b, c, C=, R為實(shí)數(shù)集為實(shí)數(shù)集AB，BAABC， A(BC)A， AR2， R3-11-優(yōu)制課程優(yōu)制課程v笛卡兒積的性質(zhì)笛卡兒積的性質(zhì) 定理定理1.20 設(shè)設(shè)A、B、C為任意集合，為任意集合， 表示表示，或或運(yùn)算，那么：運(yùn)算，那么：A (B C) = (A B) (A C) (B C) A = (B A) (C A) 定理定理1.21 對(duì)任意有限集合對(duì)任意有限集合A1, A2, , An，有：，有：|A1

7、A2 An| = |A1|A2|An|-12-優(yōu)制課程優(yōu)制課程vPowerPoint Template_Sub 1.1集合的概念與表示集合的概念與表示1.2集合運(yùn)算集合運(yùn)算1.3集合的歸納定義集合的歸納定義-13-優(yōu)制課程優(yōu)制課程v集合的表示方法集合的表示方法列舉法列舉法描述法描述法試定義算術(shù)表達(dá)式的集合試定義算術(shù)表達(dá)式的集合SS = 123, 55, 1+2, 100， (993)10, ?S = x | x是一算術(shù)表達(dá)式是一算術(shù)表達(dá)式 ?(1) 如果如果x是整數(shù)，則是整數(shù)，則x S（是算術(shù)表達(dá)式是算術(shù)表達(dá)式） (2) 如果如果x, y S ，則，則(+ x) 、( x) 、(x + y)

8、、(x y) 、(x y) 、(xy) 均均 S （均（均是算術(shù)表達(dá)式是算術(shù)表達(dá)式） (3)只有有限次應(yīng)用條款只有有限次應(yīng)用條款1、2所得的符號(hào)序列所得的符號(hào)序列 S以上第三種定義方法稱為歸納法以上第三種定義方法稱為歸納法-14-優(yōu)制課程優(yōu)制課程v集合的歸納定義集合的歸納定義(inductive definition) (inductive definition) 一個(gè)集合的一個(gè)集合的歸納定義歸納定義由三部分組成：由三部分組成：1、基礎(chǔ)條款：基礎(chǔ)條款： 指出某些元素屬于欲定義之集合；指出某些元素屬于欲定義之集合； 奠基，確定集合的基本成員，其他成員可以此為基礎(chǔ)逐奠基，確定集合的基本成員，其他成

9、員可以此為基礎(chǔ)逐步確定。一般來(lái)講要求基礎(chǔ)集合盡可能的小。步確定。一般來(lái)講要求基礎(chǔ)集合盡可能的小。2、歸納條款：歸納條款： 指出由已確定元素構(gòu)造新元素的規(guī)則；指出由已確定元素構(gòu)造新元素的規(guī)則； 從基本元素出發(fā)，反復(fù)運(yùn)用這些規(guī)則，可得到欲定義之從基本元素出發(fā)，反復(fù)運(yùn)用這些規(guī)則，可得到欲定義之集合的所有成員。集合的所有成員。3、終極條款：終極條款： 斷定只有有限次應(yīng)用條款斷定只有有限次應(yīng)用條款1、2所得元素所得元素才是欲定義之集合的元素。才是欲定義之集合的元素。 保證整個(gè)定義過(guò)程所規(guī)定的集合只包括滿足要求的那些保證整個(gè)定義過(guò)程所規(guī)定的集合只包括滿足要求的那些對(duì)象。對(duì)象。完備性條款完備性條款純粹性條款

10、純粹性條款-15-優(yōu)制課程優(yōu)制課程v歸納定義舉例歸納定義舉例 例例1.11 歸納定義偶數(shù)集合歸納定義偶數(shù)集合E+基礎(chǔ)條款：基礎(chǔ)條款：0 E+歸納條款：如果歸納條款：如果x E+，那么，那么x+2 E+ 如果如果x E+，那么，那么x-2 E+終極條款：只有有限次應(yīng)用條款終極條款：只有有限次應(yīng)用條款1、2所得元素才是所得元素才是E+的元素的元素 -16-優(yōu)制課程優(yōu)制課程v與形式語(yǔ)言有關(guān)的一些概念與形式語(yǔ)言有關(guān)的一些概念字母表：字母表：指有限非空的符號(hào)的集合，一般用指有限非空的符號(hào)的集合，一般用 表示表示二進(jìn)制基數(shù)的集合二進(jìn)制基數(shù)的集合 =0，126個(gè)英文字母定義的集合個(gè)英文字母定義的集合 =a,

11、 b, c, , x, y, z 字：字：指有限數(shù)目的符號(hào)所組成的串，若每一符號(hào)均取自字指有限數(shù)目的符號(hào)所組成的串，若每一符號(hào)均取自字母表母表 之上，則稱為字母表之上，則稱為字母表 之上的一個(gè)字，用之上的一個(gè)字，用 表示空字表示空字 01，100，101， a, aa, bike, iwefhweoi, .字的運(yùn)算：字的運(yùn)算：毗連毗連（或并置）（或并置） x=01, y=100, x與與y的毗連的毗連xy=01100 x=apple, y= , x與與y的毗連的毗連xy=apple-17-優(yōu)制課程優(yōu)制課程v歸納定義歸納定義字的概念字的概念 是一個(gè)字母表，是一個(gè)字母表， +是是 上字的集合上字的

12、集合。 +的歸納定義：的歸納定義：1、基礎(chǔ)條款：如果、基礎(chǔ)條款：如果a，則，則a+（或（或+）2、歸納條款：如果、歸納條款：如果x+且且，則，則 x+3、終極條款：只有有限次應(yīng)用條款、終極條款：只有有限次應(yīng)用條款1、2所得之元素才所得之元素才是是 +之元素之元素例如例如 = 0，1 +=0，1，00，01，10，11，000，001，010，011， -18-優(yōu)制課程優(yōu)制課程v歸納定義歸納定義 * * *= + *可歸納定義如下：可歸納定義如下：1、基礎(chǔ)條款：、基礎(chǔ)條款：*2、歸納條款：如果、歸納條款：如果x*且且 ，則，則 x*3、終極條款：只有有限次應(yīng)用條款、終極條款：只有有限次應(yīng)用條款1

13、、2所得之元素才所得之元素才是是 *之元素之元素對(duì)于某個(gè)字母表對(duì)于某個(gè)字母表 ，如果如果L *，則，則L稱為稱為 上的上的一個(gè)一個(gè)形式語(yǔ)言形式語(yǔ)言(formal language)-19-優(yōu)制課程優(yōu)制課程v歸納定義字頭和字尾歸納定義字頭和字尾字字w的的字頭字頭w可以歸納定義如下：可以歸納定義如下：1、基礎(chǔ)條款：、基礎(chǔ)條款： 是是w的字頭的字頭2、歸納條款：如果、歸納條款：如果w為為w的字頭，且的字頭，且w = w w”（其中（其中 ，w、 w” *），則），則w 也是也是w的字頭的字頭3、終極條款：只有有限次應(yīng)用條款、終極條款：只有有限次應(yīng)用條款1、2所得之元素才是所得之元素才是w的字頭的字頭

14、若字若字w=0100011，則，則w的字頭有哪些？的字頭有哪些？若若w為為w的字頭，且的字頭，且w=ww，則，則w稱為稱為w的的字尾字尾請(qǐng)歸納定義字尾的概念請(qǐng)歸納定義字尾的概念-20-優(yōu)制課程優(yōu)制課程v自然數(shù)自然數(shù)從本質(zhì)上看自然數(shù)是滿足下列特性的一列符號(hào)：從本質(zhì)上看自然數(shù)是滿足下列特性的一列符號(hào)：它們中有一個(gè)為首的符號(hào)它們中有一個(gè)為首的符號(hào)每個(gè)符號(hào)都有且僅有一個(gè)直接后繼符號(hào)每個(gè)符號(hào)都有且僅有一個(gè)直接后繼符號(hào)為首的符號(hào)不是任何符號(hào)的直接后繼符號(hào)為首的符號(hào)不是任何符號(hào)的直接后繼符號(hào)沒(méi)有兩個(gè)符號(hào)具有相同的直接后繼符號(hào)沒(méi)有兩個(gè)符號(hào)具有相同的直接后繼符號(hào)自然數(shù)僅指這列符號(hào)中的符號(hào)自然數(shù)僅指這列符號(hào)中的符

15、號(hào)-21-優(yōu)制課程優(yōu)制課程v皮亞諾五公理皮亞諾五公理皮亞諾（皮亞諾（Peano）用）用五條公理五條公理刻畫(huà)自然數(shù)的概念刻畫(huà)自然數(shù)的概念P1. 至少有一個(gè)客體是自然數(shù)，記為至少有一個(gè)客體是自然數(shù)，記為0P2. 如果如果n是自然數(shù)，那么是自然數(shù)，那么n必定恰有一個(gè)直接必定恰有一個(gè)直接后繼，記為后繼，記為nP3. 0不是任何自然數(shù)的直接后繼不是任何自然數(shù)的直接后繼P4. 如果自然數(shù)如果自然數(shù)m，n的直接后繼的直接后繼m，n相同，相同，則則m = nP5. 沒(méi)有不滿足上述條件的客體是自然數(shù)沒(méi)有不滿足上述條件的客體是自然數(shù)-22-優(yōu)制課程優(yōu)制課程v歸納定義自然數(shù)歸納定義自然數(shù)歸納定義條款歸納定義條款0N

16、如果如果xN，則，則x + 1N除有限次應(yīng)用上述條款得到的元素外，除有限次應(yīng)用上述條款得到的元素外，N中無(wú)中無(wú)其它元素其它元素能否作為自然數(shù)的定義？能否作為自然數(shù)的定義？0是什么？是什么？+又是什么？又是什么？-23-優(yōu)制課程優(yōu)制課程v用集合定義自然數(shù)用集合定義自然數(shù)為在集合論中定義自然數(shù)，首先要選擇為在集合論中定義自然數(shù)，首先要選擇一個(gè)集合一個(gè)集合作為為首作為為首的那個(gè)自然數(shù)，然后要確定的那個(gè)自然數(shù)，然后要確定一種集合運(yùn)算一種集合運(yùn)算作為求直接后繼作為求直接后繼的運(yùn)算的運(yùn)算用用作為起始自然數(shù)作為起始自然數(shù)，用如下定義的運(yùn)算作為，用如下定義的運(yùn)算作為求直接后繼求直接后繼運(yùn)算運(yùn)算定義定義6：設(shè)設(shè)A是任意集合，稱集合是任意集合，稱集合 A為為A的的直接后繼集合直接后繼集合，如果如果 A = AA = = = = , , = , , = , , , -24-優(yōu)制課程優(yōu)制課程v用集合定義自然數(shù)用集合定義自然數(shù)自然數(shù)的歸納定義自然數(shù)的歸納定義基礎(chǔ)條款：基礎(chǔ)條款：N歸納條款：如果歸納條款：如果x N，則，則x= xx N終極條款（略）終極條款（略）N=, , , , , , , , 把把記作記作0，則，則N=0, 0, 0, 0, 可以證明，如此定義的自然數(shù)可以證明，如此定義的自然數(shù)滿足