離散數(shù)學(xué)及其應(yīng)用第1章-命題邏輯課件

1、第一部分 數(shù)理邏輯（Mathematical Logic)形式邏輯是研究思維的形式結(jié)構(gòu)和規(guī)律的科學(xué)，它撇開具體的、個(gè)別的思維內(nèi)容，從形式結(jié)構(gòu)方面研究概念、判斷和推理及其正確聯(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é)科。上個(gè)世紀(jì)30年代以后，數(shù)理邏輯進(jìn)入一個(gè)嶄新的發(fā)展階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密切關(guān)聯(lián)。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一部分 數(shù)理邏輯（Mathematical Logic)1931年Godel

2、不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了1936年Turing機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)算機(jī)問世。從廣義上講，數(shù)理邏輯包括四論、兩演算即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本書課程只研究這兩個(gè)演算。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一部分 數(shù)理邏輯（Mathematical Logic)數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時(shí)態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional L

3、ogic） 1.1 命題及其表示方法(Proposition and Its Expression)1.2 邏輯聯(lián)結(jié)詞(Logical Connectives)1.3 命題公式與翻譯(Propositional Formula & Its Translation)1.4 真值表與等價(jià)公式(Truth Tables and Prepositional Equivalences)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）1.5 重言式與蘊(yùn)含式(Tautology and Implication )1.6 其它聯(lián)結(jié)詞(Other Connect

4、ives)1.7 對(duì)偶與范式(Dual & Normal Form)1.8 推理理論(Inference Theory )2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法1.1.1 命題1.1.2 命題的表示方法1.1.3 命題的分類2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法 1.1.1 命題（Proposition) 數(shù)理邏輯研究的中心問題是推理（inference),而推理的前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)判斷的陳述句構(gòu)成了推理的

5、基本單位。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法 基本概念 命題：能夠判斷真假的陳述句。 命題的真值：命題的判斷結(jié)果。命題的真值只取兩個(gè)值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 真命題：判斷為正確的命題，即真值為真的命題。 假命題：判斷為錯(cuò)誤的命題，即真值為假的命題。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院因而又可以稱命題是具有唯一真值的陳述句。判斷命題的兩個(gè)步驟： 1、是否為陳述句； 2、是否有確定的、唯一的真值。 例：判斷下列句子是否為命題。 (1). 100是自然數(shù)。 T

6、 (2). 太陽(yáng)從西方升起。 F 第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法(3). 3+3=8 . F(4). How do you do ? 疑問句，不是命題(5). 明年的十月一日是晴天。是命題，其真值到明年十月一日方可知道。(6). x+39 不是命題(7). 我正在說謊。是悖論2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法(8). 1+101=

7、110 二進(jìn)制中為真，十進(jìn)制中為假。(9). 如果太陽(yáng)從西方升起，那么2是奇數(shù)。T(10). 國(guó)足能殺入2006世界杯當(dāng)且僅當(dāng)2+2=4。F(11). 今天天氣多好啊！ 感嘆句，不是命題(12). 請(qǐng)你關(guān)上門！ 祁使句，不是命題， (13). 別的星球上有生物。 是命題，客觀上能判斷真假。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法說明：（1）只有具有確定真值的陳述句才是命題。 一切沒有判斷內(nèi)容的句子，無所謂 是非的句子，如感嘆句、祁使句、 疑問 句等都不是命題。（2） 因?yàn)槊}只有兩種真值，所以“命題 邏 輯”又

