第1章-命題邏輯

1、1,第1篇 數(shù)理邏輯 Mathematical Logic,,2,引言,邏輯是不可戰(zhàn)勝的,因?yàn)橐磳?duì)邏輯還得使用邏輯. ——P.Boutroux數(shù)學(xué)在過去幾乎完全與科學(xué)相聯(lián)結(jié),而邏輯則與希臘哲學(xué)連結(jié).但二者在現(xiàn)代都發(fā)展了.邏輯變得更數(shù)學(xué)了而數(shù)學(xué)變得更邏輯了.無法在二者之間劃分界限.

2、 ——D.Vira現(xiàn)代數(shù)學(xué)和數(shù)理邏輯已經(jīng)使下述事情成為可能,即不但在物理和工程中應(yīng)用數(shù)學(xué),而且在工業(yè)規(guī)劃、醫(yī)學(xué)、生物化學(xué)、生物物理,以至于在哲學(xué)和語言學(xué)問題中應(yīng)用數(shù)學(xué). ——H.F.Fehr,3,赫拉克利特,赫拉克利特(Heraclitus, 約公元前540年

3、-前480年)古希臘哲學(xué)家赫拉克利特認(rèn)為神是涵蓋整個(gè)世界的事物. 但他常常用邏各斯(logos, 即理性)一詞來代替神. 他相信世界上有“普遍的理性”來指導(dǎo)大自然發(fā)生的每一件事.,什么是邏輯?,4,logic最早被清末的嚴(yán)復(fù)翻譯成漢語邏輯, 屬音義意義相結(jié)合的公認(rèn)比較完美的翻譯, 當(dāng)然主要是音譯. 后由中國傳入日本, 但在日語中則注明只是對(duì)logic的注音, logic在日語中的正式漢語翻譯詞為“論理”.logic另外有個(gè)很好的意

4、譯譯名“理則”, 稱為理則學(xué), 這是由牟宗三先生翻譯所作, 比早期的邏輯翻譯更符合logic的英文定義與拉丁詞源. 1.思維的規(guī)律; 2.客觀的規(guī)律; 3.指處理事情的方式,規(guī)矩的意思.邏輯是人的一種抽象思維, 是人通過概念,判斷,推理,論證來理解和區(qū)分客觀世界的思維過程.,什么是邏輯?(續(xù)),5,邏輯學(xué)是研究人的思維的科學(xué).它包含:辯證邏輯:是研究人的思維中的辯證法.例如:用全面的和發(fā)展的觀點(diǎn)觀察事物;具體問題具體分析;實(shí)

5、踐是檢查事物正誤的唯一標(biāo)準(zhǔn);等等.形式邏輯:是研究人的思維的形式和一般規(guī)律.這里我們只關(guān)心形式邏輯.,什么是邏輯?(續(xù)),6,人的思維過程: 概念 ? 判斷 ? 推理 正確的思維: 概念清楚, 判斷正確, 推理合乎邏輯. 人們是通過各種各樣的學(xué)習(xí)(理論學(xué)習(xí)和從實(shí)踐中學(xué)習(xí))來掌握許多概念和判斷.而形式邏輯主要是研究推理的.推理: 是由若干個(gè)已知的判斷

6、(前提),推出新的判斷(結(jié)論)的思維過程.,什么是邏輯?(續(xù)),7,推理方法類比推理:由個(gè)別事實(shí)推出個(gè)別結(jié)論. 如: 地球上有空氣和水, 地球上有生物. 火星上有空氣和水. ?火星上有生物.歸納推理:由若干個(gè)別事實(shí)推出一般結(jié)論. 如: 銅能導(dǎo)電. 鐵能導(dǎo)電. 錫能導(dǎo)電. 鉛能導(dǎo)電. …… ?一切金屬都導(dǎo)電.演繹推理: 由一般規(guī)律推出個(gè)別事實(shí).形式邏輯主要是研究演繹推理的.,什么是邏輯?(續(xù)),8,演繹

7、推理 舉例例1: 如果天下雨, 則路上有水. (一般規(guī)律) 天下雨了. (個(gè)別事實(shí)) 推出結(jié)論: 路上有水. (個(gè)別結(jié)論)例2: (大前提): 所有金屬都導(dǎo)電. (一般規(guī)律) (小前提): 銅是金屬. (個(gè)別事實(shí)) 推出結(jié)論: 銅能導(dǎo)電. (個(gè)別結(jié)論),什么是邏輯?(續(xù)),

