《邏輯學(xué)真值表及命題演算.ppt》由會員分享，可在線閱讀，更多相關(guān)《邏輯學(xué)真值表及命題演算.ppt（56頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第五章 真值表方法與命題演算,教學(xué)重點(diǎn)與要點(diǎn) 完全真值表法的判定功用 歸謬賦值法的操作與判定 命題演算證明方法的應(yīng)用與構(gòu)造,一、真值聯(lián)結(jié)詞,定義：真值聯(lián)結(jié)詞是指僅僅表示復(fù)合命題與肢命題之間真假關(guān)系的聯(lián)結(jié)詞。 真值聯(lián)結(jié)詞主要有五個： （否定）、（合取）、 （析?。?、（蘊(yùn)涵）、 （等值）,二、真值形式,定義：真值形式是指由真值聯(lián)結(jié)詞和命題變項所構(gòu)成的形式結(jié)構(gòu)。 五種基本的真值形式 否定式： p 合取式：pq 析取式：pq 蘊(yùn)涵式：pq 等值式：pq,三、五種基本真值形式的真值表,定義，真值表是數(shù)理邏輯中用以定義命題聯(lián)結(jié)詞并確定復(fù)合命題真或假的一種圖表。 T 表示“真”、F 表示“假” 1、p,2、

2、 pq,3、pq,4、pq,5、pq,真值表判定程序的三個要求,（1）程序的每一步都是由事先給定的規(guī)則明 確規(guī)定好的； （2）對于所判定的對象是否具有某種性質(zhì)， 該程序能夠給出唯一確定的結(jié)果； （3）該程序能夠在有窮步驟結(jié)束。 判定程序的特點(diǎn)： 機(jī)械的、能行的、可判定的。,完全真值表法,完全真值表的作法 三個步驟： 1、找出已給命題公式的所有變項，并豎行列出這些變項的所有真值組合； 2、根據(jù)命題公式的結(jié)構(gòu)，由繁到簡的依次橫行列出，一次只引進(jìn)一個連接詞，直至列出該公式本身； 3、依據(jù)基本真值表，有變項的真值逐步計算出每個部分的真值，最后列出整個公式得真值。,,,完全真

3、值表法的判定功能,（1）命題公式的性質(zhì)判定 （2）推理形式有效性的判定 （3）命題公式之間關(guān)系的判定,重言式、矛盾式、可滿足式的判定,1、重言式（又叫永真式）是指在一個命題形式中不論其中的變項取什么值，該命題形式的值總是真的。 如： p p,2、矛盾式（又叫永假式）是指在一個命題形式中不論其中的變項取什么值，該命題形式的值總是假的。 如： p p,3、可滿足式（協(xié)調(diào)式）是指在一個命題形式中不論其中的變項取什么值，該命題形式的值至少在一種情況下是真的。 如：p q,真值表判定任一命題形式是否是重言式。 例1、（（pq）p）q,例2、（（pq）p） q,真值表判定任意兩個復(fù)合命題之間是否具有等值關(guān)

4、系,例1、（p q） p q,由真值表可知這兩個命題之間具有等值關(guān)系。,例2、 （p q）； p q,三、真值表幫助解決一些推理問題,例：列出A、B、C三命題的真值表，并回答當(dāng)A、B、C三命題恰有一個為真時，甲是否是木工？ A、如果甲不是木工，則乙是泥工。 B、如果乙不是泥工，則甲不是木工。 C、甲不是木工，且乙不是泥工 。,解 設(shè)p表示“甲是木工”；q表示“乙是泥 工”。 A：pq B：qp C：pq,練習(xí)題,一、用真值表判定下列真值形式是否是重言式 1、（（Pq） p）q 2、（（Pq） q）P,二、請用真值表判定下列各組命題形式之間是否具有等值關(guān)系。 1、 （Pq） Pq

5、2、 （Pq） Pq,三、列出A、B兩命題的真值表，并回答A、B恰有一個為假時，王軍是否考上了大學(xué)？ A：如果王軍考上了大學(xué)，那么李偉就沒有考上大學(xué)。 B：王軍沒有考上大學(xué)。,四、列出A、B、C三命題的真值表，并回答當(dāng)A、B、C三命題恰有一真時，是否甲村所有人家都有彩電？ A、甲村所有人家都有彩電，并且乙村所有人家都有彩電。 B、或者甲村所有人家都有彩電，或者乙村所有人家都有彩電。 C、如果乙村所有人家都有彩電，那么甲村有些人家沒有彩電。,真值表法的局限性,1、完全真值表法的局限性 判定多變項命題公式過于繁瑣。 2、歸謬賦值法的局限性 僅能判定蘊(yùn)涵式， 3、真值樹法的局限性 判定結(jié)構(gòu)復(fù)雜的

