1、離散數(shù)學(xué)(Discrete Mathematics),第一部分 數(shù)理邏輯（Mathematical Logic),邏輯：是研究推理的科學(xué)。公元前四世紀(jì)由希臘的哲學(xué)家亞里斯多德首創(chuàng)。作為一門獨(dú)立科學(xué)，十七世紀(jì)，德國的萊布尼茲(Leibniz)給邏輯學(xué)引進(jìn)了符號, 又稱為數(shù)理邏輯(或符號邏輯)。 邏輯可分為：1. 形式邏輯（通過數(shù)學(xué)方法） 數(shù)理邏輯 2. 辯證邏輯 指引進(jìn)一套符號體系的方法。 辯證邏輯是研究反映客觀世界辯證發(fā)展過程的人類思維的形態(tài)的。,第一部分 數(shù)理邏輯（Mathematical Logic),形式邏輯是研究思維的形式結(jié)構(gòu)和規(guī)律的科學(xué)，它撇開具體的、個別的思維內(nèi)容，從形式結(jié)構(gòu)方面研

2、究概念、判斷和推理及其正確聯(lián)系的規(guī)律。 數(shù)理邏輯是用數(shù)學(xué)方法研究推理的形式結(jié)構(gòu)和推理的規(guī)律的數(shù)學(xué)學(xué)科。它的創(chuàng)始人Leibniz，為了實(shí)現(xiàn)把推理變?yōu)檠菟愕南敕ǎ褦?shù)學(xué)引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學(xué)科。 上個世紀(jì)30年代以后，數(shù)理邏輯進(jìn)入一個嶄新的發(fā)展階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密切關(guān)聯(lián)。,第一部分 數(shù)理邏輯（Mathematical Logic),1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了1936年Turing機(jī)的產(chǎn)生，十年后，第一臺電子計(jì)算機(jī)問世。 從廣義上講，數(shù)理邏輯包括四論、兩演算即集合論、模型論、遞歸論

3、、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本書也只研究這兩個演算。,2020/9/28,第一部分 數(shù)理邏輯（Mathematical Logic),數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透推動了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。 本篇我們只從語義出發(fā)，對數(shù)理邏輯中的命題演算與謂詞演算等作一簡單的、直接的、非形式化的介紹，將不涉及任何公理系統(tǒng)。,2020/9/28,第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,1.1.1 命題（Proposition) 1.1.2 命題

4、的表示方法 1.1.3 命題的分類,2020/9/28,第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,1.1.1 命題 數(shù)理邏輯研究的中心問題是推理（inference),而推理的前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)判斷的陳述句構(gòu)成了推理的基本單位。 基本概念 命題：能夠判斷真假的陳述句。 命題的真值：命題的判斷結(jié)果。命題的真值只取兩個 值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 真命題：判斷為正確的命題，即真值為真的命題。 假命題：判斷為錯誤的命題，即真值為假的命題。,2020/9/28,哈哈， 這句話不是命題哦！,第一

5、章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,因而又可以稱命題是具有唯一真值的陳述句。 判斷命題的兩個步驟： 1、是否為陳述句； 2、是否有確定的、唯一的真值。 例：判斷下列句子是否為命題。 (1). 100是自然數(shù)。 T (2). 太陽從西方升起。 F (3). 3+3=8 . F,哈哈， 這句話不是命題哦！,第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,(4). How do you do ? 疑問句，不是命題 (5). 明年的十月一日是晴天。是命題，其真值到明年 十月一日方可知道。 (6). x+39 不是命題 (7

6、). 我正在說謊。是悖論 (8). 1+101=110 二進(jìn)制中為真，十進(jìn)制中為假。 (9). 如果太陽從西方升起，那么2是奇數(shù)。T (10). 國足能殺入2006世界杯當(dāng)且僅當(dāng)2+2=4。F,第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,(11). 今天天氣多好??！ 感嘆句，不是命題 (12). 請你關(guān)上門！ 祁使句，不是命題， (13). 別的星球上有生物。 是命題，客觀上能判斷真 假。 說明： （1）只有具有確定真值的陳述句才是命題。一 切沒有判斷內(nèi)容的句子，無所謂是非的句子， 如感嘆句、祁使句、疑問句等都不是命題。,第一章 命題邏輯（Proposi

7、tional Logic）1.1 命題及其表示方法,（2） 因?yàn)槊}只有兩種真值，所以“命題邏輯”又稱 “二值邏輯”。 (3) “具有確定真值”是指客觀上的具有，與我們是否知道它的真值是兩回事。如上例中的（5）和（13）。 1.1.2 命題的表示方法 在本書中，用大寫英文字母A,B,P,Q或帶下標(biāo)的字母P1,P2,P3 , ,或數(shù)字(1),2, ,等表示命題，稱之為命題標(biāo)識符。,第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,例如： P：羅納爾多是球星。 Q：5是負(fù)數(shù)。 P3：明天天氣晴。 (2)：太陽從西方升起。 皆為符號化的命題，其真值依次為1、0、1或