8、稱 “二值邏輯”。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法 (3) “具有確定真值”是指客觀上的具有，與我們 是否知道它的真值是兩回事。如上例中 的（5）和（13）。1.1.2 命題的表示方法 在本書中，用大寫英文字母A,B,P,Q或帶下標(biāo)的字母P1,P2,P3 , ,或數(shù)字(1),2, ,等表示命題，稱之為命題標(biāo)識(shí)符。 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法例如： P：羅納爾多是球星。 Q：5是負(fù)數(shù)。 P3：明天天氣晴。 (

9、2)：太陽(yáng)從西方升起。 皆為符號(hào)化的命題，其真值依次為1、0、1或0、0。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法 命題標(biāo)識(shí)符又有命題常量、命題變?cè)驮幼冊(cè)?。命題常量：表示確定命題的命題標(biāo)識(shí)符。命題變?cè)好}標(biāo)識(shí)符如僅是表示任意命題的位置標(biāo) 志，就稱為命題變?cè)?。原子變?cè)寒?dāng)命題變?cè)硎驹用}時(shí)，該變?cè)Q為 原子變?cè)?。命題變?cè)灿肁,B,P,Q,P1,P2,P3 , , 表示。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.1 命題及其表示方法1.1

10、.3 命題的分類：簡(jiǎn)單/原子命題：不能分解為更簡(jiǎn)單的陳述語(yǔ)句的命題(如上例中的命題)。復(fù)合命題：由簡(jiǎn)單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。聯(lián)結(jié)詞就是復(fù)合命題中的運(yùn)算符。 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法注意：（1）一個(gè)符號(hào)(如P), 它表示的是命題常量還是命題變?cè)?，一般由上下文來確定。（2）命題變?cè)梢员硎救我饷}，它不能確定真值，故命題變?cè)皇敲}。這與“變數(shù)x不是數(shù)”是一樣的道理。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）1.1 命題及其表示方法小結(jié)：

11、本節(jié)主要介紹了命題、命題的真值、原子命題、復(fù)合命題、命題標(biāo)識(shí)符、命題常量、命題變?cè)驮幼冊(cè)母拍睢?重點(diǎn)理解和掌握命題、命題變?cè)?、?jiǎn)單（原子）命題、復(fù)合命題四個(gè)概念。 作業(yè)：P2 1,22022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2 邏輯聯(lián)結(jié)詞(Logical Connectives) 1.2.1 否定聯(lián)結(jié)詞(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é)詞Biconditi

12、onal) 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 在命題邏輯中,主要研究的是復(fù)合命題,而復(fù)合命題是由原子命題與邏輯聯(lián)結(jié)詞組合而成,聯(lián)結(jié)詞組是復(fù)合命題的重要組成部分.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1.2.1 否定聯(lián)結(jié)詞 定義1.2.1 設(shè)P為一命題， P的否定是一個(gè)新的復(fù)合命題, 稱為P的否定式，記作 “P”讀作“非P”. 符號(hào)“ ” 稱為否定聯(lián)結(jié)詞。 P為真當(dāng)且僅當(dāng)P為假.說明： “”屬于一元(unary)運(yùn)算符.第一章 命題邏輯（Propositional Lo

13、gic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)“”的定義也可用下表來說明. 聯(lián)結(jié)詞“”的定義真值表 P P01102022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)例1. P: 天津是一個(gè)城市. Q: 3是偶數(shù).于是: P: 天津不是一個(gè)城市. Q: 3不是偶數(shù).例2. P:蘇州處處清潔. Q:這些都是男同學(xué).

14、 P:蘇州不處處清潔 (注意,不是處處不清潔). Q:這些不都是男同學(xué).2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（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的合取式，記作PQ，符號(hào)“” 稱為合取聯(lián)結(jié)詞. PQ為真當(dāng)且僅當(dāng)P和Q同時(shí)為真. 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)

15、 聯(lián)結(jié)詞“”的定義真值表PQ P Q 0000101001112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)說明：“” 屬于二元(binary)運(yùn)算符.合取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算結(jié)果才為真，否則為假。自然語(yǔ)言中的表示“并且”意思的聯(lián)結(jié)詞，如“既又”、“不但而且”、“雖然但是”、“一面一面”、 “和”、 “與”等都可以 符號(hào)化為 。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical

16、Connectives)例3. 將下列命題符號(hào)化. (1) 李平既聰明又用功. (2) 李平雖然聰明, 但不用功. (3) 李平不但聰明,而且用功. (4) 李平不是不聰明,而是不用功.解: 設(shè) P:李平聰明. Q:李平用功.則 (1) PQ (2) PQ (3) PQ (4) (P)Q 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)注意：不要見到“與”或“和”就使用聯(lián)結(jié)詞 ！例如: (1)李敏和李華是姐妹。 (2)李敏和張華是朋友。 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章

17、命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 例4. 試生成下列命題的合取. (1) P: 我們?cè)?-503. Q: 今天是星期二. (2) S：李平在吃飯. R：張明在吃飯. 解: (1) PQ :我們?cè)?-503且今天是星期二. (2) SR:李平與張明在吃飯. 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2

18、邏輯聯(lián)結(jié)詞(Logical Connectives)1.2.3 析取聯(lián)結(jié)詞(Disjunction)定義1.2.3 設(shè)P,Q為二命題，復(fù)合命題“P或Q” 稱為P與Q的析取式，記作PQ ，符號(hào)稱為析取聯(lián)結(jié)詞. PQ為真當(dāng)且僅當(dāng) P與Q中至少有一個(gè)為真. 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 聯(lián)結(jié)詞“”的定義真值表PQ PQ 0000111011112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logica

19、l Connectives)說明：“” 屬于二元(binary)運(yùn)算符.析取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為假時(shí)，運(yùn)算結(jié)果才為假，否則為真。 由析取聯(lián)結(jié)詞的定義可以看出， “”與漢語(yǔ)中的聯(lián)結(jié)詞“或”意義相近，但又不完全相同。在現(xiàn)代漢語(yǔ)中，聯(lián)結(jié)詞的“或”實(shí)際上有“可兼或”和“排斥或”之分。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)考察下面命題：（1）小王愛打球或愛跑步。（可兼或） 設(shè)P：小王愛打球。 Q：小王愛跑步。 則上述命題可符號(hào)化為：P Q（2）林芳學(xué)過英語(yǔ)或法語(yǔ)。 （可兼

20、或）設(shè)P：林芳學(xué)過英語(yǔ)。 Q：林芳學(xué)過法語(yǔ)。 則上述命題可符號(hào)化為： P Q2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)（3）派小王或小李中的一人去開會(huì)。（排斥或） 設(shè)P：派小王去開會(huì)。Q：派小李去開會(huì)。 則上述命題可符號(hào)化為：(PQ) (PQ)（4）人固有一死，或重于泰山或輕于鴻毛. (排斥或） （5）ab=0, 即a=0 或 b=0. （可兼或） 由此可見, “P Q”表示的是“可兼或”.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Lo

21、gic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)注意：當(dāng)P和Q客觀上不能同時(shí)發(fā)生時(shí)，“P或Q”可以符號(hào)化為“P Q”。例如：小王現(xiàn)在在宿舍或在圖書館。設(shè) P：小王現(xiàn)在在宿舍。Q：小王現(xiàn)在在圖書館。則上述命題可符號(hào)化為：PQ。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)1.2.4. 條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞Co

22、nditional)定義1.2.4 設(shè)P,Q為二命題，復(fù)合命題“如果P則Q(若P則Q)” 稱為P與Q的條件命題,記作P Q. PQ為假當(dāng)且僅當(dāng)P為真且Q為假.稱符號(hào)“”為條件聯(lián)結(jié)詞。并稱P為前件，Q為后件. 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 聯(lián)結(jié)詞“”的定義真值表PQP Q0010111001112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 注：（1）PQ表

23、示的基本邏輯關(guān)系是,Q是P的必要條件或P是Q的充分條件. 因此復(fù)合命題“只要P就Q”、“因?yàn)镻，所以Q”、“P僅當(dāng)Q”、“只有Q才P”等都可以符號(hào)化為 PQ 的形式。（2） “” 屬于二元(binary)運(yùn)算.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)例5. 將下列命題符號(hào)化。 （1）天不下雨，則草木枯黃。 P：天下雨。 Q：草木枯黃。則原命題可表示為： PQ。 （2）如果小明學(xué)日語(yǔ)，小華學(xué)英語(yǔ)，則小芳學(xué)德語(yǔ)。 P：小明學(xué)日語(yǔ). Q：小華學(xué)英語(yǔ). R：小芳學(xué)德語(yǔ).則原命題可表示為

