逻辑集合与计数原理课件.ppt

1、主題內容一、簡單的邏輯概念：介紹或、且、否定及笛摩根定律二、集合的定義、集合的表示法與操作三、基本計數原理四、加法原理、乘法原理、取捨原理 一、簡單的邏輯概念“若P則Q”成立時，P稱為Q的充分條 件，Q稱為P的必要條件；以符號P Q表示命題“若P則Q”成立 如果命題“若P則Q”與其逆命題“若Q則P”皆成立，則P是Q的充要條 件，而Q也是P的充要條件，以符號P Q表示命題介紹 原命題：P Q 逆命題：Q P 否定命題：P Q 否逆命題：Q P 原命題與否逆命題同真假 逆命題與否定命題同真假或與且“且”代表兩個條件必須同時成立；“或”則代表兩個條件中只要有一個條件成立即可(如果這兩個條件都成立也可

2、以)例1.“x=0且x=2”代表x“同時是0，又是2”，此為一個不能成立的命題 例2.“x2”代表”x2或x=2”，因此“22”是一個正確的命題笛摩根定律(AB)=ABABSABSABS(AB)AB笛摩根定律(AB)=ABABSABSABS(AB)AB二、何謂集合？集合集合的定義，最簡單的說法，即是在最原始的集合論樸素集合論中的定義，集合就是”一堆東西”集合裡的“東西”，叫作元素元素習慣上，我們會用大小寫字母大小寫字母來代表集合或元素稱為空集合，即集合內沒有任何元素我們一般習慣把集合畫成圖形來說明一些集合關係，其圖形稱作文氏圖文氏圖常用名詞 Part 1若x為集合A的元素，則稱x屬於屬於A，記

3、作若集合A中的所有元素皆為集合B中的元素，則稱A包含於包含於B，記作 。此時稱A是B的子集子集舉例來說，若N所有正整數所成的集合，Z是所有整數所成的集合，則 且 x AAB2 常用名詞 Part 2 交集交集 ：若A、B為兩集合，則集合內的元素為為A且且B的元素，以圖形來看就是下圖兩圓相交的區域。ABAB常用名詞 Part 3 聯集聯集 ：若A、B為兩集合，則集合 內的元素為為A或或B的元素，以圖形來看就是下圖兩圓所包含的所有區域。ABAB常用名詞 Part 4 差集差集：若A、B為兩集合，則集合 定義為 。例：則ABxA xB1,2,3,4,5A 2,4,6,8,10B 1,3,5AB常用名

4、詞 Part 5 乘積集合乘積集合：兩個集合X和Y的乘積集合（Cartesian product），表示為X Y，是其第一個構件是X的成員而第二個構件是Y的一個成員的所有可能的有序對：(,)XYx y xXyY三、基本計數原理窮舉法樹狀圖窮舉法 What is 窮舉 How to 窮舉：使用時機好的例子不好的例子 窮舉方法：順序窮舉 /排列窮舉 /組合窮舉What is 窮舉遇到一個問題 1.列出問題的所有可能解2.根據題目條件逐個判定3.滿足條件 得到一個解窮舉使用時機1.問題可能解的個數不是特別大2.答案的變化具有一定的規律性窮舉法的範例1.給定不考慮運算優先順序的4個算數符號 2.輸入任

5、5個正整數 A1 A2 A3 A4 A53.在每個相鄰的正整數間填入一個上述的算數符號，構成一個算數表達式4.給定一個M，使該算數表達式剛好為M5.求出，所有可能的算數表達式窮舉法的範例(cont.)A1(+-x)A2(+-x)A3(+-x)A4(+-x)A5 最多僅有 44 種解法 有規律：4個位置所要填的算數符號 用去填充 用一個4重迴圈，即可以完成不適用窮舉的例子1.給定一個正數的集合 A=a1,a2,a3,an,(n30)2.4個算數符號不考慮運算優先順序3.從A中選取若干的元素，用上述算數符號連結起來成一個表達式4.給定一個M，求出，以最少的運算次數可以產生M的算數表達式不適用窮舉的

6、例子(cont)此例與上個例子均為根據結果來組合表 達式，不同的是：集合A中的個數和順序選取無法確定 無法用固定的循環來控制和窮舉 適合用搜索回朔法窮舉的方法排列窮舉/組合窮舉利用數學中排列組合的知識，產生出問題的答案的所有可能解，根據題設中答案的檢驗條件去判斷是否有滿足的答案。順序窮舉將問題的答案範圍內所有情況與自然數建立起一個一一對應的關係，從而可以按自然數的變化順序去窮舉問題的所有可能解。樹狀圖 處理離散事物的計數時，依問題的特性，適當的分類，以樹狀的圖形結構表示，此圖形稱 樹狀圖樹狀圖圖例賓客親戚朋友大伯家 4人林家 3人李家 2人王家 4人姑媽家 4人二伯家 2人四、加法原理、乘法原

7、理、取捨原理加法原理乘法原理取捨原理 何謂加法原理 加法原理加法原理：若A與B是不相交的有限集合，則|A B|=|A|+|B|。例例：從甲地到乙地有飛機、火車與巴士等三種交通工具可到達,其中飛機每天有3班,火車每天有15班，巴士每天25班，若A先生欲從甲地至乙地，很明顯地，此問題的A先生只能選擇一種交通工具的某個班次，故共有3+15+25=43個交通班次可選擇。何謂乘法原理 乘法原理乘法原理：假設A與B是不相交的有限集合，則|A B|=|A|B|例例：某迷宮有進出口共四處，一人由不同進出口進出的方法共有幾種?解：第一個步驟:進4種選法。第二個步驟:出3種選法。由乘法原理知,共有43種方法。取捨

8、原理 取捨原理取捨原理(又稱排容原理排容原理)：令A,B,C為三個有限集合，則（1）|AB|=|A|+|B|A B|。（2）|ABC|=|A|+|B|+|C|AB|B C|C A|+|ABC|。教學網頁設計理念 本教學網頁打算透過生活化主題，帶領學生漸進認識學習排列組合，希望能以更生動的方式幫助學習，激發學生們學習的興趣。教學網頁預期目標了解簡單的邏輯概念，並能熟知符號的運用。知道如何操作集合的表示與運算。能運用加法原理、乘法原理以及計數原理解決相關數學問題。教學網頁設計規劃流程首先介紹基本的符號以及觀念，帶領學生對邏輯與集合有初步的認識。從生動、生活化的互動式活動融入情境，並進一步了問題背後的更多的數學概念。將重要的概念做統整，以利學生對知識的理解。設計通關測驗，使學生自我檢測學習效果。參考資料 機率學習館http:/eprob.math.nsysu.edu.tw/PerComb.htm http:/ 高中課本