數(shù)理邏輯—命題邏輯(3)

1、1,第一章 命題邏輯,1.4 范式及用途,2,引言 給定一個(gè)命題公式，如何判斷它的類型—是重言式、矛盾式、還是可滿足式？ 目前已經(jīng)給出了兩種方法，即真值表法和邏輯等價(jià)演算法。 還有第三種方法，這就是把命題公式化成一種統(tǒng)一的、標(biāo)準(zhǔn)的公式—范式。,3,給定命題變元p,q， 則p，q，┑p， ┑q，p∨q，p∨ ┑q， ┑p∨q， ┑p∨┑q等都是簡單析取式，而 p，q，┑p， ┑q，p∧q，p∧ ┑q， ┑p∧q，

2、┑p∧┑q 都等都是簡單合取式。,1.簡單析取式和簡單合取式定義 僅由有限個(gè)命題變元或其否定構(gòu)成的析取式稱為簡單析取式。僅由有限個(gè)命題變元或其否定構(gòu)成的合取式稱為簡單合取式。,4,2.析取范式和合取范式定義(1)僅由有限個(gè)簡單合取式構(gòu)成的析取式稱為析取范式；　 (2)僅由有限個(gè)簡單析取式構(gòu)成的合取式稱為合取范式。顯然任何析取范式的對(duì)偶式為合取范式；任何合取范式的對(duì)偶式為析取范式。,5,例如：A=(p∧┒q∧r)∨(┒p∧q)∨

3、(p∧┒q) 　　 則A為析取范式。 A的對(duì)偶式為：　 A*=(p∨┒q∨r)∧(┒p∨q)∧(p∨┒q) 顯然，A*為合取范式。 對(duì)任何給定的命題公式，都能求出與之等價(jià)的析取范式與合取范式。,6,定理 (范式存在定理) 任一命題公式都存在著與之等價(jià)的析取范式和合取范式。,下述分析給出了任何命題公式范式存在性的證明，這證明同時(shí)也是求其范式的具體步驟，

4、即(1).消去對(duì) {┒、∧、∨} 來說冗余的聯(lián)結(jié)詞。即用基本的邏輯恒等式及置換規(guī)則將→、?聯(lián)結(jié)詞消去，所用的邏輯恒等式是 p→q? ┒p∨q p ?q ? (┒p∨q)∧(p∨┒q),7,(2).否定號(hào)消去或內(nèi)移　若遇有┒┒p或┒(p∧q)，┒(p∨q) 等形式，利用雙重否定律和德.摩根律可將否定號(hào)消去或內(nèi)移，即 ┒┒p?p ； ┒(p∧q)?┒p∨┒q ；

5、 ┒(p∨q)?┒p∧┒q。,8,(3).利用分配律 　若是求析取范式，應(yīng)該利用“∧”對(duì)“∨”的分配律；若是求合取范式，應(yīng)該利用“∨”對(duì)“∧”的分配律。 　任給一個(gè)命題公式A，經(jīng)過以上三步演算，可得到一個(gè)與A邏輯等價(jià)的析取范式或合取范式。 值得注意的是，任何命題公式的析取范式和合取范式都不是唯一的，我們把其中運(yùn)算符最少的稱為最簡析取(合取)范式。,9,例1 求下面命題公式的合取范式和析取范式。解 (1)求合取范式,

6、至此，求出了原公式的合取范式。但上式可再化簡，得 ：?(p∨q)∧(┒r∨p)，該式也是原公式的合取范式（最簡），這說明與某個(gè)命題公式等價(jià)的合取范式是不唯一的。,10,(2)求析取范式　　　　　　　　　　　 　 　　最后結(jié)果為原公式的析取范式，利用交換律和吸收律得 ，也是原公式的析取范式，由此可見，與命題公式等值的析取范式也是不唯一的。,11,例2 求P∧(

7、P→Q)的最簡析取范式。,解： P∧(P→Q) ?P∧(┒P∨Q) ? P∧┒P∨P∧Q ? 0∨P∧Q ? P∧Q,12,3.極小項(xiàng)與主析取范式定義 在含n個(gè)命題變元的簡單合取式中，若每個(gè)命題變元與其否定不同時(shí)存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變元或其否定出現(xiàn)在從左起的第i位上(若命題變元無下標(biāo)，則按字典順序)，這樣的簡單合取式稱為極小項(xiàng)。顯然，n個(gè)變元可構(gòu)成2n個(gè)不同

