離散數(shù)學(xué)及應(yīng)用講課稿課件

離散數(shù)學(xué)及應(yīng)用離散數(shù)學(xué)及應(yīng)用引言（續(xù)）

故計(jì)算機(jī)各分支領(lǐng)域中的理論問題，交錯(cuò)地使用著現(xiàn)代數(shù)學(xué)的各種不同的論題。因?yàn)橛?jì)算機(jī)系統(tǒng)從本質(zhì)上說是一種離散性的結(jié)構(gòu)，它的許多性質(zhì)可以在有限數(shù)學(xué)系統(tǒng)的框架中來理解，從中選出一些必要而且是基本的主干論題稱為離散數(shù)學(xué)。因此，離散數(shù)學(xué)是隨著計(jì)算機(jī)科學(xué)的發(fā)展而逐步建立的，它形成于七十年代初期，是一門新興的工具性學(xué)科。引言（續(xù)）引言（續(xù)）離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)，是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心、骨干課程。它以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素，因此它充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。引言（續(xù)）引言（續(xù)）二、該課程的主要內(nèi)容：離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個(gè)部分：數(shù)理邏輯，包括命題邏輯和謂詞邏輯。(教材的第一、二章)

集合論，包括集合、關(guān)系和函數(shù)。（教材的第三、四章）代數(shù)系統(tǒng)，包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)和格。（教材的第五、六章）圖論，包括圖的基本概念，幾種特殊的圖。(教材的第七章)引言（續(xù)）二、該課程的主要內(nèi)容：引言（續(xù)）三、學(xué)習(xí)該課程的目的：

1.為學(xué)習(xí)計(jì)算機(jī)后繼課程，如數(shù)據(jù)結(jié)構(gòu)、編譯理論、操作系統(tǒng)、數(shù)據(jù)庫(kù)原理、形式語(yǔ)言及自動(dòng)機(jī)、軟件工程與方法學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)和人工智能、高級(jí)程序設(shè)計(jì)語(yǔ)言等，提供必要的數(shù)學(xué)基礎(chǔ)；為閱讀計(jì)算機(jī)文章作充分的數(shù)學(xué)準(zhǔn)備。引言（續(xù)）三、學(xué)習(xí)該課程的目的：引言（續(xù)）數(shù)理邏輯：人工智能，數(shù)據(jù)庫(kù)，形式語(yǔ)言及自動(dòng)機(jī)，高級(jí)程序設(shè)計(jì)語(yǔ)言。集合論：信息結(jié)構(gòu)與檢索，數(shù)據(jù)結(jié)構(gòu)。

圖論：可計(jì)算性理論，計(jì)算機(jī)網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu)。代數(shù)結(jié)構(gòu)：開關(guān)理論，邏輯設(shè)計(jì)和程序理論，語(yǔ)法分析。

2.通過學(xué)習(xí)離散數(shù)學(xué)，可以培養(yǎng)和提高自己的抽象思維和邏輯推理能力，獲得解決實(shí)際問題能力，為以后的軟、硬件學(xué)習(xí)和研究開發(fā)工作，打下堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。引言（續(xù)）數(shù)理邏輯：人工智能，數(shù)據(jù)庫(kù)，形式語(yǔ)言及自動(dòng)機(jī)，引言（續(xù)）四、教學(xué)要求：

通過該課程的學(xué)習(xí)，學(xué)生應(yīng)當(dāng)了解并掌握計(jì)算機(jī)科學(xué)中普遍采用的離散數(shù)學(xué)中的一些基本概念、基本思想、基本方法。五、自學(xué)要求：