8、0、0。 命題標(biāo)識符又有命題常量、命題變元和原子變元 之分。 命題常量：表示確定命題的命題標(biāo)識符。,第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法,命題變元：命題標(biāo)識符如僅是表示任意命題的位置標(biāo) 志，就稱為命題變元。 原子變元：當(dāng)命題變元表示原子命題時，該變元稱為 原子變元。 命題變元也用A,B,P,Q,P1,P2,P3 , , 表示。 1.1.3 命題的分類： 簡單/原子命題：不能分解為更簡單的陳述語句的命題(如上例中的命題)。 復(fù)合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。 聯(lián)結(jié)詞就是復(fù)合命題中的運(yùn)算符。,第一章 命題邏輯（Propositional L

9、ogic）1.1 命題及其表示方法,注意： （1）一個符號(如P), 它表示的是命題常量還是命題變元，一般由上下文來確定。 （2）命題變元可以表示任意命題，它不能確定真值，故命題變元不是命題。這與“變數(shù)x不是數(shù)”是一樣的道理。 小結(jié)：本節(jié)主要介紹了命題、命題的真值、原子命題、復(fù)合命題、命題標(biāo)識符、命題常量、命題變元和原子變元的概念。重點(diǎn)理解和掌握命題、命題變元兩個概念。 作業(yè)：P8 （1）,19,離散數(shù)學(xué)(Discrete Mathematics),20,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),1.2.1 否定聯(lián)結(jié)

10、詞(Negation) 1.2.2 合取聯(lián)結(jié)詞(Conjunction) 1.2.3 析取聯(lián)結(jié)詞(Disjunction) 1.2.4 條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞Conditional) 1.2.5 雙條件聯(lián)結(jié)(等值聯(lián)結(jié)詞Biconditional) ,21,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),在命題邏輯中,主要研究的是復(fù)合命題,而復(fù)合命 題是由原子命題與邏輯聯(lián)結(jié)詞組合而成,聯(lián)結(jié)詞組是 復(fù)合命題的重要組成部分. 1.2.1 否定聯(lián)結(jié)詞 定義1.2.1 設(shè)P為一命題， P的否定是一個新的復(fù)合命題, 稱為P的否定式，記

11、作 “P”讀作“非P”. 符號“ ” 稱為否定聯(lián)結(jié)詞。 P為真當(dāng)且僅當(dāng)P為假. 說明： “”屬于一元(unary)運(yùn)算符,22,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),“”的定義也可用下表來說明. 聯(lián)結(jié)詞“”的定義真值表,23,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),例1. P: 天津是一個城市. Q: 3是偶數(shù). 于是: P: 天津不是一個城市. Q: 3不是偶數(shù). 例2. P:蘇州處處清潔. Q:這些都是男同學(xué). P:蘇州不處處清潔

12、 (注意,不是處處不清潔). Q:這些不都是男同學(xué).,24,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),1.2.2 合取聯(lián)結(jié)詞(Conjunction) 定義1.2.2 設(shè)P,Q為二命題，復(fù)合命題“P并且Q”（或“P與Q”）稱為P與Q的合取式，記作P Q，符號“” 稱為合取聯(lián)結(jié)詞. PQ 為真當(dāng)且僅當(dāng)P和Q同時為真. 聯(lián)結(jié)詞“”的定義真值表,25,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),說明：“” 屬于二元(binary)運(yùn)算符. 合取運(yùn)算

13、特點(diǎn)：只有參與運(yùn)算的二命題全為真時，運(yùn)算 結(jié)果才為真，否則為假。 自然語言中的表示“并且”意思的聯(lián)結(jié)詞，如“既 又”、“不但而且”、“雖然但是”、“一面一面”、 “和”、 “與”等都可以符號化為 。,26,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),例3. 將下列命題符號化. (1) 李平既聰明又用功. (2) 李平雖然聰明, 但不用功. (3)李平不但聰明,而且用功. (4)李平不是不聰明,而是不用功. 解: 設(shè) P:李平聰明. Q:李平用功. 則 (1) PQ (2) P Q (3) PQ (4) (P) Q 注意

14、：不要見到“與”或“和”就使用聯(lián)結(jié)詞 ！ 例如: (1)見課本P11 例題6 (2) 李敏和李華是姐妹。 （3）李敏和張華是朋友。,27,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),例4. 試生成下列命題的合取. (1) P: 我們在XNA303. Q: 今天是星期二. (2) S：李平在吃飯. R：張明在吃飯. 解: (1) PQ :我們在XNA303且今天是星期二. (2) SR:李平與張明在吃飯.,28,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connecti

