《2-2 命題邏輯的等值和推理演算》由會(huì)員分享，可在線閱讀，更多相關(guān)《2-2 命題邏輯的等值和推理演算（34頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),第,2,章 命題邏輯的等值和推理演算,2.1,等值定理,2.2,等值公式,2.3,命題公式與真值表的關(guān)系,2.4,聯(lián)結(jié)詞的完備集,2.5,對(duì)偶式,2.6,范式,2.7,推理形式,2.8,基本的推理公式,2.9,推理演算,2.10,歸結(jié)推理法,討論,等值演算,討論,推理演算,2.4,聯(lián)結(jié)詞的完備集,定義,在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為,冗余的聯(lián)結(jié)詞,，否則稱為,獨(dú)立的聯(lián)結(jié)詞,。,如：,P,Q,=,P,Q,P,Q,=(,P,Q,)(,P,Q,),在,，,中、是冗余的。

2、,在,，,中，,P,Q,=,（,P,Q,）,所以是冗余的。,在,，,中無冗余的聯(lián)結(jié)詞。,同理，,在,，,中無冗余的聯(lián)結(jié)詞。,聯(lián)結(jié)詞的完備集,定義,設(shè),C,是聯(lián)結(jié)詞的集合，若對(duì)任一命題公式都由,C,中的聯(lián)結(jié)詞表示出來的公式與之等值，就說,C,是,完備的聯(lián)結(jié)詞集合。,顯然，全體聯(lián)結(jié)詞的無限集合是完備的。,，,，,，,，,，,，,，,，,等也是完備的,。,是完備的,2.5,對(duì)偶式,定義,在僅含聯(lián)結(jié)詞,，的命題公式,A,中，將聯(lián)結(jié)詞,，,F,，,T,分別換成,，,T,，,F,所得的公式稱為公式,A,的,對(duì)偶式,，記為,A,*,如：,P,Q,與,P,Q,是對(duì)偶式,(,P,Q,),R,與,(,P,Q,),

3、R,是對(duì)偶式,推廣,在僅含有聯(lián)結(jié)詞,，的命題公式中，將聯(lián)結(jié)詞,，,F,，,T,分別換成,，,T,，,F,，就得到了它的對(duì)偶式。,與對(duì)偶式有關(guān)的定理,設(shè),A,和,A,*,互為對(duì)偶式，,P,1,P,2,P,n,是出現(xiàn)在,A,和,A,*,中的全部命題變項(xiàng)，,令,A,=,A,(,P,1,P,2,P,n,),A,=A,(,P,1,P,2,P,n,),定理,2.5.1,：,(,A,*)=(,A,)*,(,A,)=(,A,),如：,A,=,P,(,Q,R,),則：,A*=,P,(,Q,R,),，,A,=,P,(,Q,R,),A=,P,(,Q,R,),所以：,(,A,)*=,P,(,Q,R,),(,A,*)=

4、,P,(,Q,R,),所以：,(,A,),=,P,(,Q,R,),(,A,)=,P,(,Q,R,),(A*)=(,A)*,(,A,)=(,A),與對(duì)偶式有關(guān)的定理,定理,2.5.2,：,(,A,*)*=,A,(,A,),=,A,定理,2.5.3,：,A,=,A,*,如：,A,=,P,(,Q,R,),則,：,A,=,P,(,Q,R,),A,*=,P,(,Q,R,),所以：,A,*,=,P,(,Q,R,),=,A,此定理為摩根律：,(,A,B,)=,A,B,(,A,B,)=,A,B,的另一種形式,，,與對(duì)偶式有關(guān)的定理,定理,2.5.4,若,A,=,B,，必有,A,*=,B,*,證：,A,=,B,

5、A,B,永真,A,B,永真,A,*,B,*,永真,A,*,B,*,永真,A,*=,B,*,定理,2.5.5,若,A,B,永真，必有,B,*,A,*,永真,（作業(yè)）,定理,2.5.6,A,與,A,同永真，同可滿足,A,與,A,*,同,永真，同可滿足,對(duì)偶性是邏輯規(guī)律，給證明公式的等值和求否定帶來方便,依定理,2.5.3,有，,A=A*,，,B,=B*,2.6,范 式,簡單析取式,它是僅由有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式。,如,:,P,，,Q,，,P,，,Q,，,P,Q,，,P,Q,，,P,Q,它是,重言式,當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題變項(xiàng)及其否定；,如：,P,Q,P,是重言式,簡單合取式,它是僅由