由于課時(shí)少，內(nèi)容多且抽象，故要求課前預(yù)習(xí)，課后復(fù)習(xí)；認(rèn)真完成習(xí)題，通過做課后習(xí)題，來加深對(duì)該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯推理能力。作業(yè)每星期一交，作為平時(shí)成績(jī)。引言（續(xù)）四、教學(xué)要求：引言（續(xù)）六、參考教材：1.《離散數(shù)學(xué)及其應(yīng)用》魏雪麗等編著機(jī)械工業(yè)出版社2.《離散數(shù)學(xué)》左孝凌等著上海科技文獻(xiàn)出版社3.《離散數(shù)學(xué)—理論·分析·題解》左孝凌等著上?？萍嘉墨I(xiàn)出版社4.《DiscreteMathematicsandItsApplications》（英文版）(美)KennethH.Rosen著機(jī)械工業(yè)出版社引言（續(xù)）六、參考教材：引言（續(xù)）七、考核方式：期末考試成績(jī)占70%,平時(shí)成績(jī)占30%.引言（續(xù)）七、考核方式：第一部分?jǐn)?shù)理邏輯（MathematicalLogic)邏輯：是研究推理的科學(xué)。公元前四世紀(jì)由希臘的哲學(xué)家亞里斯多德首創(chuàng)。作為一門獨(dú)立科學(xué)，十七世紀(jì)，德國(guó)的萊布尼茲(Leibniz)給邏輯學(xué)引進(jìn)了符號(hào),又稱為數(shù)理邏輯(或符號(hào)邏輯)。邏輯可分為：1.形式邏輯（通過數(shù)學(xué)方法）數(shù)理邏輯

2.辯證邏輯指引進(jìn)一套符號(hào)體系的方法。

辯證邏輯是研究反映客觀世界辯證發(fā)展過程的人類思維的形態(tài)的。第一部分?jǐn)?shù)理邏輯（MathematicalLogic)第一部分?jǐn)?shù)理邏輯（MathematicalLogic)形式邏輯是研究思維的形式結(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)。第一部分?jǐn)?shù)理邏輯（MathematicalLogic)第一部分?jǐn)?shù)理邏輯（MathematicalLogic)1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了1936年Turing機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)算機(jī)問世。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本書課程只研究這兩個(gè)演算。第一部分?jǐn)?shù)理邏輯（MathematicalLogic)第一部分?jǐn)?shù)理邏輯（MathematicalLogic)數(shù)理邏輯與計(jì)算機(jī)學(xué)、控制論、人工智能的相互滲透推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時(shí)態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。第一部分?jǐn)?shù)理邏輯（MathematicalLogic)第一章命題邏輯（PropositionalLogic）

1.1

命題及其表示方法(PropositionandItsExpression)1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)1.3命題公式與翻譯(PropositionalFormula&ItsTranslation)1.4真值表與等價(jià)公式(TruthTablesandPrepositionalEquivalences)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）1.5重言式與蘊(yùn)含式(TautologyandImplication

)1.6其它聯(lián)結(jié)詞(OtherConnectives)1.7對(duì)偶與范式(Dual&NormalForm)1.8推理理論(InferenceTheory

)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）1.1命題及其表示方法1.1.1

命題1.1.2命題的表示方法1.1.3命題的分類第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法1.1.1命題（Proposition)

數(shù)理邏輯研究的中心問題是推理（inference),而推理的前提和結(jié)論都是表達(dá)判斷的陳述句，因而表達(dá)判斷的陳述句構(gòu)成了推理的基本單位。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法基本概念命題：能夠判斷真假的陳述句。命題的真值：命題的判斷結(jié)果。命題的真值只取兩個(gè)值:真（用T(true)或1表示）、假（用F(false)或0表示）。真命題：判斷為正確的命題，即真值為真的命題。假命題：判斷為錯(cuò)誤的命題，即真值為假的命題。第一章命題邏輯（PropositionalLogic）因而又可以稱命題是具有唯一真值的陳述句。判斷命題的兩個(gè)步驟：1、是否為陳述句；2、是否有確定的、唯一的真值。

例：判斷下列句子是否為命題。(1).100是自然數(shù)。T(2).太陽(yáng)從西方升起。F第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法因而又可以稱命題是具有唯一真值的陳述句。第一章命題邏輯（第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法(3).3+3=8.F(4).Howdoyoudo?疑問句，不是命題(5).明年的十月一日是晴天。是命題，其真值到明年十月一日方可知道。(6).x+3>9不是命題(7).我正在說謊。是悖論第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法(8).1+101=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).別的星球上有生物。是命題，客觀上能判斷真假。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法說明：（1）只有具有確定真值的陳述句才是命題。一切沒有判斷內(nèi)容的句子，無所謂是非的句子，如感嘆句、祁使句、疑問句等都不是命題。（2）因?yàn)槊}只有兩種真值，所以“命題邏輯”又稱“二值邏輯”。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法(3)“具有確定真值”是指客觀上的具有，與我們是否知道它的真值是兩回事。如上例中的（5）和（13）。1.1.2命題的表示方法在本書中，用大寫英文字母A,B,…,P,Q或帶下標(biāo)的字母P1,P2,P3,

