2-2 命題邏輯的等值和推理演算

《2-2 命題邏輯的等值和推理演算》由會員分享，可在線閱讀，更多相關《2-2 命題邏輯的等值和推理演算（34頁珍藏版）》請在裝配圖網上搜索。

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

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

3、R,是對偶式,推廣,在僅含有聯結詞,，的命題公式中，將聯結詞,，,F,，,T,分別換成,，,T,，,F,，就得到了它的對偶式。,與對偶式有關的定理,設,A,和,A,*,互為對偶式，,P,1,P,2,P,n,是出現在,A,和,A,*,中的全部命題變項，,令,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),與對偶式有關的定理,定理,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,的另一種形式,，,與對偶式有關的定理,定理,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,*,永真,（作業）,定理,2.5.6,A,與,A,同永真，同可滿足,A,與,A,*,同,永真，同可滿足,對偶性是邏輯規律，給證明公式的等值和求否定帶來方便,依定理,2.5.3,有，,A=A*,，,B,=B*,2.6,范 式,簡單析取式,它是僅由有限個命題變項或其否定構成的析取式。,如,:,P,，,Q,，,P,，,Q,，,P,Q,，,P,Q,，,P,Q,它是,重言式,當且僅當它同時含一個命題變項及其否定；,如：,P,Q,P,是重言式,簡單合取式,它是僅由

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

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

8、(,P,Q,),R,=,(,P,Q,),R,（消去,）,=,P,Q,R,（結合律）,這既是,A,的,析取范式,（由,3,個簡單合取式組成的析取式）,又是,A,的,合取范式,（由一個簡單析取式組成的合取式）,求公式的范式舉例,(,2),B,=(,P,Q,),R,解,(,P,Q,),R,=,(,P,Q,),R,（消去第一個,）,=,(,P,Q,),R,（消去第二個,）,=,(,P,Q,),R,（否定號內移,摩根律）,這已為,析取范式,（兩個簡單合取式構成）,繼續：,(,P,Q,),R,=,(,P,R,),(,Q,R,),（,對,分配律）,這一步得到,合取范式,（由兩個簡單析取式構成,）,極小項,定

9、義,n,個命題變項的,簡單合取式,，其中每個命題變項與其否定不同時出現，,而二者之一必出現且僅出現一次,，這樣的簡單合取式稱為,極小項,。,如：兩個命題變元,P,和,Q,，其極小項為：,P,Q,，,P,Q,，,P,Q,，,P,Q,說明,n,個命題變項產生,2,n,個極小項，它們互不等值,用,m,i,表示第,i,個極小項，,每個小項的,n,個變元排序相同。（按下標或字典順序），分別記為,其中,i,是該極小項,成真賦值,的十進制表示,.,m,11,m,10,m,01,m,00,極小項,由,P,Q,R,三個命題變項形成的極小項,極小項,成真賦值,名稱,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,主析取范式,主析取范式,設命題公式,A,中含,n,個命題變項，如果,A,的析取范式中的簡單合取式全是,極小項,，則稱該析取范式為,A,的,主析取范式,如：,n,=3,命題變項為,P,Q,R,時，主析取范式,：,(,P,Q,R,),(,P,Q,R,)=,m,1,m,3,定理,任何命題公式都存在與之等值的主析取范式,并且是惟一的,.,求主析取范式的方法,等值演算法和真值表法,用等價演算法求主析取范式的步驟,1.,求,A,的析

11、取范式,A,；,2.,若,A,的某簡單合取式,B,中不含某命題變項或其否 定，則將,B,展成如下形式：,B,=,B,1,=,B,(,P,i,P,i,),=,(,B,P,i,),(,B,B,i,),3.,將重復出現的命題變項、矛盾式及重復出現的極小項都“消去”。,4.,將極小項按由小到大的順序排列，并用,表示之，如,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),判斷公式的類型,設,A,含,n,個命題變項，則,A,為重言式,A,的主析取范式含,2,n,個極小項,如命題變項為,P,Q,時，,A=,(0,1,2,3),A,為矛盾式,A,的主析取范式為,0,如,A=,0,A,為可滿足式,A,的主析取范式中至少含一個極小項,如,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),判斷兩個公式是否等值,如,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,),定理,任何命題公式都存在與之等值的主析取范式,并且是惟一的,.,主析取范式的應用,(4),舉例,例：甲、乙、丙、丁四人參加考試，有人問他們，誰的成績最好，,甲說：,“,不是我,”,乙說：,“,是丁,”,丙說：,“,是乙,”,丁說：,“,不是我,”,四人的回答只有一人符合實際，,問是誰的成績最好，若只有一人成績最好，他是誰？,解此類問題的步驟為：,將簡

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