離散數(shù)學(xué)及其應(yīng)用第3章-命題演算與推理(上)課件

1、2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所11離散數(shù)學(xué)Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所2第3章 命題演算與推理（上）2022/7/25 命題公式與等值演算23 命題的概念與運(yùn)算1 命題演算與推理(上)3 聯(lián)結(jié)詞的完備集2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所4命題的概念與運(yùn)算 命題的概念與運(yùn)算 邏輯與命題邏輯 命題的基本概念 命題的常用聯(lián)結(jié)詞2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所6 邏輯學(xué)邏輯學(xué)-是一門研究思維形式和思維規(guī)律的科學(xué)，包含：辯證邏輯：研究人的思維中的辯證法。例如：用全面的和發(fā)展的觀點(diǎn)觀察事物；具體問

2、題具體分析；實(shí)踐是檢查事物正誤的唯一標(biāo)準(zhǔn)；等等。形式邏輯：研究人的思維的形式和一般規(guī)律。本課程只關(guān)心形式邏輯。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所7 人類的思維規(guī)律人類的思維過程：通過學(xué)習(xí)掌握概念和判斷，然后進(jìn)行推理，即： 概念 判斷 推理 推理：由若干個(gè)已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。正確的思維： 概念清楚，判斷正確，推理合乎邏輯2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所8邏輯推理實(shí)例公安人員審查一件盜竊案，已知的事實(shí)如下：甲或乙盜竊了錄音機(jī)；若甲盜竊者，則作案時(shí)間不會(huì)發(fā)生在午夜前；若乙的證詞正確，則午夜時(shí)屋里的燈光未滅；若乙的證詞不正確，則作案時(shí)間發(fā)生在午夜前；午夜時(shí)屋里

3、的燈光滅了。問：盜竊者是誰？2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所9邏輯推理實(shí)例前提：甲或乙盜竊了錄音機(jī)；若甲盜竊了錄音機(jī)，則作案時(shí)間不可能發(fā)生在午夜前；若乙的證詞正確，則午夜時(shí)屋里的燈光沒有滅；若乙的證詞不正確，則作案時(shí)間發(fā)生在午夜前；午夜時(shí)屋里的燈光熄滅了。結(jié)論：后承關(guān)系，推理盜竊錄音機(jī)的是乙2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所10學(xué)習(xí)邏輯的目的 各門科學(xué)都是在特殊領(lǐng)域的思維推理活動(dòng),故邏輯是一切科學(xué)的公共基礎(chǔ). 邏輯思維能力是學(xué)習(xí)、工作乃至日常生活中的重要能力.2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所11 古典邏輯亞里士多德的三段論(syllogism) 從兩個(gè)前提推出一個(gè)結(jié)論的邏輯論證

4、形式: 1.大前提(major premise) 人都是兩足動(dòng)物 2.小前提(minor premise) 希臘人都是人 3.結(jié)論(conclusion) 希臘人都是兩足動(dòng)物2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所12 數(shù)理邏輯數(shù)理邏輯的創(chuàng)始人德國數(shù)學(xué)家萊布尼茨1646-1716英國數(shù)學(xué)家布爾1815-1864德國數(shù)學(xué)家弗雷格1848-19252022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所13 萊布尼茨Gottfried Wilhelm Leibniz (1646-1716) 首先使用“數(shù)理邏輯”這個(gè)術(shù)語 Leibnizs Dream:把推理歸結(jié)為(符號(hào))計(jì)算.提出“思維演算”的思想： “發(fā)生爭論時(shí)我們

5、可以簡單地說:讓我們計(jì)算一下吧,看誰正確.”2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所14 布 爾George Boole (1815-1864) 1847年的論文: 邏輯的數(shù)學(xué)分析:論演繹推理的演算法. 發(fā)明了布爾代數(shù)(邏輯代數(shù),命題代數(shù),布爾邏輯)，初步實(shí)現(xiàn)了Leibniz夢(mèng)想。 布爾代數(shù)亦可解釋成集合代數(shù),開關(guān)代數(shù)，是計(jì)算機(jī)數(shù)字邏輯的基礎(chǔ)。 附注:Augustus de Morgan (1806-1871)幾乎同時(shí)獨(dú)立地做出重要貢獻(xiàn).2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所15 弗雷格Friedrich Ludwig Gottlob Frege (1848-1925)1879年的重要著作： 概