…,或數(shù)字(1),[2],…,等表示命題，稱之為命題標(biāo)識(shí)符。

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法例如：P：羅納爾多是球星。Q：5是負(fù)數(shù)。P3：明天天氣晴。(2)：太陽(yáng)從西方升起。皆為符號(hào)化的命題，其真值依次為1、0、1或0、0。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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,

…,表示。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法1.1.3命題的分類：簡(jiǎn)單/原子命題：不能分解為更簡(jiǎn)單的陳述語(yǔ)句的命題(如上例中的命題)。復(fù)合命題：由簡(jiǎn)單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。聯(lián)結(jié)詞就是復(fù)合命題中的運(yùn)算符。

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法注意：（1）一個(gè)符號(hào)(如P),它表示的是命題常量還是命題變?cè)?，一般由上下文來確定。（2）命題變?cè)梢员硎救我饷}，它不能確定真值，故命題變?cè)皇敲}。這與“變數(shù)x不是數(shù)”是一樣的道理。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法小結(jié)：本節(jié)主要介紹了命題、命題的真值、原子命題、復(fù)合命題、命題標(biāo)識(shí)符、命題常量、命題變?cè)驮幼冊(cè)母拍睢?/p>

重點(diǎn)理解和掌握命題、命題變?cè)⒑?jiǎn)單（原子）命題、復(fù)合命題四個(gè)概念。作業(yè)：P21,2第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)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é)詞Biconditional)

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

在命題邏輯中,主要研究的是復(fù)合命題,而復(fù)合命題是由原子命題與邏輯聯(lián)結(jié)詞組合而成,聯(lián)結(jié)詞組是復(fù)合命題的重要組成部分.第一章命題邏輯（PropositionalLogic）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)算符.第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)1.2.1否定聯(lián)結(jié)詞┐第一章命題邏輯（Proposi第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)“┐”的定義也可用下表來說明.聯(lián)結(jié)詞“┐”的定義真值表

P

┐P0110第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)例1.P:天津是一個(gè)城市.Q:3是偶數(shù).于是:┐P:天津不是一個(gè)城市.

┐Q:3不是偶數(shù).例2.P:蘇州處處清潔.Q:這些都是男同學(xué).┐P:蘇州不處處清潔(注意,不是處處不清潔).┐Q:這些不都是男同學(xué).第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)1.2.2合取聯(lián)結(jié)詞(Conjunction∧

)定義1.2.2設(shè)P,Q為二命題，復(fù)合命題“P并且Q”（或“P與Q”）稱為P與Q的合取式，記作P∧Q，符號(hào)“∧”

稱為合取聯(lián)結(jié)詞.P∧Q為真當(dāng)且僅當(dāng)P和Q同時(shí)為真.

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

聯(lián)結(jié)詞“∧”的定義真值表PQ

P

Q

000010100111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)說明：“∧”

屬于二元(binary)運(yùn)算符.合取運(yùn)算特點(diǎn)：只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算結(jié)果才為真，否則為假。自然語(yǔ)言中的表示“并且”意思的聯(lián)結(jié)詞，如“既…又…”、“不但…而且…”、“雖然…但是…”、“一面…一面…”、“…和…”、“…與…”等都可以符號(hào)化為∧。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)例3.將下列命題符號(hào)化.(1)李平既聰明又用功.(2)李平雖然聰明,但不用功.(3)李平不但聰明,而且用功.(4)李平不是不聰明,而是不用功.解:設(shè)P:李平聰明.Q:李平用功.則(1)P∧Q(2)P∧┐Q(3)P∧Q(4)┐(┐P)∧┐Q第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)注意：不要見到“與”或“和”就使用聯(lián)結(jié)詞∧！例如:(1)李敏和李華是姐妹。(2)李敏和張華是朋友。

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)例4.試生成下列命題的合取.(1)P:我們?cè)?-503.Q:今天是星期二.

(2)S：李平在吃飯.R：張明在吃飯.解:(1)P∧Q:我們?cè)?-503且今天是星期二.(2)S∧R:李平與張明在吃飯.

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)1.2.3析取聯(lián)結(jié)詞(Disjunction)∨定義1.2.3設(shè)P,Q為二命題，復(fù)合命題“P或Q”稱為P與Q的析取式，記作P∨Q，符號(hào)∨稱為析取聯(lián)結(jié)詞.P∨Q為真當(dāng)且僅當(dāng)P與Q中至少有一個(gè)為真.

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