15、ves),1.2.3 析取聯(lián)結(jié)詞(Disjunction) 定義1.2.3 設(shè)P,Q為二命題，復(fù)合命題“P或Q” 稱為P與Q的析取式，記作PQ ，符號稱為析取聯(lián)結(jié)詞. PQ為真當(dāng)且僅當(dāng) P與Q中至少有一個為真. 聯(lián)結(jié)詞“”的定義真值表,29,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),說明：“” 屬于二元(binary)運(yùn)算符. 析取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為假時，運(yùn)算結(jié)果才為假，否則為真。 由析取聯(lián)結(jié)詞的定義可以看出， “”與漢語中的聯(lián)結(jié)詞“或”意義相近，但又不完全相同。在現(xiàn)代漢語中，聯(lián)結(jié)詞的“或”實(shí)際上有“

16、可兼或”和“排斥或”之分?？疾煜旅婷}： （1）小王愛打球或愛跑步。（可兼或） 設(shè)P：小王愛打球。 Q：小王愛跑步。 則上述命題可符號化為：P Q,30,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),（2）林芳學(xué)過英語或法語。 （可兼或） 設(shè)P：林芳學(xué)過英語。 Q：林芳學(xué)過法語。 則上述命題可符號化為： P Q （3）派小王或小李中的一人去開會。（排斥或） 設(shè)P：派小王去開會。Q：派小李去開會。 則上述命題可符號化為：(P Q) ( PQ) （4）人固有一死，或重于泰山或輕于鴻毛.(排斥或） （5）ab=0, 即a=0

17、或 b=0. （可兼或） 由此可見, “P Q”表示的是“可兼或”.,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),注意：當(dāng)P和Q客觀上不能同時發(fā)生時，“P或Q”可以符號化為“P Q”。 例如：小王現(xiàn)在在宿舍或在圖書館。 設(shè) P：小王現(xiàn)在在宿舍。Q：小王現(xiàn)在在圖書館。 則上述命題可符號化為：P Q。,32,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),1.2.4. 條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞Conditional) 定義1.2.4 設(shè)P,Q為二命題，復(fù)

18、合命題“如果P則Q(若P則Q)” 稱為P與Q的條件命題,記作P Q. P Q為假當(dāng)且僅當(dāng)P為真且Q為假.稱符號“”為條件聯(lián)結(jié)詞。并稱P為前件，Q為后件. 聯(lián)結(jié)詞“”的定義真值表,33,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),注：（1）P Q表示的基本邏輯關(guān)系是,Q是P的必要條件或P是Q的充分條件. 因此復(fù)合命題“只要P就Q”、“因?yàn)镻，所以Q”、“P僅當(dāng)Q”、“只有Q才P”等都可以符號化為P Q 的形式。 （2） ”“ 屬于二元(binary)運(yùn)算符。 例5. 將下列命題符號化。 （1）天不下雨，則草木枯黃。 P：

19、天下雨。 Q：草木枯黃。 則原命題可表示為： PQ。,34,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),（2）如果小明學(xué)日語，小華學(xué)英語，則小芳學(xué)德語。 P：小明學(xué)日語 Q：小華學(xué)英語 R：小芳學(xué)德語. 則原命題可表示為：(PQ)R （3）只要不下雨，我就騎自行車上班。 P：天下雨。Q：我騎自行車上班。 則原命題可表示為： PQ。 （4）只有不下雨，我才騎自行車上班。 P：天下雨。Q：我騎自行車上班。 則原命題可表示為： Q P 。,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logi

20、cal Connectives),（5）如果 2+2=4, 則太陽從東方升起。 (P Q, T) P Q 如果 2+2=4, 則太陽從西方升起。 (P R, F) R 如果 2+2 4, 則太陽從東方升起。 (P Q , T) 如果 2+2 4, 則太陽從西方升起。 (P R, T) 注意: (1)與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！ (2) 在數(shù)學(xué)中，“若P則Q”往往表示前件P為真，則后件Q為真的 推理關(guān)系. 但數(shù)理邏輯中，當(dāng)前件P為假時， P Q的真值為真。,36,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectiv

21、es),1.2.5 雙條件聯(lián)結(jié)(等值聯(lián)結(jié)詞Biconditional) 定義1.2.5 設(shè)P,Q為二命題，復(fù)合命題“P當(dāng)且僅當(dāng)Q” 稱為P與Q的雙條件命題，記作P iff Q或 PQ，符號稱為雙條件（等值）聯(lián)結(jié)詞。 PQ為真當(dāng)且僅當(dāng)P，Q真值相同。 聯(lián)結(jié)詞“”的定義真值表,37,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),注：（1）P僅當(dāng)Q 可譯為PQ P當(dāng)Q 可譯為QP P當(dāng)且僅當(dāng)Q 譯為PQ （2）“”屬于二元(binary)運(yùn)算符。 (3) 雙條件命題PQ所表達(dá)的邏輯關(guān)系是, P與Q互為充分必要條件,相當(dāng)于(P

22、Q) (Q P). 只要P與Q的真值同為1或同為0, PQ的真值就為1, 否則PQ的真值為0. 雙條件聯(lián)結(jié)詞連接的兩個命題之間可以沒有因果關(guān)系。 例6.分析下列命題的真值. (1) 2+2=4 當(dāng)且僅當(dāng)3是奇數(shù) . (PQ) P： 2+2=4. Q：3是奇數(shù) .,38,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),(2) 2+2=4 當(dāng)且僅當(dāng)3不是奇數(shù) . (PQ) (3) 2+2 4 當(dāng)且僅當(dāng)3是奇數(shù) . (PQ) (4) 2+2 4 當(dāng)且僅當(dāng)3不是奇數(shù) . (PQ) 約 定:1. 運(yùn)算次序優(yōu)先級：，. 2. 相同的運(yùn)

