《命題邏輯等值演算》PPT課件.ppt

第二章命題邏輯等值演算,內(nèi)容：1.等值式2.析取范式與合取范式3.聯(lián)結(jié)詞的完備集,基本要求：,1.深刻理解等值式的概念。2.牢記24個基本等值式，這是等值演算的基礎(chǔ)；能熟練地應(yīng)用它們進行等值演算。3.了解簡單析取式、簡單合取式、析取范式、合取范式的概念。4.深刻理解極小項及極大項的定義及它們的名稱，及名稱下角標(biāo)與成真賦值的關(guān)系。5.熟練掌求公式的主析取范式的方法。6.熟練掌握由公式的主析取范式求公式的主合取范式的方法。7.會用公式的主析取范式（主合取范式）求公式的成真賦值、成假賦值。8.會將公式等值地化為任何聯(lián)結(jié)詞完備集中的公式。,某公司派小李或小張去上海出差，若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司是如何派遣的？,解：復(fù)合命題（公式）,例題,(p∨q),(p?r),(q?s),?r,∧,∧,∧,A=,(p∨q),(p?r),(q?s),?r,∧,∧,∧,A=,麻煩??！,計算量大??！,方法很多：真值表法等值演算法,,2.1等值式,1.例子看下面三個公式的真值表PQP?Q?P∨Q?Q??P00111011111000011111從真值表可以看出，不論對P、Q作何指派，都使得P?Q、?P∨Q和?Q??P的真值相同，表明它們之間彼此等價。,2.定義：A、B是含有命題變元P1,P2,…,Pn的命題公式，如不論對P1,P2,…,Pn作任何指派，都使得A和B的真值相同，則稱之為A與B等價，記作A?B。顯然P?Q??P∨Q??Q??P3.重要的等價公式⑴雙重否定律??A?A⑵冪等律A∨A?AA∧A?A⑶交換律A∨B?B∨AA∧B?B∧A⑷結(jié)合律A∨(B∨C)?(A∨B)∨CA∧(B∧C)?(A∧B)∧C,(6)德摩根律?(A∨B)??A∧?B?(A∧B)??A∨?B(7)吸收律A∨(A∧B)?AA∧(A∨B)?A(8)零律A∨1?1A∧0?0(9)同一律A∨0?AA∧1?A(10)排中律A∨?A?1(11)矛盾律A∧?A?0,⑸分配律A∨(B∧C)?(A∨B)∧(A∨C)A∧(B∨C)?(A∧B)∨(A∧C),(∨對∧的分配律),(∧對∨的分配律),(13)等價等值式A?B?(A?B)∧(B?A)A?B?(?A∨B)∧(A∨?B)A?B?(A∧B)∨(?A∧?B)(14)假言易位A?B??B??A(15)等價否定等值式A?B??A??B(16)歸謬論(A?B)∧(A??B)??A,(12)蘊含等值式A?B??A∨B,4.等價公式的證明方法方法1：用列真值表。（不再舉例）方法2：用公式的等價變換.(用置換定律)置換定律:A是一個命題公式，X是A中的一部分且也是合式公式，如果X?Y，用Y代替A中的X得到公式B，則A?B。應(yīng)用置換定律以及前面列出的等價公式可以對給定公式進行等價變換。,等值演算：由已知等值式推演出新的等值式的過程。,例題1.用等值演算法證明下面等值式：((p∨q)∧?(p∧q))??(p?q)q?(p?r)?(p∧q)?r,證明：(1)從左邊開始演算(p∨q)∧?(p∧q)???(p∨q)∧?(p∧q)(雙重否定律)??(?(p∨q)∨(p∧q))(德摩根律)??((?p∧?q)∨(p∧q))(德摩根律)??((?p∨p)∧(?p∨q)∧(?q∨p)∧(?q∨q))(分配律),??((?p∨q)∧(?q∨p))(同一律)??((p?q)∧(q?p))(蘊含等值式)??(p?q)(等價等值式),1,1,例題1.用等值演算法證明下面等值式：(2)q?(p?r)?(p∧q)?r,證明：(2)從右邊開始演算(p∧q)?r??(p∧q)∨r(蘊含等值式)??p∨?q∨r(德摩根律)??q∨(?p∨r)(交換律)??q∨(p?r)(蘊含等值式)?q?(p?r)(蘊含等值式),例題2.用等值演算法判斷下列公式的類型：(?p∨q)→(p∧q)p→(p∨?q∨r)(?(p→q)∧q)∧r,解：(1)(?p∨q)→(p∧q)??(?p∨q)∨(p∧q)(蘊含等值式)?(??p∧?q)∨(p∧q)(德摩根定律)?(p∧?q)∨(p∧q)(雙重否定律)?p∧(?q∨q)(分配律)?p∧1(排中律)?p(同一律),因為p是可滿足式，故式(1)為可滿足式,例題2.用等值演算法判斷下列公式的類型：(2)p→(p∨?q∨r),解：(2)p→(p∨?q∨r)??p∨(p∨?q∨r)(蘊含等值式)?(?p∨p)∨(?q∨r)(分配律)?1∨(?q∨r)(排中律)?1(零律),因為1是重言式，故式(2)為重言式,例題2.用等值演算法判斷下列公式的類型：(3)(?(p→q)∧q)∧r,解：(3)(?(p→q)∧q)∧r??(?p∨q)∧q)∧r(蘊含等值式)?p∧(?q∧q)∧r(德摩根律、結(jié)合律)?p∧0∧r(矛盾律)?0(零律),因為p是矛盾式，故式(3)為矛盾式,某公司派小李或小張去上海出差，若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司是如何派遣的？,(p∨q),(p?r),(q?s),?r,∧,∧,∧,A=,例題.用等值演算法解決實際問題,p：派小李去上海出差q：派小張去上海出差r：小趙要加班s：小王也去上海出差,?(p∨q)∧(?p∨r)∧(?q∨s)∧?r(德摩根律),?(p∨q)∧(?p∨r)∧?r∧(?q∨s)(交換律),?(p∨q)∧(?p∧?r)∧(?q∨s)(分配律、矛盾律),?((p∧?p∧?r)∨(q∧?p∧?r))∧(?q∨s)(分配律),?(q∧?p∧?r)∧(?q∨s)(矛盾律),?(q∧?p∧?r∧s)(分配律、矛盾律),結(jié)論：派遣方案為：派小張和小王去上海出差，只有這一種方案,2.2.范式,范式就是命題公式形式的規(guī)范形式。這里約定在范式中只含有聯(lián)結(jié)詞?、∨和∧。一.析取范式與合取范式1.合取式與析取式合取式：是用“∧”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。如P、?P、P∧?Q、P∧?Q∧?R析取式：是用“∨”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。如P、?P、P∨?Q、P∨?Q∨?R注:∵P∨P?PP∧P?P∴P是合(析)取式.,2.析取范式公式A如果寫成如下形式：A1∨A2∨...∨An(n≥1)其中每個Ai(i=1,2..n)是合取式，稱之為A的析取范式。3.合取范式公式A如果寫成如下形式：A1∧A2∧...∧An(n≥1)其中每個Ai(i=1,2..n)是析取式，稱之為A的合取范式。例如，P?Q的析取范式與合取范式：P?Q?(P∧Q)∨(?P∧?Q)----析取范式P?Q?(?P∨Q)∧(P∨?Q)----合取范式,4.析取范式與合取范式的寫法⑴先用相應(yīng)的公式去掉?和?。蘊含等值式P?Q??P∨Q等價等值式P?Q?(P∧Q)∨(?P∧?Q)P?Q?(P?Q)∧(Q?P)P?Q?(?P∨Q)∧(P∨?Q)⑵用公式的否定公式或德摩根律將?后移到命題變元之前。?A(P1,P2,…,Pn)?A*(?P1,?P2,…,?Pn)?(P∨Q)??P∧?Q?(P∧Q)??P∨?Q⑶用分配律、冪等律等公式進行整理，使之成為所要求的形式。,(對偶式),例如求(P?Q)?R的析取范式與合取范式(P?Q)?R??((?P∨Q)∧(P∨?Q))∨R?(P∧?Q)∨(?P∧Q)∨R------析取范式(P?Q)?R??((P∧Q)∨(?P∧?Q))∨R?((?P∨?Q)∧(P∨Q))∨R?(?P∨?Q∨R)∧(P∨Q∨R)---合取范式,二.主析取范式與主合取范式一個公式的析取范式與合取范式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。㈠主析取范式1.極小項⑴定義：在一個有n個命題變元的合取式中，每個變元必出現(xiàn)且僅出現(xiàn)一次，稱這個合取式是個極小項。例如，有兩個變元的極小項：P∧Q、P∧?Q、?P∧Q、?P∧?Q,⑵極小項的性質(zhì)m3m2m1m0PQP∧QP∧?Q?P∧Q?P∧?Q00FFFFFT01FTFFTF10TFFTFF11TTTFFFa).有n個變元，則有2n個極小項。b).每一組指派有且只有一個極小項為T。為了記憶方便，可將各組指派對應(yīng)的為T的極小項分別記作m0,m1,m2,…,m2n-1上例中m0??P∧?Qm1??P∧Qm2?P∧?Qm3?P∧Q,2.主析取范式定義析取范式A1∨A2∨...∨An,,其中每個Ai(i=1,2..n)都是極小項，稱之為主析取范式。3.主析取范式的寫法方法Ⅰ：列真值表⑴列出給定公式的真值表。⑵找出真值表中每個“T”對應(yīng)的極小項。(如何根據(jù)一組指派寫對應(yīng)的為“T”的項：如果變元P被指派為T，P在極小項中以P形式出現(xiàn)；如變元P被指派為F,P在極小項中以?P形式出現(xiàn)(因要保證該極小項為T))。⑶用“∨”聯(lián)結(jié)上述極小項，即可。,例如求P?Q和P?Q的主析取范式PQP?QP?QFFTTFTTFTFFFTTTTP?Q?m0∨m1∨m3?(?P∧?Q)∨(?P∧Q)∨(P∧Q)P?Q?m0∨m3?(?P∧?Q)∨(P∧Q)思考題:永真式的主析取范式是什么樣？,方法Ⅱ：用公式的等價變換⑴先寫出給定公式的析取范式A1∨A2∨...∨An。⑵為使每個Ai都變成極小項，對缺少變元的Ai補全變元，比如缺變元R，就用∧聯(lián)結(jié)永真式(R∨?R)形式補R。⑶用分配律等公式加以整理。P?Q??P∨Q?(?P∧(Q∨?Q))∨((P∨?P)∧Q)?(?P∧Q)∨(?P∧?Q)∨(P∧Q)∨(?P∧Q)?(?P∧Q)∨(?P∧?Q)∨(P∧Q),㈡主合取范式1.極大項⑴定義:在有n個命題變元的析取式中，每個變元必出現(xiàn)且僅出現(xiàn)一次,稱之為極大項。例如，有兩個變元的極大項及其真值表：M0M1M2M3PQP∨QP∨?Q?P∨Q?P∨?QFFFTTTFTTFTTTFTTFTTTTTTF,⑵極大項的性質(zhì)a).有n個變元，則有2n個極大項。b).每一組指派有且只有一個極大項為F。為了記憶方便，可將各組指派對應(yīng)的為F的極大項分別記作M0,M1,M2,…,M2n-1。上例中M0?P∨QM1?P∨?QM2??P∨QM3??P∨?Q,⑵極大項與極小項之間的關(guān)系,定理2.3：,2.主合取范式定義合取范式A1∧A2∧...∧An,,其中每個Ai(i=1,2..n)都是極大項，稱之為主合取范式。3.主合取范式的寫法方法Ⅰ：列真值表⑴列出給定公式的真值表。⑵找出真值表中每個“F”對應(yīng)的極大項。如何根據(jù)一組指派寫對應(yīng)的為“F”的極大項：如果變元P被指派為F，P在極大項中以P形式出現(xiàn)；如變元P被指派為T，P在極大項中以?P形式出現(xiàn)(確保該極大項為F)。⑶用“∧”聯(lián)結(jié)上述大項，即可。,例如求P?Q和P?Q的主合取范式PQP?QP?QFFTTFTTFTFFFTTTTP?Q?M2??P∨QP?Q?M1∧M2?(P∨?Q)∧(?P∨Q),方法Ⅱ：用公式的等價變換⑴先寫出給定公式的合取范式A1∧A2∧...∧An。⑵為使每個Ai變成極大項，對缺少變元的析取式Ai補全變元，比如缺變元R，就用∨聯(lián)結(jié)永假式(R∧?R)形式補R。⑶用分配律等公式加以整理。,例如，求(P?Q)?R的主合取范式(P?Q)?R??(?P∨Q)∨R?(P∧?Q)∨R?(P∨R)∧(?Q∨R)?(P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)?(P∨Q∨R)∧(P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R),三.主范式的應(yīng)用1.應(yīng)用主析取范式解決實際問題某公司派小李或小張去上海出差，若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司是如何派遣的？A＝(p∨q)∧(p?r)∧(q?s)∧?r?(p∨q)∧(?p∨r)∧(?q∨s)∧?r,?((p∧?p)∨(p∧s)∨(q∧?p)∨(q∧s))∧((?q∧?r)∨(r∧?r)),0,0,?((p∧s)∨(q∧?p)∨(q∧s))∧(?q∧?r)?(p∧s∧?q∧?r)∨0∨0?(p∧s∧?q∧?r)?m9,應(yīng)用2用主析取范式或主合取范式判斷兩個命題公式是否等值,,(1)設(shè)A=(p∧q)∨(?p∧q∧r)，B=(p∨(q∧r))∧(q∨(?p∧r)),,解：求A與B的主析取范式A=(p∧q)∨(?p∧q∧r)?(p∧q∧?r)∨(p∧q∧r)∨(?p∧q∧r)?(p∧q∧?r)∨(p∧q∧r)∨(?p∧q∧r),m6,m7,m3,?m3∨m6∨m7,B=(p∨(q∧r))∧(q∨(?p∧r))?(p∧q)∨(p∧?p∧r)∨(q∧r∧q)∨(q∧r∧?p∧r)?(p∧q∧r)∨(p∧q∧?r)∨(?p∧q∧r)∨(p∧q∧r)∨(?p∧q∧r),?m3∨m6∨m7,,,m7,m6,m3,?m3∨m6∨m7,由于A與B有相同的主析取范式，所以A?B,解：求A與B的主合取范式A=(p∧q)∨(?p∧q∧r)?(p∨?p)∧(p∨q)∧(p∨r)∧(q∨?p)∧(q∨?p)∧(q∨r)?(p∨q)∧(p∨r)∧(q∨?p)∧(q∨?p)∧(q∨r)?(p∨q)∧(p∨r)∧(?p∨q)∧(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),應(yīng)用2用主析取范式或主合取范式判斷兩個命題公式是否等值,,(1)設(shè)A=(p∧q)∨(?p∧q∧r)，B=(p∨(q∧r))∧(q∨(?p∧r)),,,M1,M0,M2,M5,M4,?M0∧M1∧M2∧M4∧M5,?M0∧M1∧M2∧M4∧M5,B=(p∨(q∧r))∧(q∨(?p∧r))?(p∨q)∧(p∨r)∧(q∨?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),解：求A與B的主合取范式A=(p∧q)∨(?p∧q∧r),應(yīng)用2用主析取范式或主合取范式判斷兩個命題公式是否等值,,(1)設(shè)A=(p∧q)∨(?p∧q∧r)，B=(p∨(q∧r))∧(q∨(?p∧r)),,M1,M0,M2,M5,M4,?M0∧M1∧M2∧M4∧M5,?M0∧M1∧M2∧M4∧M5,由于A與B有相同的主合取范式，所以A?B,說明：,A=(p∧q)∨(?p∧q∧r),?m3∨m6∨m7,?M0∧M1∧M2∧M4∧M5,沒出現(xiàn)在主析取范式中的極小項為m0,m1,m2,m4,m5.沒出現(xiàn)在主合取范式中的極大項為M3,M6,M7.所以由公式的主析取范式可以得到主合取范式也可由公式的主合取范式確定主析取范式,在演算中，若求主合取范式方便，則可先求主合取范式，然后再寫出主析取范式，這樣比直接求主析取范式方便；若求主析取范式方便，則可先求主析取范式，然后再寫出主合取范式，這樣比直接求主合取范式方便；,應(yīng)用3.判斷命題公式的類型設(shè)公式A中含n個命題變項，容易看出(1)A為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n個極小項。(2)A為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任何極小項。此時，記A的主析取范式為0.(3)A為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含有一個極小項。例題：用公式的主析取范式判斷公式的類型：,,應(yīng)用4.求命題公式的成真和成假賦值如在上例(3)中，000，001，011，101,111是成真賦值，010,100，110是成假賦值。,四、主析取范式與主合取范式的相互轉(zhuǎn)化,1.由公式的主析取范式求主合取范式步驟：,,,,例題：,2.重言式與矛盾式的主析取范式與主合取范式矛盾式無成真賦值，因而矛盾式的主合取范式含2n（n為公式中命題變項個數(shù)）個極大項，而重言式無成假賦值，因而主合取式不含任何極大項。將重言式的主合取式記為1，至于可滿足式，它的主合取范式中極大項的個數(shù)一定小于2n,注：A?B當(dāng)且僅當(dāng)A與B有相同的真值表，又當(dāng)且僅當(dāng)A與B有相同的主析取范式（主合取范式）。因而可以這樣說，真值表與主析取范式（主合取范式）是描述命題公式標(biāo)準(zhǔn)形的兩種不同的等價形式，因而兩者是可以相互確定的，即由A的主析取（主合?。┓妒?，立即可確定A的真值表，反之，由A的真值表可以立刻確定A的主析取（主合?。┓妒健?本節(jié)要掌握：析取范式、合取范式、主析取范式、主合取范式的寫法，范式的應(yīng)用。作業(yè)：習(xí)題二（P39）1,3(2),4(3),5(2),8(2),11(3),12,13,1415(1),16(2),23,25,30,