聯(lián)結(jié)詞“∨”的定義真值表PQP

Q 000011101111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)說明：“∨”

屬于二元(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í)際上有“可兼或”和“排斥或”之分。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)考察下面命題：（1）小王愛打球或愛跑步。（可兼或）

設(shè)P：小王愛打球。Q：小王愛跑步。則上述命題可符號(hào)化為：P∨Q（2）林芳學(xué)過英語(yǔ)或法語(yǔ)。

（可兼或）設(shè)P：林芳學(xué)過英語(yǔ)。Q：林芳學(xué)過法語(yǔ)。則上述命題可符號(hào)化為：P∨Q第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)（3）派小王或小李中的一人去開會(huì)。（排斥或）設(shè)P：派小王去開會(huì)。Q：派小李去開會(huì)。則上述命題可符號(hào)化為：(P∧┐Q)∨(┐P∧Q)（4）人固有一死，或重于泰山或輕于鴻毛.

(排斥或）（5）ab=0,即a=0或b=0.

（可兼或）由此可見,“P∨Q”表示的是“可兼或”.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)注意：當(dāng)P和Q客觀上不能同時(shí)發(fā)生時(shí)，“P或Q”可以符號(hào)化為“P∨Q”。例如：小王現(xiàn)在在宿舍或在圖書館。設(shè)P：小王現(xiàn)在在宿舍。Q：小王現(xiàn)在在圖書館。則上述命題可符號(hào)化為：P∨Q。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)1.2.4.條件聯(lián)結(jié)詞(蘊(yùn)涵聯(lián)結(jié)詞Conditional)→定義1.2.4設(shè)P,Q為二命題，復(fù)合命題“如果P則Q(若P則Q)”稱為P與Q的條件命題,記作P

Q.P

Q為假當(dāng)且僅當(dāng)P為真且Q為假.稱符號(hào)“”為條件聯(lián)結(jié)詞。并稱P為前件，Q為后件.

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

聯(lián)結(jié)詞“

”的定義真值表PQP→

Q001011100111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)注：（1）P

Q表示的基本邏輯關(guān)系是,Q是P的必要條件或P是Q的充分條件.

因此復(fù)合命題“只要P就Q”、“因?yàn)镻，所以Q”、“P僅當(dāng)Q”、“只有Q才P”等都可以符號(hào)化為

P

Q的形式。（2）

“”

屬于二元(binary)運(yùn)算.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)例5.將下列命題符號(hào)化。（1）天不下雨，則草木枯黃。

P：天下雨。Q：草木枯黃。則原命題可表示為：┐P→Q。（2）如果小明學(xué)日語(yǔ)，小華學(xué)英語(yǔ)，則小芳學(xué)德語(yǔ)。P：小明學(xué)日語(yǔ).Q：小華學(xué)英語(yǔ).R：小芳學(xué)德語(yǔ).則原命題可表示為：(P∧Q)→R第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)（3）只要不下雨，我就騎自行車上班。P：天下雨。Q：我騎自行車上班。則原命題可表示為：┐P→Q。（4）只有不下雨，我才騎自行車上班。P：天下雨。Q：我騎自行車上班。則原命題可表示為：

Q

→┐P。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

（5）如果2+2=4,則太陽(yáng)從東方升起。(P→Q,T)PQ

如果2+2=4,則太陽(yáng)從西方升起。(P→R,F)R

如果2+2≠4,則太陽(yáng)從東方升起。(┐P→Q,T)

如果2+2≠4,則太陽(yáng)從西方升起。(┐P→R,T)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)

注意:

(1)與自然語(yǔ)言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！(2)在數(shù)學(xué)中，“若P則Q”往往表示前件P為真，則后件Q為真的推理關(guān)系.但數(shù)理邏輯中，當(dāng)前件P為假時(shí)，P→Q的真值為真。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)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的雙條件命題，記作PiffQ或P

Q，符號(hào)

稱為雙條件（等值）聯(lián)結(jié)詞。P

Q為真當(dāng)且僅當(dāng)P，Q真值相同。

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)聯(lián)結(jié)詞“

”的定義真值表PQP

Q001010100111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)注：（1）P僅當(dāng)Q可譯為P→QP當(dāng)Q可譯為Q→PP當(dāng)且僅當(dāng)Q譯為P

Q

