命題邏輯等值演算市公開(kāi)課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系第二章命題邏輯等值演算/10/10命題邏輯等值演算第1頁(yè)第二章命題邏輯等值演算

等值式

析取范式與合取范式聯(lián)結(jié)詞完備集可滿足性問(wèn)題與消解法知識(shí)點(diǎn)：等值式、置換規(guī)則、等值演算、(主)析取范式、(主)合取范式、聯(lián)結(jié)詞完備集、其它聯(lián)結(jié)詞、可滿足性問(wèn)題、消解法教學(xué)要求：深刻了解和掌握命題邏輯中基本概念教學(xué)重點(diǎn)：等值演算、(主)析取范式、(主)合取范式課時(shí):4/10/10命題邏輯等值演算第2頁(yè)§2.1等值式定義2.1設(shè)A,B是兩個(gè)命題公式,若A,B組成等價(jià)式AB為重言式,則稱A與B是等值,記為AB注意:是元語(yǔ)言符號(hào)，不是聯(lián)結(jié)詞?/10/10命題邏輯等值演算第3頁(yè)§2.1等值式16組(24個(gè))主要等值式雙重否定律A?┐┐A冪等律

A?A∨A,A?A∧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∨B)?┐A∧┐B┐(A∧B)?┐A∨┐B吸收律

A∨(A∧B)?A,

A∧(A∨B)?A零律

A∨1?1,A∧0?0?/10/10命題邏輯等值演算第4頁(yè)§2.1等值式同一律

A∨0?A，A∧1?A排中律

A∨┐A?1矛盾律

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?/10/10命題邏輯等值演算第5頁(yè)§2.1等值式代入實(shí)例：比如在蘊(yùn)涵等值式中

1.取A=p,B=q時(shí)，得到等值式p→q?┐p∨q2.取A=p→q,B=┐p時(shí)，得到等值式

(p→q)→┐p?┐(p→q)∨┐p?/10/10命題邏輯等值演算第6頁(yè)§2.1等值式判別兩個(gè)公式是否等值方法真值表法等值演算:

以一組基本又是主要重言式為基礎(chǔ)進(jìn)行公式之間演算置換規(guī)則：設(shè)Ф(A)是含公式A命題公式Ф(B)是用公式B置換了Ф(A)中A后得到命題公式若B?A,則Ф(B)?Ф(A)代入規(guī)則：在一個(gè)重言式(矛盾式)中，將同一命題變項(xiàng)全部用同一個(gè)命題公式替換后,得到公式仍是重言式(矛盾式)?/10/10命題邏輯等值演算第7頁(yè)§2.1等值式例1用等值演算法驗(yàn)證等值式

(p∨q)→r?(p→r)∧(q→r)

證：(p→r)∧(q→r)

?(┐p∨r)∧(┐q∨r)(蘊(yùn)涵等值式,替換規(guī)則)?(┐p∧┐q)∨r(分配律)?┐(p∨q)∨r(德摩根律)

?(p∨q)→r(蘊(yùn)涵等值式)用等值演算法判斷公式類(lèi)型

(1)(p→q)∧p→q(2)┐(p→(p∨q))∧r(3)p∧(((p∨q)∧p)→q)?/10/10命題邏輯等值演算第8頁(yè)§2.2析取范式與合取范式每種數(shù)字標(biāo)準(zhǔn)形都能提供很多信息，如代數(shù)式因式分解可判斷代數(shù)式根情況。邏輯公式在等值演算下也有標(biāo)準(zhǔn)形--范式范式有兩種析取范式合取范式

?/10/10命題邏輯等值演算第9頁(yè)§2.2析取范式與合取范式文字:

命題變項(xiàng)及其否定統(tǒng)稱作文字。簡(jiǎn)單析取式:僅有有限個(gè)文字組成析取式。簡(jiǎn)單合取式:僅有有限個(gè)文字組成合取式。析取范式:由有限個(gè)簡(jiǎn)單合取式組成析取式。合取范式:由有限個(gè)簡(jiǎn)單析取式組成合取式。

