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

數(shù)理邏輯命題邏輯第1頁，本講稿共55頁引言給定一個命題公式，如何判斷它的類型—是重言式、矛盾式、還是可滿足式？目前已經(jīng)給出了兩種方法，即真值表法和邏輯等價演算法。還有第三種方法，這就是把命題公式化成一種統(tǒng)一的、標準的公式—范式。2第2頁，本講稿共55頁給定命題變元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都等都是簡單合取式。

1.簡單析取式和簡單合取式定義

僅由有限個命題變元或其否定構(gòu)成的析取式稱為簡單析取式。僅由有限個命題變元或其否定構(gòu)成的合取式稱為簡單合取式。3第3頁，本講稿共55頁2.析取范式和合取范式定義(1)僅由有限個簡單合取式構(gòu)成的析取式稱為析取范式；(2)僅由有限個簡單析取式構(gòu)成的合取式稱為合取范式。顯然任何析取范式的對偶式為合取范式；任何合取范式的對偶式為析取范式。4第4頁，本講稿共55頁例如：A=(p∧┒q∧r)∨(┒p∧q)∨(p∧┒q)則A為析取范式。

A的對偶式為：A*=(p∨┒q∨r)∧(┒p∨q)∧(p∨┒q)顯然，A*為合取范式。對任何給定的命題公式，都能求出與之等價的析取范式與合取范式。5第5頁，本講稿共55頁定理(范式存在定理)任一命題公式都存在著與之等價的析取范式和合取范式。下述分析給出了任何命題公式范式存在性的證明，這證明同時也是求其范式的具體步驟，即(1).消去對{┒、∧、∨}來說冗余的聯(lián)結(jié)詞。即用基本的邏輯恒等式及置換規(guī)則將→、?聯(lián)結(jié)詞消去，所用的邏輯恒等式是p→q?┒p∨qp

?q?(┒p∨q)∧(p∨┒q)6第6頁，本講稿共55頁(2).否定號消去或內(nèi)移若遇有┒┒p或┒(p∧q)，┒(p∨q)等形式，利用雙重否定律和德.摩根律可將否定號消去或內(nèi)移，即┒┒p?p；

┒(p∧q)?┒p∨┒q；

┒(p∨q)?┒p∧┒q。7第7頁，本講稿共55頁(3).利用分配律

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

8第8頁，本講稿共55頁例1求下面命題公式的合取范式和析取范式。解(1)求合取范式

至此，求出了原公式的合取范式。但上式可再化簡，得：?(p∨q)∧(┒r∨p)，該式也是原公式的合取范式（最簡），這說明與某個命題公式等價的合取范式是不唯一的。

9第9頁，本講稿共55頁(2)求析取范式

最后結(jié)果為原公式的析取范式，利用交換律和吸收律得，也是原公式的析取范式，由此可見，與命題公式等值的析取范式也是不唯一的。

10第10頁，本講稿共55頁例2求P∧(P→Q)的最簡析取范式。解：P∧(P→Q)?P∧(┒P∨Q)

?

P∧┒P∨P∧Q?

0∨P∧Q?

P∧Q

11第11頁，本講稿共55頁3.極小項與主析取范式定義

在含n個命題變元的簡單合取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或其否定出現(xiàn)在從左起的第i位上(若命題變元無下標，則按字典順序)，這樣的簡單合取式稱為極小項。顯然，n個變元可構(gòu)成2n個不同的極小項。12第12頁，本講稿共55頁例如，3個命題變元可形成8個極小項。

┒P∧┒Q∧┒R

┒P∧┒Q∧R

┒P∧Q∧┒R

┒P∧Q∧R P∧┒Q∧┒RP∧┒Q∧RP∧Q∧┒RP∧Q∧R 13第13頁，本講稿共55頁如果將命題變元看成1，命題變元的否定看成0，則每個極小項對應一個二進制數(shù)，因而也對應一個十進制數(shù)。14第14頁，本講稿共55頁3個命題變元構(gòu)成的8個極小項對應情況如下：

┒P∧┒Q∧┒R 0000

┒P∧┒Q∧R 0011

┒P∧Q∧┒R 0102

┒P∧Q∧R 0113P∧┒Q∧┒R 1004P∧┒Q∧R 1015P∧Q∧┒R 1106P∧Q∧R 1117極小項二進制十進制15第15頁，本講稿共55頁可用對應的十進制數(shù)作下標，用mi表示這一項,即：

┒P∧┒Q∧┒R 0000m0

┒P∧┒Q∧R 0011m1

┒P∧Q∧┒R 0102m2

┒P∧Q∧R 0113m3

P∧┒Q∧┒R 1004m4

P∧┒Q∧R 1015m5

P∧Q∧┒R 1106m6

P∧Q∧R 1117m7