8、的極小項(xiàng)。,13,例如，3個(gè)命題變元可形成8個(gè)極小項(xiàng)。,┒P∧┒Q∧┒R ┒P∧┒Q∧ R ┒P∧ Q ∧┒R ┒P∧Q∧R P∧┒Q∧┒R P∧┒ Q∧R P∧Q∧ ┒R P∧Q∧R,14,如果將命題變元看成1，命題變元的否定看成0，則每個(gè)極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，因而也對(duì)應(yīng)一個(gè)十進(jìn)制數(shù)。,15,3個(gè)命題變元構(gòu)成的8個(gè)極小項(xiàng)對(duì)應(yīng)情況如下：,┒P∧┒Q∧┒R 0 0 0

9、 0 ┒P∧┒Q∧ R 0 0 1 1 ┒P∧ Q ∧┒R 0 1 0 2 ┒P∧Q∧R 0 1 1 3 P∧┒Q∧┒R 1 0 0 4 P∧┒ Q∧R 1 0 1

10、 5 P∧Q∧ ┒R 1 1 0 6 P∧Q∧R 1 1 1 7,極小項(xiàng) 二進(jìn)制 十進(jìn)制,16,可用對(duì)應(yīng)的十進(jìn)制數(shù)作下標(biāo)，用mi表示這一項(xiàng), 即：,┒P∧┒Q∧┒R 0 0 0 0 m0 ┒P∧┒Q∧ R 0 0 1

11、 1 m1 ┒P∧ Q ∧┒R 0 1 0 2 m2 ┒P∧Q∧R 0 1 1 3 m3 P∧┒Q∧┒R 1 0 0 4 m4 P∧┒ Q∧R 1 0 1 5 m5 P∧Q∧ ┒R

12、 1 1 0 6 m6 P∧Q∧R 1 1 1 7 m7,極小項(xiàng) 二進(jìn)制 十進(jìn)制 mi表示,17,一般地, n個(gè)變元的極小項(xiàng)是: m0 ?┒P1∧┒P2∧┒P3 …∧┒Pn m1 ?┒P1∧┒ P2∧┒P3 …∧Pn …… m2n-1 ? P1∧P2∧P

13、3 …∧Pn,18,極小項(xiàng)有以下3個(gè)性質(zhì)： (1)在極小項(xiàng)中，將命題變元記為1，命題變元的否定記為0，則每個(gè)極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)。則該二進(jìn)制數(shù)是該極小項(xiàng)唯一的成真賦值。,19,極小項(xiàng)有以下3個(gè)性質(zhì)： (1)在極小項(xiàng)中，將命題變元記為1，命題變元的否定記為0，則每個(gè)極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)。則該二進(jìn)制數(shù)是該極小項(xiàng)唯一的成真賦值。　(2)任意兩個(gè)不同的極小項(xiàng)的合取式的值永假。例如，,20,極小項(xiàng)有以下3個(gè)性質(zhì)： (1)在極小項(xiàng)

14、中，將命題變元記為1，命題變元的否定記為0，則每個(gè)極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)。則該二進(jìn)制數(shù)是該極小項(xiàng)唯一的成真賦值?！?2)任意兩個(gè)不同的極小項(xiàng)的合取式的值永假。例如， 　　                       

15、60;                　　　(3)全體極小項(xiàng)的析取式的值永真，即,21,定義 設(shè)命題公式A中含n個(gè)命題變元，如果A的析取范式中的簡單合取式全是極小項(xiàng)，則稱該析取范式為A的主析取范式。,定理 任何命題公式的主析取范式都是存在的，并且是唯一的。這是因?yàn)槿魏我粋€(gè)命