（2）“”屬于二元(binary)運(yùn)算符。

(3)雙條件命題P

Q所表達(dá)的邏輯關(guān)系是,P與Q互為充分必要條件,相當(dāng)于(P

Q)∧(Q

P).只要P與Q的真值同為1或同為0,P

Q的真值就為1,否則P

Q的真值為0.雙條件聯(lián)結(jié)詞連接的兩個(gè)命題之間可以沒有因果關(guān)系。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)例6.分析下列命題的真值.(1)2+2=4當(dāng)且僅當(dāng)3是奇數(shù).(P

Q)P：2+2=4.Q：3是奇數(shù).

(2)2+2=4當(dāng)且僅當(dāng)3不是奇數(shù).(P

┐Q)(3)2+2≠4當(dāng)且僅當(dāng)3是奇數(shù).(┐P

Q)(4)2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù).(┐P

┐Q)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)約定: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é)詞的內(nèi)涵及它們與自然語(yǔ)言中相應(yīng)聯(lián)結(jié)詞的不同之處.第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結(jié)詞(LogicalConnectives)作業(yè):1.P522.預(yù)習(xí)1.3,1.4思考題:1.何謂合式公式?2.復(fù)合命題符號(hào)化的基本步驟是什么?3.何謂真值表?4.兩個(gè)命題公式等價(jià)的涵義是什么?5.兩個(gè)等價(jià)的命題公式其真值表有何關(guān)系?第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.3命題公式與翻譯1.3命題公式與翻譯1.3.1命題公式1.3.2復(fù)合命題的符號(hào)化(翻譯)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.3命題公式與翻譯(PropositionalFormula&ItsTranslation)1.3.1命題合式公式(Well-formedformula)(wff)定義1.3.1:單個(gè)命題變?cè)兔}常量稱為原子公式。命題合式公式是由命題變?cè)⒚}常量、聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號(hào)串。我們以如下遞歸的形式來定義合式公式：第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.3命題公式與翻譯定義1.3.2：(1)原子公式是合式公式(wff)。（2）若A是合式公式，則(┐A)也是合式公式。（3）若A，B是合式公式，則(A∧B)，(A∨B)，(A

B)，(A

B)也是合式公式。（4）當(dāng)且僅當(dāng)有限次地應(yīng)用(1)~(3)所得到的包含原子公式、聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.3命題公式與翻譯注:

(1)合式公式也稱為命題公式，并簡(jiǎn)稱為公式。(2)命題公式一般不是命題,僅當(dāng)公式中的命題變?cè)么_定的命題代入時(shí),才得到一個(gè)命題.其真值依賴于代換變?cè)哪切┟}的真值.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）1.3命題公式與翻譯例1：指出(P→(P

Q))是否是命題公式(wff)，如果是，則具體說明。解：①P是wff由(1)②Q是wff由(1)③P

Q是wff由(2)①②④(P→(P

Q))由(2)①③第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（ProPositionalLogic）1.3命題公式與翻譯例2:(P

Q),(R∧S)∨┐Q,P，(┐P)等均為合式公式，而PQ∨S,(P

W)∧Q)等不是合式公式。第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.3命題公式與翻譯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)化表示.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.3命題公式與翻譯例3：1)我今天進(jìn)城，除非下雨。2)僅當(dāng)你走我將留下。3)假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。4)除非你努力，否則你將失敗。5)一個(gè)人起初說：“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)”；后來他改說，“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的。”問他前后主張的差異在什么地方，試以命題形式進(jìn)行分析。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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:2第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式1.4.1真值表(TruthTable)1.4.2等價(jià)公式(ProPositionalEquivalences)1.4.1真值表前面在定義聯(lián)結(jié)詞時(shí),曾經(jīng)使用過真值表,下面給出真值表的定義.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式定義1.4.1(對(duì)公式的賦值或解釋)設(shè)P1,P2,…,Pn是出現(xiàn)在公式A中的全部的命題變?cè)?給P1,P2,…,Pn各指定一個(gè)真值，稱為對(duì)A的一個(gè)賦值或解釋。若指定的一組值使A的真值為真(假),稱這組值為A的成真(假)賦值.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例如:對(duì)公式(P

Q)∧R，賦值011(即令P=0，Q=1，R=1)為(P

Q)∧R的成真賦值;另一組賦值010為(P

Q)∧R的成假賦值；還有000，001，111……第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.4真值表與等價(jià)公式考慮：含有n個(gè)命題變?cè)墓焦灿卸嗌俳M不同的賦值？定義1.4.2(真值表)在命題公式A中,對(duì)于命題變?cè)拿恳唤M賦值和由它們所確定的命題公式A的真值列成表，稱做命題公式A的真值表。第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(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)賦值的后面。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例1.