6、念文字:一種模仿算術(shù)語言構(gòu)造的純思維的形式語言 是第一個(gè)公理化謂詞邏輯系統(tǒng) 是自Aristotle以來邏輯的最重要進(jìn)展 基本實(shí)現(xiàn)了Leibniz夢(mèng)想2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所16 數(shù)理邏輯的概念 用數(shù)學(xué)方法研究演繹推理的一門數(shù)學(xué)學(xué)科 數(shù)學(xué)方法通過引進(jìn)一整套形式化符號(hào)系統(tǒng)的方法。因此，數(shù)理邏輯有時(shí)候也稱為符號(hào)邏輯 數(shù)理邏輯的構(gòu)成 一套符號(hào)體系 + 一組運(yùn)算規(guī)則2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所17 數(shù)理邏輯的內(nèi)容 數(shù)理邏輯包括： 命題邏輯、謂詞邏輯、公理化集合論、遞歸論、模型論、證明論 本課程只討論“命題邏輯”和“謂詞邏輯”2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所18 命題邏輯命題

7、邏輯也稱命題演算，或語句邏輯。研究內(nèi)容： （1）研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系 （2）研究什么是命題？ （3）研究如何表示命題？ （4）研究如何由一組前提推導(dǎo)一些結(jié)論？2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所19 數(shù)理邏輯與軟件程序算法數(shù)據(jù) 算法邏輯控制2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所20 數(shù)理邏輯與硬件命題邏輯 數(shù)字邏輯與門電路 計(jì)算機(jī)組成原理 命題的概念與運(yùn)算 邏輯與命題邏輯 命題的基本概念 命題的常用聯(lián)結(jié)詞2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所22命題的概念命題是一個(gè)或真或假的陳述句，但不能既真又假。確定命題語句真值的幾點(diǎn)說明： 1、時(shí)間性 2、區(qū)域性 3、標(biāo)準(zhǔn)

8、性2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所23命題的概念 真命題：命題表達(dá)的內(nèi)容為真或者說命題的取值為真； 假命題：否則命題表達(dá)的內(nèi)容為假或者說命題的取值為假； 真值:命題或真或假的取值。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所24 命題舉例（1） 合肥是安徽的省會(huì)。 （2） 中國是世界上人口最多的國家。（3） 圓周率 是一個(gè)有理數(shù)。 （4） 整數(shù) 3 能被 2 整除。（5） 小張是個(gè)大學(xué)生。 （6） 今天是你的生日。（7） 2100 年元旦是晴天。 （8） 地球外的星球上也有人。（9） 我正在說假話。 （10） 滿山的杜鵑花， 真讓人心曠神怡！（11） 請(qǐng)把門關(guān)上。 （12） 你是餓了嗎？ 【分

9、析】語句(1)到(8)都是命題。其中：語句(1)、(2)的判斷都符合實(shí)際情況，因而都是真值為的命題， 即為真命題； 語句(3),(4)的判斷都是錯(cuò)誤的，因而都是真值為的命題，即為假命題； 對(duì)于語句(5)、(6)、(7)、(8)，其真值雖然是唯一確定的，但是確定正確這些命題真值的相關(guān)條件均未知， 故這些命題的真值均為未知。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所25 命題舉例【分析】 語句（9）雖然是一個(gè)陳述句， 但是如將其作為命題， 則根據(jù)該命題所表達(dá)的含義可知，其真值的取值無論為真還是為假，都會(huì)產(chǎn)生矛盾。因此，該陳述句是一個(gè)悖論，其真值既不能為真，也不能為假，不能作為命題。 語句(10)、(1

10、1)、(12)均不是陳述句，都不能形成一個(gè)邏輯上的是非判斷， 因而都不能成為命題。 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所26 命題舉例2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所27 命題舉例【注意】一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等?！窘狻空Z句（1）到（8）都是命題，其中語句（1）、（2） 為真命題，命題（3）、（4） 是假命題，命題（5）、（6）、（7）、（8）的真值未知。 語句（9） 到（12） 都不是命題。 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所28 命題的基本概念【定義】對(duì)于任意一個(gè)給定的命題，當(dāng)它不能再分解為更加簡單的陳述句時(shí)，則稱

11、該命題為原子命題；否則，稱之為復(fù)合命題。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所29 命題的基本概念【例題】父親讓兩個(gè)孩子（一男一女）在后院玩耍，并囑咐他們不要把身上搞臟。然而，在玩的過程中，兩個(gè)孩子都在額頭上沾了泥。當(dāng)孩子們回來后，父親首先說他們當(dāng)中至少有一個(gè)人額頭上有泥，然后問每個(gè)孩子能否確定自己額頭上是否有泥，兩個(gè)孩子都說不能；可是當(dāng)父親第二次問同樣問題時(shí)，兩個(gè)孩子都說可以。假設(shè)：（1）每個(gè)孩子都可以看到對(duì)方的額頭上是否有泥，但不能看見自己的額頭；（2）兩個(gè)孩子都很誠實(shí)并且都同時(shí)回答每一次提問。試分析兩孩子能夠做出正確判斷的原因。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所30 命題的基本概念2

