湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯.ppt

《湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯.ppt》由會員分享，可在線閱讀，更多相關(guān)《湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯.ppt（84頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第一章 命題邏輯,楊圣洪 yangshenghong8@ 13007432216,引言 邏輯學(xué)是推理的基礎(chǔ)，在社會學(xué)、自然科學(xué)尤其計算機(jī)學(xué)科中得到普遍應(yīng)用。 數(shù)理邏輯是邏輯學(xué)的一個分支，也是數(shù)學(xué)的分支，它用數(shù)學(xué)方法研究推理規(guī)律，它采用符號的方法來描述和處理思維形式、思維過程和思維規(guī)律，它在程序設(shè)計、數(shù)字電路設(shè)計、計算機(jī)原理、人工智能等計算機(jī)課程得到了廣泛應(yīng)用。 命題邏輯是數(shù)理邏輯的基礎(chǔ)部分， 但究竟什么是命題？ 如何表示命題？ 如何構(gòu)造出復(fù)雜的命題？ 在本章將討論這些問題。,1.1 命題及聯(lián)結(jié)詞 對錯確定的陳述語句稱為命題。如： (1)湖南大學(xué)是一本學(xué)校。 (2)命題邏輯是計算機(jī)科學(xué)的基礎(chǔ)課程。 (3)命題及聯(lián)結(jié)詞是命題邏輯的最基礎(chǔ)的內(nèi)容。 (4)4是素數(shù)。 (5)湖南大學(xué)坐落于湘江以東。 (6)2011年湖南長沙輕軌通車。 其中(1)、(2)、(3) 與事實相符，是對的、正確的，稱為真命題，或者稱命題的值為“真”，簡記為T或數(shù)字1。 而(4)、(5)明顯與事實不相符，是錯的、不正確，稱為假命題，或稱命題的值為“假”，簡記為F或數(shù)字0。 陳述句(6)的正確性，到2011年12月時能確定的，若屆時開通了則它是對的、為真命題，否為假命題。,1.1 命題及聯(lián)結(jié)詞 對錯確定的陳述語句稱為命題。如： (7) x與y之和為100，其中x為整數(shù)，y為整數(shù) (8)1加1等于10 (7)的對錯不確定的。當(dāng)x為50、y為50時是對的，當(dāng)x為51、y為52時是錯的。 (8)的對錯是不確定的，為二進(jìn)制時正確，當(dāng)為八進(jìn)制、十進(jìn)制時是錯的，因此這兩個陳述句不是命題。 (9)岳麓山的紅葉真美呀！ (10)動作快點！ (11)你是離散數(shù)學(xué)老師嗎？ 這三個語句不是陳述語句，因此不是命題。,1.1 命題及聯(lián)結(jié)詞 對錯確定的陳述語句稱為命題。如： (12)我在說假話。 (13)我只給自己不能理發(fā)的人理發(fā)。 (14)派出所說:必須先房子再能上戶口 單位后勤說:必須先有戶口才能分房 你能上到戶口與要到房子嗎? 這是一個悖論，其真值不能確定，故不是命題。。,1.1 命題及聯(lián)結(jié)詞 對錯確定的陳述語句稱為命題。如： (13)我既要學(xué)程序設(shè)計，又要學(xué)離散數(shù)學(xué)。 (14)我們早餐在公寓食堂或外面早點攤上吃。 (15)我不是數(shù)學(xué)院的學(xué)生 這三個陳述句都與事實相符，是對的，是真命題，其值為真(T/1)。 其中(13)與(14)可分解為另外二句話的組合， 而(15)是對“我是數(shù)學(xué)院學(xué)生”的否定，這些語句稱為“復(fù)合命題”，不能再分解的語句稱為“簡單命題”或“原子命題”，為了便于推理與書寫，常用小寫字母表示簡單命題或原子命題。,1.1 命題及聯(lián)結(jié)詞 簡單命題組合成復(fù)雜命題時所使用的輔助詞稱為“聯(lián)結(jié)詞”。 命題邏輯中的聯(lián)結(jié)詞歸納為以下5種。 合取?：C語言中 && and 并且 析取?：C語言中 || or 或 否定?：C語言中 ! not 非,不是,否定 條件式?：C語言中 if () 如果…那么 如p則q 雙條件式?： 如p則q且如q則p,當(dāng)且僅當(dāng),1.1 命題及聯(lián)結(jié)詞 定義1.1合?。?當(dāng)p、q都對，即取值為真(T或1)時，“p合取q”的值為真.,1.1 命題及聯(lián)結(jié)詞 定義1.1合?。?當(dāng)p、q都對，即取值為真(T或1)時，“p合取q”的值為真，其他情況為假。,邏輯運算符“合取”，與漢語中“并且、而且、同時”含義相當(dāng),1.1 命題及聯(lián)結(jié)詞 定義1.2析?。?當(dāng)p、q都不對，即取值為假(F或0)時，“p析取q”的值為假，其他情況為真。,邏輯運算符“析取”，與漢語中“或”含義相當(dāng)，但有細(xì)微的區(qū)別,1.1 命題及聯(lián)結(jié)詞 邏輯運算符“析取” 與漢語的“或”幾乎一致但有區(qū)別： (16)“講離散數(shù)學(xué)的老師是楊老師或劉老師”，可以表示為“講離散數(shù)學(xué)的老師是楊老師”?“講離散數(shù)學(xué)的老師是劉老師”，這兩個原子命題有可能都是對的，這種“或”稱為“可同時為真的或”，或簡稱為“可兼或”。 (17)“離散數(shù)學(xué)的教室是102或302”，不可以表示為“離散數(shù)學(xué)的教室是102”?“離散數(shù)學(xué)的教室是302”，因為這兩個原子命題不可能都對，只能這二種情況之一，這種“或”稱為“不可同時為真的或”，或簡稱為“不可兼或”、“排斥或”. 這種“或”表示不能簡單表示為“析取”，需要聯(lián)合使用下面將要介紹的“否定”與“析取”符號，才能準(zhǔn)確表達(dá)。,1.1 命題及聯(lián)結(jié)詞 定義1.3否定:當(dāng)p是1 ，p的否定?p即為0。,邏輯運算符“否定”，與漢語中“否定”含義相當(dāng). “我不是數(shù)學(xué)院的學(xué)生”可表示為“?我是數(shù)學(xué)院的學(xué)生” “離散數(shù)學(xué)的教室是102或302”,表示 離散數(shù)學(xué)的教室是102不是302“ 或 “離散數(shù)學(xué)的教室是302不是102“ p:離散數(shù)學(xué)的教室是102 q:離散數(shù)學(xué)的教室是302 上面的語句表示: (p??q)?(?p?q),1.1 命題及聯(lián)結(jié)詞 定義1.4條件:當(dāng)p是1 ,q是0時,p?q為0,即1?0為0,其他情況為1。,邏輯運算符“如果…那么”，它是用單個運算符表示一個復(fù)合語句。 如老媽說：“如果期終考了年級前10名，那么獎勵1000元”。 p:期終考了年級前10名 q:獎勵1000元 則上面的語句表示為p?q。 當(dāng)p為1即“期終考了年級前10”， 且q為0即“沒有獎勵1000元” 這時老媽的話是假話空話， 故p?q為0,1.1 命題及聯(lián)結(jié)詞 定義1.4條件式(蘊含式):當(dāng)p是1 ,q是0時,p?q為0,即1?0為0,其他情況為1。 p為前件,q為后件,(1)當(dāng)p為1即“我期終考了年級前10” q為0即“我老媽沒有獎勵1000元” 這時老媽的話為假，即p?q為0 (2)當(dāng)p為1即“我期終考了年級前10” q為1即“我老媽獎勵1000元” 這時媽媽的話就對了，即p?q為1 (3)至于p為0即“我期終考了年級不是前10”時,無論q為1或為0，即無論“我老媽獎勵1000元“或不獎勵，都不能說老媽的話是假的，故可善意的認(rèn)為p?q為1均為1,1.1 命題及聯(lián)結(jié)詞 定義1.5雙條件:當(dāng)p與q值相同0時,p?q為1,不同為0。 稱p與q的等價式,“我明年賺了10萬當(dāng)且僅當(dāng)我買彩票中了大獎”， 可以表示為“我明年賺了10萬?我買彩票中了大獎”,1.2公式及其賦值 對錯明確的陳述語句稱為命題，其真值確定，又稱為命題常元或命題常項，相當(dāng)于初等數(shù)學(xué)中的“常數(shù)”。 數(shù)學(xué)的運算符號為“加+、減-、乘x、除?、冪?”， 命題邏輯的符號“合取?、析取?、否定?、條件?、雙條件?” 數(shù)學(xué)中用變量x表示某些數(shù)，如x2+x+10是代數(shù)式， 命題邏輯用變量表示任意一個命題，如p,q,r,這時由符號與變量所構(gòu)成命題表達(dá)式，簡稱為“命題公式”。 代數(shù)式的書寫有規(guī)律，命題公式也有規(guī)律與約束，稱滿足這些規(guī)則的公式為“合式公式”，也稱為“命題公式”，簡稱為“公式”。,1.2公式及其賦值 定義1.2.1 合式公式的生成規(guī)則 (1)單個命題變元、命題常元為合式公式(原子公式)。 (2)若A是合式公式，則?A、(A)也是合式公式。 (3)若A、B是合式公式，則A?B、A?B、A?B、A?B是合式公式。 (4)有限次使用(2)~(3)形成的字符串均為合式公式。 如：(p?1)?q是合式公式。 因為p、1是合公式，則(p?1)是合式公式，而r是合式公式，故(p?1)?q是合式公式。 (p?1)r?不是合式公式。 因為p、1是合公式，則(p?1)是合式公式，而r是合式公式，但(p?1) r?不是合法公式。,1.2公式及其賦值 對于代數(shù)式x2+y+10，當(dāng)x與y的值不確定時，該代數(shù)式的值是不確定的。 對于公式 (p?1)?q，由于p與q值不確定時，公式(p?1)?q的值不確定，因而不是命題。 只有當(dāng)p與q的值確定后，公式(p?1)?q的值才能確定，我們可能像表1.2到表1.5一樣，給出公式在各種情況下的取值，即得到這個公式的真值表。,p與q每一種取值稱為p、q的一種解釋,1.2公式及其賦值 公式(?p?q)、p?q的真值表如下表。,真值表的構(gòu)造方法： (1)命題變元的取值從全0開始，依次加1，直到全1，當(dāng)有n個變元時，則共有2n種不同的取值情況。 (2)分步驟計算公式的值 (3)見黑板上寫,成真賦值:如p?q為(0,0),(0,1),(1,1) 成假賦值:如p?q為(1,0),1.2公式及其賦值 公式(p?q)?(q?p)、p?q的真值表。,無論p/q取何值，這兩個公式的值總相等。,1.2公式及其賦值 公式 ?(p?q)、? p? ? q的真值表。,無論p/q取何值，這兩個公式的值總相等。,1.2公式及其賦值 公式p?q、? p?q的真值表。,無論p/q取何值，這兩個公式的值總相等。,1,1.2公式及其賦值 公式p?q、?q??p的真值表。,無論p/q取何值，這兩個公式的值總相等，若前者稱為原命題，后者為逆否命題,1,1.2公式及其賦值 公式p?(q?r)、(p?q)?(p?r)的真值表。,無論p/q取何值，這兩個公式的值，與前面各例不同，此表是將運算結(jié)果寫在聯(lián)結(jié)詞的下方！,1.3 等值式 一、復(fù)習(xí) 由前節(jié)可知： p?q與?p?q、 ?q??p p?q與(p?q)?(q?p) 、(p?q)?(?p??q) ?(p?q)與?p ? ?q p?(q?r)、(p?q)?(p?r) 的真值表完全一樣，稱為等值。 定義1.3.1 設(shè)A、B是兩個合法的命題公式，無論其中的命題變元取何值，這兩個公式的總相等，稱為兩個公式等值，記為A?B,由定義及前節(jié)習(xí)題有： (1)p?q??p?q??q??p 條件式的等值式 (2)p?q?(p?q)?(q?p)?(p?q)?(?p??q) 雙條件 (3)p???p 雙重否定律 (4)p?p?p?p?p 冪等律 (5)p?q? q?p，p?q? q?p 交換律 (6) p?(q?r) ?(p?q) ? r 結(jié)合律 p?(q?r) ? (p?q) ? r (7) p?(q?r) ?(p?q)?(p?r) 分配律 p?(q?r) ? (p?q)?(p?r) (8) p?(p?r) ?p 吸收律(多吃少) p?(p?r) ?p (9) ?(p?q) ??p??q 德摩律 ?(p?q) ??p??q 將以上等值式中的變元換成合式公式仍等值！,如：p?q ? ?p?q 則有 A?B ? ?A?B 盡管A/B可能很復(fù)雜，但是公式值也只有0、1二種可能，公式A/B的組合只有0/0,0/1,1/0,1/1四種，如下表所示,顯然有 A?B ? ?A?B,置換規(guī)則：當(dāng)將公式A中的子公式B換成C得到公式D后，若B?C，那么A?D。 因為A、D除了“A中B所在之處、D中C所在之處”外，其他地方均相同，而不同之處的B與C等值，所以公式A、公式D的真值表應(yīng)該完全他相同，故A?D。 當(dāng)將一個公式的局部進(jìn)行等值替換后， 仍與原公式等值，這也是數(shù)學(xué)中最常見的方法，不斷對局部進(jìn)行等值替換的操作，稱為“等值演算”。 利用該規(guī)則及前述的等值式，可進(jìn)行等值演算，從而推導(dǎo)出新的公式。,求證 (p?q)?r?(p?r) ? (q?r) (p?q)?r ??(p?q)?r 條件式的等值式 ?(?p??q) ?r 利用德摩律 ?r? (?p??q) 交換律 ?(r??p)?( r??q) 分配律 ?(?p ? r)?( ?q?r) 交換律 ?(p?r) ? (q?r) 條件式等值式,等值演算的基本套路 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) 確保公式只保留? ? ?聯(lián)結(jié)詞 (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)恰當(dāng)使用分配律、吸收律。,利用等值演算，判斷公式的類型 ((p?q)?p)?q ((p?q)?p)?q ?((?p?q)?p)?q (條件式的等值式) ??((?p?q)?p)?q (條件式的等值式) ? (? (?p?q)??p)?q (德摩律) ? ((p??q)??p)?q (德摩律) ? (p??q)?(?p?q) (結(jié)合律) ? (p??q)? ? (p??q) (逆用德摩律) ?A??A (A= (p??q)) ?1 稱為永真式或重言式， 即利用等值演算，可以判斷公式的類型。,利用等值演算判斷公式類型：?(p?(p?q))?r 解： ?(p?(p?q))?r ??(?p?(p?q))?r (條件式的等值式) ??((?p?p)?q) ?r (結(jié)合律) ??(1?q) ?r (析取的性質(zhì)即析取定義真值表) ??1?r (析取的性質(zhì)即析取定義真值表) ?0?r (否定的定義) ?0 (析取的性質(zhì)即析取定義真值表) 永假式或矛盾式。 問題：盡管有套路可行，但是隨意性還是比較大，能否有某種方式肯定能成功呢？,1.4 析取范式與合取范式 文字：命題變項(變元)及其否定稱為文字. 如:p,q,r, ?p, ?q, ?r 簡單析取式:僅由有限個文字構(gòu)成的析取式. 如:p?q, ?p?q,p??q, ?p? ?q,p?q?r 簡單合取式:僅由有限個文字構(gòu)成的合取式. 如:p?q, ?p?q,p??q, ?p??q,p?q?r 定理：簡單析取式與簡單合取式 (1)一個簡單析取式Ai是重言式? 含有某個命題變元及其否定式，如Ai=p??p?… (2)一個簡單合取式Ai是矛盾式? 含有某個命題變元及其否定式，如Ai=p??p?…,1.4 析取范式與合取范式 析取范式：由有限個簡單合取式的析取構(gòu)成的命題公式稱為析取范式。 總體是析取式?，每對括號內(nèi)是合取式 A=(p?q)?(?p?r) 合取范式：由有限個簡單析取式的合取構(gòu)成的命題公式稱為合取范式。 總體是合取式?，每對括號內(nèi)是析取式 A=(p?q)?(?p?r),1.4 析取范式與合取范式 總體是析取式?，每對括號內(nèi)是合取式 A=(p?q)?(?p?r) 析取范式 總體是合取式?，每對括號內(nèi)是析取式 A=(p?q)?(?p?r) 合取范式 定理：析取范式與合取范式 (1)一個析取范式A是矛盾式? 每個簡單合取式是矛盾式。 A=(p?q)?(?p?r) (2)一個合取范式A是重言式? 每個簡單析取式是重言式。 A=(p?q)?(?p?r),1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 經(jīng)過第1步、第2步轉(zhuǎn)換后，公式中只有?、?、?三種運算符。 經(jīng)過第3步后，?從括號外深入到變元的前面，與變元結(jié)合成文文字，文字之間只有?、?。,1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 如果外層運算符全部是?，而內(nèi)層子公式全部是簡單析取式，則已經(jīng)是合取范式。 如果內(nèi)層某子公式形如A?(B?C)，不是簡單析取式，則轉(zhuǎn)換為(A?B)?(A?C)。,1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 如果外層運算符全部是?，而內(nèi)層子公式全部是簡單合取式，則已經(jīng)是析取范式。 如果內(nèi)層某子公式形如A?(B?C)，不是簡單合取式，則轉(zhuǎn)換為(A?B)?(A?C)。因此有： (1)不是永假的命題公式，存在析取范式。 (2)不是永真的命題公式，存在合取范式。,1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 如析取式范式：(p?q) ?r ?(?p?q) ?r ?((?p?q)?r)?(?(?p?q)??r) ?(?p ?r)?(q?r)?(p??q??r),1.4 析取范式與合取范式 求(p?q) ?r的析取范式、合取范式 解：(1)求析取范式。即外層是?，內(nèi)層是?，所以?轉(zhuǎn)換模式為A?B? (A?B)?(?A??B) (p?q) ?r ?((p?q) ?r)?( ? (p?q) ?? r) (整體為析取) ?((?p?q) ?r)?( ? (?p?q) ?? r) (A?B??A?B) ?((?p?q) ?r)?( (p??q) ?? r) (德摩律) ?((?p ?r )?(q?r))?( (p??q) ?? r) (分配律) ?(?p ?r )?(q?r)?( p??q ?? r) (結(jié)合律),1.4 析取范式與合取范式 解：(1)求合取范式。所以?轉(zhuǎn)換模式為A?B?(?A?B)?(A??B) (p?q) ?r ?(? (p?q)?r)?( (p?q)?? r) (整體為合取) ?(? (?p?q)?r)?( (?p?q)?? r) (條件等價式) ?((p??q)?r)?( (?p?q)?? r) (德摩律) ?((p?r) ?(?q?r))?( (?p?q)?? r) (分配律) ?(p?r) ?(?q?r)?( ?p?q?? r) (結(jié)合律),1.4 析取范式與合取范式 小項：在含有n個變元的簡單合取式中,每個命題變元或其否定僅出現(xiàn)一次,且各變元按其字母順序出現(xiàn),則該簡單合取式為(極)小項。 如：p?q?r, p??q?r, p?q??r, ?p?q?r (?p ?r), (q?r) 非小項 大項：在含有n個變元的簡單析取式中,每個命題變元或其否定僅出現(xiàn)一次,且各變元按其字母順序出現(xiàn),則該簡單析取式為(極)大項。 如：p?q?r, p??q?r, p?q??r, ?p?q?r (p?r), (?q?r) 非大項,1.4 析取范式與合取范式 主析取范式：一個析取范式中，如果所有簡單合取式均為(極)小項，則稱為主析取范式。 (p?q) ?r ?(?p ?r)?(q?r)?(p??q??r) 不是 (?p?q?r)?(?p??q?r)? (p?q?r)?(p??q??r) 是主析取范式,1.4 析取范式與合取范式 主合取范式：一個合取范式中，如果所有簡單析取式均為(極)大項，則稱為主合取范式。 (p?q)?r ?(p?r)?(?q?r)?(?p?q??r) 不是 ?(p?q?r)? (p??q?r) ?(?p??q?r) ?(?p?q??r) 是主合取范式,1.4 析取范式與合取范式—獲取方法 通過轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時可能還缺少某個變元， 因為p??p?1，1?r?1，可在缺少變元的小項中加入形如“p??p”的公式。 如小項(?p?r)缺少變元q，加入q??q，即 ?p?r ??p?1?r ??p?(q??q)?r ?(?p?q?r)?(?p??q?r)。,1.4 析取范式與合取范式—獲取方法 通過轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時可能還缺少某個變元， 因為p??p?1，1?r?1，可在缺少變元的小項中加入形如“p??p”的公式。 (p?q) ?r ?(?p?r)?(q?r)?(p??q??r) ?(?p?(q??q)? r)?((p??p)?q?r)?(p??q??r) ?(?p?q?r )?(?p??q?r)? (p?q?r )?(?p?q?r) ?(p??q??r) ?(?p?q?r )?(?p??q?r)? (p?q?r )? (p??q??r),1.4 析取范式與合取范式—獲取方法 通過轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時可能還缺少某個變元， 因為p??p?0，0?p?p，可在缺少變元的大項中加入形如“p??p”的公式 。 如 p?r ?p?0?r ?p?(q??q)?r ?(p?q?r)?(p??q?r),1.4 析取范式與合取范式—獲取方法 通過轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時可能還缺少某個變元， 因為p??p?0，0?p?p，可在缺少變元的大項中加入形如“p??p”的公式 。 (p?q) ?r ?(p?r)?(?q?r)?(?p?q??r) ?(p?(q??q)?r)?((p??p)??q?r)?(?p?q??r) ?(p?q?r)?(p??q?r)?(p??q?r)?(?p??q?r)? (?p?q??r) ?(p?q?r) ?(p??q?r)?(?p??q?r) ? (?p?q??r),1.4 析取范式與合取范式 當(dāng)一個公式比較復(fù)雜時，得到其析取范式、合取范式的演算量比較大，再將簡單析取式轉(zhuǎn)換為大項，或簡單合取式轉(zhuǎn)換為小項，又需要進(jìn)一步演算，能否直接基于原公式，不進(jìn)行等值演算直接得到，或者能按某種統(tǒng)一的方式得到其主析取范式、主合取范式呢？ 通過真值表可以實現(xiàn)！為此先研究小項與大項的性質(zhì)。,1.4 析取范式與合取范式 通過真值表可以實現(xiàn)！為此先研究小項與大項的性質(zhì)，下表是各小項的真值表。,1. 3個變元的小項共有8個，它們各不相同。 2.從每一行來看，命題變元的每個指派中，只有一個小項的值為1。 3.從每一列來看，每個小項僅在一個指派中值為1，其余7種指派中均為0。 4.小項值為1(如?p??q??r=1)時，?p,?q,?r均為1，即(p,q,r)=(0,0,0)，取該值為小項編號，如最后一行。,(5)根據(jù)小項的編號，可寫出小項的具體形式。 如小項m101，其編號為101，表示(p,q,r)=(1,0,1)時該小項的值為1，而小項是文字的合取，故小項的各個文字必須為1,則文字只能是p、?q、r,故該小項為p??q?r。 規(guī)則：1對應(yīng)變元本身(如p)，0對應(yīng)其否定(如?p) 。 如m00為?p??q、m01為?p?q、m10為p??q、m11為p?q。 很重要！,(1)三個變元的大項共有8個。 (2) 每一行:每個指派中，只有一個大項的值為0。 (3)每一列:每個大項僅在一個指派下值為0。 (4)大項值為0(如?p??q??r=0) 時，?p、?q、?r均為0，則(p,q,r)=(1,1,1)，將其記為大項編號,如表最后行。,(5)根據(jù)大項的編號，可寫出大項的具體形式。 如大項M101,其編號為101，表示(p,q,r)=(1,0,1)時該大項的值為0，而大項是文字的析取，故各個文字必須為0，文字只能是?p、q、?r，故該大項為?p?q??r。 規(guī)則：1對應(yīng)變元的否定(如?p)，0對應(yīng)變元(如p) 如M00為p?q,M01為p??q,M10為?p?q, M11為?p??q。,1.4 析取范式與合取范式—獲取方法 1、先轉(zhuǎn)換析取式或合取式，再合取1或析取0。 2、先建立真值表， 取出所有成真賦值對應(yīng)的小項，析取所有小項得主析取范式。小項與成真賦值對應(yīng)。 取出所有成假賦值對應(yīng)的大項，合取所有大項得主合取范式。大項與成假賦值對應(yīng)。 如用真值表求主范式: (p?q)?r, p?q, p?q, ?(p?q)?q,p?(p?q),(p?q) ?r的主析取范式、主合取范式,主析取范式 ?公式值為1的指派對應(yīng)小項的析取 m001? m011? m100? m111 1變元,0變元否定, 使小項=1 (?p??q?r)? (?p?q?r)?(p??q??r)?( p?q?r),(p?q) ?r的主析取范式、主合取范式,主合取式范式 ?公式值為0的指派對應(yīng)大項的合取 ? M000? M010? M101? M110 1變元否定0變元,使大項=0 (p?q?r)?( p??q?r)?( ?p?q??r)?( ?p??q?r),(p?q)?r、與其主析取范式、主合取范式的真值完全一樣，說明三者互相等值，一般情況下有如下定理 ： (1)不是永假的命題公式，有等值的主析取范式。 (2)不是永真的命題公式，有等值的主合取范式。 由于永假沒有取值為1的解釋，故無相應(yīng)小項，故沒有主析取范式。永真無取值為0的解釋,故沒有主合取范式.,設(shè)計一個電子評分系統(tǒng)，3位專家打分，如果有2位以上專家打分為“通過”，則總成績?yōu)椤巴ㄟ^” 。,對應(yīng)的主析取范式?值為1的指派對應(yīng)的小項的析取 ?m011?m101?m110?m111 ?(?x1?x2?x3)? (x1??x2?x3)?(x1?x2??x3)?(x1?x2?x3) ?((?x1?x2?x3)?(x1??x2?x3))?((x1?x2??x3)? (x1?x2?x3)) ?( ((?x1?x2)? (x1??x2))?x3)?(((x1?x2?(?x3?x3))) ?(((?x1?x2)? (x1??x2))?x3)?( x1?x2) ?((?x1??x2)?(x1?x2)?x3)?( x1?x2) 與非或門表示,某公司要從曹、喬、宋、黎、鄒5人中，選擇一些人承包一項工程，考慮到人與人組合優(yōu)化的問題，需滿足如下約束條件： (1)如果曹去，那么喬也去； (2)黎、鄒兩人中必有一人去； (3)喬、宋兩人中去且僅去一人； (4)宋、黎兩人同去或同時不去； (5)若鄒去，則曹、喬也同去； 解：用小寫字母表示： c:曹去， q：喬去 s：宋去 l：黎去 z：鄒去時，以上5句話可表示為如下的公式： (c?q)、(l?z)、((q??s)?(?q?s))、(s?l)、(z?(q?c))， 5句話同時成立即每句話的值均為1，也即其合取式(c?q)?(l?z)?((q??s)?(?q?s))?(s?l)?(z?(q?c))為1,(c?q)?(l?z)?((q??s)?(?q?s))?(s?l)?(z?(q?c)) ? (?c?q)?(l?z)?((q??s)?(?q?s))?((s?l)?(?s??l))?(?z?(q?c)) ?(?c?q)?(l?z)?(?z?(q?c))?((q??s?s?l)?(q??s??s??l)?(?q?s?s?l)?(?q?s??s??l)) ?(?c?q)?(l?z)?(?z?(q?c))?((q??s??l)?(?q?s?l)) ?(?c?q)?(l?z)?((?z?q??s??l)?(?z??q?s?l)?(q?c??s??l)) ?(?c?q)?((?z??q?s?l)?(z?q?c??s??l)) ?(?c??z??q?s?l)?(z?q?c??s??l) 因(c?q)?(l?z)?((q??s)?(?q?s))?(s?l)?(z?(q?c))為1，故1?(?c??z??q?s?l)?(z?q?c??s??l)， 故1?(?c??z??q?s?l)或1?(z?q?c??s??l) 故 方案一是：曹不去、鄒不去、喬不去，宋與黎去。 方案二是：曹去、喬去、鄒去，宋與黎均不去,在某班班委的選舉中，該班的甲、乙、丙學(xué)生預(yù)言： 甲說：王娟為班長、劉強(qiáng)為生活委員； 乙說：金鑫為班長、王娟為生活委員； 丙說：劉強(qiáng)為班長、王娟為學(xué)習(xí)委員； 結(jié)果公布后，發(fā)現(xiàn)甲、乙、丙三人都恰好對了一半，請問王娟、劉強(qiáng)、金鑫各任何職？ 解：p1,q1,r1:表示王娟，劉強(qiáng)，金鑫是班長； p2,q2,r2:分別表示王娟，劉強(qiáng)，金鑫是學(xué)習(xí)委員； p3,q3,r3:分別表示王娟，劉強(qiáng)，金鑫是生活委員； “每個人說法對一半”將是一個非常復(fù)雜的公式(p1??q3?r1??p3?q1??p2)?( p1??q3?r1??p3??q1?p2)?( p1??q3??r1?p3?q1??p2)?( p1??q3??r1?p3??q1?p2)?( ?p1?q3?r1??p3?q1??p2)?( ?p1?q3?r1??p3??q1?p2)?( ?p1?q3??r1?p3?q1??p2)?( ?p1?q3??r1?p3??q1?p2)，要構(gòu)造這9個變元的真值表，將需要29=512行，工作量實在太大了， ！,參考“真值表”，設(shè)計如下的判斷表,,1.6 推理理論 從已知條件、假設(shè)、前提或公理出發(fā)，根據(jù)推理規(guī)則推出結(jié)論、定理的過程，稱為推理 。 定義1 設(shè)A與C是兩個命題公式，若A?C為永真式(重言式)，則稱C是A的有效結(jié)論，或稱A可以邏輯推出C，記為A?C. 由“?”的定義可知，當(dāng)A為假時，A?C肯定為真，故只要考慮A為真時C是否為真即可，故有: 定義2 設(shè)A與C是兩個命題公式，若當(dāng)A為真時C也為真，則稱C是A的有效結(jié)論，或稱A可以邏輯推出C，記為A?C。 一般情況下，利用定義2去證明要簡單些，我們在其他學(xué)科中遇到的證明都是基于定義2的。 判斷A?C為永真可用等值演算、真值表等方法,例題 求證：A?(A?B)?B (A?(A?B)) ?B ??(A?(A?B))?B (?的等值式) ?? (A?(?A?B))?B (?的等值式) ? ? ((A??A)?(A?B))?B (分配律) ?? (0?(A?B))?B (合取的性質(zhì)) ?? (A?B)?B (析取的性質(zhì)) ?(?A??B)?B (德摩律) ??A?(?B?B) (結(jié)合律) ??A?1 (析取的性質(zhì)) ? 1 (析取的性質(zhì)) 所以(A?(A?B)) ?B是重言式，真值表也證永真 所以A?(A?B)?B。這是有名的“假言推理(modus ponens)”，或“分離原則”,假如我今年進(jìn)入年級前10名老爸給我買iphone 4; 期末考試后我為年級第8名，所以老爸應(yīng)該給我買iphone4。這是假言推理。 A?(A?B)?B 從形式上看，結(jié)論B是A?B的后件，推導(dǎo)的結(jié)果是將后件分離出來，故也稱為分離原則。 利用假言推理規(guī)則或分離規(guī)則，結(jié)合析取、合取、否定的定義，只要不歉麻煩，幾乎可推出所有的結(jié)論。 為了提高推理效率，還需要學(xué)習(xí)、掌握某些推理規(guī)則。,例題 求證 A?A?B 采用定義1來證明，即證明A?A?B為永真式。 A?A?B ??A?(A?B) (?的等值式) ?(?A?A)?B (結(jié)合律) ?1?B (析取的性質(zhì)) ?1 (析取的性質(zhì)) 所以A?A?B,例題 求證 A?B?A A?B?A ??(A?B)?A (?的等值式) ?(?A??B)?A (德摩律) ??A??B?A (結(jié)合律) ?1??B (析取的性質(zhì)) ?1 (析取的性質(zhì)) 類似 A?B?B 根據(jù)?的定義可知A?B為真時，A與B均為真，因此由推理定義2可知 A?B?A， A?B? B 。 同樣由?的定義可知A為真時 A?B為真，故由推理定義2可知A?A?B。 然這3個推理式不必記憶！推理定義2效率較高,例題 求證 (A?B)?(B?C)?(A?C) 根據(jù)定義1，要證明下式為永真式。 (A?B)?(B?C) ? (A?C) ??((A?B)?(B?C)) ?(A?C) (?的等值式) ??((?A?B)?( ?B?C)) ?(?A?C) (?的等值式) ?((A??B) ? (B??C)) ?(?A?C) (德摩律) ?((A? B)?(A? ?C )?(?B ? B) ?(?B??C)) ?(?A?C) (分配律) ?((A? B)?(A? ?C )?1?(?B??C)) ?(?A?C) (析取的性質(zhì)) ?((A? B)?(A? ?C )?(?B??C)) ?(?A?C) (析取的性質(zhì)) ?(A? B??A?C)?(A? ?C??A?C )?(?B??C??A?C) (分配律) ?(1? B?C)?(1? ?C?C )?(?B??A?1) (析取的性質(zhì)) ?1?1?1 (析取的性質(zhì)) ?1 (析取的性質(zhì)) 判斷公式的類型，除等值演算外，還有真值表與范式等方法。,例題 求證 (A?B)?(B?C)?(A?C),由上表可知， (A?B)?(B?C) ? (A?C) 為重言式， 由定義1可知(A?B)?(B?C)? (A?C)。 這是有名的傳遞律，要記住呀！,例題 求證 (A?B)?(C?D)?(A?C)?B?D 利用定義1證明了假言推理規(guī)則(A?B)?A?B,傳遞規(guī)則(A?B)?(B?C)?(A?C)。 有了這2條規(guī)則后,可用定義2來證明推理式了。 由于這2條規(guī)則的結(jié)論中沒有析取式，只有條件式，因此將題中結(jié)論?轉(zhuǎn)換為? B?D,題設(shè)中?轉(zhuǎn)換為? (1)(A?B)?(C?D)?(A?C)為真 前提條件(定義2的套路) (2) (A?B)為真 (1)及合取的性質(zhì) (3) (C?D)為真 (1)及合取的性質(zhì) (4) (A?C)為真 (1)及合取的性質(zhì) (5)(?B??A)為真 (2)及(A?B)? (?B??A) (6) (?A?C)為真 (4)及(A?C) ?(?A?C) (7) (?B?C)為真 (5)、(6)及推理傳遞律 (8) (?B?D)為真 (7)、(3)及推理傳遞律 (9) B?D為真 (8)及(?B?D) ?B?D,例題 求證 (A?B)?(C?D)?(?B??D)?A??C 可用傳遞律來證明，還有更高效的方法 由定義1只要證((A?B)?(C?D)?(?B??D))?(A??C)為重言式，而 ((A?B)?(C?D)?(?B??D))?(A??C) ??((A?B)?(C?D)?(?B??D))? (?A??C) ?(? ((A?B)?(C?D)?(?B??D))??A)??C) ??((A?B)?(C?D)?(?B??D))?A)??C) ?((A?B)?(C?D)?(?B??D))?A)??C 故只需證 ((A?B)?(C?D)?(?B??D))?A)??C為重言式 即只需證明(A?B)?(C?D)?(?B??D))?A??C A從結(jié)論中挪到前提中，這種技巧稱為附加條件(CP)法，適合于結(jié)論為條件式的情形。,例題 求證 (A?B)?(C?D)?(?B??D)?A??C (1)(A?B)?(C?D)?(?B??D)?A為真 CP規(guī)則及前提 (2)A?B為真 (1)及合取的性質(zhì) (3)A為真 (1)及合取的性質(zhì) (4)B為真 (2)(3)及假言推理式(A?B)?A?B (5)?B??D為真 (1)及合取的性質(zhì) (6)B??D為真 (5)及?B??D?B??D (7)?D為真 (4)(6)及假言推理式(B??D)?B??D (8)C?D為真 (1)及合取的性質(zhì) (9)?D??C為真 (8)及原命題?逆否命題 (10)?C為真 (7)(9)假言推理式(?D??C)??D??C 提示：熟練后可不寫(1)式，直接引用(2)(3)(5)(8)！,例題 求證 (A?B)?(C?D)?(?B??D)?A??C (1)A?B為真 前提條件 (2)A為真 附加前提 (3)B為真 (1)(2)及假言推理式(A?B)?A?B (4)?B??D為真 前提條件 (5)B??D為真 (4)及?B??D?B??D (6)?D為真 (3)(5)及假言推理式(B??D)?B??D (7)C?D為真 前提條件 (8)?D??C為真 (7)及原命題?逆否命題 (9)?C為真 (6)(8)假言推理式(?D??C)??D??C,求證 (W?R)?V, V?(C?S),S?U,?C,?U??W 提示：此處用逗號簡寫前述各例中的合取式，從而鼓勵大家直接引用前提。 利用假言推理、傳遞律及前面所學(xué)的等值式，可以推出結(jié)論。在黑板上演示一番 考慮到本題的結(jié)論是?W，可采用反證法。 根據(jù)定義2可知“當(dāng)前提為真時結(jié)論也為真”， 反證法是“前提為真時，假設(shè)結(jié)論不為真即結(jié)論的否定為真”。 即基于前提、結(jié)論否定進(jìn)行推理。 如果推出了一個矛盾的結(jié)論出來，則說明“假設(shè)結(jié)論不為真”是錯誤的，即表示結(jié)論只能為真了,求證 (W?R)?V, V?(C?S),S?U,?C,?U??W (1)??W為真 假設(shè)結(jié)論?W為0即? ? W為1(真) (2)W為真 (1)與否定的性質(zhì) (3)(W?R)為真 (2)與析取的性質(zhì) (4)(W?R)?V為真 前提條件 (5)V為真 (4)(3)假言推理((W?R)?V)?(W?R)? V (6)V?(C?S)為真 前提條件 (7) (C?S)為真 (5)(6)假言推理(V?(C?S))?V?(C?S) (8) ?C?S為真 (7)與條件式的等值式C?S??C?S (9)?C為真 前提條件 (10)S為真 (8)(9)與假言推理(?C?S)?( ?C)?S (11) S?U為真 前提條件 (12)U為真 (10)(11)假言推理(S?U)?S?U (13) ?U為真 前提條件 顯然(12)與(13)矛盾，故假設(shè)有誤！,應(yīng)用題 天氣情況要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回來后不做飯， 結(jié)論是：如果我已做飯那么肯定天下雨了。 解：用M表示天晴， R表示天下雨， C表示爬山， F表示做飯，則問題可表示為 M?R，M?C，C??F?F?R (M??R)?(?M?R) ，M?C，C??F?F?R,應(yīng)用題M?R，M?C，C??F?F?R (1)F為真 附件前提 (2)C??F為真 前提條件 (3)??F??C為真 (2)的等值式 (4) F??C為真 (3)的等值式 (5) ?C為真 (1)(4)的假言推理 (6) M?C為真 前提條件 (7)?C??M為真 (6)的等值式 (8) ?M為真 (5)(7)的假言推理 (9) M?R為真 前提條件 (10) ?M?R為真 (9)的等值式 (11) R為真 (8)(10)的假言推理,應(yīng)用題M?R，M?C，C??F?F?R (1)F為真 附件前提 (2)C??F為真 前提條件 (3)??F??C為真 (2)的等值式 (4) F??C為真 (3)的等值式 (5) ?C為真 (1)(4)的假言推理 (6) M?C為真 前提條件 (7)?C??M為真 (6)的等值式 (8) ?M為真 (5)(7)的假言推理 (9) (M??R)?(?M?R)為真 前提條件 (10) ? (M??R) ? (?M?R)為真 (9)的等值式 (11) ? M?R ? (?M?R)為真 (10)的等值式 (12) ? M?R為真 (8)與析取的定義 (13) (?M?R)為真 (11)(12)的假言推理 (14) R為真 (13)與合取的定義,定義2證明推理式的規(guī)律 (1)利用“條件等值式”，盡可能將前提、中間結(jié)論及最終結(jié)論中的“析取式”轉(zhuǎn)換為“條件式”，以便可引用假言推理、傳遞律。 (2)如果結(jié)論為條件式，則將條件式的前件做為附加前提。CP原則 (3)如果結(jié)論的否定在前提中多次出現(xiàn)，可采 用反證法。 (4)每一步的推理理由可簡化，如“前提條件”簡寫為“P”，“假言推理”可簡寫“M”，等值式只寫“等值”或簡寫“E”。 (5)這種從前提出發(fā)，應(yīng)用已證明的推理式，不斷推出中間結(jié)論，最后推出結(jié)論的方式，稱為自然推理，這是最常見的方式。,1.7消解規(guī)則 證明(A?C)?(B??C)?A?B (1) (A?C)為真 前提條件 (2) ?A? C為真 與(1)等值 (3) B??C為真 前提條件 (4) ?C? B為真 與(3)等值 (5)C?B為真 與(4)等值 (6) ?A?B為真 (2)(5)傳遞律 (7) A?B為真 與(6)等值 因此當(dāng)(A?C)?(B??C)為真時，A?B為真。 由于(A?C?(B??C)中互補(bǔ)的公式C、?C同時消失了，稱“A?B”為 “(A?C)，(B??C)”的消解式。 因此在采用定義2進(jìn)行推理時，只要(A?C)、(B??C)同時為真，則可直接寫出A?B為真，從而節(jié)省大量的中間環(huán)節(jié)，提高了證明效率。,1.7消解規(guī)則 例題 (A?B)?(C?D)?(?B??D)?A??C 利用條件式的等值式，則此題等價于證明 (?A?B)?(?C?D)?(?B??D)??A??C (1) (?A?B)為真 前提條件 (2) (?B??D)為真 前提條件 (3) ?A??D為真 當(dāng)(1)(2)為真消解式?A??D為真 (4) ?C?D為真 前提條件 (5) ?A??C為真 當(dāng)(3)(4)為真消解式?A??C為真 采用假言推理原則時，盡可能將析取轉(zhuǎn)換為條件式。 采用消解法時，盡可能將條件式轉(zhuǎn)換為析取。 消解法是一種高效的方法。 消解法可完成1.6節(jié)中所有推理式,1.7消解規(guī)則 采用定傳遞律證明了(A?C)?(B??C)?A?B 因A?B? ?A?B,故可用假言推理及CP原則證明 (1) ?A為真 附加前提 (2) (A?C)為真 前提條件 (3) ?A? C為真 與(1)等值 (4) C為真 (1)(3)假言推理 (5) B ? ?C 為真 前提條件 (6)C?B為真 與(4)等值 (7) B為真 (4)(6)假言推理 用假言推理證明了消解規(guī)則，反過來 用消解規(guī)則可證明假言推理,1.7消解規(guī)則 用假言推理證明了消解規(guī)則證明了 (A?C)?(B??C)?A?B 反過來，用消解規(guī)則可證明假言推理 A?(A?B)?B A?B為真 前提條件 ?A ?B為真 與(1)等值 A為真 前提條件 B為真 (2)(3)消解得到 “假言推理”與“消解規(guī)則”可以互相推出，因此一方推出的結(jié)論另一方也可以推出 因此習(xí)題三可由消解規(guī)則推導(dǎo)出來呀,