8、9,數(shù)理邏輯(Mathematical Logic)是用數(shù)學(xué)的方法研究形式邏輯.所謂“數(shù)學(xué)方法”:是建立一套有嚴(yán)格定義的符號(hào), 即建立一套形式語言, 來研究形式邏輯.所以數(shù)理邏輯也稱為“符號(hào)邏輯”.數(shù)理邏輯的主要內(nèi)容:邏輯演算, 證明論, 遞歸論, 模型論, 公理集合論我們這里只涉及邏輯演算中“命題邏輯”和“謂詞邏輯”.數(shù)理邏輯與數(shù)學(xué)的其它分支,計(jì)算機(jī)科學(xué),人工智能,語言學(xué)等學(xué)科均有密切聯(lián)系.下面就前面兩個(gè)例子,說明如何將推

9、理符號(hào)化的.,什么是數(shù)理邏輯?,10,數(shù)理邏輯把推理符號(hào)化之一:例1: 如果天下雨, 則路上有水. 天下雨了. 所以路上有水. 設(shè)P表示:天下雨. 設(shè)Q表示:路上有水.設(shè)?表示:如果…則… 例1的推理過程表示為: 前提1: P?Q (如果天下雨,則路上有水.) 前提2: P (天下雨了.) 結(jié) 論: Q (路上有水.) (這就是第一章命題邏輯中要討論的問題.),什么是數(shù)理邏輯?(續(xù)),1

10、1,數(shù)理邏輯把推理符號(hào)化之二:例2: 所有金屬都導(dǎo)電. 銅是金屬. 所以銅能導(dǎo)電.設(shè)M(x): x是金屬. C(x): x能導(dǎo)電.設(shè)?x 表示: 所有的x. 設(shè) a 表示銅.例2的推理過程表示為:前提: ?x(M(x)?C(x)) (所有金屬都導(dǎo)電.) M(a)?C(a) 前提: M(a) (銅是金屬.) 結(jié)論: C(a)

11、 (銅能導(dǎo)電.) (其中符號(hào)M(x), C(x)是謂詞, 所以這就是第二章“謂詞邏輯”中所討論的內(nèi)容.),什么是數(shù)理邏輯?(續(xù)),12,Dijkstra談數(shù)理邏輯,“假如我早年在數(shù)理邏輯上下點(diǎn)功夫, 就不會(huì)出那么多錯(cuò)誤, 不少東西在數(shù)理邏輯上早就講過了。如果我年輕20歲, 一定會(huì)去學(xué)數(shù)理邏輯?！?——Dijkstra,Edsger Wybe Dijks

12、tra (1930-2002),13,錢學(xué)森談“計(jì)算機(jī)與數(shù)理邏輯”,電子計(jì)算機(jī)與數(shù)理邏輯具有非常密切的關(guān)系。正是在數(shù)理邏輯中，把人類的推理過程分解成一些非常簡單原始的、非常機(jī)械的動(dòng)作，才使得用機(jī)器代替人類的推理的設(shè)想有了實(shí)現(xiàn)的可能。 有了電子計(jì)算機(jī)，使用它時(shí)，必須先進(jìn)行程序設(shè)計(jì)，把整個(gè)推理、計(jì)算過程絲毫不漏地考慮到，統(tǒng)統(tǒng)編入程序，而機(jī)器則依次而運(yùn)行；如稍有錯(cuò)誤，將立即得到毫無意義的結(jié)果。可見必須有足夠的數(shù)理邏輯的訓(xùn)練，熟悉推理過

13、程的全部細(xì)節(jié),才能從事程序設(shè)計(jì)。 此外，程序設(shè)計(jì)是一個(gè)很細(xì)致又很麻煩的工作，如何從事程序設(shè)計(jì)，如何防止在計(jì)算過程中出錯(cuò)，如何很快地發(fā)現(xiàn)這種錯(cuò)誤而及時(shí)加以改正，都是程序設(shè)計(jì)理論(軟件理論)中非常根本又非常重要的內(nèi)容，大家都認(rèn)為，這些內(nèi)容都與數(shù)理邏輯息息相關(guān)。,14,第1章 命題邏輯,15,第1章 命題邏輯,1.1 命題邏輯基本概念 1.2 命題邏輯等值演算 1.3 范式1.4 命題邏輯推理理論,16,1.1 命題邏輯基本