12、022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所31 命題的基本概念2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所32 小 結(jié) 命題一定是陳述句，但并非一切陳述句都是命題。 命題的真值有時(shí)可明確給出，有時(shí)還需要依靠環(huán)境、條件、時(shí)間、實(shí)際情況才能確定其真值。 命題的概念與運(yùn)算 邏輯與命題邏輯 命題的基本概念 命題的常用聯(lián)結(jié)詞2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所34 聯(lián)結(jié)詞的概念 命題可以通過邏輯聯(lián)結(jié)詞(邏輯運(yùn)算)構(gòu)成新的命題復(fù)合命題。 復(fù)合命題的真值依賴于其中簡單命題的真值。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所35 聯(lián)結(jié)詞舉例 【例】 （1）期中考試，張三沒有考及格。 （2）其中考試，張三和李四都考及格了。 （

13、3）期中考試，張三和李四中有人考了90分。 （4）如果張三能考90分，那么李四也能考90分。 （5）張三能考90分，當(dāng)且僅當(dāng)李四也能考90分。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所36 五個(gè)常用聯(lián)結(jié)詞 ：Negation (NOT) 否定詞 ：Conjunction (AND) 合取詞 ：Disjunction (OR) 析取詞 ：Implication (if then) 蘊(yùn)涵詞 ：Biconditional (if and only if) 等價(jià)詞2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所37372022/7/25 “非”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所38382022/7/25命題

14、否定的真值表如下：PPTFFT “非”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所39 “與”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所40402022/7/25當(dāng)且僅當(dāng)P和Q都為真時(shí)，PQ才為真PQPQTTTTFFFTFFFF “與”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所41412022/7/25 “與”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所42422022/7/25 “與”運(yùn)算【分析】在自然語言中，除了聯(lián)結(jié)詞 “并且”，其它的一些聯(lián)結(jié)詞， 例如“不但而且”、“既也”、“雖然但是”、“一方面另一方面”等也表示同時(shí)為真的含義，因而也可用合取聯(lián)結(jié)詞表示。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究

15、所43432022/7/25 “與”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所44 “(可兼)或”運(yùn)算P: 李明在教室。Q: 米盧是個(gè)好教練。PQ: 李明在教室或米盧是個(gè)好教練。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所45PQ的真值為F，當(dāng)且僅當(dāng)P與Q均為FPQPQTTTTFTFTTFFF “(可兼)或”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所46 “(可兼)或”運(yùn)算【例題】用復(fù)合命題表示下圖所示的開關(guān)電路：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所47 “(可兼)或”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所48 “蘊(yùn)涵”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所49 “蘊(yùn)涵”運(yùn)算例：P表示：缺

16、少水分。Q表示：植物會(huì)死亡。PQ：如果缺少水分，植物就會(huì)死亡。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所50當(dāng)且僅當(dāng)P為真且Q為假時(shí)，PQ為假PQPQTTTTFFFTTFFT “蘊(yùn)涵”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所51【注意】“”既表示充分條件也表示必要條件，它決定了哪個(gè)作為前件，哪個(gè)作為后件。【例】令：P：天氣好。 Q：我去公園。1.如果天氣好，我就去公園。（充分）2.只要天氣好，我就去公園。（充分）3.僅當(dāng)天氣好，我才去公園。（必要）4.只有天氣好，我才去公園。（必要）命題1、2 寫成： PQ 命題3、4 寫成： QP “蘊(yùn)涵”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所52 “等價(jià)

17、”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所53“” :等價(jià)聯(lián)結(jié)詞PQ（P當(dāng)且僅當(dāng)Q）：當(dāng)p和q有著相同的真值時(shí)， p q 為真）PQPQTTTTFFFTFFFT “等價(jià)”運(yùn)算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所54 小 結(jié)設(shè)命題P,Q表示任意兩個(gè)命題,則最常見的命題聯(lián)結(jié)詞有：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所55552022/7/25 小 結(jié)P QPPQPQPQPQ0 0100110 1101101 0001001 101111設(shè)命題P,Q表示任意兩個(gè)命題,則有：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所56 命題符號(hào)化 1. 首先要明確給定命題的含義。 2. 對(duì)于復(fù)合命題，找聯(lián)結(jié)詞，用聯(lián)

18、結(jié)詞斷句，分解出各個(gè)原子命題。 3. 設(shè)原子命題符號(hào)，并用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題符號(hào)，構(gòu)成給定命題的符號(hào)表達(dá)式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所57 若干要點(diǎn)聯(lián)結(jié)詞與自然語言之間的對(duì)應(yīng)并非一一對(duì)應(yīng)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所58 例 題【例】符號(hào)化下列命題 說離散數(shù)學(xué)無用且枯燥無味是不對(duì)的。 P：離散數(shù)學(xué)是有用的。 Q：離散數(shù)學(xué)是枯燥無味的。 該命題可寫成： (PQ) 人不犯我，我不犯人；人若犯我，我必犯人。 P：人犯我。Q：我犯人。 該命題可寫成：(PQ)(PQ) 或?qū)懗桑?PQ2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所59592022/7/25 例 題【例】符號(hào)化下列命題 （1