極小項二進制十進制mi表示16第16頁，本講稿共55頁一般地,n個變元的極小項是:m0?┒P1∧┒P2∧┒P3

…∧┒Pnm1?┒P1∧┒P2∧┒P3

…∧Pn……m2n-1?P1∧P2∧P3…∧Pn

17第17頁，本講稿共55頁極小項有以下3個性質(zhì)：(1)在極小項中，將命題變元記為1，命題變元的否定記為0，則每個極小項對應一個二進制數(shù)。則該二進制數(shù)是該極小項唯一的成真賦值。

18第18頁，本講稿共55頁極小項有以下3個性質(zhì)：(1)在極小項中，將命題變元記為1，命題變元的否定記為0，則每個極小項對應一個二進制數(shù)。則該二進制數(shù)是該極小項唯一的成真賦值。(2)任意兩個不同的極小項的合取式的值永假。例如，

19第19頁，本講稿共55頁極小項有以下3個性質(zhì)：(1)在極小項中，將命題變元記為1，命題變元的否定記為0，則每個極小項對應一個二進制數(shù)。則該二進制數(shù)是該極小項唯一的成真賦值。(2)任意兩個不同的極小項的合取式的值永假。例如，

(3)全體極小項的析取式的值永真，即20第20頁，本講稿共55頁定義

設(shè)命題公式A中含n個命題變元，如果A的析取范式中的簡單合取式全是極小項，則稱該析取范式為A的主析取范式。定理任何命題公式的主析取范式都是存在的，并且是唯一的。這是因為任何一個命題公式都可求得它的析取范式（范式存在定理），而析取范式可化為主析取范式。21第21頁，本講稿共55頁求給定命題公式A的主析取范式的步驟如下：

1.求A的最簡析取范式A′；

22第22頁，本講稿共55頁求給定命題公式A的主析取范式的步驟如下：

1.求A的最簡析取范式A′；2.若A′的某簡單合取式B中不含命題變元pi

或其否定┒pi，則將B展成如下形式：

23第23頁，本講稿共55頁求給定命題公式A的主析取范式的步驟如下：

1.求A的最簡析取范式A′；2.若A′的某簡單合取式B中不含命題變元pi

或其否定┒pi，則將B展成如下形式：

3.將重復出現(xiàn)的命題變元、矛盾式及重復出現(xiàn)的極小項都“消去”。即將p∧p用p代替，p∧┒p用0代替、mi∨mi用mi代替。

24第24頁，本講稿共55頁求給定命題公式A的主析取范式的步驟如下：

1.求A的最簡析取范式A′；2.若A′的某簡單合取式B中不含命題變元pi

或其否定┒pi，則將B展成如下形式：

3.將重復出現(xiàn)的命題變元、矛盾式及重復出現(xiàn)的極小項都“消去”。即將p∧p用p代替，p∧┒p用0代替、mi∨mi用mi代替。

4.將極小項按由小到大的順序排列，并用Σ表示之，如m1∨m2∨m5用表示。25第25頁，本講稿共55頁例1求命題公式的主析取范式

解先求地原公式的析取范式為：p∨(q∧┑r)含兩個簡單合取式p和(q∧┑r)。在p中無q或┑q，r或┑r出現(xiàn)，因而應該用p∧(┒q∨q)∧(┒r∨r)取代。在(q∧┑r)中無┒p或p，因而應該用(┒p∨p)∧(q∧┑r)取代，然后展開得極小項。于是有：26第26頁，本講稿共55頁(析取范式)27第27頁，本講稿共55頁由由極小項定義可知，上式中，2，4，5，6，7的二進制表示010，100，101，110，111為原公式的成真賦值，而此公式的主析取范式中沒出現(xiàn)的極小項m0、m1、m3的下標為0、1、3，則對應的二進制表示000，001，011為原公式的成假賦值。因而，只要知道一個命題公式A的主析取范式，可立即寫出A的真值表。

反之，若知道了A的真值表，找出A的所有成真賦值，用其對應的十進制數(shù)作為極小項的下標，就可求得A的主析取范式中所含的全部極小項，從而可得到A的主析取范式。定理

在公式A的真值表中，所有真值為1的賦值所對應的極小項的析取式即為A的主析取范式。28第28頁，本講稿共55頁例2試由p∧q∨r的真值表求它的主析取范式。1111111011101010000110110000101010000000p∧q∨rp∧qrqp由表可知，001，011，101，110，111是原公式的成真賦值，因而對應的十進制數(shù)1，3，5，6，7為下標的極小項構(gòu)成的主析取范式，而其它極小值不在它的主析取范式中，即29第29頁，本講稿共55頁主析取范式的用途

1.判斷兩命題公式是否邏輯等價。由于任何命題公式的主析取范式都是唯一的，因而若A?B，說明A與B有相同的主析取范式，反之，若A，B有相同的主析取范式，必有A?B。