14、概念,1.1.1 命題與聯(lián)結(jié)詞命題與真值(簡單命題, 復(fù)合命題)聯(lián)結(jié)詞(¬, ?, ?, ?, ?) 1.1.2 命題公式與分類命題公式及其賦值真值表命題公式的分類,17,命題及其真值,命題: 判斷結(jié)果惟一的陳述句命題的真值: 判斷的結(jié)果, 真或假例 (1)北京是中華人民共和國的首都.(2)南京是中華人民共和國的首都.真命題: 真值為真的命題假命題: 真值為假的命題注意: 感嘆句, 祈使句, 疑

15、問句都不是命題陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題,18,例 下列句子中那些是命題？ (1) 北京是中華人民共和國的首都.(2) 2 + 5 ＝10.(3) x + 6 ＞ 4.(4) 你會(huì)開車嗎？(5) 2050年元旦南京是晴天.(6) 這只兔子跑得真快呀！(7) 請(qǐng)關(guān)上窗戶！(8) 我正在說謊話.,真命題,假命題,真值不確定,疑問句,感嘆句,祈使句,悖論,(1),(2),(5)是命題, (3),(4

16、),(6)~(8)都不是命題,真值確定, 但未知,實(shí)例,19,我正在,謊話!,說,悖論:一種導(dǎo)致矛盾的陳述.悖論(paradox)一詞來自希臘語“para+dokein”, 意思是“多想一想”.,20,簡單命題與復(fù)合命題,簡單命題(原子命題):簡單陳述句構(gòu)成的命題簡單命題的符號(hào)化:用p, q, r, … , pi, qi, ri (i≥1)表示用“1”表示真, 用“0”表示假復(fù)合命題:由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句 例

17、 (1)如果明天天氣好, 我們就出去郊游.設(shè)p:明天天氣好, q:我們出去郊游, 如果p, 則q (2)張三一面喝茶一面看報(bào).設(shè)p:張三喝茶, q:張三看報(bào), p并且q,21,聯(lián)結(jié)詞,定義1.1 設(shè)p為命題, 復(fù)合命題 “非p”(或 “p的否定”)稱為p的否定式, 記作?p, 符號(hào)?稱作否定聯(lián)結(jié)詞, 并規(guī)定?p為真當(dāng)且僅當(dāng) p為假.例(1) p:北京是中華人民共和國的首都.?p:北京不是中華人民共和

18、國的首都.p為真, ?p為假(2) p:2是合數(shù), ?p: 2不是合數(shù), p為假, ?p為真,“否定”真值表,22,聯(lián)結(jié)詞(續(xù)),定義1.2 設(shè)p,q為二命題, 復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式, 記作p ? q, ? 稱作合取聯(lián)結(jié)詞, 并規(guī)定 p ? q為真當(dāng)且僅當(dāng) p與q同時(shí)為真.例(1) p:2是偶數(shù), q: 2是素?cái)?shù),p?q: 2是偶素?cái)?shù),p為真, q為真, p?q為真(2) p:

19、2是偶數(shù), q: 4是奇數(shù),p?q: 2是偶數(shù)且4是奇數(shù),p為真, q為假, p?q為假,“并且”真值表,23,實(shí)例,例 將下列命題符號(hào)化. (1) 王曉既用功又聰明.(2) 王曉不僅聰明, 而且用功.(3) 王曉雖然聰明, 但不用功.,解: 記 p:王曉用功, q:王曉聰明,(1) p ? q,(2) p ? q,(3) ?p ? q,24,實(shí)例(續(xù)),例 將下列命題符號(hào)化. (4) 張輝與王麗都是三好

20、生.(5) 張輝與王麗是同學(xué).(6) 王曉很聰明并且3是素?cái)?shù).,解: (4) 記 r:張輝是三好生, s:王麗是三好生. r ? s,(5) 簡單命題, 記 t:張輝與王麗是同學(xué),(6) 記u:王曉很聰明, v:3是素?cái)?shù). u ? v,注意: 只考慮命題與命題之間的形式關(guān)系,而不顧及語句的含義.,25,聯(lián)結(jié)詞(續(xù)),定義1.3 設(shè) p,q為命題, 復(fù)合命題“p或q”稱作p與q的析取式,記作p ? q, ? 稱作析取