19、）四川不是人口最多的省份； （2）王超是一個(gè)德智體全面發(fā)展的好學(xué)生； （3）教室的燈不亮可能是燈管壞了或者是停電了； （4）如果周末天氣晴朗，那么學(xué)院將組織我們到石象湖春游； （5）兩個(gè)三角形全等當(dāng)且僅當(dāng)三角形三邊對(duì)應(yīng)相等。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所60602022/7/25 例 題【例】符號(hào)化下列命題（1）除非明天不下雨且不下雪，否則我將不去學(xué)校；（2）只要明天不下雨或不下雪，我就去學(xué)校；（3）只有明天不是雨夾雪，我才去學(xué)校；（4）明天上午我將雨雪無阻一定去學(xué)校。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所61612022/7/25 例 題【例】符號(hào)化下列命題 除非你陪伴我或代我叫車子

20、，否則我將不出去。 如果你陪伴我并且代我叫輛車子，那么我將出去。 如果你不陪伴我或不代我叫輛車子，那么我將不出去。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所62622022/7/25聯(lián)結(jié)詞的應(yīng)用 聯(lián)結(jié)詞“”、“”、“”同構(gòu)成計(jì)算機(jī)的與門、或門和非門電路是相對(duì)應(yīng)的，從而命題邏輯是計(jì)算機(jī)硬件電路的表示、分析和設(shè)計(jì)的重要工具。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所63632022/7/25【例】用復(fù)合命題表示如下圖所示的邏輯電路P QPQP【解】設(shè)P：輸入端為高電位，Q：輸入端為高電位,則 “與門” 對(duì)應(yīng)于 PQ “或門” 對(duì)應(yīng)于 PQ “非門”對(duì)應(yīng)于 P 應(yīng)用實(shí)例2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所

21、64 應(yīng)用實(shí)例【例題】 使用命題聯(lián)結(jié)詞將下列命題符號(hào)化：（1） 說離散數(shù)學(xué)無用且枯燥無味是不對(duì)的。（2） 只有我不復(fù)習(xí)功課, 我才去看電影。（3） 除非你陪我或代我叫車，否則我將不出去。（4） 若兩個(gè)圓面積相等，則半徑相等，反之亦然。（5） 如果天不下雨且不刮風(fēng)，我就去書店看書，否則我就在家休息。（6） 若不是他生病或出差，老板是不會(huì)同意他不參加這個(gè)會(huì)議的。 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所65 應(yīng)用實(shí)例【分析】 命題（1） 直接按題意進(jìn)行符號(hào)化； 命題（2），“我不復(fù)習(xí)功課”是“我去看電影”的一個(gè)必要條件，可用“” 表示； 命題（3） 中“除非否則不”表示如果前件不發(fā)生， 那我就一定不

22、會(huì)做什么， 或者說若做了什么， 則前件一定發(fā)生， 因此，如果我出去的話，你肯定是陪我或者替我叫車，或者說如果你既不陪我，也不替我叫車，那我肯定不出去；2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所66 應(yīng)用實(shí)例【分析】命題（4）， 由兩圓面積相等可推出其半徑相等，半徑相等也可推出兩圓面積相等， 故“圓半徑相等”與“圓面積相等”之間是等價(jià)關(guān)系， 可用“” 表示； 命題（5）中用了三個(gè)聯(lián)結(jié)詞“如果就”、“且”和“或”，其中“或”聯(lián)結(jié)詞是從命題中理解出來的， 沒有明確給出。 因?yàn)閺拿}中“否則”一詞可理解為“否則， 如果天下雨或刮風(fēng)，我就在家休息”； 命題（6）則可以理解為“他不生病并且不出差，老板就不同意

23、他不參加會(huì)議”。 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所67 應(yīng)用實(shí)例2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所68 應(yīng)用實(shí)例2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所69 應(yīng)用實(shí)例【解】令P表示 “A是騎士”，Q表示 “B是騎士”，則P和 Q分別表示 “A是流氓”和“B是流氓”。首先假設(shè)A是騎士，即P為真。由于A是騎士，那么A說的命題“B是騎士”就為真，即Q為真。此時(shí)，A和B就是一類人。但如果B是騎士，那么B的話也應(yīng)該為真，即(PQ)(PQ)為真，由此得到矛盾，因?yàn)锳和B都是騎士。故此時(shí)不存在A是騎士的情形。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所70 應(yīng)用實(shí)例如果A是流氓，則由題意知A所說的命題“B

