《邏輯學(xué)真值表及命題演算.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《邏輯學(xué)真值表及命題演算.ppt（56頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(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é)詞主要有五個(gè)： （否定）、（合取）、 （析?。ⅲㄌN(yùn)涵）、 （等值）,二、真值形式,定義：真值形式是指由真值聯(lián)結(jié)詞和命題變項(xiàng)所構(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,真值表判定程序的三個(gè)要求,（1）程序的每一步都是由事先給定的規(guī)則明 確規(guī)定好的； （2）對(duì)于所判定的對(duì)象是否具有某種性質(zhì)， 該程序能夠給出唯一確定的結(jié)果； （3）該程序能夠在有窮步驟結(jié)束。 判定程序的特點(diǎn)： 機(jī)械的、能行的、可判定的。,完全真值表法,完全真值表的作法 三個(gè)步驟： 1、找出已給命題公式的所有變項(xiàng)，并豎行列出這些變項(xiàng)的所有真值組合； 2、根據(jù)命題公式的結(jié)構(gòu)，由繁到簡(jiǎn)的依次橫行列出，一次只引進(jìn)一個(gè)連接詞，直至列出該公式本身； 3、依據(jù)基本真值表，有變項(xiàng)的真值逐步計(jì)算出每個(gè)部分的真值，最后列出整個(gè)公式得真值。,,,完全真

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

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

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

6、公式時(shí)，樹(shù)冠過(guò)大操作不便。 4、問(wèn)題： 是否有一種方法既能解決命題邏輯有效性的判定問(wèn)題又能解決有效性的推導(dǎo)問(wèn)題？,命題演算的證明方法,一、命題演算方法概述 1、命題演算方法在問(wèn)題求解上的必要性認(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）依序編號(hào)排列前提，將結(jié)論寫(xiě)在最后一個(gè)前提的右側(cè)并用“/”斷開(kāi)。 （2）依據(jù)已知前提結(jié)合相關(guān)規(guī)則推出新

7、的命題，依次編號(hào)寫(xiě)在下面。 （3）在推出的新命題右側(cè)括號(hào)內(nèi)注明前提依據(jù)和規(guī)則依據(jù)。 （4）證明結(jié)束寫(xiě)上證畢字樣。,推證實(shí)例分析 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,,,,,畫(huà)一個(gè)完全真值表,實(shí)例分析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 永真式 永假式 可真式,**,實(shí)例分析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,,,,,,等值,矛盾,,,,實(shí)例分析4：用歸謬賦值法判定（（pq）q）P這個(gè)推理是否有效？,（（pq）q）P

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

13、 6. B （2，5，銷去） 7. A （1，6，銷去） 證畢。,直接證明法（實(shí)例分析一）,直接證法（實(shí)例分析二）,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é)論處在命題的后件，要獲證必須基于對(duì)前件C的肯定。 (2) C與前提1關(guān)聯(lián)，要獲

14、取必須基于主聯(lián)結(jié)關(guān)系的銷去。 (3) 前提1的銷去，取決于對(duì)前提2中條件A的否定。 (4) 要獲取對(duì)A的否定，必須基于對(duì)后件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è)證明法（實(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è)證明法（實(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. 引入) 證畢。,,,,反證法（實(shí)例分析一）,在證明中的綜合應(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.引入),,,,,,,