21、聯(lián)結(jié)詞, 并規(guī)定p ? q為假當(dāng)且僅當(dāng)p與q同時(shí)為假.,“或者”真值表,例 張三和李四至少有一人會(huì)英語.(即,張三或李四會(huì)英語)設(shè) p:張三會(huì)英語, q:李四會(huì)英語,符號(hào)化為p?q,26,相容或與排斥或,例 張三和李四至少有一人會(huì)英語.(即,張三或李四會(huì)英語)設(shè) p:張三會(huì)英語, q:李四會(huì)英語, 符號(hào)化為p?q,例 今晚我看電視或者我讀書.不能同時(shí)看電視和讀書.設(shè) p:今晚我看電視, q:今晚我讀書, 符號(hào)化為(

22、p??q)?(?p?q),27,例 將下列命題符號(hào)化(1) 2或4是素?cái)?shù).(2) 2或3是素?cái)?shù).(3) 4或6是素?cái)?shù).,解 記 p:2是素?cái)?shù), q:3是素?cái)?shù), r:4是素?cái)?shù), s:6是素?cái)?shù),(1) p ? r, 真值: 1(2) p ? q, 真值: 1(3) r ? s, 真值: 0,實(shí)例,28,例 將下列命題符號(hào)化(4) 元元只能拿一個(gè)蘋果或一個(gè)梨.(5) 王曉紅生于1975年或1976年.(6) 今天是晴

23、天或3是素?cái)?shù).,解,(4) 記t:元元拿一個(gè)蘋果,u:元元拿一個(gè)梨. (t??u)?(?t?u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年. (v??w)?(?v?w) 又可形式化為 v?w(6)記v:今天是晴天, w:3是素?cái)?shù). v?w,實(shí)例(續(xù)),29,聯(lián)結(jié)詞(續(xù)),定義1.4 設(shè) p,q為二命題, 復(fù)合命題 “如果p,則q” 稱作p與q的蘊(yùn)涵式, 記作p?q, 并稱

24、p是蘊(yùn)涵式的前件, q為蘊(yùn)涵式的后件. ?稱作蘊(yùn)涵聯(lián)結(jié)詞, 并規(guī)定, p?q為假當(dāng)且僅當(dāng) p為真且q為假.例如果明天天氣好, 我們就出去郊游.設(shè)p:明天天氣好, q:我們出去郊游, 形式化為 p?q,“蘊(yùn)含”真值表,30,聯(lián)結(jié)詞(續(xù)),說明: (1) p?q 的邏輯關(guān)系: p是q的充分條件, q為p的必要條件(2) 當(dāng)p為假時(shí), p?q為真(不管q為真, 還是為假)例 如果你掙的錢超過＄25000, 那你必須備案交

25、稅.(3) “如果p, 則q”的多種表述方式: 若p, 就q 只要p, 就q p僅當(dāng)q 只有q才p 除非q, 才p 除非q, 否則非p,31,實(shí)例,例 設(shè)p:天冷, q:小王穿羽絨服.將下列命題符號(hào)化 (1) 只要天冷, 小王就穿羽絨服.(2) 因?yàn)樘炖? 所以小王穿羽絨服.(3) 若小王不穿羽絨服, 則天不冷.(4) 只有天冷, 小王才穿羽絨服.(5

26、) 除非天冷, 小王才穿羽絨服.(6) 除非小王穿羽絨服, 否則天不冷.(7) 如果天不冷, 則小王不穿羽絨服.(8) 小王穿羽絨服僅當(dāng)天冷的時(shí)候.,注意: p?q 與 ?q??p 等值(真值相同),p?q,p?q,p?q,p?q,q?p,q?p,q?p,q?p,32,聯(lián)結(jié)詞(續(xù)),定義1.5 設(shè)p, q為命題, 復(fù)合命題 “p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式, 記作p?q, ?稱作等價(jià)聯(lián)結(jié)詞. 并規(guī)定p?q為真當(dāng)且僅當(dāng)

27、 p與q同時(shí)為真或同時(shí)為假.p?q 的邏輯關(guān)系: p與q互為充分必要條件例這件事張三能做好, 且只有張三能做好.設(shè)p:張三做這件事, q:這件事做好了形式化為: p?q,“等價(jià)”真值表,33,實(shí)例,例 求下列命題的真值(1) 2+2＝4 當(dāng)且僅當(dāng) 3+3＝6.(2) 2+2＝4 當(dāng)且僅當(dāng) 3是偶數(shù).(3) 2+2＝4 當(dāng)且僅當(dāng) 太陽從東方升起.(4) 2+2＝5 當(dāng)且僅當(dāng) 美國位于非洲.(5) f (x)在x0處可