24、是騎士”為假，也就是說Q為假，即B也是流氓。進(jìn)一步，如果B是流氓，那么B說的命題也為假，這與A和B都是流氓的判斷是一致的。因此得出的結(jié)論為：A和B都是流氓。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所71本節(jié)內(nèi)容到此結(jié)束謝謝大家！2022/7/25命題的概念與運(yùn)算1命題公式與等值演算2 本章學(xué)習(xí)內(nèi)容(上)3 聯(lián)結(jié)詞的完備集2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所73命題公式與等值演算 命題公式與等值演算 命題公式的基本知識(shí) 等值關(guān)系與等值演算 公式的內(nèi)否與對(duì)偶2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所75752022/7/25 命題變?cè)?如果命題標(biāo)識(shí)符表示一個(gè)具體、確定的命題，稱為命題常元。 如果命題標(biāo)識(shí)

25、符表示任意一個(gè)命題，稱為命題變?cè)?命題是能判斷真假的陳述句。 命題變?cè)砣我獾拿}，其真值是不確定的，它的變域是集合T，F(xiàn)(或0，1) 。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所76762022/7/25 命題公式 把命題常元，命題變?cè)凑找欢ǖ倪壿嬳樞蚝鸵?guī)則，用命題聯(lián)結(jié)詞連接起來就構(gòu)成了命題演算的合式公式，也叫命題公式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所77 命題公式的定義 按下列規(guī)則構(gòu)成的符號(hào)串稱為命題演算的合式公式，也稱為命題公式，簡稱公式。 單個(gè)命題變?cè)统Ｔ呛鲜焦健?如果A是合式公式，那么A是合式公式。 如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)是合式

26、公式。 當(dāng)且僅當(dāng)有限次地應(yīng)用了、所得到的符號(hào)串是合式公式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所78 命題公式的定義 上面的定義給出合式公式定義的方法稱為歸納定義，它包括三部分： 基礎(chǔ)、歸納、界限 其中是基礎(chǔ)，和是歸納，是界限。 以后將多次出現(xiàn)這種形式的定義。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所79 命題公式舉例【例】下列符號(hào)串是合式公式： (pq)，(pq)，(p(pq)， (pq)(qr)(st) 【例】下列符號(hào)串不是合式公式： (pq)(q)，(pq，(pq)q)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所80802022/7/25 一些約定【約定】為方便，最外層括號(hào)可以不寫，合式公式可以寫

27、成： PQ，PR，(PQ)R【約定】邏輯聯(lián)接詞優(yōu)先級(jí)： 、 、 、 、 此時(shí)PQR也是合式公式 原子公式：表示原子命題的命題變量是最簡單的命題公式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所81812022/7/25 例 題【例】試用符號(hào)形式寫出下列命題：（1）雖然今天天氣晴朗，老陳還是不來；【解】 設(shè) P：今天天氣晴朗, Q：老陳要來, 則有： PQ；（2）除非你陪伴我或代我叫車子，否則我將不出去；【解】 設(shè) P:你陪伴我; Q:你代我叫車子; R:我出去。 則有：RPQ 或 PQR；2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所82 例 題【例題】對(duì)于下列字符串，試判別哪些是命題公式，哪些不是，為什么

28、？ （1） (QPS)； （2）(PQ)(QP)； （3）(PQR)； （4） (PP)(QQ)R)； （5） (PQ)(Q) ； （6）(PQ)(QR)(ST)；2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所83 例 題【分析】由命題公式的定義可知：一個(gè)命題公式可以是一個(gè)單個(gè)的命題變?cè)?，也可以是由多個(gè)命題公式通過命題聯(lián)結(jié)詞以及括弧聯(lián)結(jié)而成的。因此有：（1）、（2）、（6）是命題公式，因?yàn)樗鼈兌紳M足命題公式的定義。（3）、（4）、（5）都不是命題公式，（3）中“PQ”之間沒有聯(lián)結(jié)詞，所表達(dá)的含義不明確，（4）中多了一個(gè)“)”，（5）是因?yàn)槭且粋€(gè)二元聯(lián)結(jié)詞，(Q)中的左邊缺少命題變量或者命題公式，因而不

29、是命題公式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所84 例 題【解】（1）、（2）、（6）是命題公式，（3）、（4）、（5）不是命題公式。由命題公式的定義可知：（1）表示原子命題的命題變量是最簡單的命題公式，通常稱之為原子公式；（2）就像初等代數(shù)中的多項(xiàng)式?jīng)]有具體數(shù)值一樣，命題公式也沒有具體的真值，只有當(dāng)命題公式中每個(gè)命題變量都進(jìn)行具體的真值指派以后，才可確定命題公式的真值；2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所85 例 題（3）命題公式的結(jié)構(gòu)可以很簡單，例如原子命題公式，也可以很復(fù)雜；（4）為敘述方面，對(duì)于命題變量P和Q，通常也分別將(P)、(PQ)、(PQ)、(PQ)、(PQ)稱為否定式、