23、算符按從左至右次序計(jì)算，否則要 加上括號。 3.最外層圓括號可省去。 小結(jié): 本節(jié)介紹了五種聯(lián)結(jié)詞(，),重點(diǎn)是理解和掌握五種聯(lián)結(jié)詞的內(nèi)涵及它們與自然語言中相應(yīng)聯(lián)結(jié)詞的不同之處.,39,第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives),作業(yè): 1. P8 (3), (5). 2. 預(yù)習(xí)1.3, 1.4 思考題: 1. 何謂合式公式? 2. 復(fù)合命題符號化的基本步驟是什么? 3.何謂真值表? 4. 兩個命題公式等價的涵義是什么? 5.兩個等價的命題公式其真值表有何關(guān)系?,40,離散數(shù)學(xué)(Discrete Mathematics

24、),41,第一章 命題邏輯（Propositional Logic）1.3命題公式與翻譯,1.3.1 命題公式 1.3.2 復(fù)合命題的符號化(翻譯) 1.3.1 命題合式公式(Well-formed formula)(wff) 定義1.3.1:單個命題變元和命題常量稱為原子公式。 命題合式公式是由命題變元、命題常量、聯(lián)結(jié)詞和圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串。我們以如下遞歸的形式來定義合式公式：,42,第一章 命題邏輯（Propositional Logic）1.3命題公式與翻譯,定義1.3.2：(1)原子公式是合式公式(wff)。 （2）若A是合式公式，則( A)也是合式公式。 （3）若

25、A，B是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式。 （4）當(dāng)且僅當(dāng)有限次地應(yīng)用(1)(3)所得到的包含原子公式、聯(lián)結(jié)詞和括號的符號串是合式公式。 注: (1)合式公式也稱為命題公式，并簡稱為公式。 (2)命題公式一般不是命題,僅當(dāng)公式中的命題變元用確定的命題代入時,才得到一個命題.其真值依賴于代換變元的那些命題的真值.,43,第一章 命題邏輯（Propositional Logic）1.3命題公式與翻譯,例1：指出(P(PQ)是否是命題公式(wff)，如果是，則具體說明。 解： P是wff 由(1) Q是wff 由(1) PQ是wff 由(3) (P(PQ) 由(3) 例

26、2: (P Q) , (R S) Q , P，( P)等均為合式公式，而PQ S , (P W) Q)等不是合式公式。,44,第一章 命題邏輯（Propositional Logic）1.3命題公式與翻譯,1.3.2 復(fù)合命題的符號化(翻譯) 有了命題演算的合式公式的概念,我們可以把自然語言中的有些語句(復(fù)合命題),翻譯成數(shù)理邏輯中的符號形式.基本步驟如下: (1) 分析出各簡單命題,將它們符號化; (2) 使用合適的聯(lián)結(jié)詞,把簡單命題逐個的聯(lián)結(jié)起來,組成復(fù)合命題的符號化表示.,45,第一章 命題邏輯（Propositional Logic）1.3命題公式與翻譯,例3： 1) 我今天進(jìn)城，除非

27、下雨。1-3.(7) 2) 僅當(dāng)你走我將留下。 3) 假如上午不下雨，我去看電影，否則就在家里 讀書或看報(bào)。 4)除非你努力，否則你將失敗。P11例5 5)一個人起初說：“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)”；后來他改說，“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的?！眴査昂笾鲝埖牟町愒谑裁吹胤剑囈悦}形式進(jìn)行分析。 1-3.(6),46,第一章 命題邏輯（Propositional Logic）1.3命題公式與翻譯,例4：P10 例題1 小結(jié)：本節(jié)介了命題公式的概念及復(fù)合命題的符號化.重點(diǎn)是理解命題公式的遞歸定義,掌握復(fù)合命題的符號化方法. 作業(yè): P12 (1),(5),4

28、7,離散數(shù)學(xué)(Discrete Mathematics),48,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,1.4.1 真值表(Truth Table) 1.4.2 等價公式(Propositional Equivalences) 1.4.1 真值表 前面在定義聯(lián)結(jié)詞時,曾經(jīng)使用過真值表,下面給出 真值表的定義. 定義1.4.1 (對公式的賦值或解釋)設(shè)P1 , P2 ,Pn是出 現(xiàn)在公式A中的全部的命題變元, 給P1 , P2 ,Pn各指 定一個真值，稱為對A的一個賦值或解釋。若指定的 一組值使A的真值為真(假), 稱這組值為A的成真(假)賦值.,49

