邏輯集合與計(jì)數(shù)原理課件

邏輯、集合與計(jì)數(shù)原理數(shù)99丙曾子軒張郁苓李承修邏輯、集合與計(jì)數(shù)原理數(shù)99丙曾子軒張郁苓李主題內(nèi)容一、簡單的邏輯概念：介紹「或」、「且」、「否定」及笛摩根定律二、集合的定義、集合的表示法與操作三、基本計(jì)數(shù)原理四、加法原理、乘法原理、取捨原理主題內(nèi)容一、簡單的邏輯概念：介紹「或」、「且」、「否定」及笛一、簡單的邏輯概念“若P則Q”成立時，P稱為Q的充分條件，Q稱為P的必要條件；以符號P

Q表示命題“若P則Q”成立?如果命題“若P則Q”與其逆命題“若Q則P”皆成立，則P是Q的充要條件，而Q也是P的充要條件，以符號P

Q表示一、簡單的邏輯概念“若P則Q”成立時，P稱為Q的充分條件，命題介紹原命題：P

Q逆命題：Q

P否定命題：～P～Q否逆命題：～Q～P原命題與否逆命題同真假逆命題與否定命題同真假命題介紹原命題：PQ或與且“且”代表兩個條件必須同時成立；“或”則代表兩個條件中只要有一個條件成立即可(如果這兩個條件都成立也可以)例1.“x=0且x=2”代表x“同時是0，又是2”，此為一個不能成立的命題例2.“x≥2”代表”x>2或x=2”，因此“2≥2”是一個正確的命題或與且“且”代表兩個條件必須同時成立；“或”則代表兩個條件中笛摩根定律(A∩B)’=A’∪B’ABSABSABS(A∩B)’A’∪B’笛摩根定律(A∩B)’=A’∪B’ABSABSABS(A∩B笛摩根定律(A∪B)’=A’∩B’ABSABSABS(A∪B)’A’∩B’笛摩根定律(A∪B)’=A’∩B’ABSABSABS(A∪B二、何謂集合？集合的定義，最簡單的說法，即是在最原始的集合論樸素集合論中的定義，集合就是”一堆東西”集合裡的“東西”，叫作元素習(xí)慣上，我們會用大小寫字母來代表集合或元素稱為空集合，即集合內(nèi)沒有任何元素我們一般習(xí)慣把集合畫成圖形來說明一些集合關(guān)係，其圖形稱作文氏圖二、何謂集合？集合的定義，最簡單的說法，即是在最原始的集合論常用名詞Part1若x為集合A的元素，則稱x屬於A，記作若集合A中的所有元素皆為集合B中的元素，則稱A包含於B，記作。此時稱A是B的子集舉例來說，若N所有正整數(shù)所成的集合，Z是所有整數(shù)所成的集合，則且常用名詞Part1若x為集合A的元素，則稱x屬於A，記作常用名詞Part2交集：若A、B為兩集合，則集合內(nèi)的元素為為A且B的元素，以圖形來看就是下圖兩圓相交的區(qū)域。AB常用名詞Part2交集：若A、B為兩集合，則集合內(nèi)常用名詞Part3聯(lián)集：若A、B為兩集合，則集合內(nèi)的元素為為A或B的元素，以圖形來看就是下圖兩圓所包含的所有區(qū)域。AB常用名詞Part3聯(lián)集：若A、B為兩集合，則集合常用名詞Part4差集：若A、B為兩集合，則集合定義為。例：則常用名詞Part4差集：若A、B為兩集合，則集合常用名詞Part5乘積集合：兩個集合X和Y的乘積集合（Cartesianproduct），表示為X×Y，是其第一個構(gòu)件是X的成員而第二個構(gòu)件是Y的一個成員的所有可能的有序?qū)Γ撼Ｓ妹~Part5乘積集合：兩個集合X和Y的乘積集合（C三、基本計(jì)數(shù)原理窮舉法樹狀圖三、基本計(jì)數(shù)原理窮舉法窮舉法Whatis窮舉Howto窮舉：

※使用時機(jī)

※好的例子＆不好的例子窮舉方法：

順序窮舉/排列窮舉/組合窮舉窮舉法Whatis窮舉Whatis窮舉遇到一個問題…列出問題的所有可能解根據(jù)題目條件逐個判定滿足條件→

得到一個解Whatis窮舉遇到一個問題…窮舉–使用時機(jī)問題可能解的個數(shù)不是特別大答案的變化具有一定的規(guī)律性窮舉–使用時機(jī)問題可能解的個數(shù)不是特別大窮舉法的範(fàn)例給定不考慮運(yùn)算優(yōu)先順序的4個算數(shù)符號

＋－×÷輸入任5個正整數(shù)A1

A2

A3

A4

A5在每個相鄰的正整數(shù)間填入一個上述的算數(shù)符號，構(gòu)成一個算數(shù)表達(dá)式給定一個M，使該算數(shù)表達(dá)式剛好為M求出，所有可能的算數(shù)表達(dá)式窮舉法的範(fàn)例給定不考慮運(yùn)算優(yōu)先順序的4個算數(shù)符號

＋－×窮舉法的範(fàn)例(cont.)A1(+-x÷)A2(+-x÷)A3(+-x÷)A4(+-x÷)A5最多僅有44種解法有規(guī)律：4個位置所要填的算數(shù)符號

用＋－×÷去填充

→

用一個4重迴圈，即可以完成窮舉法的範(fàn)例(cont.)A1(+-x÷)A2(+-x÷不適用窮舉的例子給定一個正數(shù)的集合

A={a1,a2,a3,…an},(n≦30)4個算數(shù)符號＋－×÷不考慮運(yùn)算優(yōu)先順序從A中選取若干的元素，用上述算數(shù)符號連結(jié)起來成一個表達(dá)式給定一個M，求出，以最少的運(yùn)算次數(shù)可以產(chǎn)生M的算數(shù)表達(dá)式不適用窮舉的例子給定一個正數(shù)的集合

A={a1,a2,不適用窮舉的例子(cont)※此例與上個例子均為根據(jù)結(jié)果來組合表達(dá)式，不同的是：集合A中的個數(shù)和順序選取無法確定→

無法用固定的循環(huán)來控制和窮舉→

適合用搜索回朔法不適用窮舉的例子(cont)※此例與上個例子均為根據(jù)結(jié)果來組窮舉的方法排列窮舉/組合窮舉＊利用數(shù)學(xué)中排列組合的知識，產(chǎn)生出問題的答案的所有可能解，根據(jù)題設(shè)中答案的檢驗(yàn)條件去判斷是否有滿足的答案。順序窮舉＊將問題的答案範(fàn)圍內(nèi)所有情況與自然數(shù)建立起一個一一對應(yīng)的關(guān)係，從而可以按自然數(shù)的變化順序去窮舉問題的所有可能解。

窮舉的方法排列窮舉/組合窮舉樹狀圖處理離散事物的計(jì)數(shù)時，依問題的特性，適當(dāng)?shù)姆诸?，以樹狀的圖形結(jié)構(gòu)表示，此圖形稱樹狀圖樹狀圖處理離散事物的計(jì)數(shù)時，依問題的特性，適當(dāng)?shù)姆诸?，以樹狀樹狀圖圖例賓客親戚朋友大伯家4人林家3人李家2人王家4人姑媽家4人二伯家2人樹狀圖圖例賓客親戚朋友大伯家4人林家3人李家2人王家四、加法原理、乘法原理、取捨原理加法原理乘法原理取捨原理四、加法原理、乘法原理、取捨原理加法原理何謂加法原理加法原理：若A與B是不相交的有限集合，則

|A

B|=|A|+|B|。例：從甲地到乙地有飛機(jī)、火車與巴士等三種交通工具可到達(dá),其中飛機(jī)每天有3班,火車每天有15班，巴士每天25班，若A先生欲從甲地至乙地，很明顯地，此問題的A先生只能選擇一種交通工具的某個班次，故共有3+15+25=43個交通班次可選擇。何謂加法原理加法原理：若A與B是不相交的有限集合，則|A何謂乘法原理乘法原理：假設(shè)A與B是不相交的有限集合，則|A

B|=|A|

|B|例：某迷宮有進(jìn)出口共四處，一人由不同進(jìn)出口進(jìn)出的方法共有幾種?

解：第一個步驟:進(jìn)→4種選法。第二個步驟:出→3種選法。由乘法原理知,共有4×3種方法。何謂乘法原理乘法原理：假設(shè)A與B是不相交的有限集合，則|A取捨原理取捨原理(又稱排容原理)：令A(yù),B,C為三個有限集合，則（1）|A

B|=|A|+|B|

|A

B|。（2）|A

B

C|=|A|+|B|+|C|

|A

B|

|B

C|

|C

A|+|A

B

C|。取捨原理取捨原理(又稱排容原理)：令A(yù),B,C為三個有限教學(xué)網(wǎng)頁設(shè)計(jì)理念本教學(xué)網(wǎng)頁打算透過生活化主題，帶領(lǐng)學(xué)生漸進(jìn)認(rèn)識學(xué)習(xí)排列組合，希望能以更生動的方式幫助學(xué)習(xí)，激發(fā)學(xué)生們學(xué)習(xí)的興趣。教學(xué)網(wǎng)頁設(shè)計(jì)理念本教學(xué)網(wǎng)頁打算透過生活化主題，帶領(lǐng)學(xué)生漸進(jìn)認(rèn)教學(xué)網(wǎng)頁預(yù)期目標(biāo)了解簡單的邏輯概念，並能熟知符號的運(yùn)用。知道如何操作集合的表示與運(yùn)算。能運(yùn)用加法原理、乘法原理以及計(jì)數(shù)原理解決相關(guān)數(shù)學(xué)問題。教學(xué)網(wǎng)頁預(yù)期目標(biāo)了解簡單的邏輯概念，並能熟知符號的運(yùn)用。教學(xué)網(wǎng)頁設(shè)計(jì)規(guī)劃流程首先介紹基本的符號以及觀念，帶領(lǐng)學(xué)生對邏輯與集合有初步的認(rèn)識。