28、導(dǎo)的充要條件是它在 x0處連續(xù).,1,0,1,1,0,34,聯(lián)結(jié)詞(續(xù)),35,復(fù)合命題的符號(hào)化,例 將下列命題符號(hào)化(1)只有你主修計(jì)算機(jī)科學(xué)或不是新生,才可以從校園網(wǎng)訪問因特網(wǎng).(2) 除非你已滿16周歲,否則只要你身高不足4英尺就不能乘公園滑行鐵道.,解: (1)設(shè)p:你主修計(jì)算機(jī)科學(xué), q:你是新生, r:你可以從校園網(wǎng)訪問因特網(wǎng). 符號(hào)化為r?(p??q)(2)設(shè)p:你已滿16周歲, q:你身高不足4英尺, r:你

29、能乘公園滑行鐵道. 符號(hào)化為(?p?q)??r,36,命題常項(xiàng): 簡單命題2+2=4.北京是一個(gè)大城市.0,1命題變項(xiàng): 不確指的簡單命題用p, q, r, … 表示p, q, r, …稱為取值0或1的變項(xiàng)p, q, r, …既以可表示命題常項(xiàng), 又可以表示命題變項(xiàng), 需要由上下文確定它們表示的是常項(xiàng)還是變項(xiàng).,命題公式,37,命題公式,定義1.6 合式公式 (命題公式, 公式) 遞歸定義如下:(1) 單個(gè)命題常項(xiàng)或變

30、項(xiàng)是合式公式,并稱作原子合式公式(2) 若A是合式公式, 則 (?A)也是合式公式(3) 若A, B是合式公式, 則(A?B), (A?B), (A?B), (A?B)也 是合式公式(4) 只有有限次地應(yīng)用(1)~(3)形成的符號(hào)串才是合式公式,說明: (1)聯(lián)結(jié)詞優(yōu)先級(jí): ( ), ?, ?, ?, ?, ?; (2)同級(jí)按從左到右的順序進(jìn)行; (3)在不影響運(yùn)算順序時(shí), 括號(hào)可以省去.,例 0, p, ?p?q

31、, (p?q)?(?p?r), p?q?r, (p?q)?r,38,公式的賦值,定義1.7 設(shè)p1, p2, … , pn是出現(xiàn)在公式A中全部的命題變項(xiàng), 給 p1, p2, … , pn指定一組真值, 稱為對(duì)A的一個(gè)賦值或解釋.使公式為真的賦值稱作成真賦值, 使公式為假的賦值稱作成假賦值說明: (1) 賦值記作?=?1?2…?n, ?i=0或1, 諸?i之間不加標(biāo)點(diǎn)符號(hào)(2) 通常賦值與命題變項(xiàng)之間按下標(biāo)或字母順序?qū)?yīng),

32、 即當(dāng)A的全部命題變項(xiàng)為p1, p2, … , pn時(shí), 給A賦值?1?2…?n是指p1=?1, p2=?2,…, pn=?n; 當(dāng)A的全部命題變項(xiàng)為p,q,r,…時(shí), 給A賦值?1?2?3…是指p=?1, q=?2, r=?3, …,39,實(shí)例,例 公式A=(?p1 ? ?p2 ? ?p3)?(p1 ? p2) 000是成真賦值, 001是成假賦值 公式B=(p?q)?r 000是成假賦值, 0

33、01是成真賦值,40,真值表,例 給出公式的真值表(1) (q?p) ?q?p,真值表: 命題公式在所有可能的賦值下的取值的列表含n個(gè)變項(xiàng)的公式有2n個(gè)賦值.,41,實(shí)例(續(xù)),(2) ?(?p?q)?q,42,實(shí)例(續(xù)),(3) (p?q)??r,43,命題公式的分類,重言式(永真式): 無成假賦值的命題公式矛盾式(永假式): 無成真賦值的命題公式可滿足式: 非矛盾式的命題公式注意: 重言式是可滿足式, 但反之不真.例

34、 上例中(1) (q?p)?q?p 重言式,可滿足式(2) ?(?p?q)?q 矛盾式(3) (p?q)??r 非重言式的可滿足式,44,1.2 命題邏輯等值演算,1.2.1 等值式與基本等值式1.2.2 等值演算,45,若A與B在所有可能賦值下的真值都相同, 即A與B有相同的真值表, 稱A與B等值.,例 判斷 ?(p?q) 與 ?p??q 是否等值解,結(jié)論: ?(p?q)與?p??q等值,等值式