29、,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,比如:對公式(PQ)R,賦值011(即令P=0,Q=1,R=1) 為(PQ)R的成真賦值; 另一組賦值010為(PQ)R的成假賦值；還有000，001，111 考慮：含有n個命題變元的公式共有多少組不同的賦值？ 定義1.4.2(真值表)在命題公式A中, 對于命題變元的每一組賦值和由它們所確定的命題公式A的真值列成表，稱做命題公式A 的真值表。,50,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,對公式A構(gòu)造真值表的具體步驟為： （1）找出公式中所有命題變元P1 , P2

30、,Pn , 列出全部的2n組賦值。 （2）按從小到大的順序列出對命題變元P1 , P2 ,Pn ,的全部2n組賦值。 （3）對應(yīng)各組賦值計(jì)算出公式A的真值，并將其列在對應(yīng)賦值的后面。,51,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,例1. 給出(PQ)(PQ)的真值表：,52,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,例1. 給出(PQ)(PQ)的真值表：,53,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,例2：構(gòu)造公式 (P Q) R的 真值表。,54,第一章 命題邏輯

31、（Propositional Logic） 1.4真值表與等價公式,例2：構(gòu)造公式 (P Q) R的 真值表。,55,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,練習(xí)1：構(gòu)造公式 (PQ)( Q P真值表。,56,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,練習(xí)1：構(gòu)造公式 (PQ)( Q P真值表。,57,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,練習(xí)2：構(gòu)造公式 (P Q Q 真值表。,58,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價

32、公式,練習(xí)2：構(gòu)造公式 (P Q Q 真值表。,59,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,1.4.2 等價公式 給定n個 命題變元, 按合式公式的形成規(guī)則可以形成無數(shù)多個命題公式, 但這些無窮盡的命題公式中，有些具有相同的真值表?？紤]：由n個命題變元能生成? 種真值(表)不同的命題公式？,60,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,1.4.2 等價公式 定義1.4.3: 給定兩個命題公式A和B,設(shè)P1 , P2 ,Pn為出現(xiàn)于A和B中的所有原子變元,若給P1 , P2 ,Pn任一組真值指派, A和B的

33、真值都相同,則稱A和B是等價的或邏輯相等.記作A B 注: (1) “ ”不是邏輯聯(lián)結(jié)詞. (2)命題公式之間的邏輯相等關(guān)系具有： 自反性：A A ；對稱性：若A B，則B A； 傳遞性：若A B且B C，則A C。,61,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,證明公式等價的方法： 1. 真值表法 2. 等值演算法 1. 真值表法 例1. (PQ) (PQ) 見真值表例題1. 例2. 證明: PQ (PQ)(QP),62,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,證明公式等價的方法： 1. 真值表法 2.

34、等值演算法 1. 真值表法 例1. (PQ) (PQ) 見真值表例題1. 例2. 證明: PQ (PQ)(QP),63,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,例3：判斷公式 P(QR)、(PQ)R是否等價。,64,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,由真值表可知，兩個公式為等價式。 2、等值演算法(Equivalent Caculation)（利用P15表1-4.8) 重要的等價式(補(bǔ)充): 11. 蘊(yùn)涵等值式: PQ PQ 12. 等價等值式: PQ (PQ)(QP) 13. 假言易位: PQ Q

35、P 14. 等價否定等值式: PQ PQ 15. 歸謬論: (PQ ) ( P Q) P,65,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,其中P, Q, R等代表任意命題公式. 這樣上面的每一個公式都是一個模式, 它可以代表無數(shù)多個同類型的命題公式. 例如, PPT 中, 用(PQ)置換P,則得 (PQ)(PQ)T ,用P置換P,則得 (P)(P)T 。 等值演算中使用的一條重要規(guī)則：置換規(guī)則。 定義1.4.4(子公式)：如果X是wff A的一部分,且X本身也是wff，則稱X是A的子公式。例如, P(PQ)為Q (P(PQ)的子公式。,66,第一章 命

36、題邏輯（Propositional Logic） 1.4真值表與等價公式,定理1.4.1(置換定理Axiom of replacement)設(shè)X是wff A的子wff，若XY，則若將A中的X用Y來置換，所得公式B與A等價，即AB。 證：因?yàn)閷ψ冊娜我恢概?X與Y真值相同，所以Y 取代X后，公式B與公式A對變元的任一指派真值也相同,所以AB。 注: 滿足定理1.4.1的條件的置換稱為等價置換(或等價代換). 定義1.4.5(等值演算)：根據(jù)已知的等價公式,推演出另外一些等價公式的過程稱為等值演算.,67,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,例1：

37、 證明 Q（P（PQ）QP 證: Q（P（PQ）QP P(吸收律) 例2： 證明 PQQ PQ 證： (PQ)Q(PQ)(QQ)(PQ)TPQ 例3：證明（PQ）（QP） PQR 證：（PQ）（QP） （PQ）（QR） （PQ）（QR） （PQ）（QR） （PQR）（QQR） PQR,68,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,例4：驗(yàn)證P(QR) (P Q) R 證: 右 (P Q) R P Q R P ( Q R) P (Q R) P (Q R) 練：1.(P Q) (P R) P (Q R) 2.(P Q) ( P Q) (P Q) (P Q

38、),69,第一章 命題邏輯（Propositional Logic） 1.4真值表與等價公式,等值演算在計(jì)算機(jī)硬件設(shè)計(jì)中,在開關(guān)理論和電子元器件中都占有重要地位. 小結(jié): 本節(jié)介紹了真值表、公式等價、等值演算和等價置換等概念，給出了常用的重要等價公式（24個）。重點(diǎn)掌握用真值表法驗(yàn)證公式的等價性和等值演算法推演兩個公式等價。 作業(yè)：P17 1 c,e, 4 a,c, 7d,e, 8. 預(yù)習(xí): 1.5, 1.6 思考題：9,70,離散數(shù)學(xué)(Discrete Mathematics),張捷,71,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology

39、and Implication),1.5.1 命題公式的分類 1.5.2 重言式(Tautology)與矛盾式 (contradictory)的性質(zhì) 1.5.3 蘊(yùn)含式( Implication),72,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),1.5.1 命題公式的分類 復(fù)合命題 (compound propositions) 定義1.5.1 設(shè)A為任一命題公式， （1）若A在其各種賦值下的取值均為真，則稱A是重言式或永真式, 記為T或1。 （2）若A在其各種賦值下的取值均為假，則稱A是矛盾式或永假