16、題公式都可求得它的析取范式（范式存在定理），而析取范式可化為主析取范式。,22,求給定命題公式A的主析取范式的步驟如下： 　1.求A的最簡析取范式A′；,23,求給定命題公式A的主析取范式的步驟如下： 　1.求A的最簡析取范式A′； 　2.若A′的某簡單合取式B中不含命題變元pi 或其否定┒pi，則將B展成如下形式：,24,求給定命題公式A的主析取范式的步驟如下： 　1.求A的最簡析取范式A′； 　2.若A′的某簡單合取式

17、B中不含命題變元pi 或其否定┒pi，則將B展成如下形式： 　　　 　3.將重復(fù)出現(xiàn)的命題變元、矛盾式及重復(fù)出現(xiàn)的極小項(xiàng)都“消去”。即將p∧p用p代替，p∧┒p用0代替、mi∨mi用 mi代替。,25,求給定命題公式A的主析取范式的步驟如下： 　1.求A的最簡析取范式A′； 　2.若A′的某簡單合取式B中不含命題變元pi 或其否定┒pi，則將B展成如下形式： 　　　

18、 　3.將重復(fù)出現(xiàn)的命題變元、矛盾式及重復(fù)出現(xiàn)的極小項(xiàng)都“消去”。即將p∧p用p代替，p∧┒p用0代替、mi∨mi用 mi代替。 　4.將極小項(xiàng)按由小到大的順序排列，并用Σ表示之，如m1∨m2∨m5用 表示。,26,例1 求命題公式 的主析取范式 解 先求地原公式的析取范式為：p∨(q∧┑r)含兩個(gè)簡單合取式p和(q∧┑r)。

19、在p中無q或┑q，r或┑r出現(xiàn)，因而應(yīng)該用p∧(┒q∨q)∧(┒r∨r)取代。在(q∧┑r) 中無┒p 或p，因而應(yīng)該用(┒p∨p)∧ (q∧┑r) 取代，然后展開得極小項(xiàng)。于是有：,27,(析取范式 ),28,由由極小項(xiàng)定義可知，上式中，2，4，5，6，7的二進(jìn)制表示010，100，101，110，111為原公式的成真賦值，而此公式的主析取范式中沒出現(xiàn)的極小項(xiàng)m0 、m1 、m3 的下標(biāo)為0、1、3，則對(duì)應(yīng)的二進(jìn)制表示000，001

20、，011為原公式的成假賦值。因而，只要知道一個(gè)命題公式A的主析取范式，可立即寫出A的真值表。 　　反之，若知道了A的真值表，找出A的所有成真賦值，用其對(duì)應(yīng)的十進(jìn)制數(shù)作為極小項(xiàng)的下標(biāo)，就可求得A的主析取范式中所含的全部極小項(xiàng)，從而可得到A的主析取范式。,定理 在公式A的真值表中，所有真值為1的賦值所對(duì)應(yīng)的極小項(xiàng)的析取式即為A的主析取范式。,29,例2 試由 p∧q∨r 的真值表求它的主析取范式。,由表可知，001，011，101，110

21、，111是原公式的成真賦值，因而對(duì)應(yīng)的十進(jìn)制數(shù)1，3，5，6，7為下標(biāo)的極小項(xiàng) 構(gòu)成 的主析取范式，而其它極小值不在它的主析取范式中，即,30,主析取范式的用途 1.判斷兩命題公式是否邏輯等價(jià) 。由于任何命題公式的主析取范式都是唯一的，因而若A?B，說明A與B有相同的主析取范式，反之，若A，B有相同的主析取范式，必有A?B 。 舉例2.判斷命題公式的類型 。設(shè)A是含n個(gè)命題變元的命題公式，

22、A為重言式，當(dāng)且僅當(dāng)A的主析取范式中含全部2n 個(gè)極小項(xiàng)；A為矛盾式，當(dāng)且僅當(dāng)A的主析取范式中不含任何極小項(xiàng)，可設(shè)A的主析取范式為0；若A的主析取范式中至少含一個(gè)極小項(xiàng)，則A是可滿足式。舉例3.求命題公式的成真和成假賦值 。舉例,31,練習(xí)：用主析取范式法判斷題下列公式的類型，并求公式的成真賦值。(p→q)→(┐q→┐p),分析： 求主析取范式可用真值表法，也可以用邏輯等價(jià)演算法： (p→q)→(┐q→┐p)? ┐(┐

23、p∨q)∨(q∨┐p) (消去→)? (p∧┐q)∨┐p∨q (┐內(nèi)移) (已為析取范式)? (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) ? m2∨m0∨m1∨m1∨m3 ? m0∨m1∨m2∨m3 所以，該式為重言式，00，01，10，11為成真賦值。,32,4.極大項(xiàng)與主合取范式 定義 在含n個(gè)命題變元的簡單析取式中，若每個(gè)命題變元與其否定不同時(shí)存在，而二者之一必出現(xiàn)且