24、：(PQ)R2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) （3）只要不下雨，我就騎自行車上班。 P：天下雨。Q：我騎自行車上班。 則原命題可表示為： PQ。 （4）只有不下雨，我才騎自行車上班。 P：天下雨。Q：我騎自行車上班。 則原命題可表示為： Q P 。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) （5）如果 2+2=4, 則太陽(yáng)從東方升起。 (PQ, T) P

25、Q 如果 2+2=4, 則太陽(yáng)從西方升起。 (PR, F) R 如果 2+24, 則太陽(yáng)從東方升起。 (PQ , T) 如果 2+2 4, 則太陽(yáng)從西方升起。 (PR, T)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 注意: (1)與自然語(yǔ)言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！ (2) 在數(shù)學(xué)中，“若P則Q”往往表示前件P為真，則后件Q為真的推理關(guān)系. 但數(shù)理邏輯中，當(dāng)前件P為假時(shí)， PQ的真值為真。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositi

26、onal Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)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，符號(hào)稱為雙條件（等值）聯(lián)結(jié)詞。 PQ為真當(dāng)且僅當(dāng)P，Q真值相同。 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives) 聯(lián)結(jié)詞“”的定義真值表PQP Q0010101001112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（P

27、ropositional 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)于(PQ)(QP). 只要P與Q的真值同為1或同為0, PQ的真值就為1, 否則PQ的真值為0. 雙條件聯(lián)結(jié)詞連接的兩個(gè)命題之間可以沒有因果關(guān)系。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)例6.

28、分析下列命題的真值. (1) 2+2=4 當(dāng)且僅當(dāng)3是奇數(shù) . (PQ) P： 2+2=4. Q：3是奇數(shù) . (2) 2+2=4 當(dāng)且僅當(dāng)3不是奇數(shù) . (PQ)(3) 2+24 當(dāng)且僅當(dāng)3是奇數(shù) . (PQ)(4) 2+24 當(dāng)且僅當(dāng)3不是奇數(shù) . (PQ)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)約 定:1. 運(yùn)算次序優(yōu)先級(jí)：，. 2. 相同的運(yùn)算符按從左至右次序計(jì)算，否則要加上括號(hào)。 3.最外層圓括號(hào)可省去。 小結(jié): 本節(jié)介紹了五種聯(lián)結(jié)詞(，),重點(diǎn)是理解和掌握五種聯(lián)結(jié)詞

29、的內(nèi)涵及它們與自然語(yǔ)言中相應(yīng)聯(lián)結(jié)詞的不同之處.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.2邏輯聯(lián)結(jié)詞(Logical Connectives)作業(yè): 1. P5 2 2. 預(yù)習(xí) 1.3, 1.4思考題: 1. 何謂合式公式? 2. 復(fù)合命題符號(hào)化的基本步驟是什么? 3.何謂真值表? 4. 兩個(gè)命題公式等價(jià)的涵義是什么? 5.兩個(gè)等價(jià)的命題公式其真值表有何關(guān)系?2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯1.3 命題公式與翻譯1.3.1 命題公式1.3.2 復(fù)

30、合命題的符號(hào)化(翻譯)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯(Propositional Formula & Its Translation)1.3.1 命題合式公式(Well-formed formula)(wff)定義1.3.1:單個(gè)命題變?cè)兔}常量稱為原子公式。命題合式公式是由命題變?cè)?、命題常量、聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號(hào)串。我們以如下遞歸的形式來定義合式公式：2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯定義1.