30、合取式、析取式、蘊(yùn)涵式和等價(jià)式，在合取式(PQ)中，P、Q被稱為合取項(xiàng)，在析取式(PQ)中，P、Q被稱為析取項(xiàng)。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所86862022/7/25 公式的解釋【定義】設(shè)P1,P2,Pn是出現(xiàn)在公式G中的所有命題變?cè)?，指定P1,P2,Pn一組真值，例如(0,1, ,1)，則稱這組真值為對(duì)公式G的一個(gè)解釋或賦值, 記為2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所87872022/7/25 賦值類型 若指定的賦值使G的真值為T，則稱這個(gè)賦值為G的成真賦值， 若指定的賦值使G的真值為F，則稱這個(gè)賦值為G的成假賦值。 【例】給公式(pqr)的賦值 賦值011是指p=0，q=1，r

31、=1，它是該公式的成真賦值； 賦值110是指p=1，q=1，r=0，它是該公式的成假賦值。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所88 真值表的概念 若公式G中有個(gè)不同的命題變?cè)瑒t該公式應(yīng)有2n個(gè)不同的解釋。 將公式G在其所有可能解釋下的真值情況列成的表，稱為G的真值表。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所89 真值表的概念 在命題公式G中，對(duì)G的每一個(gè)賦值，就確定了G的一個(gè)真值，把這些所有的真值匯列成表，稱該表為命題公式G的真值表。PQPPQ(PQ)QTTFTTTFFTTFTTTTFFTFF2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所90902022/7/25 真值表舉例【例題】構(gòu)造公式 (PQ

32、)R的真值表。【分析】構(gòu)造真值表的可以分為以下三步：（1）列出公式所有命題變?cè)约捌渌械目赡苜x值狀態(tài)；（2）按運(yùn)算優(yōu)先級(jí)從高到低的順序?qū)懗雒}公式各層次運(yùn)算表達(dá)式；（3）針對(duì)各個(gè)賦值狀態(tài)計(jì)算出各層次的真值，直到最后計(jì)算出公式的真值。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所91912022/7/25 真值表舉例【解】按照如上步驟，構(gòu)造真值表如下：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所92922022/7/25 真值表舉例【例題】構(gòu)造公式 (PQ)(QP)的真值表?！窘狻颗c上述解法類似，寫出公式：P、Q、PQ、QP、(PQ)(QP)的真值表如表所示。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所93932

33、022/7/25 真值表舉例【例題】 有一邏輯學(xué)家誤入某部落， 該部落酋長對(duì)邏輯學(xué)家說： “今有兩扇門，一為死亡門，一為自由門，你可任意開啟其中一扇以選擇死亡和自由。 現(xiàn)派兩人助你選擇，這兩人負(fù)責(zé)解答你提出的任何問題，但是這兩人中一名天性誠實(shí)、一名說謊成性。 ” 邏輯學(xué)家沉思片刻，即手指一門向一人發(fā)問，然后選擇一門從容離去。 試問： 該邏輯學(xué)家如何發(fā)問？2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所94 真值表舉例【分析】邏輯學(xué)家問其中一人： “這扇門是死亡門，他將回答是， 對(duì)嗎？ ”如果被問者天性誠實(shí)， 且回答對(duì)，那么另外一人則說謊成性，回答是則意味著不是，也就是說，邏輯學(xué)家手指之門不是死亡門。 其

34、它情況可類似分析，具體可通過列出真值表進(jìn)行分析。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所95 真值表舉例【解】令表示命題 “被問者天性誠實(shí)”； 表示命題 “被問者回答對(duì)”； 表示命題 “另外一人回答是”； 表示命題 “這扇門是死亡門”。 則可列出如下真值表。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所96 真值表舉例 此時(shí)， 手指一門向一人發(fā)問： “這扇門是死亡門，他將回答是， 對(duì)嗎？ ”如果被人回答是，則由真值表可知， 這扇門不是死亡門，即為自由門，邏輯學(xué)家可開啟此門離去；如果被人回答不是，則由真值表可知， 該門是死亡門，邏輯學(xué)家可開啟另外一扇門離去。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所97972