35、,?(p?q)?(?p??q),1111,46,等值式,定義1.8 若等價(jià)式A?B是重言式, 則稱A與B等值, 記作A?B, 并稱A?B是等值式.說明: (1) ?是元語言符號(hào), 不要混同于?和=(2) A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同, 即A與B有相同的真值表(3) n個(gè)命題變項(xiàng)的真值表共有 個(gè), 故每個(gè)命題公式都有無窮多個(gè)等值的命題公式(4) 可能有啞元出現(xiàn). 在B中出現(xiàn), 但不在A

36、中出現(xiàn)的命題變項(xiàng)稱作A的啞元. 同樣,在A中出現(xiàn), 但不在B中出現(xiàn)的命題變項(xiàng)稱作B的啞元. 啞元的值不影響命題公式的真值.,47,實(shí)例,例 判斷下述3個(gè)公式之間的等值關(guān)系: p?(q?r), (p?q)?r, (p?q)?r解,p?(q?r) ? (p?q)?r, 但與(p?q)?r不等值,48,基本等值式,雙重否定律 ??A ? A冪等律 A?A ? A, A?A

37、 ? A交換律 A?B ? B?A, A?B ? B?A結(jié)合律 (A?B)?C ? A?(B?C) (A?B)?C ? A?(B?C)分配律 A?(B?C) ? (A?B)?(A?C) A?(B?C) ? (A?B)?(A?C)德摩根律 ?(A?

38、B) ? ?A??B ?(A?B) ? ?A??B吸收律 A?(A?B) ? A, A?(A?B) ? A,49,基本等值式(續(xù)),零律 A?1 ? 1, A?0 ? 0 同一律 A?0 ? A, A?1 ? A排中律 A??A ? 1

39、矛盾律 A??A ? 0蘊(yùn)涵等值式 A?B ? ?A?B等價(jià)等值式 A?B ? (A?B)?(B?A)假言易位 A?B ? ?B??A等價(jià)否定等值式 A?B ? ?A??B歸謬論 (A?B)?(A??B) ? ?A,50,等值演算,等值演算: 由已知的等值式推演出新的等值

40、式的過程置換規(guī)則: 若A?B, 則?(A)??(B) 例 證明 p?(q?r) ? (p?q)?r證 p?(q?r) ? ?p?(?q?r) (蘊(yùn)涵等值式) ? (?p??q)?r (結(jié)合律) ? ?(p?q)?r (德摩根律) ? (p?q)?r (蘊(yùn)涵等值式),51,實(shí)例,等值演算不能直接證明兩個(gè)公式不等值. 證明兩個(gè)公式不等值的基本

41、思想是找到一個(gè)賦值使一個(gè)成真, 另一個(gè)成假.,例 證明: p?(q?r) (p?q)?r方法一 真值表法(見前例)方法二 觀察法. 容易看出000使左邊成真, 使右邊成假.方法三 先用等值演算化簡公式, 再觀察.A=p?(q?r) ? ?p?(?q?r) ? ?p??q?rB=(p?q)?r ? (?p?q)?r ? ?(?p?q)?r ? (p??q)?r容易看出000,010是A的成真賦值, 是B的成

42、假賦值.,52,實(shí)例,例 用等值演算法判斷下列公式的類型(1) q??(p?q) 解 q??(p?q) ? q??(?p?q) (蘊(yùn)涵等值式) ? q?(p??q) (德摩根律) ? p?(q??q) (交換律,結(jié)合律) ? p?0 (矛盾律) ? 0 (零律)該式為矛盾

43、式.,53,實(shí)例(續(xù)),(2) (p?q)?(?q??p) 解 (p?q)?(?q??p) ? (?p?q)?(q??p) (蘊(yùn)涵等值式) ? (?p?q)?(?p?q) (交換律) ? 1該式為重言式.,54,實(shí)例(續(xù)),(3) ((p?q)?(p??q))?r 解 ((p?q)?(p??q))?r ? (p?(q??q))?r (分配律) ?

44、p?1?r (排中律) ? p?r (同一律)非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.,總結(jié): A為矛盾式當(dāng)且僅當(dāng)A?0; A為重言式當(dāng)且僅當(dāng)A?1說明: 演算步驟不惟一, 應(yīng)盡量使演算短些.,55,1.3 范式,1.3.1 析取范式與合取范式簡單析取式與簡單合取式析取范式與合取范式1.3.2 主析取范式與主合取

45、范式極小項(xiàng)與極大項(xiàng)主析取范式與主合取范式,56,簡單析取式與簡單合取式,文字:命題變項(xiàng)及其否定的統(tǒng)稱簡單析取式:有限個(gè)文字構(gòu)成的析取式例 p, ?q, p??q, p?q?r, …簡單合取式:有限個(gè)文字構(gòu)成的合取式例 p, ?q, p??q, p?q?r, …定理1.1 (1) 一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它的否定(2) 一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它的否定,57,析

