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

1、1,第一章 命題邏輯,1.4 范式及用途,2,引言 給定一個命題公式，如何判斷它的類型—是重言式、矛盾式、還是可滿足式？ 目前已經(jīng)給出了兩種方法，即真值表法和邏輯等價演算法。 還有第三種方法，這就是把命題公式化成一種統(tǒng)一的、標準的公式—范式。,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òu)成的析取式稱為簡單析取式。僅由有限個命題變元或其否定構(gòu)成的合取式稱為簡單合取式。,4,2.析取范式和合取范式定義(1)僅由有限個簡單合取式構(gòu)成的析取式稱為析取范式；　 (2)僅由有限個簡單析取式構(gòu)成的合取式稱為合取范式。顯然任何析取范式的對偶式為合取范式；任何合取范式的對偶式為析取范式。,5,例如：A=(p∧┒q∧r)∨(┒p∧q)∨

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

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

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

6、至此，求出了原公式的合取范式。但上式可再化簡，得 ：?(p∨q)∧(┒r∨p)，該式也是原公式的合取范式（最簡），這說明與某個命題公式等價的合取范式是不唯一的。,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.極小項與主析取范式定義 在含n個命題變元的簡單合取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或其否定出現(xiàn)在從左起的第i位上(若命題變元無下標，則按字典順序)，這樣的簡單合取式稱為極小項。顯然，n個變元可構(gòu)成2n個不同

8、的極小項。,13,例如，3個命題變元可形成8個極小項。,┒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，則每個極小項對應一個二進制數(shù)，因而也對應一個十進制數(shù)。,15,3個命題變元構(gòu)成的8個極小項對應情況如下：,┒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,極小項 二進制 十進制,16,可用對應的十進制數(shù)作下標，用mi表示這一項, 即：,┒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,極小項 二進制 十進制 mi表示,17,一般地, n個變元的極小項是: m0 ?┒P1∧┒P2∧┒P3 …∧┒Pn m1 ?┒P1∧┒ P2∧┒P3 …∧Pn …… m2n-1 ? P1∧P2∧P

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

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

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

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

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

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

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

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

22、A為重言式，當且僅當A的主析取范式中含全部2n 個極小項；A為矛盾式，當且僅當A的主析取范式中不含任何極小項，可設A的主析取范式為0；若A的主析取范式中至少含一個極小項，則A是可滿足式。舉例3.求命題公式的成真和成假賦值 。舉例,31,練習：用主析取范式法判斷題下列公式的類型，并求公式的成真賦值。(p→q)→(┐q→┐p),分析： 求主析取范式可用真值表法，也可以用邏輯等價演算法： (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.極大項與主合取范式 定義 在含n個命題變元的簡單析取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且

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

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個命題變項共產(chǎn)生 個極大項，分別記為 。極大項也有3個性質(zhì)：(1)在極大項中，將命題變元記做0，命題變元的否定記為1，則每個極大項對應一個二進制數(shù)，該二進制數(shù)是該極大項唯一的成假賦值。(2)任意兩個不同的極大項的析取式的值永真。例如， 　　 (3)全體極大項的合取式的值永假，即,35,定義 設命題公式A中含n個命題變項，如果A的合取范式中的簡單析取式全是極大項，則稱該合

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

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

30、與極小項小標互補，則A的主合取范式為,41,6.主析取范式在實際中的應用 例 某科研所要從3名骨干A、B、C中挑選1-2名出國進修，由于工作需要選派時要滿足以下條件：（1）若A去，則C同去。（2）若B去，則C不能去。（3）若C不去，則A或B可以去。問所里應如何選派他們？,42,解 先命題符號化。設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.主析取范式的個數(shù) 一般來說，含n個變元的命題公式，其數(shù)量是無限的，但每個命題公式都對應著一個與它等價的主析取范式。如果兩個命題公式有相同的主析取

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

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

34、5 、 f6 、 f 7、 f8 、 f 13 、 f 14 、 f 15已定義； f 1 、 f10 、 f 11 、 f 16作為運算意義不大。因此， 只需再定義以下 4 個聯(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　　蘊含否定： P → Q ?┒(P→Q),,51,2.聯(lián)結(jié)詞的歸約 9 個聯(lián)結(jié)詞是否都必要? 顯然不是的, 只用∧ , ∨ , ┒三個聯(lián)結(jié)詞構(gòu)造的式子, 就足以把一切命題公式等價地表示出來。 根據(jù)德·摩根定律: ┒(P∧Q)?┒P∨┒Q, ┒(P∨Q) ?┒P∧┒Q 所以, ∧和∨中去掉一個也足以把一切命題公式等價地表示出來。

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