6、公式時，樹冠過大操作不便。 4、問題： 是否有一種方法既能解決命題邏輯有效性的判定問題又能解決有效性的推導(dǎo)問題？,命題演算的證明方法,一、命題演算方法概述 1、命題演算方法在問題求解上的必要性認(rèn)知 2、命題演算與形式系統(tǒng)構(gòu)造 3、公理系統(tǒng)與自然演繹系統(tǒng) 4、自然演繹法的基本思想 5、具體推證方法的認(rèn)知 直接證明法 間接證明法 反證法,一、直接證明法,1、直接證明法的特點(diǎn)認(rèn)知 勿需附加任何前提即可依規(guī)則從給定的前提推導(dǎo)出結(jié)論。 2、直接證明法的操作步驟 （1）依序編號排列前提，將結(jié)論寫在最后一個前提的右側(cè)并用“/”斷開。 （2）依據(jù)已知前提結(jié)合相關(guān)規(guī)則推出新

7、的命題，依次編號寫在下面。 （3）在推出的新命題右側(cè)括號內(nèi)注明前提依據(jù)和規(guī)則依據(jù)。 （4）證明結(jié)束寫上證畢字樣。,推證實例分析 1.AB 2.CD 3.AC BD,直接證明法,1.AB 2.CD 3.AC BD 4.AC (3.等值) 5.AD (4.2.連鎖) 6.BA (1.易位) 7.BD (6.4.連鎖) 8.BD (7.等值) 證畢。,二、假設(shè)證明法,1、間接推證法的特點(diǎn)認(rèn)知 給定前提不夠，需要附加。 2、假設(shè)證明法的基本思路 附加假設(shè)，依據(jù)蘊(yùn)涵引入的規(guī)則有條件 的推出相關(guān)結(jié)論。 3、假設(shè)證明法的模式構(gòu)造,,解法二：假設(shè)證法,1.AB 2.CD

8、 3.AC BD 4. B (假設(shè)) 4. D (假設(shè)) 5. A (1.4.銷去) 5. C (2.4.銷去) 6. C (3.5.銷去) 6. A (4.5.銷去) 7. D (2.6.銷去) 7. B (1.6.銷去) 8.BD (47.引入) 8.DB (47.引入) 9.BD (8.等值) 9.DB (8.等值) 證畢。 10.BD (9.交換) 證畢。,,,,,,,三、反證法,1、反證法的特點(diǎn)認(rèn)知 前提不夠，需要

9、附加。 附加與結(jié)論相矛盾的命題作為假設(shè)依據(jù)規(guī)則進(jìn)行推導(dǎo)尋求矛盾。找到矛盾后利用否定引入或銷去規(guī)則反證結(jié)論成立。 2、反證法的模式構(gòu)造,解法三：反證法,1.AB 2.CD 3.AC BD 4. (BD) (反設(shè)) 5. BD (4.等值) 6. B (5.銷去) 7. A (1.6.銷去) 8. C (3.7.銷去) 9. D (2.8.銷去) 10. D (5.銷去) 11. DD (9.10.引入) 12.BD (411.銷去) 證畢。,,,,假設(shè)證明法與反證法的區(qū)別與綜合應(yīng)用,一、假設(shè)證明法與反

10、證法的區(qū)別 二、假設(shè)證明法與反證法的綜合應(yīng)用 1、在證明中的綜合應(yīng)用 【例析4301】 2、在推理中的綜合應(yīng)用 【4302】 三、命題邏輯定理的證明,((pq) p) q p q pq (pq) p ((pq) p) q T T T T T T F F F T F T T F T F F T F T,,,,,畫一個完全真值表,實例分析2,p q pp q q pq T T T F T T F T

11、 F T F T T F T F F T F F 永真式 永假式 可真式,**,實例分析3：判斷3pq；pq； pq的真假關(guān)系,p q pq pq pq T T T T F T F F F T F T T T F F F T T F,,,,,,等值,矛盾,,,,實例分析4：用歸謬賦值法判定（（pq）q）P這個推理是否有效？,（（pq）q）P

12、 F T F T T T F T T,,,,,,,,,,,由上表可知： q 的賦值出現(xiàn)矛盾，此命題形式是重言式，與之相對應(yīng)的推理形式是有效式。,運(yùn)用歸謬賦值法要注意：, 由于給變項賦值過程中有先后的不同，因而具體矛盾的出現(xiàn)可能不同。 只有當(dāng)賦值過程中矛盾不可避免的出現(xiàn)時，才能表明原公式是重言式，相應(yīng)的推理有效。 賦值過程中，變項的值有時候不能惟一的確定，此時需要討論。,*返回*,1. AB 2. BC 3. CD 4. D /A 5. C （3，4，銷去）