35、022/7/25 真值表的說明 設(shè)P1，P2,Pn為命題公式P中命題變?cè)瑢?duì)于命題變?cè)恳环N真值指派的可能組合，都能唯一確定P的真值（即有2的n次冪種分布）。 為有序列出公式的真值表，在對(duì)命題變?cè)鲋概蓵r(shí)，可按二進(jìn)制數(shù)次序列表。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所98982022/7/25 真值表的說明為有序列出G(P1,P2,Pn)的真值表，可以將F看成0，將T看成1，按照二進(jìn)制數(shù)000, 0001, 00010, , 1110, 111(即十進(jìn)制的0,1,2,. ,2n -1)的次序進(jìn)行指派列真值表。如G(P,Q)的真值表可按照如下次序指派： 00(F,F)，01(F,T)，10(T,F

36、)，11(T,T)如G(P,Q,R)的真值表可按照如下次序指派： 000(F,F,F), 001(F,F,T), 010(F,T,F), 011(F,T,T) 100(T,F,F), 101(T,F,T), 110(T,T,F), 111(T,T,T)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所99992022/7/25 例 題【例】構(gòu)造命題公式pq的真值表，并求成真賦值和成假賦值?！窘狻棵}公式pq的真值表下表所示。00，01，11是成真賦值，10是成假賦值。ppqpq00110111100011012022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1001002022/7/25 例 題 【例】構(gòu)造命題公式(

37、pq)(pq)的真值表，并求成真賦值和成假賦值。 【解】命題公式(pq)(pq)的真值表如下表所示。00， 11是成真賦值，01，10是成假賦值。 pqpqpqpq(pq)(pq)00011110101000100010011100012022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1011012022/7/25 例 題【例】列出P(QR)的真值表 P Q R QRP(QR)000 F F F T T001 F F T T T010 F T F F T 011 F T T T T100 T F F T T101 T F T T T110 T T F F F111 T T T T T2022/7/25計(jì)算

38、機(jī)應(yīng)用技術(shù)研究所1021022022/7/25 公式的分類【例】求列公式的真值表： 1 ()； 2()； 3 () (Q)。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1031032022/7/25 公式的分類從這三個(gè)真值表可以看到：公式 G1 對(duì)所有可能的解釋具有“真”值公式 G3 對(duì)所有可能的解釋均具有“假”值公式 G2 則具有“真”和“假”值2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1041042022/7/25 公式的分類 公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。 公式G稱為永假公式(矛盾式), 如果在它的所有解釋之下都為“假”。 公式G稱為可滿足式，如果它不是永假的。2

39、022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1051052022/7/25 公式的分類如果A，B是永真式(永假式)，則(AB)、(AB)、(AB)和(AB)也都是永真式(永假式) 。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所106公式的分類永真式G的否定G是矛盾式； 矛盾式G的否定G是永真式。永真式一定是可滿足式; 可滿足式不一定是永真式可滿足式的否定不一定是矛盾式三種特殊公式之間的關(guān)系：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所107公式的分類三種特殊公式之間的關(guān)系：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1081082022/7/25 例 題【例】寫出下列公式的真值表，并驗(yàn)證其公式是永真式、永假式、可滿足公

40、式。 （1）G1=()()； （2）G2=(Q)(Q)(Q)； （3）G3=(PQ)Q。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1091092022/7/25 例 題 命題公式與等值演算 命題公式的基本知識(shí) 等值關(guān)系與等值演算 公式的內(nèi)否與對(duì)偶2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所111 命題公式與等值演算【例題】使用真值表分析如下兩個(gè)命題公式在真值取值上的聯(lián)系： P(QP)；P(PQ)【解】寫出公式P、Q、P、Q、QP、P(QP)、PQ、P(PQ)的真值表，如表所示：2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所112 命題公式與等值演算從真值表可以看出：公式P(QP)和P（PQ)的取值在命題變?cè)乃?/p>

41、有取值狀態(tài)下均保持一致。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所113 公式等值的定義 【定義】A、B是含有命題變?cè)狿1,P2, Pn的命題公式，如不論對(duì)P1, P2 , , Pn作任何指派，都使得A和B的真值相同，則稱之為命題公式A與B等價(jià)或等值，記作AB。 顯然有： PQPQ (PQ)(PQ)PQ2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所114 例題【例題】判斷命題公式P(QR)與命題公式(PQ)R是否是等值關(guān)系。 【分析】要判斷上述兩個(gè)命題公式是否等值，可以通過真值表枚舉方式比較兩個(gè)公式的真值在任意解釋下是否都相同?！窘狻繉懗龉絇、Q、R、P(QR)、(PQ)R的真值表，如表所示。2022/

42、7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所115 例題通過上表，不難看出P(QR)與(PQ)R是等值關(guān)系2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所116觀察下列真值表 P QP QP Q（P Q）（ P Q ） P Q F F T TT T F T T TFF T F F FFF T T T TTT是否發(fā)現(xiàn)什么問題？P Q P Q？（P Q）（ P Q ） P Q ？ 公式的等值關(guān)系2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所117 命題公式與等值演算【定理】對(duì)于命題公式A和B，AB的充分必要條件是公式ABT?！咀C明】 首先證明充分性：若ABT，則該式表示在任一組真值指派下公式AB的值均為真，或者 A、B的真值都一定

43、相同，故公式A和B等值，即有AB。 再證必要性：若AB，則A、B在任何解釋下均有相同的真值，也就是說AB在任何解釋下均為真，或者說AB與T有相同的真值，即有ABT。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所118 與的區(qū)別2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所119 命題公式與等值演算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所120 命題公式與等值演算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所121 等值的性質(zhì)可以證明，命題公式的等值關(guān)系有如下性質(zhì)： (1) 自反性，即對(duì)任意命題公式A， AA (2) 對(duì)稱性，即對(duì)任意命題公式A和B，若AB，則BA (3) 傳遞性，即對(duì)任意命題公式A，B和C，若AB，BC