31、3.2：(1)原子公式是合式公式(wff)。 （2）若A是合式公式，則(A)也是合式公式。 （3）若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式。 （4）當(dāng)且僅當(dāng)有限次地應(yīng)用(1)(3)所得到的包含原子公式、聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯注: (1)合式公式也稱為命題公式，并簡(jiǎn)稱為公式。 (2)命題公式一般不是命題,僅當(dāng)公式中的命題變?cè)么_定的命題代入時(shí),才得到一個(gè)命題.其真值依賴于代換變?cè)哪切┟}的真值.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

32、第一章 命題邏輯（ProPositional Logic）1.3命題公式與翻譯例1：指出(P(PQ)是否是命題公式(wff)，如果是，則具體說明。解： P是wff 由(1) Q是wff 由(1) PQ是wff 由(2) (P(PQ) 由(2) 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic）1.3命題公式與翻譯例2: (P Q) , (R S) Q , P，(P)等均為合式公式，而PQ S , (P W) Q)等不是合式公式。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯

33、1.3.2 復(fù)合命題的符號(hào)化(翻譯)有了命題演算的合式公式的概念,我們可以把自然語(yǔ)言中的有些語(yǔ)句(復(fù)合命題),翻譯成數(shù)理邏輯中的符號(hào)形式.基本步驟如下:(1) 分析出各簡(jiǎn)單命題,將它們符號(hào)化;(2) 使用合適的聯(lián)結(jié)詞,把簡(jiǎn)單命題逐個(gè)的聯(lián)結(jié)起來,組成復(fù)合命題的符號(hào)化表示.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯例3：1) 我今天進(jìn)城，除非下雨。2) 僅當(dāng)你走我將留下。3) 假如上午不下雨，我去看電影，否則就在家里 讀書或看報(bào)。4)除非你努力，否則你將失敗。5)一個(gè)人起初說：“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)

34、”；后來他改說，“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的。”問他前后主張的差異在什么地方，試以命題形式進(jìn)行分析。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.3命題公式與翻譯例4：P6 例1.3.3 ，例1.3.4(5) ，例1.3.5小結(jié)：本節(jié)介了命題公式的概念及復(fù)合命題的符號(hào)化.重點(diǎn)是理解命題公式的遞歸定義,掌握復(fù)合命題的符號(hào)化方法.作業(yè): P7: 22022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式1.4.1 真值表(Truth Table)1.4.2

35、 等價(jià)公式(ProPositional Equivalences)1.4.1 真值表 前面在定義聯(lián)結(jié)詞時(shí),曾經(jīng)使用過真值表,下面給出真值表的定義.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式定義1.4.1 (對(duì)公式的賦值或解釋)設(shè)P1 , P2 ,Pn是出現(xiàn)在公式A中的全部的命題變?cè)? 給P1 , P2 ,Pn各指定一個(gè)真值，稱為對(duì)A的一個(gè)賦值或解釋。若指定的一組值使A的真值為真(假), 稱這組值為A的成真(假)賦值.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）

36、1.4真值表與等價(jià)公式例如:對(duì)公式(PQ)R，賦值011(即令P=0，Q=1， R=1) 為(PQ)R的成真賦值; 另一組賦值010為(PQ)R的成假賦值；還有000，001，1112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.4真值表與等價(jià)公式考慮：含有n個(gè)命題變?cè)墓焦灿卸嗌俳M不同的賦值？定義1.4.2(真值表)在命題公式A中, 對(duì)于命題變?cè)拿恳唤M賦值和由它們所確定的命題公式A的真值列成表，稱做命題公式A 的真值表。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與

37、等價(jià)公式對(duì)公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有命題變?cè)狿1 , P2 ,Pn , 列出全部的2n組賦值。（2）按從小到大的順序列出對(duì)命題變?cè)狿1 , P2 ,Pn ,的全部2n組賦值。（3）對(duì)應(yīng)各組賦值計(jì)算出公式A的真值，并將其列在對(duì)應(yīng)賦值的后面。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式例1. 給出(PQ)(PQ)的真值表：PQPQ(PQ)PQ(PQ)(PQ)000110112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.4真值表與等價(jià)公式例1

