命題邏輯等值演算

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

等值式

析取范式與合取范式聯(lián)結(jié)詞完備集可滿足性問題與消解法知識點：等值式、置換規(guī)則、等值演算、(主)析取范式、(主)合取范式、聯(lián)結(jié)詞完備集、其它聯(lián)結(jié)詞、可滿足性問題、消解法教學(xué)要求：深刻理解和掌握命題邏輯中的基本概念教學(xué)重點：等值演算、(主)析取范式、(主)合取范式學(xué)時:42022/10/19§2.1等值式定義2.1設(shè)A,B是兩個命題公式,若A,B構(gòu)成的等價式AB為重言式,則稱A與B是等值的,記為AB注意:是元語言符號，不是聯(lián)結(jié)詞?2022/10/19§2.1等值式16組(24個)重要的等值式雙重否定律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?2022/10/19§2.1等值式同一律

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

A∨┐A?1矛盾律

A∧┐A?0蘊(yùn)涵等值式

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

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

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

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

(A→B)∧(A→┐B)?┐A?2022/10/19§2.1等值式代入實例：例如在蘊(yùn)涵等值式中

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

(p→q)→┐p?┐(p→q)∨┐p?2022/10/19§2.1等值式判別兩個公式是否等值的方法真值表法等值演算:

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

(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)涵等值式)用等值演算法判斷公式的類型

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

?2022/10/19§2.2析取范式與合取范式文字:

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

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

┐q)∧(p∨r)?2022/10/19§2.2析取范式與合取范式一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式范式存在定理:

任一命題公式都存在著與之等值的析取范式與合取范式?2022/10/19§2.2析取范式與合取范式求范式可使用如下步驟:1.消去聯(lián)結(jié)詞→,?

2.否定號的消去（利用雙重否定律）或內(nèi)移（利用德摩根）3.利用分配律：利用∧對∨的分配律求析取范式利用∨對∧的分配律求合取范式?2022/10/19§2.2析取范式與合取范式極小項:在含有n個命題變項的簡單合取式中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上,稱這樣的簡單合取式為極小項。極大項:在含有n個命題變項的簡單析取式中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上,稱這樣的簡單析取式為極大項。?2022/10/19§2.2析取范式與合取范式主析取范式:設(shè)由n個命題變項構(gòu)成的析取范式中所有的簡單合取式都是極小項，則稱該析取范式為主析取范式。主合取范式:設(shè)由n個命題變項構(gòu)成的合取范式中所有的簡單析取式都是極大項，則稱該合取范式為主合取范式。任何命題公式都存在與之等值的主析取范式和主合取范式,并且是唯一的。?2022/10/19§2.2析取范式與合取范式p,q,r形成的極小項與極大項設(shè)mi與Mi是命題變項p1,p2,…,pn形成的極小項和大項，則┐mi?Mi，┐Mi?mi?2022/10/19§2.2析取范式與合取范式注意：可以由公式的主析取范式求主合取范式。反之，也可以由公式的主合取范式確定主析取范式矛盾式無成真賦值，因而矛盾式的主合取范式含2n（n為公式中命題變項個數(shù)）個極大項而重言式無成假賦值，因而主合取范式不含任何極大項重言式的主合取范式記為1。矛盾式的主析取范式為0可滿足式的主析取范式中至少含有一個極小項,主合取范式中極大項的個數(shù)一定小于2n?2022/10/19§2.2析取范式與合取范式含n個命題變項的所有無窮多合式公式中，和它們等值的主析取范式（主合取范式）共有多少種不同的情況。n個命題變項可產(chǎn)生2n個極小項（極大項），因而共可產(chǎn)生種不同的主析取范式（主合取范式）?2022/10/19§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?2022/10/19§2.3聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集:

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

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

?2022/10/19§2.3聯(lián)結(jié)詞完備集以下聯(lián)結(jié)詞集都是完備集：

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

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

(3)S3={┐,∧}

(4)S4={┐,∨}

(5)S5={┐,→}根據(jù)需要，人們還可構(gòu)造形式上更為簡單的聯(lián)結(jié)詞完備集。例如，在計算機(jī)硬件設(shè)計中，用與非門或者或非門來設(shè)計邏輯線路時，就需要構(gòu)造新聯(lián)結(jié)詞完備集。?2022/10/19§2.3聯(lián)結(jié)詞完備集例2：某電路中有一個燈泡和三個開關(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)用命題公式構(gòu)造F(b)在聯(lián)結(jié)詞完備集{┐,∧}上構(gòu)造F(c)在聯(lián)結(jié)詞完備集{┐,→,?}上構(gòu)造F?2022/10/19§2.3聯(lián)結(jié)詞完備集解：F=(┐p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(p∧q∧┐r)(b)(c)留作課后練習(xí)?2022/10/19§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時輸出F為1pqrF?2022/10/19§2.4可滿足性問題與消解法命題公式的可滿足性問題是算法理論的核心問題之一解決方法:真值表法、主析取范式或主合取范式缺點:計算量大新方法:消解法命題公式的可滿足性問題可以歸結(jié)為合取范式的可滿足性問題例1判斷下列公式是否是可滿足式p∧(p∨q)∧(p∨┐q)∧(q∨┐r)∧(q∨r)?2022/10/19§2.4可滿足性問題與消解法消解法永真式可以從合取范式中消去不含任何文字的簡單析取式為空簡單析取式,規(guī)定它是不可滿足的含有空簡單析取式的合取范式是不可滿足的設(shè)l是一個文字,

稱作文字l的補(bǔ)?2022/10/19§2.4可滿足性問題與消解法定義2.9設(shè)C1,C2是兩個簡單析取式,C1含文字l,C2含文字lc.從C1中刪去l,從C2中刪去lc,然后再將所得到的結(jié)果析取成一個簡單析取式,稱這樣得到的簡單析取式為C1,C2的消解式或消解結(jié)果