40、式, 記為F或0。 （3）若A不是矛盾式則稱A為可滿足式(satisfiable)。注: 由定義可知,重言式一定是可滿足式,反之不真.,73,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),判別命題公式的類型有兩種方法: 真值表法和等值 演算法. 等值演算法是將所給命題公式通過等值演算化為最 簡單的形式, 然后再進(jìn)行判別. 例1.判別下列命題公式的類型. (1). Q(PQ)P) (重言式) (2). (PP) (QQ)R (矛盾式) (3). (P Q)P. (可滿足式),74,第一章 命題邏輯（Prop

41、ositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),1.5.2 重言式(Tautology)與矛盾式(contradictory)的性質(zhì)定理1.5.1:任何兩個重言式的合取或析取,仍然是一重言式.（由冪等律立得） 證明:設(shè)A和B為兩個重言式,則不論A和B的分量指派任何真值,總有A為T,B為T,故A B T,A B T 定理1.5.2:一個重言式(矛盾式),對同一分量都用任何合式公式置換,其結(jié)果仍為一重言式(矛盾式). 證明: 由于重言式(矛盾式)的真值與對變元的賦值無關(guān)，故對同一變元以任何合式公式置換后，重言式(矛盾式)的真值仍永為T（

42、F）。,75,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),定理1.5.3： A,B是兩個命題公式，A B的充要條件是A B為重言式。 證明: 若AB為重言式，則AB永為T，即A，B的真 值表相同，所以AB。 反之，若A B，則A，B真值表相同， 所以 AB永為T，所以AB為重言式。 1.5.3 蘊(yùn)含式( Implication) 定義1.5.2：當(dāng)且僅當(dāng)P Q是一個重言式時，我們稱“P蘊(yùn)含Q”，并記作P Q.,76,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tau

43、tology and Implication),它們之間具有如下關(guān)系: PQ Q P 由P21 表1-5.1 QP P Q 可以得出 因此, 要證明P Q有三種方法: 1)真值表法:即列出PQ的真值表,觀察其是否為永真。 2)直接證法:假定前件P是真，推出后件Q是真。 3)間接證法:假定后件是假，推出前件是假,即證 Q P 。,77,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),例: 證明Q（PQ）P 1) 法1：真值表 2) 法2：若 Q(PQ)為真，則 Q，PQ為真， 所以Q為假，P為假，所以P為真。

44、 3) 法3：若P為假，則P為真，再分二種情況： 若Q為真，則Q為假,從而Q（PQ） 為假. 若Q為假，則PQ為假，則Q（PQ）為假. 根據(jù) ，所以 Q（PQ）P P21 表1-5.2給出了14個蘊(yùn)含式, 它們都可以用上述方法加以推證.,78,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),等價式與蘊(yùn)含式的關(guān)系: 定理1.5.4: 設(shè)P,Q為任意兩個命題公式,PQ的充要條件為PQ且QP. 證：若PQ，則PQ為永真式 因?yàn)?PQ （PQ）（QP） 所以 PQ，QP為永真式,從而 PQ，QP. 反之，若PQ，Q

