《3-第一章命題邏輯》由會(huì)員分享，可在線閱讀，更多相關(guān)《3-第一章命題邏輯（19頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,信息工程學(xué)院,大連大學(xué),第一章 命題邏輯,1.1,命題及其表示法,1.2,聯(lián)結(jié)詞,1.3,命題公式與翻譯,1.4,真值表與等價(jià)公式,1.5,重言式與蘊(yùn)含式,1.7,對(duì)偶與范式,1.8,推理理論,Propositional Logic,第一章 命題邏輯,1.1,命題及其表示法,1.2,聯(lián)結(jié)詞,1.3,命題公式與翻譯,1.4,真值表與等價(jià)公式,1.5,重言式與蘊(yùn)含式,1.7,對(duì)偶與范式,1.8,推理理論,Propositional Logic,第,10,頁,定義,1-3.1,命題合式公式,(Well-formed formula,wff

2、,),（,1,）單個(gè)命題變?cè)旧硎呛鲜焦健?（,2,）若,A,是合式公式，則,(,A),也是合式公式。,（,3,）若,A,，,B,是合式公式，則,(AB),，,(AB),，,(A,B),，,(A,B),也是合式公式。,（,4,）當(dāng)且僅當(dāng)有限次地應(yīng)用,(1)(3),所得到的包含命題變?cè)?、?lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。,1.3,命題公式與翻譯,第,10,頁,1.3,命題公式與翻譯,例：判斷下列式子是否是合適公式,第,12,頁,例,1,給出 的真值表。,練習(xí)：給出下列命題公式的真值表。,（,1,）,（,2,）,1.4,真值表與等價(jià)公式,n,個(gè)命題變?cè)M成的命題公式共有,2,n,種賦值（指派）。,

3、定義,1-4.2,設(shè),A,B,為兩個(gè)命題公式，若,A,B,構(gòu)成的,雙條件,A,B,為重言式，則稱,A,與,B,是,等價(jià)的（等值的）記作,A B,。,第,12,頁,1.4,真值表與等價(jià)公式,第,13,頁,1.4,真值表與等價(jià)公式,定義,1-4.3,如果,X,是合式公式,A,的一部分，且,X,本身,也是一個(gè)合式公式，則稱,X,為公式,A,的,子公式,。,定理,1-4.1,設(shè),X,是合式公式,A,的子公式，若,X Y,，,如果將,A,中的,X,用,Y,來置換，所得到公式,B,與公式,A,等價(jià)，即,A B,。,第,16,頁,復(fù)習(xí),練習(xí),1,：化簡(jiǎn)下面的式子。,（,1,）,（,2,）,第一章 命題邏輯,

4、1.1,命題及其表示法,1.2,聯(lián)結(jié)詞,1.3,命題公式與翻譯,1.4,真值表與等價(jià)公式,1.5,重言式與蘊(yùn)含式,1.7,對(duì)偶與范式,1.8,推理理論,Propositional Logic,第,16,頁,1.7,對(duì)偶與范式,定義,1-7.1,在給定的命題公式中，如果它僅用聯(lián)結(jié)詞 ，則將聯(lián)結(jié)詞 換成 ，將 換成 ，若有特殊變?cè)?F,和,T,亦相互取代，所得公式稱為原,公式的對(duì)偶式。,例,1,：寫出下列表達(dá)式的對(duì)偶式,一、對(duì)偶式,對(duì)偶式的作用,見書上,30,頁,定理,7.1-7.2,第,17,頁,1.7,對(duì)偶與范式,二、范式,定義,1-7.2,一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng),它具有型式：,其

5、中 都是由命題變?cè)蚱浞穸ㄋM成,的析取式。,合取范式的特點(diǎn)：,（,1,）不出現(xiàn) 和 （,2,）否定符號(hào)出現(xiàn)在變?cè)?（,3,）總體看是合取式（,4,）每個(gè)合取項(xiàng)是析取式,（,5,）每個(gè)合取項(xiàng)中只包含命題變?cè)蚱浞穸ā?第,18,頁,1.7,對(duì)偶與范式,二、范式,定義,1-7.3,一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng),它具有型式：,其中 都是由命題變?cè)蚱浞穸ㄋM成,的合取式。,析取范式的特點(diǎn)：,（,1,）不出現(xiàn) 和 （,2,）否定符號(hào)出現(xiàn)在變?cè)?（,3,）總體看是析取式（,4,）每個(gè)析取項(xiàng)是合取式,（,5,）每個(gè)析取項(xiàng)中只包含命題變?cè)蚱浞穸ā?第,19,頁,1.7,對(duì)偶與范式,二、范式,例

6、,2:,判斷下列各式是否為析取范式或合取范式。,第,20,頁,1.7,對(duì)偶與范式,二、范式,例,3:,求 合取范式。,例,4:,求 析取范式。,合取范式和析取范式的化歸步驟：見書上,31,頁,第,20,頁,1.7,對(duì)偶與范式,三、主范式,例,5:,試求 和,的主析取范式。,例,6:,試求 主析取范式。,主析取范式的化歸步驟：見書上,36,頁,(1),主析取范式,每個(gè)析取項(xiàng)中所有變?cè)家霈F(xiàn),每個(gè)變?cè)怀霈F(xiàn)一次（命題變?cè)蚱浞穸ǎ?第,20,頁,1.7,對(duì)偶與范式,三、主范式,定義,1-7.4,n,個(gè)變?cè)暮先∈剑Q作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但,兩者必須出現(xiàn)且僅出現(xiàn)一

7、次。,定義,1-7.5,對(duì)于給定的命題公式，如果有一個(gè)等價(jià),公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱為原式的主析取范式。,定理,1-7.3,在真值表中，一個(gè)公式的真值為,T,的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式的主析取范式。,第,20,頁,1.7,對(duì)偶與范式,三、主范式,例,7:,試求 的主合取范式。,例,8:,試求 主合取范式。,主合取范式的化歸步驟：見書上,38,頁,(2),主合取范式,每個(gè)合取項(xiàng)中所有變?cè)家霈F(xiàn),每個(gè)變?cè)怀霈F(xiàn)一次（命題變?cè)蚱浞穸ǎ?第,20,頁,1.7,對(duì)偶與范式,三、主范式,定義,1-7.6,n,個(gè)變?cè)奈鋈∈?，稱作布爾析取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)

8、存在，但,兩者必須出現(xiàn)且僅出現(xiàn)一次。,定義,1-7.7,對(duì)于給定的命題公式，如果有一個(gè)等價(jià),公式，它僅由大項(xiàng)的合取所組成，則該等價(jià)式稱為原式的主合取范式。,定理,1-7.3,在真值表中，一個(gè)公式的真值為,T,的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。,第,21,頁,1.7,對(duì)偶與范式,例,9:,用真值表求 的主合取范式。,例,10:,求 的成真指派。,例,11:,某科研所要從,3,名科研骨干,A,B,C,中挑選,12,名出國(guó)進(jìn)修，由于工作需要，選派需滿足如,下條件：,（,1,）若,A,去，則,C,同去；,（,2,）若,B,去，則,C,不能去；,（,3,）若,C,不去，則,A,或,B,可以去。,問：有幾種選派方案,分別都是什么？,