44、，則AC (4) 如果A(P1,P2,Pn)B(P1,P2,Pn)，則： A(P1,P2,Pn)B(P1,P2,Pn)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所122 例 題【例題 】證明語句“不會(huì)休息的人不會(huì)工作， 沒有豐富知識(shí)的人也不會(huì)工作”， 與語句“工作得好的人一定會(huì)休息并且有豐富的知識(shí)”， 具有相同的邏輯含義。 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所123 例 題2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所124 基本等值式2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所125 基本等值式2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所126 基本等值式 以上共24個(gè)等值式都可用真值表證明。下面僅驗(yàn)證德摩根律：

45、(AB)AB ABABABAB (AB)00111010110010100101011000102022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所127 例 題【例】 求證吸收律 P(PQ)P【證】( P(PQ) (PF)(PQ) (同一律) P(FQ) (分配律) PF (零律) P (同一律)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所128 例 題【例】求證 (PQ)(PQ) P【證】(PQ)(PQ) (PQ)(PQ) (常用等值式) (PQ)(PQ) (摩根定律) (PQ)(PQ) (對(duì)合律) P(QQ) (分配律) PT (互補(bǔ)律) P (同一律)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所129 例 題【

46、例】化簡(PQ)(P(PQ)【解】 原公式(PQ)(PP)Q) (常用等值式)(PQ)(PQ) (對(duì)合律，冪等律)(PQ)(QP) (交換律)(PQ)Q)P (結(jié)合律)QP (吸收律)2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所130 代入定理2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所131 替換定理【定理】設(shè)G1是G的子公式，H1是任一命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H， 若G1H1，則GH。熟記 24個(gè)基本等值公式 理解 代入定理 和 替換定理2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所132 代入定理【例】設(shè)G(P, Q)=(P(PQ)Q，證明公式G是一個(gè)永真公式。另有兩個(gè)公式

47、：H(P, Q)=PQ; S(P,Q)=PQ進(jìn)一步驗(yàn)證代入定理的正確性。【解】由真值表易證G是一個(gè)永真公式。將H和S代入G中得到新公式G為：G(P, Q)= G(H, S)=(H(HS)S=(PQ) (PQ) (PQ)(PQ)由真值表易證G是一個(gè)永真公式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所133 等值演算法 證明兩個(gè)命題公式之間等值或邏輯等價(jià)的另外一種方法叫做等值演算法。 基本思路是：首先用真值表證明一組基本等值式，然后再它們?yōu)榛A(chǔ)進(jìn)行命題公式之間的等值演算。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所134命題公式的等值演算利用公式的等值演算，可以實(shí)現(xiàn)以下三個(gè)基本目的：1）判定命題公式的基本類

48、型，即判定或證明一個(gè)命題公式為永真或永假；2）證明兩個(gè)命題公式之間具有等值關(guān)系；3）對(duì)復(fù)雜的命題公式進(jìn)行化簡。 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所135命題公式的等值演算【證明】(PQ)(P(QR) (PQ)(PR) (PQ)(P(QR) (P(QR) (PQ)(P(QR) (P(QR) (PQ)(PQ)(PR)(PQ)(PQ)(PR)=1 即(PQ)(P(QR) (PQ)(PR)是永真公式。2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所136公式的等值演算 2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所137命題公式的等值演算【例題】利用命題公式的基本等值關(guān)系化簡如圖所示的電路圖：2022/7/25計(jì)算

49、機(jī)應(yīng)用技術(shù)研究所138命題公式的等值演算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所139命題公式的等值演算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所140命題公式的等值演算 命題公式與等值演算 命題公式的基本知識(shí) 等值關(guān)系與等值演算 公式的內(nèi)否與對(duì)偶 命題公式與等值演算 事實(shí)證明，只使用“否定”、 “合取”、 “析取”這三個(gè)聯(lián)結(jié)詞就可以任意的命題公式。 限制性命題公式的定義： 命題公式與等值演算 命題公式與等值演算 命題公式與等值演算 命題公式與等值演算 命題公式與等值演算 命題公式與等值演算 命題公式與等值演算2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所150本節(jié)內(nèi)容到此結(jié)束謝謝大家！2022/7/25命題的概念與運(yùn)算1命題公式與等值演算2 本章學(xué)習(xí)內(nèi)容(上)3 聯(lián)結(jié)詞的完備集2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所152聯(lián)結(jié)詞的完備集 聯(lián)結(jié)詞的完備集 聯(lián)結(jié)詞的枚舉 聯(lián)結(jié)詞的完備性 聯(lián)結(jié)詞的應(yīng)用2022/7/25計(jì)算機(jī)應(yīng)用技術(shù)研究所1