24、僅出現(xiàn)一次，且第i個(gè)命題變元或其否定出現(xiàn)在左起的第i位上(若命題變元無角碼，則按字典順序排列)，這樣的簡單析取式稱為極大項(xiàng)。 　　同極小項(xiàng)情況類似，n個(gè)命題變元可產(chǎn)生2n個(gè)極大項(xiàng)，每個(gè)極大項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)和一個(gè)十進(jìn)制數(shù)，二進(jìn)制數(shù)為該極大項(xiàng)的成假賦值，十進(jìn)制數(shù)作為該極大項(xiàng)的抽象表示的角碼。,33,例如，n=3時(shí)，有8個(gè)極大項(xiàng)，對(duì)應(yīng)的二進(jìn)制數(shù)(成假賦值)、下標(biāo)及名稱如下：

25、 -----000------0，記作M0 -----001------1，記作M1 ------010------2，記作M2 ------011------3，記作M3

26、 ------100------4，記作M4 ------101------5，記作M5 ------110------6，記作M6 ------111------7，記作

27、M7,34,一般情況下，n個(gè)命題變項(xiàng)共產(chǎn)生 個(gè)極大項(xiàng)，分別記為 。極大項(xiàng)也有3個(gè)性質(zhì)：(1)在極大項(xiàng)中，將命題變元記做0，命題變元的否定記為1，則每個(gè)極大項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，該二進(jìn)制數(shù)是該極大項(xiàng)唯一的成假賦值。(2)任意兩個(gè)不同的極大項(xiàng)的析取式的值永真。例如， 　　 (3)全體極大項(xiàng)的合取式的值永假，即,35,定義 設(shè)命題公式A中含n個(gè)命題變項(xiàng)，如果A的合取范式中的簡單析取式全是極大項(xiàng)，則稱該合

28、取范式為主合取范式?！∪我幻}公式的主合取范式一定存在，且是唯一的。,求一命題公式A的主合取范式與求主析取范式的步驟非常相似，也是先求出合取范式A′。若A′的某簡單析取式B中不含命題變項(xiàng)pi或其否定┒pi ，則將B展成如下形式：,36,例 求 的主合取范式。解:,其中 表示合取。,37,5.主析取范式與主合取范式的關(guān)系 一個(gè)命題公式的主析取和主合取范式關(guān)系非常密切。 因?yàn)闃O小項(xiàng)與極大項(xiàng)之間存在著如下關(guān)

29、系：,例如，,38,設(shè)命題公式A中含n個(gè)命題變元，如果A的主析取范式中含k個(gè)極小項(xiàng) 。則┒A的主析取范式中必含 個(gè)極小項(xiàng)，設(shè)為 即,39,簡而言之，一個(gè)命題公式的極小項(xiàng)下標(biāo)與極大項(xiàng)下標(biāo)是互補(bǔ)的。 因此，只要求出了一個(gè)命題公式的主析取范式，就可根據(jù)它的極小項(xiàng)下標(biāo)立即求得極大項(xiàng)，并求出主合取范式(反之亦然)。,40,例如，A中含3個(gè)命題變項(xiàng)，主析取范式為　　 　　　 因?yàn)闃O大項(xiàng)

30、與極小項(xiàng)小標(biāo)互補(bǔ)，則A的主合取范式為,41,6.主析取范式在實(shí)際中的應(yīng)用 例 某科研所要從3名骨干A、B、C中挑選1-2名出國進(jìn)修，由于工作需要選派時(shí)要滿足以下條件：（1）若A去，則C同去。（2）若B去，則C不能去。（3）若C不去，則A或B可以去。問所里應(yīng)如何選派他們？,42,解 先命題符號(hào)化。設(shè)p：派A去。q：派B去。r：派C去。則由已知條件可得公式： (p→r)∧(q→┑r)∧(┑r→p∨q)經(jīng)過演算