38、.給出(PQ)(PQ)的真值表：PQPQ(PQ)PQ(PQ)(PQ)0001110101111001111110012022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.4真值表與等價(jià)公式例2：構(gòu)造公式 (P Q) R的 真值表。PQRPQ(P Q) R0000010100111001011101112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式例2：構(gòu)造公式 (P Q) R的 真值表。PQRPQ(P Q) R000100011101010011111000010100

39、11010111112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式練習(xí)1：構(gòu)造公式 (PQ)(Q P)真值表。PQPQPQQP(PQ)(QP)000110112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.4真值表與等價(jià)公式練習(xí)1：構(gòu)造公式 (PQ)(Q P)真值表。PQPQPQQP(PQ)(QP)00111110110111100100111001112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表

40、與等價(jià)公式PQ (PQ)(PQ) (PQ)Q00011011練習(xí)2：構(gòu)造公式 (PQ)Q真值表。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式PQ (P Q)(PQ) (PQ)Q00100011001001011100練習(xí)2：構(gòu)造公式 (PQ)Q真值表。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式1.4.2 等價(jià)公式給定n個(gè) 命題變?cè)? 按合式公式的形成規(guī)則可以形成無數(shù)多個(gè)命題公式, 但這些無窮盡的命題公式中，有些具有相同的真值表?？紤]：由n

41、個(gè)命題變?cè)苌? 種真值(表)不同的命題公式？2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式定義1.4.3: 給定兩個(gè)命題公式A和B，設(shè)P1 ,P2 ,Pn為出現(xiàn)于A和B中的所有原子變?cè)?若給P1 , P2 ,Pn任一組真值指派, A和B的真值都相同,則稱A和B是等價(jià)的或邏輯相等.記作A B。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式注: (1) “ ”不是邏輯聯(lián)結(jié)詞.(2)命題公式之間的邏輯相等關(guān)系具有： 自反性：A A ； 對(duì)稱性：若

42、A B，則B A； 傳遞性：若A B且B C，則A C。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式證明公式等價(jià)的方法：1. 真值表法 2. 等值演算法1. 真值表法 例1.(PQ) (PQ) 見真值表例題1.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式例2. 證明: PQ (PQ)(QP)PQPQQPPQ(PQ)(QP)000110112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic）

43、1.4真值表與等價(jià)公式例2. 證明: PQ (PQ)(QP)PQPQQPPQ(PQ)(QP)0011110100101001001111112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式例3：判斷公式 P(QR)、(PQ)R是否等價(jià)。PQRPQQRP(QR)(PQ)R00001001010100001101100011010111010111112022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式PQRPQQRP(QR)(PQ)R000011100

44、10111010001101101111000111101011111010001111111例3：判斷公式 P(QR)、(PQ)R是否等價(jià)。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式 由真值表可知，兩個(gè)公式為等價(jià)式。2. 等值演算法(Equivalent Calculation) 等值演算中使用的一條重要規(guī)則：置換規(guī)則定義1.4.4(子公式)：如果X是wff A的一部分,且X本身也是wff，則稱X是A的子公式。例如, P(PQ)為Q (P(PQ)的子公式。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯

45、（ProPositional Logic） 1.4真值表與等價(jià)公式定理1.4.1(置換定理Axiom of rePlacement) 設(shè)X是wff A的子wff，若XY，則若將A中的X用Y來置換，所得公式B與A等價(jià)，即AB。證：因?yàn)閷?duì)變?cè)娜我恢概?X與Y真值相同，所以Y取代X后，公式B與公式A對(duì)變?cè)娜我恢概烧嬷狄蚕嗤?所以AB。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4真值表與等價(jià)公式注: 滿足定理1.4.1的條件的置換稱為等價(jià)置 換(或等價(jià)代換).定義1.4.5(等值演算)：根據(jù)已知的等價(jià)公式,推演出另外一些等價(jià)公式的過程稱