13、 6. B （2，5，銷去） 7. A （1，6，銷去） 證畢。,直接證明法（實例分析一）,直接證法（實例分析二）,1. (AB)C 2. CD 3. BD /A 4. D （2，銷去） 5. C （2，銷去） 6. B （3，4，銷去） 7. (AB) （1，5，銷去） 8. AB （7，等值） 9. A （6，8，銷去） 證畢。,回溯思考方法 1. A(BC) 2. AD 3. C(EF) 4. DF /E (1)“回溯”思考，首先要考察待證結(jié)論與前提的關(guān)聯(lián)性，待證結(jié)論處在命題的后件，要獲證必須基于對前件C的肯定。 (2) C與前提1關(guān)聯(lián)，要獲

14、取必須基于主聯(lián)結(jié)關(guān)系的銷去。 (3) 前提1的銷去，取決于對前提2中條件A的否定。 (4) 要獲取對A的否定，必須基于對后件D的否定，而后件D的否定處在前提4之中，要獲取 D必先分解前提4。,,直接證明法：推導(dǎo)結(jié)論,1. (BD) 2. CD 3. AB 4. (EF)C 5. AF 6. A (5. 銷去) 7. B (3.6.銷去) 8. BD (1.7.等值) 9. D (7.8.銷去) 10. C (2.9.銷去) 11. (EF) (4.10.銷去) 12. EF (11.等值) 13. F (5.銷去) 14. E (12.13.銷去

15、),直接證明法前提一致性判定,1.AB 2.BC 3.DC 4.AD 5.D 6.C 7.B 8.A 9.A 10.AA,直接證明法前提一致性判定之02,1.AB 2.BC 3.DC 4.AD 5.A 6.B 7. C 8. D,假設(shè)證明法的模式構(gòu)造,1. 給定前提 2. 3. / pq 4. p (假設(shè)） : ： ： 10. q 11. pq (4---10 引入）,,,,1. BA 2.

16、 B(AC) AC 3. A (假設(shè)) 4. B (1.3,銷去) 5. AC (2.4.銷去) 6. C (5.銷去) AC (3.6.引入) 證畢。,,,,假設(shè)證明法（實例分析一）,1.AC 2.C(E(HI)) 3.FI A(FE) 4. A (假設(shè)) 5. C (1.4.銷去) 6. E(HI) (2.5.銷去) 7. F (假設(shè)) 8. I (3.7.銷去) 9. IH (8.引入) 10. HI (9.交換) 11. (HI)

17、 (10.等值) 12. E (6.11.銷去) 13. FE (712.引入) 14. A(FE) (413.引入) 證畢。,,,,,,,假設(shè)證明法（實例分析二）,反證法的模式構(gòu)造,1. 2. / p p (反設(shè)) : : : 9. q q 10. p (49. 銷去) 證畢。,,,,.,1. 2. 3. / p 4. P (反設(shè)) : : : 9. q q 10. p (49. 引入) 證畢。,,,,,1.A B 2.C B 3. (A C) / A 4. A C (

18、3.等值) 5. A (反設(shè)) 6. B (1.5.銷去) 7. C (2.6.銷去) 8. C (4.5.銷去) 9. C C (7.8.引入) 10. A (59. 引入) 證畢。,,,,反證法（實例分析一）,在證明中的綜合應(yīng)用,1. ABC 2. (AB)C BC 3. C (假設(shè)) 4. (AB) (2.3.銷去) 5. AB (4.等值) 6. AB (1.3.銷去) 7. B (反設(shè)) 8. A (5.7.銷去) 9. A (6.7.

19、銷去) 10. AA (8.9.引入) 11. B (710.銷去) 12. CB (311.引入) 13. CB (12.等值) 14. BC (13.交換) 證畢。,,,,,,,在推理中的綜合應(yīng)用,1. (AB)C 2. (BD)(AC) 3. (BA)(CD) 4. (BC)A 5. B (假設(shè)) 6. C (反設(shè)) 7. BC (5.6.引入) 8. A (4.7.銷去) 9. BA (5.8.引入) 10. CD (3.9銷去) 11. D (6.10.銷去) 12. BD (5.11.引入) 13. AC (2.12.銷去) 14. A (8.13.銷去) 15. AA (8.14.引入) 16. C (615.銷去) 17. BC (516.引入),,,,,,,