6、有限個(gè)命題變項(xiàng)或其否定構(gòu)成的合取式。,如,:,P,，,Q,，,P,，,Q,，,P,Q,，,P,Q,它是,矛盾式,當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題變項(xiàng)及其否定。,如：,P,P,Q,是矛盾式,析取范式,析取范式,由有限個(gè)簡單合取式組成的析取式,A,1,A,2,.,A,n,（,n,1,，,A,i,都是,簡單合取式,）,如：,(P,Q R),(P Q)Q,一個(gè)析取范式是,矛盾式,，當(dāng)且僅當(dāng)其每個(gè)簡單合取式都是,矛盾式,合取范式,由有限個(gè)簡單析取式組成的合取式,A,1,A,2,.,A,n,（,n,1,A,i,都,是,簡單析取式,）,如：,(P,Q R),(P Q)Q,一個(gè)合取范式是,重言式,，當(dāng)且僅當(dāng)其每個(gè)簡單

7、析取式都是,重言式,范式,析取范式與合取范式的總稱,命題公式的范式,范式存在定理,任何命題公式都存在著與之等值的析取范式與合取范式,求公式,A,的范式的步驟,：,(1),消去,A,中的,（若存在）,A,B,=,A,B,A,B=,(,A,B,),(,A,B,)(,求析取范式時(shí),),=,(,A,B,),(,A,B,),(,求合取范式時(shí),),(2),否定聯(lián)結(jié)詞,的內(nèi)移或消去（摩根定律）,(3),使用分配律,對(duì),分配（析取范式）,對(duì),分配（合取范式）,注意：,公式的范式存在，但,不惟一,，這是它的局限性,求公式的范式舉例,例,:,求下列公式的析取范式與合取范式,(,1),A,=(,P,Q,),R,解,

8、(,P,Q,),R,=,(,P,Q,),R,（消去,）,=,P,Q,R,（結(jié)合律）,這既是,A,的,析取范式,（由,3,個(gè)簡單合取式組成的析取式）,又是,A,的,合取范式,（由一個(gè)簡單析取式組成的合取式）,求公式的范式舉例,(,2),B,=(,P,Q,),R,解,(,P,Q,),R,=,(,P,Q,),R,（消去第一個(gè),）,=,(,P,Q,),R,（消去第二個(gè),）,=,(,P,Q,),R,（否定號(hào)內(nèi)移,摩根律）,這已為,析取范式,（兩個(gè)簡單合取式構(gòu)成）,繼續(xù)：,(,P,Q,),R,=,(,P,R,),(,Q,R,),（,對(duì),分配律）,這一步得到,合取范式,（由兩個(gè)簡單析取式構(gòu)成,）,極小項(xiàng),定

9、義,n,個(gè)命題變項(xiàng)的,簡單合取式,，其中每個(gè)命題變項(xiàng)與其否定不同時(shí)出現(xiàn)，,而二者之一必出現(xiàn)且僅出現(xiàn)一次,，這樣的簡單合取式稱為,極小項(xiàng),。,如：兩個(gè)命題變?cè)?P,和,Q,，其極小項(xiàng)為：,P,Q,，,P,Q,，,P,Q,，,P,Q,說明,n,個(gè)命題變項(xiàng)產(chǎn)生,2,n,個(gè)極小項(xiàng)，它們互不等值,用,m,i,表示第,i,個(gè)極小項(xiàng)，,每個(gè)小項(xiàng)的,n,個(gè)變?cè)判蛳嗤＃ò聪聵?biāo)或字典順序），分別記為,其中,i,是該極小項(xiàng),成真賦值,的十進(jìn)制表示,.,m,11,m,10,m,01,m,00,極小項(xiàng),由,P,Q,R,三個(gè)命題變項(xiàng)形成的極小項(xiàng),極小項(xiàng),成真賦值,名稱,P,Q,R,000,m,0,P,Q,R,001,

10、m,1,P,Q,R,010,m,2,P,Q,R,011,m,3,P,Q,R,100,m,4,P,Q,R,101,m,5,P,Q,R,110,m,6,P,Q,R,111,m,7,主析取范式,主析取范式,設(shè)命題公式,A,中含,n,個(gè)命題變項(xiàng)，如果,A,的析取范式中的簡單合取式全是,極小項(xiàng),，則稱該析取范式為,A,的,主析取范式,如：,n,=3,命題變項(xiàng)為,P,Q,R,時(shí)，主析取范式,：,(,P,Q,R,),(,P,Q,R,)=,m,1,m,3,定理,任何命題公式都存在與之等值的主析取范式,并且是惟一的,.,求主析取范式的方法,等值演算法和真值表法,用等價(jià)演算法求主析取范式的步驟,1.,求,A,的析