注意:一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。一個(gè)公式析取范式或合取范式不是唯一。p,┐pp∧┐q∧rp∨┐q∨r(p∧┐q)∨(p∧r)(p∨

┐q)∧(p∨r)?/10/10命題邏輯等值演算第10頁(yè)§2.2析取范式與合取范式一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它每個(gè)簡(jiǎn)單合取式都是矛盾式一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它每個(gè)簡(jiǎn)單析取式都是重言式范式存在定理:

任一命題公式都存在著與之等值析取范式與合取范式?/10/10命題邏輯等值演算第11頁(yè)§2.2析取范式與合取范式求范式可使用以下步驟:1.消去聯(lián)結(jié)詞→,?

2.否定號(hào)消去（利用雙重否定律）或內(nèi)移（利用德摩根）3.利用分配律：利用∧對(duì)∨分配律求析取范式利用∨對(duì)∧分配律求合取范式?/10/10命題邏輯等值演算第12頁(yè)§2.2析取范式與合取范式極小項(xiàng):在含有n個(gè)命題變項(xiàng)簡(jiǎn)單合取式中，若每個(gè)命題變項(xiàng)和它否定式不一樣時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變項(xiàng)或它否定式出現(xiàn)在從左算起第i位上,稱這么簡(jiǎn)單合取式為極小項(xiàng)。極大項(xiàng):在含有n個(gè)命題變項(xiàng)簡(jiǎn)單析取式中，若每個(gè)命題變項(xiàng)和它否定式不一樣時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變項(xiàng)或它否定式出現(xiàn)在從左算起第i位上,稱這么簡(jiǎn)單析取式為極大項(xiàng)。?/10/10命題邏輯等值演算第13頁(yè)§2.2析取范式與合取范式主析取范式:設(shè)由n個(gè)命題變項(xiàng)組成析取范式中全部簡(jiǎn)單合取式都是極小項(xiàng)，則稱該析取范式為主析取范式。主合取范式:設(shè)由n個(gè)命題變項(xiàng)組成合取范式中全部簡(jiǎn)單析取式都是極大項(xiàng)，則稱該合取范式為主合取范式。任何命題公式都存在與之等值主析取范式和主合取范式,而且是唯一。?/10/10命題邏輯等值演算第14頁(yè)§2.2析取范式與合取范式p,q,r形成極小項(xiàng)與極大項(xiàng)設(shè)mi與Mi是命題變項(xiàng)p1,p2,…,pn形成極小項(xiàng)和大項(xiàng)，則┐mi?Mi，┐Mi?mi?/10/10命題邏輯等值演算第15頁(yè)§2.2析取范式與合取范式注意：能夠由公式主析取范式求主合取范式。反之，也能夠由公式主合取范式確定主析取范式矛盾式無(wú)成真賦值，因而矛盾式主合取范式含2n（n為公式中命題變項(xiàng)個(gè)數(shù)）個(gè)極大項(xiàng)而重言式無(wú)成假賦值，因而主合取范式不含任何極大項(xiàng)重言式主合取范式記為1。矛盾式主析取范式為0可滿足式主析取范式中最少含有一個(gè)極小項(xiàng),主合取范式中極大項(xiàng)個(gè)數(shù)一定小于2n?/10/10命題邏輯等值演算第16頁(yè)§2.2析取范式與合取范式含n個(gè)命題變項(xiàng)全部沒(méi)有窮多合式公式中，和它們等值主析取范式（主合取范式）共有多少種不一樣情況。n個(gè)命題變項(xiàng)可產(chǎn)生2n個(gè)極小項(xiàng)（極大項(xiàng)），因而共可產(chǎn)生種不一樣主析取范式（主合取范式）?/10/10命題邏輯等值演算第17頁(yè)§2.2析取范式與合取范式真值表和主析取范式關(guān)系(1)(2)m0∨m1∨m2∨m3∨m4∨m5∨m7(3)m1∨m3∨m4∨m5∨m7真值表和主合取范式關(guān)系(1)(2)M6(3)M0∧M2∧M6?/10/10命題邏輯等值演算第18頁(yè)§2.3聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集:

設(shè)S是一個(gè)聯(lián)結(jié)詞集合，假如任何n(n≥1)元命題公式都能夠由僅含S中聯(lián)結(jié)詞組成公式等價(jià)地表示,則稱S是聯(lián)結(jié)詞完備集。

S={┐,∧,∨}是聯(lián)結(jié)詞完備集

?/10/10命題邏輯等值演算第19頁(yè)§2.3聯(lián)結(jié)詞完備集以下聯(lián)結(jié)詞集都是完備集：

(1)S1={┐,∧,∨,→}

(2)S2={┐,∧,∨,→,?}

(3)S3={┐,∧}

(4)S4={┐,∨}

(5)S5={┐,→}依據(jù)需要，人們還可結(jié)構(gòu)形式上更為簡(jiǎn)單聯(lián)結(jié)詞完備集。比如，在計(jì)算機(jī)硬件設(shè)計(jì)中，用與非門(mén)或者或非門(mén)來(lái)設(shè)計(jì)邏輯線路時(shí)，就需要結(jié)構(gòu)新聯(lián)結(jié)詞完備集。?/10/10命題邏輯等值演算第20頁(yè)§2.3聯(lián)結(jié)詞完備集例2：某電路中有一個(gè)燈泡和三個(gè)開(kāi)關(guān)A，B，C。已知在且僅在下述四種情況下燈亮：

(1)C扳鍵向上，A,B扳鍵向下

(2)A扳鍵向上，B,C扳鍵向下

(3)B,C扳鍵向上，A扳鍵向下

(4)A,B扳鍵向上，C扳鍵向設(shè)F為1表示燈亮，p,q,r分別表示A,B,C扳鍵向上

(a)用命題公式結(jié)構(gòu)F(b)在聯(lián)結(jié)詞完備集{┐,∧}上結(jié)構(gòu)F(c)在聯(lián)結(jié)詞完備集{┐,→,?}上結(jié)構(gòu)F?/10/10命題邏輯等值演算第21頁(yè)§2.3聯(lián)結(jié)詞完備集解：F=(┐p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(p∧q∧┐r)(b)(c)留作課后練習(xí)?/10/10命題邏輯等值演算第22頁(yè)§2.3聯(lián)結(jié)詞完備集F=(┐p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(p∧q∧┐r)當(dāng)且僅當(dāng)p,q,r輸入為0,0,1或1,0,0或0,1,1或1,1,0時(shí)輸出F為1pqrF?/10/10命題邏輯等值演算第23頁(yè)§2.4可滿足性問(wèn)題與消解法命題公式可滿足性問(wèn)題是算法理論關(guān)鍵問(wèn)題之一處理方法:真值表法、主析取范式或主合取范式缺點(diǎn):計(jì)算量大新方法:消解法命題公式可滿足性問(wèn)題能夠歸結(jié)為合取范式可滿足性問(wèn)題例1判斷以下公式是否是可滿足式p∧(p∨q)∧(p∨┐q)∧(q∨┐r)∧(q∨r)?/10/10命題邏輯等值演算第24頁(yè)§2.4可滿足性問(wèn)題與消解法消解法永真式能夠從合取范式中消去不含任何文字簡(jiǎn)單析取式為空簡(jiǎn)單析取式,要求它是不可滿足含有空簡(jiǎn)單析取式合取范式是不可滿足設(shè)l是一個(gè)文字,

稱作文字l補(bǔ)?/10/10命題邏輯等值演算第25頁(yè)§2.4可滿足性問(wèn)題與消解法定義2.9設(shè)C1,C2是兩個(gè)簡(jiǎn)單析取式,C1含文字l,C2含文字lc.從C1中刪去l,從C2中刪去lc,然后再將所得到結(jié)果析取成一個(gè)簡(jiǎn)單析取式,稱這么得到簡(jiǎn)單析取式為C1,C2消解式或消解結(jié)果,記為Res(