命題邏輯等值演算市公開課一等獎省賽課獲獎課件

漳州師范學院計算機科學與工程系第二章命題邏輯等值演算/10/10命題邏輯等值演算第1頁第二章命題邏輯等值演算

等值式

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

A?A∨A,A?A∧A交換律

A∨B?B∨A，A∧B?B∧A結合律

(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頁§2.1等值式同一律

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

A∨┐A?1矛盾律

A∧┐A?0蘊涵等值式

A→B?┐A∨B等價等值式

(A?B)?(A→B)∧(B→A)假言易位

A→B?┐B→┐A等價否定等值式

A?B?┐A?┐B歸謬論

(A→B)∧(A→┐B)?┐A?/10/10命題邏輯等值演算第5頁§2.1等值式代入實例：比如在蘊涵等值式中

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

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

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

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

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

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

?(p∨q)→r(蘊涵等值式)用等值演算法判斷公式類型

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

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

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

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

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

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

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

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

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

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

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

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

(3)S3={┐,∧}

(4)S4={┐,∨}

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

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

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

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

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

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

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