給出┐(P

Q)

(┐P

┐Q)的真值表：PQP

Q┐(P

Q)┐P

┐Q┐(P

Q)

(┐P

┐Q)00011011第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.4真值表與等價(jià)公式例1.給出┐(P

Q)

(┐P

┐Q)的真值表：PQP

Q┐(P

Q)┐P

┐Q┐(P

Q)

(┐P

┐Q)000111010111100111111001第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.4真值表與等價(jià)公式例2：構(gòu)造公式(P

Q)∧R的真值表。PQRP

Q(P

Q)∧R000001010011100101110111第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例2：構(gòu)造公式(P

Q)∧R的真值表。PQRP

Q(P

Q)∧R0001000111010100111110000101001101011111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式練習(xí)1：構(gòu)造公式(P

Q)

(┐Q

┐P)真值表。PQ┐P┐QP

Q┐Q

┐P(P

Q)

(┐Q

┐P)00011011第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.4真值表與等價(jià)公式練習(xí)1：構(gòu)造公式(P

Q)

(┐Q

┐P)真值表。PQ┐P┐QP

Q┐Q

┐P(P

Q)

(┐Q

┐P)0011111011011110010011100111第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式PQ(P

Q)┐(P

Q)┐(P

Q)∧Q00011011練習(xí)2：構(gòu)造公式┐(P

Q)∧Q真值表。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式PQ(P

Q)┐(P

Q)┐(P

Q)∧Q00100011001001011100練習(xí)2：構(gòu)造公式┐(P

Q)∧Q真值表。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式1.4.2等價(jià)公式給定n個(gè)命題變?cè)?按合式公式的形成規(guī)則可以形成無數(shù)多個(gè)命題公式,但這些無窮盡的命題公式中，有些具有相同的真值表?？紤]：由n個(gè)命題變?cè)苌???種真值(表)不同的命題公式？第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式注:(1)“

”不是邏輯聯(lián)結(jié)詞.(2)命題公式之間的邏輯相等關(guān)系具有：自反性：A

A；對(duì)稱性：若A

B，則B

A；傳遞性：若A

B且B

C，則A

C。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式證明公式等價(jià)的方法：1.真值表法2.等值演算法1.真值表法

例1.┐(P

Q)

(┐P

┐Q)見真值表例題1.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例2.證明:P

Q

(P→Q)

(Q→P)PQP

QQ→PP→Q(P→Q)

(Q→P)00011011第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例2.證明:P

Q

(P→Q)

(Q→P)PQP

QQ→PP→Q(P→Q)

(Q→P)001111010010100100111111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例3：判斷公式P(QR)、(P∧Q)R是否等價(jià)。PQRP∧QQ

RP(Q

R)(P∧Q)

R0000100101010000110110001101011101011111第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式PQRP∧QQ

RP(Q

R)(P∧Q)

R00001110010111010001101101111000111101011111010001111111例3：判斷公式P(QR)、(P∧Q)R是否等價(jià)。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式

由真值表可知，兩個(gè)公式為等價(jià)式。2.等值演算法(EquivalentCalculation)

等值演算中使用的一條重要規(guī)則：置換規(guī)則定義1.4.4(子公式)：如果X是wffA的一部分,且X本身也是wff，則稱X是A的子公式。例如,P

(PQ)為Q(P

(PQ))的子公式。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.4真值表與等價(jià)公式定理1.4.1(置換定理AxiomofrePlacement)設(shè)X是wffA的子wff，若X

Y，則若將A中的X用Y來置換，所得公式B與A等價(jià)，即A

B。證：因?yàn)閷?duì)變?cè)娜我恢概?X與Y真值相同，所以Y取代X后，公式B與公式A對(duì)變?cè)娜我恢概烧嬷狄蚕嗤?所以A

B。第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式注:滿足定理1.4.1的條件的置換稱為等價(jià)置換(或等價(jià)代換).定義1.4.5(等值演算)：根據(jù)已知的等價(jià)公式,推演出另外一些等價(jià)公式的過程稱為等值演算.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式常用的等價(jià)式：