31、可得 (p→r)∧(q→┑r)∧(┑r→p∨q) ?m1∨m2∨m5由于m1=┓p∧┓q∧r,m2= ┓p∧q∧┓r,m5= p∧┓q∧r。故，選派方案有以下三種：1.C去，A、B不去。2.B去，A、C不去。3.A、C同去，B不去。,43,7.主析取范式的個(gè)數(shù) 一般來說，含n個(gè)變元的命題公式，其數(shù)量是無限的，但每個(gè)命題公式都對(duì)應(yīng)著一個(gè)與它等價(jià)的主析取范式。如果兩個(gè)命題公式有相同的主析取

32、范式，我們稱這兩個(gè)命題公式屬于一個(gè)等價(jià)類。屬于一個(gè)等價(jià)類的命題公式，顯然是互相等價(jià)的那么，含n個(gè)命題變元的命題公式，有多少個(gè)等價(jià)類呢？,44,當(dāng)n=1時(shí), 極小項(xiàng)有 21=2 個(gè), 即P 、┒P。主析取范式有:,沒有極小項(xiàng),全部極小項(xiàng),45,當(dāng)n=2 時(shí)， 極小項(xiàng)有 22=4 個(gè)。即┒P∧ ┒Q 、 ┒P∧Q 、 P∧ ┒Q 、 P∧Q。主析取范式有,46,共222=16 個(gè)。 以此類推, n個(gè)命題變元, 可構(gòu)造22n個(gè)

33、不同的主析取范式(包括F)。這個(gè)數(shù)字增長非?？? 如n=3時(shí)223=256, n=4 時(shí)224=65 536。 主合取范式和主析取范式是一一對(duì)應(yīng)的，因此，n個(gè)命題變元，也可構(gòu)造22n個(gè)不同的主合取范式(包括T)。,47,第一章 命題邏輯,1.5 聯(lián)結(jié)詞的擴(kuò)充與歸約,48,1.聯(lián)結(jié)詞的擴(kuò)充,1）. 一元運(yùn)算,永假 恒等 否定式 永真,49,2）. 二元運(yùn)算,50,除f

34、5 、 f6 、 f 7、 f8 、 f 13 、 f 14 、 f 15已定義； f 1 、 f10 、 f 11 、 f 16作為運(yùn)算意義不大。因此， 只需再定義以下 4 個(gè)聯(lián)結(jié)詞: f 12 與非： P↑Q?┒(P∧Q) f2 或非： P↓Q ?┒(P∨Q) f9 排斥或(異或)： P⊕Q ?┒(P ?Q) ? P∧┒Q∨┒P∧Q

35、 f 3 , f 4　　蘊(yùn)含否定： P → Q ?┒(P→Q),,51,2.聯(lián)結(jié)詞的歸約 9 個(gè)聯(lián)結(jié)詞是否都必要? 顯然不是的, 只用∧ , ∨ , ┒三個(gè)聯(lián)結(jié)詞構(gòu)造的式子, 就足以把一切命題公式等價(jià)地表示出來。 根據(jù)德·摩根定律: ┒(P∧Q)?┒P∨┒Q, ┒(P∨Q) ?┒P∧┒Q 所以, ∧和∨中去掉一個(gè)也足以把一切命題公式等價(jià)地表示出來。

36、,52,定義 設(shè)C是一個(gè)聯(lián)結(jié)詞集合, 用其中的聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)地表達(dá)出來, 則這個(gè)聯(lián)結(jié)詞集合稱為全功能的。,53,顯然, 任一包含∧ , ∨ , ┒的聯(lián)結(jié)詞集合都是全功能的。 {∧ , ┒} 、{∨ , ┒}是全功能的。 {↑} , {↓}也是全功能的。 但{┒} 、{∧, ∨, →, ?} 不是全功能的。,54,例1，如：,所以，,,55,例2 判斷下列命題公式的類型。,所以，該式為重言式。,所以