46、為等值演算.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式常用的等價(jià)式： 1.雙重否定律： P P 2.結(jié)合律：(PQ)RP(QR) (PQ)RP(QR) (PQ)RP(QR) 3.交換律: PQQP PQ QP PQ QP 4. 分配律: P(QR )(PQ)(PR) P(QR)(PQ)(PR)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式常用的等價(jià)式： 5.冪等律: PP P PP P 6.吸收律: P(PQ) P P(PQ) P 7.

47、德.摩根律: (PQ)PQ (PQ)PQ 8.同一律: PFP PTP 9.零律: PTT PFF2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式常用的等價(jià)式： 10.否定律： PPT PPF 11. 蘊(yùn)涵等值式: PQ PQ 12. 等價(jià)等值式: PQ(PQ)(QP) 13. 假言易位: PQQ P 14. 等價(jià)否定等值式: PQPQ 15. 歸謬論: (PQ )( PQ)P 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式其中P, Q, R

48、等代表任意命題公式. 這樣上面的每一個(gè)公式都是一個(gè)模式, 它可以代表無數(shù)多個(gè)同類型的命題公式. 例如, PPT 中, 用(PQ)置換P,則得 (PQ)(PQ)T ,用P置換P,則得 (P)(P)T 。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（ProPositional Logic） 1.4真值表與等價(jià)公式例1： 證明 Q(P(PQ)QP證: Q(P(PQ) QP P(吸收律)例2： 證明 PQQPQ證：(PQ)Q(PQ)(QQ)(PQ)T PQ2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式例3：證明(

49、PQ)(QR) PQR證：(PQ)(QR) (PQ)(QR) (PQ)(QR) (PQ)(QR) (PQR)(QQR) PQR 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式例4：驗(yàn)證P(QR) (PQ)R證: 右(PQ)R PQR P(QR) P(QR) P(QR)練：1.(PQ)(PR)P(QR) 2.(PQ)(PQ)(PQ)(PQ) 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式等值演算在計(jì)算機(jī)硬件設(shè)計(jì)中,在開關(guān)理論和電子元器件中都占

50、有重要地位.小結(jié): 本節(jié)介紹了真值表、公式等價(jià)、等值演算和等價(jià)置換等概念，給出了常用的重要等價(jià)公式（26個(gè)）。重點(diǎn)掌握用真值表法驗(yàn)證公式的等價(jià)性和等值演算法推演兩個(gè)公式等價(jià)。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.4 真值表與等價(jià)公式作業(yè)：Pg.13: 1 (2),(4)； 2 (2),(4)； 4 ；6（3）預(yù)習(xí): 1.5, 1.6思考題： Pg.13: 52022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)

51、1.5.1 命題公式的分類1.5.2 重言式(Tautology)與矛盾式 (contradictory)的性質(zhì)1.5.3 蘊(yùn)含式( ImPlication)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)1.5.1 命題公式的分類 復(fù)合命題2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)定義1.5.1 設(shè)A為任一命題公式，(1)若A在其各種賦值

52、下的取值均為真，則稱 A是重言式或永真式, 記為T或1。(2)若A在其各種賦值下的取值均為假，則稱 A是矛盾式或永假式, 記為F或0。(3)若A不是矛盾式則稱A為可滿足式(satisfiable)。注: 由定義可知,重言式一定是可滿足式,反之不真.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication) 判別命題公式的類型有兩種方法: 真值表法和等值演算法. 等值演算法是將所給命題公式通過等值演算化為最簡(jiǎn)單的形式, 然后再進(jìn)行判別.例1.判別下列命題公式的類型.(1). Q(P

53、Q)P) (重言式)(2). (PP)(QQ)R (矛盾式)(3). (PQ)P. (可滿足式)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)1.5.2 重言式(Tautology)與矛盾式(contradictory)的性質(zhì)定理1.5.1:任何兩個(gè)重言式的合取或析取,仍然是一重言式.（由冪等律立得）證明:設(shè)A和B為兩個(gè)重言式,則不論A和B的分量指派任何真值,總有A為T,B為T,故AB T，ABT。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propos