45、P，則PQ，QP為永真式, 所以（PQ）（QP）為永真式， 從而 PQ為永真式，即PQ.,79,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),蘊(yùn)含的性質(zhì): 設(shè)A，B，C為任意wff, 1) 若AB，且A為永真式，則B必為永真式. 2) 若AB，BC，則AC. 3) 若AB，AC，則ABC. 4) 若AB且CB，則ACB. 證：1)因?yàn)锳B，A永為T,所以B必永為T. 2)由I11 （AB)(BC）AC,所以若AB， BC，則（AB)(BC）永為T,從而AC永 為T, 故AC.,80,第一章 命題邏輯（Pr

46、opositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),3) （AB）（AC） （AB）（AC） A（BC） ABC 4) （AB）（CB） （AB）（CB） （AC）B （AC）B ACB,81,第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication),小結(jié)：本節(jié)介紹了命題公式的分類，重言式、矛盾式與蘊(yùn)含式的概念及其性質(zhì)，等價式與蘊(yùn)涵式的關(guān)系。 重點(diǎn)掌握: （1）用等值演算法判別命題公式的類型。 （2）重言式、矛盾式與蘊(yùn)涵式的性質(zhì)。 （3）等價式與蘊(yùn)涵式的關(guān)

47、系。 作業(yè): P23 (1)c,d ,(2) a ,(9). 預(yù)習(xí):1.6 思考題:1) 為什么要引入聯(lián)結(jié)詞 ? 2) 什么是最小聯(lián)結(jié)詞組?,82,離散數(shù)學(xué)(Discrete Mathematics),張捷,83,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),1.6.1 不可兼析取(排斥或/異或)(exclusive or) 1.6.2 與非聯(lián)結(jié)詞(Nand) 1.6.3 或非聯(lián)結(jié)詞(Nor) 1.6.4 條件否定聯(lián)結(jié)詞(Non-conditional) 1.6.5 最小聯(lián)結(jié)詞組(The minimal set of con

48、nectives),84,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),在第二節(jié)(1.2)中我們定義了五種基本的聯(lián)結(jié)詞， ， ，,但在命題邏輯中,這些聯(lián)結(jié)詞還不能很廣泛 地直接表達(dá)命題之間的聯(lián)系(例如, “P異或Q”只能間接地 表示為(PQ)(PQ),為此本節(jié)再給出邏輯設(shè)計(jì)中 常用的另外四種聯(lián)結(jié)詞. 1.6.1 不可兼析取(排斥或/異或)(exclusive or) 定義1.6.1:設(shè)P,Q為二命題，復(fù)合命題“P, Q之中恰有一個為真” 稱為P與Q的不可兼析取，記作P Q，符號“ ” 稱為異或聯(lián)結(jié)詞. P Q 為真當(dāng)且僅當(dāng)P

49、和Q的真值不同.,85,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),聯(lián)結(jié)詞“ ”的定義真值表,定義了聯(lián)結(jié)詞“ ”后, 命題邏輯中的有些命題就可以符號化為非常簡捷的形式. 例: 派小王或小李中的一人去開會。（排斥或） 設(shè)P：派小王去開會。Q：派小李去開會。 則上述命題可符號化為：(P Q),86,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),說明：“ ” 屬于二元(binary)運(yùn)算符. 聯(lián)結(jié)詞“ ”的性質(zhì): 設(shè)P, Q, R為命題公式, 則有 (1) P

50、 Q Q P (交換律) (2) (P Q) R P (Q R) (結(jié)合律) (3) P(Q R) (PQ ) (PR) (分配律) (4) (P Q) (P Q) ( PQ) (5) (P Q) (PQ) (6) P P F, F P P, T P P,87,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),定理1.6.1:設(shè)P, Q, R為命題公式, 如果 P QR,則 P RQ ,Q RP, 且P Q R 為一矛盾式. 證: 由 P QR 得 P RP (P Q)(P P) QF QQ Q RQ (P Q)F PP P Q

51、 RR RF,88,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),1.6.2 與非聯(lián)結(jié)詞(Nand) 定義1.6.2 設(shè)P,Q為二命題，復(fù)合命題“P與Q的否定” 稱為P與Q的與非式，記作PQ，符號“” 稱為與非聯(lián)結(jié)詞. PQ 為真當(dāng)且僅當(dāng)P和Q不同時為真. 聯(lián)結(jié)詞“”的定義真值表,89,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),說明: (1) 由定義可知, PQ (PQ) (2)“” 屬于二元(binary)運(yùn)算符. 聯(lián)結(jié)詞“”的性質(zhì): (1) PP