舉例2.判斷命題公式的類型。設(shè)A是含n個命題變元的命題公式，A為重言式，當且僅當A的主析取范式中含全部2n個極小項；A為矛盾式，當且僅當A的主析取范式中不含任何極小項，可設(shè)A的主析取范式為0；若A的主析取范式中至少含一個極小項，則A是可滿足式。舉例3.求命題公式的成真和成假賦值。舉例30第30頁，本講稿共55頁練習：用主析取范式法判斷題下列公式的類型，并求公式的成真賦值。(p→q)→(┐q→┐p)分析：求主析取范式可用真值表法，也可以用邏輯等價演算法：(p→q)→(┐q→┐p)?┐(┐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為成真賦值。31第31頁，本講稿共55頁4.極大項與主合取范式

定義在含n個命題變元的簡單析取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或其否定出現(xiàn)在左起的第i位上(若命題變元無角碼，則按字典順序排列)，這樣的簡單析取式稱為極大項。

同極小項情況類似，n個命題變元可產(chǎn)生2n個極大項，每個極大項對應一個二進制數(shù)和一個十進制數(shù)，二進制數(shù)為該極大項的成假賦值，十進制數(shù)作為該極大項的抽象表示的角碼。

32第32頁，本講稿共55頁例如，n=3時，有8個極大項，對應的二進制數(shù)(成假賦值)、下標及名稱如下：

-----000------0，記作M0-----001------1，記作M1

------010------2，記作M2------011------3，記作M3

------100------4，記作M4------101------5，記作M5------110------6，記作M6------111------7，記作M733第33頁，本講稿共55頁一般情況下，n個命題變項共產(chǎn)生個極大項，分別記為。極大項也有3個性質(zhì)：(1)在極大項中，將命題變元記做0，命題變元的否定記為1，則每個極大項對應一個二進制數(shù)，該二進制數(shù)是該極大項唯一的成假賦值。(2)任意兩個不同的極大項的析取式的值永真。例如，

(3)全體極大項的合取式的值永假，即34第34頁，本講稿共55頁定義設(shè)命題公式A中含n個命題變項，如果A的合取范式中的簡單析取式全是極大項，則稱該合取范式為主合取范式。

任一命題公式的主合取范式一定存在，且是唯一的。

求一命題公式A的主合取范式與求主析取范式的步驟非常相似，也是先求出合取范式A′。若A′的某簡單析取式B中不含命題變項pi或其否定┒pi，則將B展成如下形式：35第35頁，本講稿共55頁例

求的主合取范式。解:其中表示合取。

36第36頁，本講稿共55頁5.主析取范式與主合取范式的關(guān)系

一個命題公式的主析取和主合取范式關(guān)系非常密切。因為極小項與極大項之間存在著如下關(guān)系：

例如，

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

因為極大項與極小項小標互補，則A的主合取范式為

40第40頁，本講稿共55頁6.主析取范式在實際中的應用

例

某科研所要從3名骨干A、B、C中挑選1-2名出國進修，由于工作需要選派時要滿足以下條件：（1）若A去，則C同去。（2）若B去，則C不能去。（3）若C不去，則A或B可以去。問所里應如何選派他們？

41第41頁，本講稿共55頁解

先命題符號化。設(shè)p：派A去。q：派B去。r：派C去。則由已知條件可得公式：

(p→r)∧(q→┑r)∧(┑r→p∨q)經(jīng)過演算可得(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不去。42第42頁，本講稿共55頁7.主析取范式的個數(shù)

一般來說，含n個變元的命題公式，其數(shù)量是無限的，但每個命題公式都對應著一個與它等價的主析取范式。如果兩個命題公式有相同的主析取范式，我們稱這兩個命題公式屬于一個等價類。屬于一個等價類的命題公式，顯然是互相等價的那么，含n個命題變元的命題公式，有多少個等價類呢？43第43頁，本講稿共55頁當n=1時,極小項有21=2個,即P、┒P。主析取范式有:沒有極小項全部極小項44第44頁，本講稿共55頁當n=2時，極小項有22=4個。即┒P∧┒Q、┒P∧Q、P∧┒Q、P∧Q。主析取范式有45第45頁，本講稿共55頁共222=16個。以此類推,n個命題變元,可構(gòu)造22n個不同的主析取范式(包括F)。這個數(shù)字增長非?？?如n=3時223=256,n=4時224=65536。

主合取范式和主析取范式是一一對應的，因此，n個命題變元，也可構(gòu)造22n個不同的主合取范式(包括T)。46第46頁，本講稿共55頁第一章命題邏輯1.5聯(lián)結(jié)詞的擴充與歸約47第47頁，本講稿共55頁1.聯(lián)結(jié)詞的擴充1）.一元運算Pf1f2

f3f

40100110101永假恒等