46、取范式與合取范式,析取范式:由有限個(gè)簡單合取式組成的析取式A1?A2???Ar, 其中A1,A2,?,Ar是簡單合取式合取范式:由有限個(gè)簡單析取式組成的合取式A1?A2???Ar , 其中A1,A2,?,Ar是簡單析取式范式:析取范式與合取范式的統(tǒng)稱 定理1.2 (1) 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個(gè)簡單合取式都是矛盾式.(2) 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每一個(gè)簡單析取式都是重言式.,58,范式

47、存在定理,定理1.3 任何命題公式都存在著與之等值的析取范式與合取范式.證 求公式F的范式的步驟:(1) 消去F中的?, ? A?B??A?B A?B?(?A?B)?(A??B)(2) 否定聯(lián)結(jié)詞?的內(nèi)移或消去 ??A? A ?(A?B)??A??B ?(A?B)??A??B,59,范式存在定理(續(xù)),(3) 使用分配律 A?(B?C)?(A?B)?(A?C

48、) 求合取范式 A?(B?C)?(A?B)?(A?C) 求析取范式例 求?(p?q)??r 的析取范式與合取范式解 ?(p?q)??r ? ?(?p?q)??r ? (p??q)??r 析取范式 ? (p??r)?(?q??r) 合取范式注意: 公式的析取范式與合取范式不惟一.,60,極小項(xiàng)與

49、極大項(xiàng),定義1.17 在含有n個(gè)命題變項(xiàng)的簡單合取式(簡單析取式)中,若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次,而且第i(1?i?n)個(gè)文字(按下標(biāo)或字母順序排列)出現(xiàn)在左起第i位上,稱這樣的簡單合取式(簡單析取式)為極小項(xiàng)(極大項(xiàng)).,例 (1)有3個(gè)命題變項(xiàng)p1, p2, p3,?p1?p2?p3, ?p1??p2??p3, p1??p2??p3都是極小項(xiàng)?p1?p2?p3, p1??p2??p3, p1??p2??p3都是

50、極大項(xiàng)(2)有3個(gè)命題變項(xiàng)p, q, r, p?q?r, p??q?r, ?p?q??r都是極小項(xiàng)p?q?r, p??q?r, ?p?q??r都是極大項(xiàng),61,極小項(xiàng)與極大項(xiàng)(續(xù)),定理1.4 設(shè)mi 與Mi是由同一組命題變項(xiàng)形成的極小項(xiàng)和極大項(xiàng), 則 ?mi ? Mi , ?Mi ? mi,62,極小項(xiàng)與極大項(xiàng)(續(xù)),極小項(xiàng) 極大項(xiàng) 公式

51、 成真賦值 名稱 公式 成假賦值 名稱 ?p??q??r 0 0 0 m0 p?q?r 0 0 0 M0 ?p??q?r 0 0 1 m1 p?q??r 0 0 1 M1 ?p?q??r 0 1 0

52、 m2 ?p?q 1 0 M2 ?p?q?r 0 1 1 m3 ?p??q??r 1 1 M3 p??q??r 1 0 0 m4 p??q?r 1 0 1 m5 ?p?q??r 1 1

53、 0 m6 ?p?q?r 1 1 1 m7,,,,,,,,,,p,q,r形成的極小項(xiàng)與極大項(xiàng),63,主析取范式與主合取范式,主析取范式:由極小項(xiàng)構(gòu)成的析取范式主合取范式:由極大項(xiàng)構(gòu)成的合取范式例 n=3, 命題變項(xiàng)為p, q, r時(shí),(?p??q?r)?(?p?q?r) ? m1?m3 是主析取范式 (p?q??r)?(?p?q??r) ? M1?M5 是主合取范式定理1

54、.5 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是惟一的.,64,求主析取范式的步驟,設(shè)公式A含命題變項(xiàng)p1, p2, …, pn(1) 求A的析取范式A? =B1? B2? … ? Bs, 其中Bj是簡單合取式 j=1,2, … ,s (2) 若某個(gè)Bj既不含pi , 又不含?pi , 則將Bj展開成 Bj ? Bj?(pi??pi) ? (Bj?pi)?(Bj??pi)重復(fù)這