52、( PP) P (2) (PQ)(PQ) ( PQ)(PQ) (3)(PP)(QQ) P Q(PQ) PQ,90,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),1.6.3 或非聯(lián)結(jié)詞(Nor) 定義1.6.3 設(shè)P,Q為二命題，復(fù)合命題“P或Q的否定” 稱為P與Q的或非式，記作PQ ，符號“”稱為或非聯(lián)結(jié)詞. PQ為真當(dāng)且僅當(dāng) P與Q同為假. 聯(lián)結(jié)詞“”的定義真值表,91,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),說明: (1) 由定義可知, PQ (

53、PQ) (2)“” 屬于二元(binary)運(yùn)算符. 聯(lián)結(jié)詞“”的性質(zhì): (1) PP ( PP) P (2) (PQ)(PQ) (PQ) (PQ) (3)(PP)(QQ)PQ(PQ)PQ,92,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),1.6.4 條件否定聯(lián)結(jié)詞(Non-conditional) 定義1.6.4 設(shè)P,Q為二命題，復(fù)合命題“P Q” 稱為命題P與Q的條件否定式, P Q為真當(dāng)且僅當(dāng)P為真且Q為假. 聯(lián)結(jié)詞“ ”的定義真值表,93,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)

54、詞(Other Connectives),說明: (1) 由定義可知, P Q (P Q) (2)“ ” 屬于二元(binary)運(yùn)算符. 有了聯(lián)結(jié)詞 后，合式公式的定義1.3.2可加入這 四個聯(lián)結(jié)詞. 1.6.5 最小聯(lián)結(jié)詞組(The minimal set of connectives) 至此,我們一共定義了9個聯(lián)結(jié)詞,為了直接表達(dá)命題之間 的聯(lián)系,是否還需要定義其它聯(lián)結(jié)詞呢? 回答是否定的.即 含n個命題變元的所有 個互不等價的命題公式,均可由這 9個聯(lián)結(jié)詞直接表達(dá).下面我們以含兩個命題變元P，Q的所 有互等價的命題公式為例，來說明這一問題。,94,第一章 命題邏輯（Propositio

55、nal Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),由兩個命題變元P，Q所構(gòu)成的互不等價的 個命題公式 如下:,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),由上表可知, 9個聯(lián)結(jié)詞足以直接表達(dá)命題之間的各種聯(lián)系.二元運(yùn)算中，9個聯(lián)結(jié)詞并不都是必要的。,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),定義1.6.5：在一個聯(lián)結(jié)詞的集合中,如果一個聯(lián)結(jié)詞可 由該集合中的其它聯(lián)結(jié)詞定義,則稱此聯(lián)結(jié)詞為冗余聯(lián) 結(jié)詞,否則稱為獨(dú)立聯(lián)結(jié)詞.

56、不含冗余聯(lián)結(jié)詞的聯(lián)結(jié)詞組 稱為最小聯(lián)結(jié)詞組. 說明:最小聯(lián)結(jié)詞組中的聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價的表達(dá)出來。 對于9個聯(lián)結(jié)詞的集合, , , , 由于 (1) PQ (PQ)(QP) (2) PQPQ (3) PQ(PQ) (4) PQ(PQ),97,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),(5) (P Q) (PQ) (6) PQ (PQ) (7) PQ (PQ) (8) P Q (P Q) 故任意命題公式都可由僅包含,或, 的命題 公式等價代換.即9個聯(lián)結(jié)詞的集合中至少有七個冗余聯(lián) 結(jié)詞. 又注意到聯(lián)結(jié)詞

57、,和, 不再有冗余聯(lián)結(jié) 詞, 故,或, 為最小聯(lián)結(jié)詞組.但實(shí)際中為了使 用方便, 命題公式常常同時包含, .,98,第一章 命題邏輯（Propositional Logic） 1.6其它聯(lián)結(jié)詞(Other Connectives),例1:試證是最小聯(lián)結(jié)詞組. 證：P(PP)PP PQ(PQ)(PQ)(PQ)(PQ) PQ(PQ)(PP)(QQ) (PP)(QQ) 例2.試證，是最小聯(lián)結(jié)詞組 證：PQ(PQ)(PQ) PQ(P)QPQ 小結(jié):本節(jié)主要介紹了四種新的聯(lián)結(jié)詞 及最 小聯(lián)結(jié)詞組. 作業(yè): 1. P29 (1), (2), (4),99,第一章 命題邏輯（Propositional Lo

58、gic） 1.6其它聯(lián)結(jié)詞(Other Connectives),2. 預(yù)習(xí)1.7 思考題: 1. 何謂命題公式的(主)析(合)取范式? 2.命題公式的(主)析(合)取范式唯一嗎? 3.為何要將命題公式化為與之等價的主析(合)取范式? 4. 如何將命題公式化為與之等價的主析(合)取范式? 5.兩個等價的命題公式其(主)析(合)取范式有何關(guān)系?,100,離散數(shù)學(xué)(Discrete Mathematics),張捷,101,第一章 命題邏輯（Propositional Logic） 1.7對偶與范式(Dual (2)一個合取范式是重言式,當(dāng)且僅當(dāng)它的每一個簡單析取式都是重言式. 定理1.7.4 (范式存在定理) 任一個命題公式都存在著與之等價的析取范式與合取范式。,112,第一章 命題邏輯（Propositional Logic） 1.7對偶與范式(Dual (2) 除去 中所有永假的析取項(xiàng);,122,第一章 命題邏輯（Pr