1.雙重否定律：

┐┐P

P2.結(jié)合律：(P

Q)RP

(QR)(P

Q)RP

(QR)(P

Q)RP

(QR)3.交換律:P

Q

Q

PP

Q

Q

PP

Q

Q

P4.分配律:P

(QR)

(P

Q)(PR)P

(QR)

(P

Q)(PR)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式常用的等價(jià)式：

5.冪等律:P

P

PP

P

P6.吸收律:P

(P

Q)

PP

(P

Q)

P7.德.摩根律:┐(P

Q)

┐P

┐Q┐(P

Q)

┐P

┐Q8.同一律:PFPP

T

P9.零律:PTTPFF第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式常用的等價(jià)式：

10.否定律：P

┐PTP

┐PF11.

蘊(yùn)涵等值式:P

Q

┐P

Q12.等價(jià)等值式:P

Q

(P→Q)

(Q→P)13.假言易位:P

Q

┐Q

┐P14.等價(jià)否定等值式:P

Q

┐P

┐Q15.歸謬論:(P

Q)(P

┐Q)

┐P

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式其中P,Q,R等代表任意命題公式.這樣上面的每一個(gè)公式都是一個(gè)模式,它可以代表無數(shù)多個(gè)同類型的命題公式.例如,P

┐P

T中,用(PQ)置換P,則得(PQ)┐(PQ)T,用┐P置換P,則得(┐P)┐(┐P)T。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（ProPositionalLogic）

1.4真值表與等價(jià)公式例1：證明Q→(P

(P

Q))

Q→P證:Q→(P

(P

Q))

Q→P~~~~~~~~P(吸收律)例2：證明P

┐Q

Q

P

Q證：(P

┐Q)

Q

(P

Q)(┐Q

Q)(P

Q)

T

P

Q第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例3：證明(P→Q)→(Q

R)

P

Q

R證：(P→Q)→(Q

R)

(┐P

Q)→(Q

R)

┐(┐P

Q)

(Q

R)(P

┐Q)

(Q

R)

(P

Q

R)

(┐Q

Q

R)

P

Q

R

第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式例4：驗(yàn)證P(QR)(P∧Q)R證:右┐(P∧Q)∨R

┐P∨┐Q∨R

┐P∨(┐Q∨R)

┐P∨(QR))

P(QR)練：1.((P

Q)∧(PR))P(Q∧R)2.(P∧┐Q)∨(┐P∧Q)(P∨Q)∧┐(P∧Q)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式等值演算在計(jì)算機(jī)硬件設(shè)計(jì)中,在開關(guān)理論和電子元器件中都占有重要地位.小結(jié):

本節(jié)介紹了真值表、公式等價(jià)、等值演算和等價(jià)置換等概念，給出了常用的重要等價(jià)公式（26個(gè)）。重點(diǎn)掌握用真值表法驗(yàn)證公式的等價(jià)性和等值演算法推演兩個(gè)公式等價(jià)。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價(jià)公式作業(yè)：Pg.13:1(2),(4)；2(2),(4)；4；6（3）預(yù)習(xí):1.5,1.6思考題：Pg.13:5第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)1.5.1命題公式的分類1.5.2重言式(Tautology)與矛盾式

(contradictory)的性質(zhì)1.5.3蘊(yùn)含式(

ImPlication)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)1.5.1命題公式的分類

復(fù)合命題第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)定義1.5.1設(shè)A為任一命題公式，(1)若A在其各種賦值下的取值均為真，則稱A是重言式或永真式,記為T或1。(2)若A在其各種賦值下的取值均為假，則稱A是矛盾式或永假式,記為F或0。(3)若A不是矛盾式則稱A為可滿足式(satisfiable)。注:由定義可知,重言式一定是可滿足式,反之不真.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)

判別命題公式的類型有兩種方法:真值表法和等值演算法.等值演算法是將所給命題公式通過等值演算化為最簡(jiǎn)單的形式,然后再進(jìn)行判別.例1.判別下列命題公式的類型.(1).Q∨┓((┓P∨Q)∧P)(重言式)(2).(P∨┓P)

(Q∧┓Q)∧R(矛盾式)(3).(P

Q)∧┓P.(可滿足式)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)1.5.2重言式(Tautology)與矛盾式(contradictory)的性質(zhì)定理1.5.1:任何兩個(gè)重言式的合取或析取,仍然是一重言式.（由冪等律立得）證明:設(shè)A和B為兩個(gè)重言式,則不論A和B的分量指派任何真值,總有A為T,B為T,故A∧B