55、個(gè)過程, 直到所有簡單合取式都是長度為n的極小項(xiàng)為止(3) 消去重復(fù)出現(xiàn)的極小項(xiàng), 即用mi代替mi?mi(4) 將極小項(xiàng)按下標(biāo)從小到大排列,65,實(shí)例,例 求?(p?q)??r 的主析取范式解 ?(p?q)??r ? (p??q)??r p??q ? (p??q)?1 (同一律) ? (p??q)?(?r?r)

56、 (排中律) ? (p??q??r)?(p??q?r) (分配律) ? m4?m5 ?r ? (?p?p)?(?q?q)??r (同一律,排中律) ? (?p??q??r)?(?p?q??r)?(p??q??r)?(p?q??r) ? m0? m

57、2? m4? m6 (分配律)得 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6可記作 ? ?(0,2,4,5,6),66,主析取范式快速求法,設(shè)公式含有n個(gè)命題變項(xiàng), 則長度為k的簡單合取式可展開成2n?k個(gè)極小項(xiàng)的析取,例 求 A ? (?p?q)?(?p??q?r)?r 的主析取范式解 用快速

58、求法 ?p?q ? (?p?q??r)?(?p?q?r) ? m2? m3 ?p??q?r ? m1 r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1? m3? m5? m7得 A? m1? m2? m3? m5? m7 ??(1,2,3,5,7),67,求主合取范式的步驟,設(shè)公式A含命題變項(xiàng)p1, p2, …, pn(1) 求A

59、的合取范式A? =B1?B2? … ?Bs, 其中Bj是簡單析取式 j=1,2, … ,s (2) 若某個(gè)Bj既不含pi , 又不含?pi , 則將Bj展開成 Bj ? Bj?(pi??pi) ? (Bj?pi)?(Bj??pi)重復(fù)這個(gè)過程, 直到所有簡單析取式都是長度為n的極大項(xiàng)為止(3) 消去重復(fù)出現(xiàn)的極大項(xiàng), 即用Mi代替Mi?Mi(4) 將極大項(xiàng)按下標(biāo)從小到大排列,68,實(shí)例,例 求?(

60、p?q)??r 的主合取范式解 ?(p?q)??r ? (p??r)?(?q??r) p??r ? p?0??r (同一律) ? p?(q??q)??r (矛盾律) ? (p?q??r)?(p??q??r) (分配律)

61、 ? M1?M3 ?q??r ? (p??p)??q??r (同一律,矛盾律) ? (p??q??r)?(?p??q??r) (分配律) ? M3?M7得 ?(p?q)??r ? M1?M3?M7可記作 ? ?(1,3,7),69,主合取范式快速求法,設(shè)公式含有n個(gè)命題變項(xiàng), 則長

62、度為k的簡單析取式可展開成2n?k個(gè)極大項(xiàng)的合取,例 求 B??p?(p?q??r)的主合取范式解 ?p ? (?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1得 B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7),70,由主析取范式求主合取范式,設(shè),沒有出現(xiàn)的極小項(xiàng)是,其中t=2n?s,,于是,例

63、求A=(?p??q?r)?(?p?q?r)?(p?q?r)的主合取范式解 A ? m1? m3? m7 ? M0 ? M2 ? M4 ? M5 ? M6,71,例 求?(p?q)??r 的主析取范式和主合取范式解 令A(yù) = ?(p?q)??r,p q r ?(p?q) ?r A ?A 0 0 0

64、0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0

65、 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0

66、 1 1 0 1 1 1 0 0 0 1,真值表法,72,求主析取范式:1.選出表中A的成真賦值所在行對(duì)應(yīng)的變項(xiàng)之值如下: 000,010,100,101,1102.將所尋出的各行變項(xiàng)之值還原成相應(yīng)的原子命題符號(hào), 值為1者還原為原變量, 值

67、為0者還原為原變量的否定,得到: ?p ?q ?r, ?p q ?r, p ?q ?r, p ?q r, p q ?r3.將上述各行分別構(gòu)成合取式: ?p??q??r, ?p?q??r, p??q??r, p??q?r, p?q??r4.將上述各合取式用析取詞”?”聯(lián)結(jié), 所得的析取式即為所求的主析取范式: (?p??q??r)?(?p?q??r)?(p??q??r)?(p??q?r)?(p?q??r),真值

68、表法(續(xù)),73,求主合取范式:,真值表法(續(xù)),2.再由?A的主析取范式得到A的主合取范式:A ? ??A ? ?((?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.求A的主合取范式, 先求?A的主析取范式:?A? (?p??q?r)?(?p?q?r)?(p?q?r),74,