邏輯集合與計(jì)數(shù)原理.ppt

邏輯、集合與計(jì)數(shù)原理,數(shù)99丙 曾子軒 張郁苓 李承修,主題內(nèi)容,一、簡(jiǎn)單的邏輯概念：介紹或、且、否定及笛摩根定律 二、集合的定義、集合的表示法與操作 三、基本計(jì)數(shù)原理 四、加法原理、乘法原理、取捨原理,一、簡(jiǎn)單的邏輯概念,“若P則Q”成立時(shí)，P稱為Q的充分條 件，Q稱為P的必要條件；以符號(hào)P Q表示命題“若P則Q”成立 如果命題“若P則Q”與其逆命題“若Q則P”皆成立，則P是Q的充要條 件，而Q也是P的充要條件，以符號(hào)P Q表示,命題介紹,原命題 ：P Q 逆命題 ：Q P 否定命題 ：P Q 否逆命題 ：Q P 原命題與否逆命題同真假 逆命題與否定命題同真假,或與且,“且”代表兩個(gè)條件必須同時(shí)成立；“或”則代表兩個(gè)條件中只要有一個(gè)條件成立即可(如果這兩個(gè)條件都成立也可以) 例1.“x=0且x=2”代表x“同時(shí)是0，又是2”，此為一個(gè)不能成立的命題 例2.“x2”代表”x2或x=2”，因此“22”是一個(gè)正確的命題,笛摩根定律,(AB)=AB,笛摩根定律,(AB)=AB,二、何謂集合？,集合的定義，最簡(jiǎn)單的說(shuō)法，即是在最原始的集合論樸素集合論中的定義，集合就是”一堆東西”集合裡的“東西”，叫作元素 習(xí)慣上，我們會(huì)用大小寫字母來(lái)代表集合或元素 稱為空集合，即集合內(nèi)沒(méi)有任何元素 我們一般習(xí)慣把集合畫成圖形來(lái)說(shuō)明一些集合關(guān)係，其圖形稱作文氏圖,常用名詞 Part 1,若x為集合A的元素，則稱x屬於A，記作 若集合A中的所有元素皆為集合B中的元素，則稱A包含於B，記作 。此時(shí)稱A是B的子集 舉例來(lái)說(shuō)，若N所有正整數(shù)所成的集合，Z是所有整數(shù)所成的集合，則 且,常用名詞 Part 2,交集 ：若A、B為兩集合，則集合內(nèi)的元素為為A且B的元素，以圖形來(lái)看就是下圖兩圓相交的區(qū)域。,常用名詞 Part 3,聯(lián)集 ：若A、B為兩集合，則集合 內(nèi)的元素為為A或B的元素，以圖形來(lái)看就是下圖兩圓所包含的所有區(qū)域。,常用名詞 Part 4,差集：若A、B為兩集合，則集合 定義為 。 例： 則,常用名詞 Part 5,乘積集合：兩個(gè)集合X和Y的乘積集合（Cartesian product），表示為X Y，是其第一個(gè)構(gòu)件是X的成員而第二個(gè)構(gòu)件是Y的一個(gè)成員的所有可能的有序?qū)Γ?三、基本計(jì)數(shù)原理,窮舉法 樹狀圖,窮舉法,What is 窮舉 How to 窮舉： 使用時(shí)機(jī) 好的例子不好的例子 窮舉方法： 順序窮舉 / 排列窮舉 / 組合窮舉,What is 窮舉,遇到一個(gè)問(wèn)題 列出問(wèn)題的所有可能解 根據(jù)題目條件逐個(gè)判定 滿足條件 得到一個(gè)解,窮舉使用時(shí)機(jī),問(wèn)題可能解的個(gè)數(shù)不是特別大 答案的變化具有一定的規(guī)律性,窮舉法的範(fàn)例,給定不考慮運(yùn)算優(yōu)先順序的4個(gè)算數(shù)符號(hào) 輸入任5個(gè)正整數(shù) A1 A2 A3 A4 A5 在每個(gè)相鄰的正整數(shù)間填入一個(gè)上述的算數(shù)符號(hào)，構(gòu)成一個(gè)算數(shù)表達(dá)式 給定一個(gè)M，使該算數(shù)表達(dá)式剛好為M 求出，所有可能的算數(shù)表達(dá)式,窮舉法的範(fàn)例 (cont.),A1(+-x)A2 (+-x) A3 (+-x) A4 (+-x) A5 最多僅有 44 種解法 有規(guī)律：4個(gè)位置所要填的算數(shù)符號(hào) 用去填充 用一個(gè)4重迴圈，即可以完成,不適用窮舉的例子,給定一個(gè)正數(shù)的集合 A = a1,a2,a3,an ,(n30) 4個(gè)算數(shù)符號(hào)不考慮運(yùn)算優(yōu)先順序 從A中選取若干的元素，用上述算數(shù)符號(hào)連結(jié)起來(lái)成一個(gè)表達(dá)式 給定一個(gè)M，求出，以最少的運(yùn)算次數(shù)可以產(chǎn)生M的算數(shù)表達(dá)式,不適用窮舉的例子(cont),此例與上個(gè)例子均為根據(jù)結(jié)果來(lái)組合表 達(dá)式，不同的是：集合A中的個(gè)數(shù)和順序選取無(wú)法確定 無(wú)法用固定的循環(huán)來(lái)控制和窮舉 適合用搜索回朔法,窮舉的方法,排列窮舉/組合窮舉 利用數(shù)學(xué)中排列組合的知識(shí)，產(chǎn)生出問(wèn)題的答案的所有可能解，根據(jù)題設(shè)中答案的檢驗(yàn)條件去判斷是否有滿足的答案。 順序窮舉 將問(wèn)題的答案範(fàn)圍內(nèi)所有情況與自然數(shù)建立起一個(gè)一一對(duì)應(yīng)的關(guān)係，從而可以按自然數(shù)的變化順序去窮舉問(wèn)題的所有可能解。,樹狀圖,處理離散事物的計(jì)數(shù)時(shí)，依問(wèn)題的特性，適當(dāng)?shù)姆诸?，以樹狀的圖形結(jié)構(gòu)表示，此圖形稱 樹狀圖,樹狀圖圖例,四、加法原理、乘法原理、取捨原理,加法原理 乘法原理 取捨原理,何謂加法原理,加法原理：若A與B是不相交的有限集合，則 |A B| = |A| + |B|。 例：從甲地到乙地有飛機(jī)、火車與巴士等三種交通工具可到達(dá),其中飛機(jī)每天有3班, 火車每天有15班，巴士每天25班，若A先生欲從甲地至乙地，很明顯地，此問(wèn)題的A先生只能選擇一種交通工具的某個(gè)班次，故共有3+15+25=43個(gè)交通班次可選擇。,何謂乘法原理,乘法原理：假設(shè)A與B是不相交的有限集合，則|A B| = |A|B| 例：某迷宮有進(jìn)出口共四處，一人由不同進(jìn)出口進(jìn)出的方法共有幾種? 解：第一個(gè)步驟: 進(jìn)4種選法。 第二個(gè)步驟: 出3種選法。 由乘法原理知, 共有43種方法。,取捨原理,取捨原理(又稱排容原理)：令A(yù), B, C為三個(gè)有限集合，則 （1）|AB|=|A| +|B| |A B|。 （2）|ABC|=|A|+|B|+|C|AB| |B C|C A|+|ABC|。,教學(xué)網(wǎng)頁(yè)設(shè)計(jì)理念,本教學(xué)網(wǎng)頁(yè)打算透過(guò)生活化主題，帶領(lǐng)學(xué)生漸進(jìn)認(rèn)識(shí)學(xué)習(xí)排列組合，希望能以更生動(dòng)的方式幫助學(xué)習(xí)，激發(fā)學(xué)生們學(xué)習(xí)的興趣。,教學(xué)網(wǎng)頁(yè)預(yù)期目標(biāo),了解簡(jiǎn)單的邏輯概念，並能熟知符號(hào)的運(yùn)用。 知道如何操作集合的表示與運(yùn)算。 能運(yùn)用加法原理、乘法原理以及計(jì)數(shù)原理解決相關(guān)數(shù)學(xué)問(wèn)題。,教學(xué)網(wǎng)頁(yè)設(shè)計(jì)規(guī)劃流程,首先介紹基本的符號(hào)以及觀念，帶領(lǐng)學(xué)生對(duì)邏輯與集合有初步的認(rèn)識(shí)。 從生動(dòng)、生活化的互動(dòng)式活動(dòng)融入情境，並進(jìn)一步了問(wèn)題背後的更多的數(shù)學(xué)概念。 將重要的概念做統(tǒng)整，以利學(xué)生對(duì)知識(shí)的理解。 設(shè)計(jì)通關(guān)測(cè)