離散數(shù)學及應用講課稿課件

離散數(shù)學及應用離散數(shù)學及應用引言（續(xù)）

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

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

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

圖論：可計算性理論，計算機網(wǎng)絡,數(shù)據(jù)結構。代數(shù)結構：開關理論，邏輯設計和程序理論，語法分析。

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

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

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

2.辯證邏輯指引進一套符號體系的方法。

辯證邏輯是研究反映客觀世界辯證發(fā)展過程的人類思維的形態(tài)的。第一部分數(shù)理邏輯（MathematicalLogic)第一部分數(shù)理邏輯（MathematicalLogic)形式邏輯是研究思維的形式結構和規(guī)律的科學，它撇開具體的、個別的思維內(nèi)容，從形式結構方面研究概念、判斷和推理及其正確聯(lián)系的規(guī)律。數(shù)理邏輯是用數(shù)學方法研究推理的形式結構和推理的規(guī)律的數(shù)學學科。它的創(chuàng)始人Leibniz，為了實現(xiàn)把推理變?yōu)檠菟愕南敕?，把?shù)學引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學科。上個世紀30年代以后，數(shù)理邏輯進入一個嶄新的發(fā)展階段，邏輯學不僅與數(shù)學結合，還與計算機科學等密切關聯(lián)。第一部分數(shù)理邏輯（MathematicalLogic)第一部分數(shù)理邏輯（MathematicalLogic)1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計算性的引入，促使了1936年Turing機的產(chǎn)生，十年后，第一臺電子計算機問世。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題演算、謂詞演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題演算和謂詞演算。本書課程只研究這兩個演算。第一部分數(shù)理邏輯（MathematicalLogic)第一部分數(shù)理邏輯（MathematicalLogic)數(shù)理邏輯與計算機學、控制論、人工智能的相互滲透推動了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時態(tài)邏輯等都是目前比較熱門的研究領域。第一部分數(shù)理邏輯（MathematicalLogic)第一章命題邏輯（PropositionalLogic）

1.1

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

)1.6其它聯(lián)結詞(OtherConnectives)1.7對偶與范式(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),而推理的前提和結論都是表達判斷的陳述句，因而表達判斷的陳述句構成了推理的基本單位。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

例：判斷下列句子是否為命題。(1).100是自然數(shù)。T(2).太陽從西方升起。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二進制中為真，十進制中為假。(9).如果太陽從西方升起，那么2是奇數(shù)。T(10).國足能殺入2006世界杯當且僅當2+2=4。F(11).今天天氣多好啊！感嘆句，不是命題(12).請你關上門！祁使句，不是命題，(13).別的星球上有生物。是命題，客觀上能判斷真假。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

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

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

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

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

1.1命題及其表示方法命題標識符又有命題常量、命題變元和原子變元之分。命題常量：表示確定命題的命題標識符。命題變元：命題標識符如僅是表示任意命題的位置標志，就稱為命題變元。原子變元：當命題變元表示原子命題時，該變元稱為原子變元。命題變元也用A,B,…,P,Q,P1,P2,P3,

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

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

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

1.1命題及其表示方法注意：（1）一個符號(如P),它表示的是命題常量還是命題變元，一般由上下文來確定。（2）命題變元可以表示任意命題，它不能確定真值，故命題變元不是命題。這與“變數(shù)x不是數(shù)”是一樣的道理。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.1命題及其表示方法小結：本節(jié)主要介紹了命題、命題的真值、原子命題、復合命題、命題標識符、命題常量、命題變元和原子變元的概念。

重點理解和掌握命題、命題變元、簡單（原子）命題、復合命題四個概念。作業(yè)：P21,2第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.2邏輯聯(lián)結詞(LogicalConnectives)1.2.1否定聯(lián)結詞(Negation)┐1.2.2合取聯(lián)結詞(Conjunction)∧1.2.3析取聯(lián)結詞(Disjunction)∨1.2.4條件聯(lián)結詞(蘊涵聯(lián)結詞Conditional)→1.2.5雙條件聯(lián)結(等值聯(lián)結詞Biconditional)

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

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

在命題邏輯中,主要研究的是復合命題,而復合命題是由原子命題與邏輯聯(lián)結詞組合而成,聯(lián)結詞組是復合命題的重要組成部分.第一章命題邏輯（PropositionalLogic）1.2.1否定聯(lián)結詞┐定義1.2.1

設P為一命題，P的否定是一個新的復合命題,稱為P的否定式，記作“┐P”讀作“非P”.符號“┐”

稱為否定聯(lián)結詞。┐P為真當且僅當P為假.說明：“┐”屬于一元(unary)運算符.第一章命題邏輯（PropositionalLogic）

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

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