11、取范式,A,；,2.,若,A,的某簡單合取式,B,中不含某命題變項(xiàng)或其否 定，則將,B,展成如下形式：,B,=,B,1,=,B,(,P,i,P,i,),=,(,B,P,i,),(,B,B,i,),3.,將重復(fù)出現(xiàn)的命題變項(xiàng)、矛盾式及重復(fù)出現(xiàn)的極小項(xiàng)都“消去”。,4.,將極小項(xiàng)按由小到大的順序排列，并用,表示之，如,m,1,m,2,m,6,用,(1,2,6),表示,。,求公式,A,=(,P,Q,),R,的主析取范式,解法,1,：,(,P,Q,),R,=,(,P,Q,),R,=,(,P,Q,),R,（析取范式）,(,P,Q,),=(,P,Q,),(,R,R,),=,(,P,Q,R,),(,P,Q,

12、R,),=,m,6,m,7,R,=,(,P,P,),(,Q,Q,),R,=,(,P,Q,R,),(,P,Q,R,),(,P,Q,R,),(,P,Q,R,),=,m,1,m,3,m,5,m,7,代入并合并相同式，得主析取范式：,(,P,Q,),R,=,m,1,m,3,m,5,m,6,m,7,=,(1,3,5,6,7),解法,2,：,(,P,Q,),R,=,(,P,Q,),R,=,(,P,Q,),R,（析取范式）,=,m,11x,m,xx1,=,(,m,11,0,m,11,1,),(,m,00,1,m,01,1,m,10,1,m,11,1,),=,(1,3,5,6,7),求公式,A,=(,P,Q,

13、),R,的主析取范式,主析取范式的用途,(,1),求公式的成真賦值和成假賦值,如前面例子中得到,(,P,Q,),R,=,m,1,m,3,m,5,m,6,m,7,其成真賦值為：,001,011,101,110,111,則其余的賦值為成假賦值,000,010,100,主析取范式的用途,(,2),判斷公式的類型,設(shè),A,含,n,個(gè)命題變項(xiàng)，則,A,為重言式,A,的主析取范式含,2,n,個(gè)極小項(xiàng),如命題變項(xiàng)為,P,Q,時(shí)，,A=,(0,1,2,3),A,為矛盾式,A,的主析取范式為,0,如,A=,0,A,為可滿足式,A,的主析取范式中至少含一個(gè)極小項(xiàng),如,A=,(2,3),(,P,Q,),Q,=(,P

14、,Q,),Q,=,P,Q,Q,=,F,（,矛盾式,）,用主析取范式判斷公式的類型,如前面例子中得到,(,P,Q,),R,=,m,1,m,3,m,5,m,6,m,7,=,(1,3,5,6,7),(,可滿足式）,(,P,Q,),P,),Q,=(,P,Q,),P,),Q,=(,P,Q,),P,Q,=,m,10,m,0 x,m,x1,=,m,10,m,00,m,01,m,01,m,11,=,m,0,m,1,m,2,m,3,=(0,1,2,3)=,T,（,重言式,）,用主析取范式判斷公式的類型,主析取范式的用途,(,3),判斷兩個(gè)公式是否等值,如,P,Q,=,P,Q,=,m,0 x,m,x1,=,m,0

15、0,m,01,m,01,m,11,=,m,0,m,1,m,3,=,(0,1,3),P,(,P,Q,),=,m,0 x,m,11,=,m,00,m,01,m,11,=,m,0,m,1,m,3,=,(0,1,3),所以,P,Q =,P,(,P,Q,),定理,任何命題公式都存在與之等值的主析取范式,并且是惟一的,.,主析取范式的應(yīng)用,(4),舉例,例：甲、乙、丙、丁四人參加考試，有人問他們，誰的成績最好，,甲說：,“,不是我,”,乙說：,“,是丁,”,丙說：,“,是乙,”,丁說：,“,不是我,”,四人的回答只有一人符合實(shí)際，,問是誰的成績最好，若只有一人成績最好，他是誰？,解此類問題的步驟為：,將簡

16、單命題符號(hào)化,寫出各復(fù)合命題,寫出由中復(fù)合命題組成的合取式,求,中所得公式的主析取范式,主析取范式的應(yīng)用舉例,解,設(shè),A,：甲的成績最好,B,：乙的成績最好，,C,：丙的成績最好,D,：丁的成績最好，,(1)(,A,D,B,D,),(2)(,A,D,B,D,),(3)(,A,D,B,D,),(4)(,A,D,B,D,),例：甲、乙、丙、丁四人參加考試，有人問他們，誰的成績最好，,甲說：,“,不是我,”,乙說：,“,是丁,”,丙說：,“,是乙,”,丁說：,“,不是我,”,四人的回答只有一人符合實(shí)際,，問是誰的成績最好，若只有一人成績最好，他是誰？,主析取范式的應(yīng)用舉例,(1)(,A,D,B,D,),(2)(,A,D,B,D,),(3)(,A,D,B,D,),(4)(,A,D,B,D,),(1)(4),構(gòu)成的析取式為,(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),主析取范式的應(yīng)用舉例,求,中所得公式的主析取范式,(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),=(,A,D,B,D,),(,A,