T，A∨B

T。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)定理1.5.2:一個(gè)重言式(矛盾式),對(duì)同一分量都用任何合式公式置換,其結(jié)果仍為一重言式(矛盾式).證明：由于重言式(矛盾式)的真值與對(duì)變?cè)馁x值無關(guān)，故對(duì)同一變?cè)匀魏魏鲜焦街脫Q后，重言式(矛盾式)的真值仍永為T（F）。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)定理1.5.3：A,B是兩個(gè)命題公式，A

B的充要條件是A

B為重言式。

證明:若A

B為重言式，則A

B永為T，即A，B的真值表相同，所以A

B。

反之，若A

B，則A，B真值表相同，所以A

B永為T，所以A

B為重言式。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)它們之間具有如下關(guān)系:

P

Q

┓Q

┓P

Q

P

┓P

┓Q原命題逆換式反換式逆反式P

QQ

P┓P

┓Q┓Q

┓P1.5.3蘊(yùn)含式（ImPlication）定義1.5.2：當(dāng)且僅當(dāng)P

Q是一個(gè)重言式時(shí)，我們稱“P蘊(yùn)含Q”，并記作P

Q.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)因此,要證明P

Q有三種方法:1)真值表法:即列出P

Q的真值表,觀察其是否永為真。2)等值演算法：通過證明P

Q1來證P

Q3)分析法：直接分析法:假定前件P是真，推出后件Q是真。間接分析法:假定后件是假，推出前件是假,即證

┓Q

┓P

。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)例:證明┐Q

(P→Q)

┐P1)法1：真值表（略）2)法2：┐Q

(P→Q)→┐P

┐(┐Q

(P→Q))∨(┐P)

Q∨┐(┐P∨Q)∨(┐P)

(┐P∨Q)∨┐(┐P∨Q)1即┐Q

(P→Q)

┐P第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)3)直接分析法：若┐Q(P→Q)為真，則┐Q，P→Q為真，所以Q為假，P為假，所以┐P為真。

間接分析法：若┐P為假，則P為真，再分二種情況：①若Q為真，則┐Q為假,從而┐Q(P→Q)為假.

②若Q為假，則P→Q為假，則┐Q(P→Q)為假.根據(jù)①②，所以┐Q(P→Q)

┐P第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)下面常用的14個(gè)蘊(yùn)含式,都可以用上述方法加以推證.1.P

Q

P2.

P

Q

Q3.P

P∨Q4.┐P

P→Q5.Q

P→Q6.┐(P→Q)

P7.┐(P→Q)

┐Q8.P

(P→Q)

Q9.┐Q

(P→Q)

┐P10.┐P

(P∨Q)

Q11.

(P→Q)

(Q→R)

P→R12.

(P∨Q)

(P→R)

(Q→R)

R13.(P→Q)

(R→S)

(P

R)→(Q

S)14.(P

Q)

(Q

R)

(P

R)第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)等價(jià)式與蘊(yùn)含式的關(guān)系:定理1.5.4:

設(shè)P,Q為任意兩個(gè)命題公式,P

Q的充要條件為P

Q且Q

P.證：若P

Q，則P

Q為永真式因?yàn)镻

Q

（P→Q）

（Q→P）所以P→Q，Q→P為永真式,從而P

Q，Q

P.反之，若P

Q，Q

P，則P→Q，Q→P為永真式,所以（P→Q）

（Q→P）為永真式，從而P

Q為永真式，即P

Q.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)蘊(yùn)含的性質(zhì):設(shè)A，B，C為任意wff,1)若A

B，且A為永真式，則B必為永真式.2)若A

B，B

C，則A

C.3)若A

B，A

C，則A

B

C.4)若A

B且C

B，則A

C

B.證：1)因?yàn)锳→B，A永為T,所以B必永為T.2)由I11（A→B)(B→C）

A→C,所以若A

B，B

C，則（A→B)(B→C）永為T,從而A→C永為T,故A

C.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊(yùn)含式(TautologyandImplication)3)（A→B）

（A→C）

（┐A

B）

（┐A

C）

┐A

（B

C）

A→B

C4)(A→B)(C→B)

(┐A

B)(┐C

B)

(┐A

┐C)

B

┐(A

C)

B

A

C→B