P

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

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

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

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

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

稱為合取聯(lián)結詞.P∧Q為真當且僅當P和Q同時為真.

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

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

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

P

Q

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

屬于二元(binary)運算符.析取運算特點：只有參與運算的二命題全為假時，運算結果才為假，否則為真。由析取聯(lián)結詞的定義可以看出，“∨”與漢語中的聯(lián)結詞“或”意義相近，但又不完全相同。在現(xiàn)代漢語中，聯(lián)結詞的“或”實際上有“可兼或”和“排斥或”之分。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

設P：小王愛打球。Q：小王愛跑步。則上述命題可符號化為：P∨Q（2）林芳學過英語或法語。

（可兼或）設P：林芳學過英語。Q：林芳學過法語。則上述命題可符號化為：P∨Q第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

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

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

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

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

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

Q.P

Q為假當且僅當P為真且Q為假.稱符號“”為條件聯(lián)結詞。并稱P為前件，Q為后件.

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

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

聯(lián)結詞“

”的定義真值表PQP→

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

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

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

因此復合命題“只要P就Q”、“因為P，所以Q”、“P僅當Q”、“只有Q才P”等都可以符號化為

P

Q的形式。（2）

“”

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

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

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

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

Q

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

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

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

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

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

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

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

注意:

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

1.2邏輯聯(lián)結詞(LogicalConnectives)1.2.5雙條件聯(lián)結(等值聯(lián)結詞Biconditional)

定義1.2.5設P,Q為二命題，復合命題“P當且僅當Q”稱為P與Q的雙條件命題，記作PiffQ或P

Q，符號

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

Q為真當且僅當P，Q真值相同。

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

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

”的定義真值表PQP

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

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

Q

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

(3)雙條件命題P