54、itional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)定理1.5.2:一個(gè)重言式(矛盾式),對(duì)同一分量都用任何合式公式置換,其結(jié)果仍為一重言式(矛盾式).證明：由于重言式(矛盾式)的真值與對(duì)變?cè)馁x值無關(guān)，故對(duì)同一變?cè)匀魏魏鲜焦街脫Q后，重言式(矛盾式)的真值仍永為T（F）。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)定理1.5.3：A,B是兩個(gè)命題公式，A B的充要條件是A B為重言式。 證明: 若AB為重言式，

55、則AB永為T，即A，B的真值表相同，所以AB。 反之，若A B，則A，B真值表相同， 所以 AB永為T，所以AB為重言式。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)它們之間具有如下關(guān)系: PQ Q P QP P Q原命題逆換式反換式逆反式PQQPP QQ P1.5.3 蘊(yùn)含式（ ImPlication）定義1.5.2：當(dāng)且僅當(dāng)P Q是一個(gè)重言式時(shí)，我們稱“P蘊(yùn)含Q”，并記作P Q.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional

56、 Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)因此, 要證明PQ有三種方法:1)真值表法: 即列出PQ的真值表,觀察其是 否永為真。2)等值演算法：通過證明PQ 1來證PQ3)分析法： 直接分析法: 假定前件P是真，推出后件Q是真。 間接分析法: 假定后件是假，推出前件是假,即證 QP 。2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)例: 證明Q(PQ)P1) 法1：真值表（略）2) 法2： Q(PQ) P (Q(PQ)(P

57、 ) Q(PQ)(P ) (PQ)(PQ) 1 即Q(PQ)P2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)3) 直接分析法：若 Q(PQ)為真，則 Q，PQ為真，所以Q為假，P為假，所以P為真。 間接分析法：若P為假，則P為真，再分二種情況： 若Q為真，則Q為假,從而Q(PQ) 為假. 若Q為假，則PQ為假，則Q(PQ)為假. 根據(jù) ，所以 Q(PQ)P2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與

58、蘊(yùn)含式(Tautology and Implication)下面常用的14個(gè)蘊(yùn)含式, 都可以用上述方法加以推證. 1. PQP 2. PQQ 3. PPQ 4. PPQ 5. QPQ 6. (PQ )P 7. (PQ )Q 8. P (PQ )Q 9. Q (PQ )P 10. P(PQ )Q11. (PQ )(QR)PR12. (PQ )(PR)(QR)R13. (PQ)(RS) (PR)(QS )14. (PQ)(QR) (PR)2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implic

59、ation)等價(jià)式與蘊(yùn)含式的關(guān)系:定理1.5.4: 設(shè)P,Q為任意兩個(gè)命題公式,PQ的充要條件為PQ且QP.證：若PQ，則PQ為永真式 因?yàn)?PQ （PQ）（QP） 所以 PQ，QP為永真式,從而 PQ，QP. 反之，若PQ，QP，則PQ，QP為永真式, 所以（PQ）（QP）為永真式， 從而 PQ為永真式，即PQ.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（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.

60、3) 若AB，AC，則ABC.4) 若AB且CB，則ACB.證：1)因?yàn)?AB，A永為T,所以 B必永為T. 2)由I11 （AB)(BC）AC,所以若AB， BC，則（AB)(BC）永為T,從而AC永 為T, 故AC.2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Propositional Logic） 1.5重言式與蘊(yùn)含式(Tautology and Implication)3) （AB）（AC） （AB）（AC） A（BC） ABC4) (AB)(CB) (AB)(CB) (AC)B (AC)B ACB 2022/7/25 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第一章 命題邏輯（Proposi