Q所表達的邏輯關系是,P與Q互為充分必要條件,相當于(P

Q)∧(Q

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

Q的真值就為1,否則P

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

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

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

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

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

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

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

1.2邏輯聯(lián)結詞(LogicalConnectives)約定:1.運算次序優(yōu)先級：┐，

，

，→，.

2.相同的運算符按從左至右次序計算，否則要加上括號。3.最外層圓括號可省去。

小結:本節(jié)介紹了五種聯(lián)結詞(┐，

，

，→，),重點是理解和掌握五種聯(lián)結詞的內(nèi)涵及它們與自然語言中相應聯(lián)結詞的不同之處.第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

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

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

1.3命題公式與翻譯(PropositionalFormula&ItsTranslation)1.3.1命題合式公式(Well-formedformula)(wff)定義1.3.1:單個命題變元和命題常量稱為原子公式。命題合式公式是由命題變元、命題常量、聯(lián)結詞和圓括號按一定的邏輯關系聯(lián)結起來的符號串。我們以如下遞歸的形式來定義合式公式：第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

B)，(A

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

1.3命題公式與翻譯注:

(1)合式公式也稱為命題公式，并簡稱為公式。(2)命題公式一般不是命題,僅當公式中的命題變元用確定的命題代入時,才得到一個命題.其真值依賴于代換變元的那些命題的真值.第一章命題邏輯（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復合命題的符號化(翻譯)有了命題演算的合式公式的概念,我們可以把自然語言中的有些語句(復合命題),翻譯成數(shù)理邏輯中的符號形式.基本步驟如下:(1)分析出各簡單命題,將它們符號化;(2)使用合適的聯(lián)結詞,把簡單命題逐個的聯(lián)結起來,組成復合命題的符號化表示.第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

1.3命題公式與翻譯例4：P6例1.3.3，例1.3.4(5)，例1.3.5小結：本節(jié)介了命題公式的概念及復合命題的符號化.重點是理解命題公式的遞歸定義,掌握復合命題的符號化方法.作業(yè):P7:2第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

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

1.4真值表與等價公式例如:對公式(P

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

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

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

1.4真值表與等價公式考慮：含有n個命題變元的公式共有多少組不同的賦值？定義1.4.2(真值表)在命題公式A中,對于命題變元的每一組賦值和由它們所確定的命題公式A的真值列成表，稱做命題公式A的真值表。第一章命題邏輯（ProPositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價公式對公式A構造真值表的具體步驟為：（1）找出公式中所有命題變元P1,P2,…,Pn,列出全部的2n組賦值。（2）按從小到大的順序列出對命題變元P1,P2,…,Pn,的全部2n組賦值。（3）對應各組賦值計算出公式A的真值，并將其列在對應賦值的后面。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.4真值表與等價公式例1.

給出┐(P

Q)

(┐P

┐Q)的真值表：PQP

Q┐(P

Q)┐P

┐Q┐(P

Q)

(┐P

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

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

Q)

(┐P

┐Q)的真值表：PQP

Q┐(P

Q)┐P

┐Q┐(P

Q)

(┐P

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

1.4真值表與等價公式例2：構造公式(P

Q)∧R的真值表。PQRP

Q(P

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

1.4真值表與等價公式例2：構造公式(P

Q)∧R的真值表。PQRP

Q(P

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

1.4真值表與等價公式練習1：構造公式(P

Q)

(┐Q

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

Q┐Q

┐P(P

Q)

(┐Q

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

1.4真值表與等價公式練習1：構造公式(P

Q)

(┐Q

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

Q┐Q

┐P(P

Q)

(┐Q

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

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

Q)┐(P

Q)┐(P

Q)∧Q00011011練習2：構造公式┐(P

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

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

Q)┐(P

Q)┐(P

Q)∧Q00100011001001011100練習2：構造公式┐(P

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

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

1.4真值表與等價公式定義1.4.3:給定兩個命題公式A和B，設P1,P2,…,Pn為出現(xiàn)于A和B中的所有原子變元,若給P1,P2,…,Pn任一組真值指派,A和B的真值都相同,則稱A和B是等價的或邏輯相等.記作A

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

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

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

A；對稱性：若A

B，則B

A；傳遞性：若A

B且B

C，則A

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

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

例1.┐(P

Q)

(┐P

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

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

Q

(P→Q)

(Q→P)PQP

QQ→PP→Q(P→Q)

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

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

Q

(P→Q)

(Q→P)PQP

QQ→PP→Q(P→Q)

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

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

RP(Q

R)(P∧Q)

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

1.4真值表與等價公式PQRP∧QQ

RP(Q

R)(P∧Q)

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

1.4真值表與等價公式

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

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

(PQ)為Q(P

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

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

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

B。證：因為對變元的任一指派,X與Y真值相同，所以Y取代X后，公式B與公式A對變元的任一指派真值也相同,所以A

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

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

1.4真值表與等價公式常用的等價式：

1.雙重否定律：

┐┐P

P2.結合律：(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真值表與等價公式常用的等價式：

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真值表與等價公式常用的等價式：

10.否定律：P

┐PTP

┐PF11.

蘊涵等值式:P

Q

┐P

Q12.等價等值式:P

Q

(P→Q)

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

Q

┐Q

┐P14.等價否定等值式:P

Q

┐P

┐Q15.歸謬論:(P

Q)(P

┐Q)

┐P

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

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

┐P

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

1.4真值表與等價公式例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真值表與等價公式例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真值表與等價公式例4：驗證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é)介紹了真值表、公式等價、等值演算和等價置換等概念，給出了常用的重要等價公式（26個）。重點掌握用真值表法驗證公式的等價性和等值演算法推演兩個公式等價。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

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

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

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

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

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

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

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

1.5重言式與蘊含式(TautologyandImplication)

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

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

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

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

T，A∨B

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

1.5重言式與蘊含式(TautologyandImplication)定理1.5.2:一個重言式(矛盾式),對同一分量都用任何合式公式置換,其結果仍為一重言式(矛盾式).證明：由于重言式(矛盾式)的真值與對變元的賦值無關，故對同一變元以任何合式公式置換后，重言式(矛盾式)的真值仍永為T（F）。第一章命題邏輯（PropositionalLogic）第一章命題邏輯（PropositionalLogic）

1.5重言式與蘊含式(TautologyandImplication)定理1.5.3：A,B是兩個命題公式，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重言式與蘊含式(TautologyandImplication)它們之間具有如下關系:

P

Q

┓Q

┓P

Q

P

┓P

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

QQ

P┓P

┓Q┓Q

┓P1.5.3蘊含式（ImPlication）定義1.5.2：當且僅當P

Q是一個重言式時，我們稱“P蘊含Q”，并記作P

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

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

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

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

Q1來證P

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

┓Q

┓P

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

1.5重言式與蘊含式(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重言式與蘊含式(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重言式與蘊含式(TautologyandImplication)下面常用的14個蘊含式,都可以用上述方法加以推證.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重言式與蘊含式(TautologyandImplication)等價式與蘊含式的關系:定理1.5.4:

設P,Q為任意兩個命題公式,P

Q的充要條件為P

Q且Q

P.證：若P

Q，則P

Q為永真式因為P

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重言式與蘊含式(TautologyandImplication)蘊含的性質(zhì):設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)因為A→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重言式與蘊含式(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