工業(yè)大學(xué)稿第講課件

離散數(shù)學(xué)23七月2023教師：陳雅頌簡(jiǎn)介

離散數(shù)學(xué)(Discretemathematics)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。它在各學(xué)科領(lǐng)域，特別在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專業(yè)的許多專業(yè)課程，如程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯技術(shù)、人工智能、數(shù)據(jù)庫(kù)、算法設(shè)計(jì)與分析、理論計(jì)算機(jī)科學(xué)基礎(chǔ)等必不可少的先行課程。

通過(guò)離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，為將來(lái)參與創(chuàng)新性的研究和開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。

隨著信息時(shí)代的到來(lái)，工業(yè)革命時(shí)代以微積分為代表的連續(xù)數(shù)學(xué)占主流的地位已經(jīng)發(fā)生了變化，離散數(shù)學(xué)的重要性逐漸被人們認(rèn)識(shí)。離散數(shù)學(xué)課程所傳授的思想和方法，廣泛地體現(xiàn)在計(jì)算機(jī)科學(xué)技術(shù)及相關(guān)專業(yè)的諸領(lǐng)域，從科學(xué)計(jì)算到信息處理，從理論計(jì)算機(jī)科學(xué)到計(jì)算機(jī)應(yīng)用技術(shù)，從計(jì)算機(jī)軟件到計(jì)算機(jī)硬件，從人工智能到認(rèn)知系統(tǒng)，無(wú)不與離散數(shù)學(xué)密切相關(guān)。

由于數(shù)字電子計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系，因此，無(wú)論計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對(duì)離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來(lái)的數(shù)學(xué)模型離散化，從而可由計(jì)算機(jī)加以處理。

離散數(shù)學(xué)是傳統(tǒng)的邏輯學(xué)，集合論（包括函數(shù)），數(shù)論基礎(chǔ)，算法設(shè)計(jì)，組合分析，離散概率，關(guān)系理論，圖論與樹，抽象代數(shù)（包括代數(shù)系統(tǒng)，群、環(huán)、域等），布爾代數(shù)，計(jì)算模型（語(yǔ)言與自動(dòng)機(jī)）等匯集起來(lái)的一門綜合學(xué)科。離散數(shù)學(xué)的應(yīng)用遍及現(xiàn)代科學(xué)技術(shù)的諸多領(lǐng)域。

離散數(shù)學(xué)課程的教學(xué)目的，不但作為計(jì)算機(jī)科學(xué)與技術(shù)及相關(guān)專業(yè)的理論基礎(chǔ)及核心主干課，對(duì)后續(xù)課程提供必需的理論支持。更重要的是旨在“通過(guò)加強(qiáng)數(shù)學(xué)推理，組合分析，離散結(jié)構(gòu)，算法構(gòu)思與設(shè)計(jì)，構(gòu)建模型等方面專門與反復(fù)的研究、訓(xùn)練及應(yīng)用，培養(yǎng)提高學(xué)生的數(shù)學(xué)思維能力和對(duì)實(shí)際問(wèn)題的求解能力?！?/p>

請(qǐng)根據(jù)下面事實(shí)，找出兇手：1.清潔工或者秘書謀害了經(jīng)理。2.如果清潔工謀害了經(jīng)理，則謀害不會(huì)發(fā)生在午夜前。3.如果秘書的證詞是正確的，則謀害發(fā)生在午夜前。4.如果秘書的證詞不正確，則午夜時(shí)屋里燈光未滅。5.如果清潔工富裕，則他不會(huì)謀害經(jīng)理。6.經(jīng)理有錢且清潔工不富裕。7.午夜時(shí)屋里燈滅了。解：令A(yù):清潔工謀害了經(jīng)理。

B:秘書謀害了經(jīng)理。

C:謀害發(fā)生在午夜前。

D:秘書的證詞是正確的.

E:午夜時(shí)屋里燈光滅了。H:清潔工富裕.

G:經(jīng)理有錢.命題符號(hào)為：AB,A→┐C,B→C,D→C,┐D→┐E,H→┐AE┐D→┐E┐┐DDD→CCA→┐C┐AABB結(jié)果是秘書謀害了經(jīng)理。

第一部分?jǐn)?shù)理邏輯第二部分集合論第五部分圖論第三部分代數(shù)結(jié)構(gòu)第四部分組合數(shù)學(xué)（選講）第六部分初等數(shù)論（選講）第一部分?jǐn)?shù)理邏輯第一章命題邏輯基本概念第二章命題邏輯等值演算第三章命題邏輯的推理理論第四章一階（謂詞）邏輯基本概念第五章一階（謂詞）邏輯等值演算與推理第二部分集合論第六章集合代數(shù)第七章二元關(guān)系第八章函數(shù)（選講）第五部分圖論第十四章圖的基本概念第十五章歐拉圖與哈密頓圖第十六章樹第十七章平面圖第十八章支配集、覆蓋集、獨(dú)立集與匹配與著色(選講)第三部分代數(shù)結(jié)構(gòu)第九章代數(shù)系統(tǒng)第十章群與環(huán)第十一章格與布爾代數(shù)（選講）第四部分組合數(shù)學(xué)（選講）第十二章基本組合計(jì)數(shù)公式（選講）第十三章遞推方程與生成函數(shù)（選講）第六部分初等數(shù)論（選講）第十九章初等數(shù)論

（選講）第一部分?jǐn)?shù)理邏輯邏輯：是人的一種抽象思維，是人通過(guò)概念、判斷、推理、論證來(lái)理解和區(qū)分客觀世界的思維過(guò)程。主要分為：制約邏輯；形式邏輯；演繹邏輯；歸納邏輯。

本篇數(shù)理邏輯，是形式邏輯的一部分。2023/7/23數(shù)理邏輯（MathematicalLogic）

---是研究演繹推理的一門學(xué)科，用數(shù)學(xué)的方法來(lái)研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。第一部分?jǐn)?shù)理邏輯所謂數(shù)學(xué)方法就是指數(shù)學(xué)采用的一般方法，包括使用符號(hào)和公式，已有的數(shù)學(xué)成果和方法，特別是使用形式的公理方法。

用數(shù)學(xué)的方法研究邏輯的系統(tǒng)思想一般追溯到萊布尼茨，他認(rèn)為經(jīng)典的傳統(tǒng)邏輯必須改造和發(fā)展，是之更為精確和便于演算。后人基本是沿著萊布尼茨的思想進(jìn)行工作的。

簡(jiǎn)而言之，數(shù)理邏輯就是精確化、數(shù)學(xué)化的形式邏輯。它是現(xiàn)代計(jì)算機(jī)技術(shù)的基礎(chǔ)。新的時(shí)代將是數(shù)學(xué)大發(fā)展的時(shí)代，而數(shù)理邏輯在其中將會(huì)起到很關(guān)鍵的作用。

數(shù)理邏輯的產(chǎn)生

利用計(jì)算的方法來(lái)代替人們思維中的邏輯推理過(guò)程，這種想法早在十七世紀(jì)就有人提出過(guò)。萊布尼茨就曾經(jīng)設(shè)想過(guò)能不能創(chuàng)造一種“通用的科學(xué)語(yǔ)言”，可以把推理過(guò)程象數(shù)學(xué)一樣利用公式來(lái)進(jìn)行計(jì)算，從而得出正確的結(jié)論。由于當(dāng)時(shí)的社會(huì)條件，他的想法并沒有實(shí)現(xiàn)。但是它的思想?yún)s是現(xiàn)代數(shù)理邏輯部分內(nèi)容的萌芽，從這個(gè)意義上講，萊布尼茨可以說(shuō)是數(shù)理邏輯的先驅(qū)。

1847年，英國(guó)數(shù)學(xué)家布爾發(fā)表了《邏輯的數(shù)學(xué)分析》，建立了“布爾代數(shù)”，并創(chuàng)造一套符號(hào)系統(tǒng)，利用符號(hào)來(lái)表示邏輯中的各種概念。布爾建立了一系列的運(yùn)算法則，利用代數(shù)的方法研究邏輯問(wèn)題，初步奠定了數(shù)理邏輯的基礎(chǔ)。

十九世紀(jì)末二十世紀(jì)初，數(shù)理邏輯有了比較大的發(fā)展，1884年，德國(guó)數(shù)學(xué)家弗雷格出版了《數(shù)論的基礎(chǔ)》一書，在書中引入量詞的符號(hào)，使得數(shù)理邏輯的符號(hào)系統(tǒng)更加完備。對(duì)建立這門學(xué)科做出貢獻(xiàn)的，還有美國(guó)人皮爾斯，他也在著作中引入了邏輯符號(hào)。從而使現(xiàn)代數(shù)理邏輯最基本的理論基礎(chǔ)逐步形成，成為一門獨(dú)立的學(xué)科。

數(shù)理邏輯的發(fā)展

數(shù)理邏輯這門學(xué)科建立以后，發(fā)展比較迅速，促進(jìn)它發(fā)展的因素也是多方面的。比如，非歐幾何的建立，促使人們?nèi)パ芯糠菤W幾何和歐氏幾何的無(wú)矛盾性。

集合論的產(chǎn)生是近代數(shù)學(xué)發(fā)展的重大事件，但是在集合論的研究過(guò)程中，出現(xiàn)了一次稱作數(shù)學(xué)史上的第三次大危機(jī)。這次危機(jī)是由于發(fā)現(xiàn)了集合論的悖論引起。什么是悖論呢？悖論就是邏輯矛盾。集合論本來(lái)是論證很嚴(yán)格的一個(gè)分支，被公認(rèn)為是數(shù)學(xué)的基礎(chǔ)。

1903年，英國(guó)唯心主義哲學(xué)家、邏輯學(xué)家、數(shù)學(xué)家羅素卻對(duì)集合論提出了以他名字命名的“羅素悖論”，這個(gè)悖論的提出幾乎動(dòng)搖了整個(gè)數(shù)學(xué)基礎(chǔ)。

羅素悖論中有許多例子，其中一個(gè)很通俗也很有名的例子就是“理發(fā)師悖論”：

某鄉(xiāng)村有一位理發(fā)師，有一天他宣布：只給不自己刮胡子的人刮胡子。那么就產(chǎn)生了一個(gè)問(wèn)題：理發(fā)師究竟給不給自己刮胡子？如果他給自己刮胡子，他就是自己刮胡子的人，按照他的原則，他又不該給自己刮胡子；如果他不給自己刮胡子，那么他就是不自己刮胡子的人，按照他的原則，他又應(yīng)該給自己刮胡子。這就產(chǎn)生了矛盾。

悖論的提出，促使許多數(shù)學(xué)家去研究集合論的無(wú)矛盾性問(wèn)題，從而產(chǎn)生了數(shù)理邏輯的一個(gè)重要分支-----公理集合論。

數(shù)理邏輯新近還發(fā)展了許多新的分支，如遞歸論、模型論等。遞歸論主要研究可計(jì)算性的理論，它和計(jì)算機(jī)的發(fā)展和應(yīng)用有密切的關(guān)系。模型論主要是研究形式系統(tǒng)和數(shù)學(xué)模型之間的關(guān)系。

數(shù)理邏輯近年來(lái)發(fā)展特別迅速，主要原因是這門學(xué)科對(duì)于數(shù)學(xué)其它分支如集合論、數(shù)論、代數(shù)、拓?fù)鋵W(xué)等的發(fā)展有重大的影響，特別是對(duì)新近形成的計(jì)算機(jī)科學(xué)的發(fā)展起了推動(dòng)作用。反過(guò)來(lái)，其他學(xué)科的發(fā)展也推動(dòng)了數(shù)理邏輯的發(fā)展。

數(shù)理邏輯論的體系

數(shù)理邏輯的主要分支包括：邏輯演算(包括命題演算和謂詞演算)、模型論、證明論、遞歸論和公理化集合論。數(shù)理邏輯和計(jì)算機(jī)科學(xué)有許多重合之處，這是因?yàn)樵S多計(jì)算機(jī)科學(xué)的先驅(qū)者既是數(shù)學(xué)家、又是邏輯學(xué)家，如阿蘭·圖靈、邱奇等。

簡(jiǎn)介：阿蘭·麥席森·圖靈，1912年生于英國(guó)倫敦，1954年死于英國(guó)的曼徹斯特，他是計(jì)算機(jī)邏輯的奠基者，許多人工智能的重要方法也源自于這位偉大的科學(xué)家。他對(duì)計(jì)算機(jī)的重要貢獻(xiàn)在于他提出的有限狀態(tài)自動(dòng)機(jī)也就是圖靈機(jī)的概念，對(duì)于人工智能，它提出了重要的衡量標(biāo)準(zhǔn)“圖靈測(cè)試”，如果有機(jī)器能夠通過(guò)圖靈測(cè)試，那他就是一個(gè)完全意義上的智能機(jī)，和人沒有區(qū)別了。阿隆佐·邱奇（1903年6月14日—1995年8月11日）是美國(guó)數(shù)學(xué)家，1936年發(fā)表可計(jì)算函數(shù)的第一份精確定義，對(duì)算法理論的系統(tǒng)發(fā)展做出巨大貢獻(xiàn)。邱奇在普林斯頓受教并工作四十年，曾任數(shù)學(xué)與哲學(xué)教授。1967年遷往加利福尼亞大學(xué)洛杉磯分校。

程序語(yǔ)言學(xué)、語(yǔ)義學(xué)的研究從模型論衍生而來(lái)，而程序驗(yàn)證則從模型論的模型檢測(cè)衍生而來(lái)。

數(shù)理邏輯的內(nèi)容

數(shù)理邏輯包括哪些內(nèi)容呢？這里我們先介紹它的兩個(gè)最基本的也是最重要的組成部分，就是“命題演算”和“謂詞演算（在本教材中也稱作一階邏輯演算）”。

學(xué)習(xí)邏輯學(xué)的意義學(xué)習(xí)邏輯學(xué)的根本意義，是訓(xùn)練和提高人們的邏輯思維能力，促進(jìn)其自覺地運(yùn)用邏輯知識(shí)，提高學(xué)習(xí)和工作的質(zhì)量。具體來(lái)說(shuō)，學(xué)習(xí)邏輯學(xué)的意義主要有：第一，有助于正確認(rèn)識(shí)事物，從已知進(jìn)到未知。第二，有助于準(zhǔn)確、嚴(yán)密地表達(dá)和論證思想。第三，有助于揭露謬誤，駁斥詭辯。第四，有助于培養(yǎng)分析理性精神和創(chuàng)新意識(shí)。

2023/7/23主要研究?jī)?nèi)容：推理

——著重于推理過(guò)程是否正確

——著重于語(yǔ)句之間的關(guān)系主要研究方法：數(shù)學(xué)的方法

——就是引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯又叫符號(hào)邏輯（SymbolicLogic）。

2023/7/23什么是數(shù)理邏輯？用數(shù)學(xué)的方法來(lái)研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。為什么要研究數(shù)理邏輯？

程序<=>算法＋數(shù)據(jù)

算法<=>邏輯＋控制小結(jié)2023/7/23命題邏輯命題邏輯基本概念命題邏輯等值演算命題邏輯推理理論主要研究?jī)?nèi)容一階邏輯（謂詞邏輯）一階邏輯基本概念一階邏輯等值演算一階邏輯推理理論2023/7/23第一章命題邏輯的基本概念

命題邏輯也稱命題演算，或語(yǔ)句邏輯。

研究?jī)?nèi)容：（1）研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系

（2）研究什么是命題？（3）研究如何表示命題？（4）研究如何由一組前提推導(dǎo)一些結(jié)論？2023/7/23第一章命題邏輯的基本概念命題邏輯的特征：

在研究邏輯的形式時(shí)，我們把一個(gè)命題只分析到其中所含的命題成份為止，不再分析下去。不把一個(gè)簡(jiǎn)單命題再分析為非命題的集合，不把謂詞和量詞等非命題成份分析出來(lái)。

2023/7/231.0本章學(xué)習(xí)要求

深刻理解:命題、聯(lián)結(jié)詞、復(fù)合命題、命題公式、等值（等價(jià)）式、等值（等價(jià)）演算、推理及證明等概念。

熟練進(jìn)行:等值（等價(jià)）演算與構(gòu)造證明。2023/7/231.1.1命題定義1.1.0具有非真即假的陳述句稱為命題,該命題可以取一個(gè)“值”，稱為真值。真值只有“真”和“假”兩種，分別用“1”(或“T”)和“0”(或“F”)表示。1.1命題與命題聯(lián)結(jié)詞2023/7/23（1）太陽(yáng)是圓的；（2）成都是一個(gè)旅游城市；（3）北京是中國(guó)的首都；（4）這個(gè)語(yǔ)句是假的；（5）1＋1<=>10；（6）ｘ+y>０；（7）我喜歡踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中國(guó)是世界上人口最多的國(guó)家；（11）今天是晴天；例1.1.1TTT/F非命題T/FFT/FTTT非命題2023/7/23例1.1.1（續(xù)）（12）把門關(guān)上；（13）你快上學(xué)去?。?4）你要出去嗎？（15）今天天氣真好??！非命題非命題非命題非命題注意：一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問(wèn)句、祈使句、二義性的陳述句等。

2023/7/23命題一定是陳述句，但并非一切陳述句都是命題。命題的真值有時(shí)可明確給出，有時(shí)還需要依靠環(huán)境、條件、實(shí)際情況、時(shí)間才能確定其真值。結(jié)論：在數(shù)理邏輯中像字母“x”、“y”、“z”等字母總是表示變量。約定：2023/7/23下列語(yǔ)句是否是命題？并判斷其真值結(jié)果？（1）四川不是一個(gè)國(guó)家；（2）3既是素?cái)?shù)又是奇數(shù)；（3）張謙是大學(xué)生或是運(yùn)動(dòng)員；（4）如果周末天氣晴朗，則我們將到郊外旅游；（5）2+2<=>4當(dāng)且僅當(dāng)雪是白的。例1.1.22023/7/23 一般來(lái)說(shuō)，命題可分兩種類型：原子命題(簡(jiǎn)單命題)：不能再分解為更為簡(jiǎn)單命題的命題。復(fù)合命題：可以分解為更為簡(jiǎn)單命題的命題。而且這些簡(jiǎn)單命題之間是通過(guò)如“或者”、“并且”、“不”、“如果...則...”、“當(dāng)且僅當(dāng)”等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而構(gòu)成一個(gè)復(fù)合命題。命題的分類2023/7/23今天天氣很冷。今天天氣很冷并且刮風(fēng)。今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。例1.1.3

通常用大寫（或小寫的）的帶或不帶下標(biāo)的英文字母Ａ、Ｂ、Ｃ、...P、Q、R、...Ai、Bi、Ci、...Pi、Qi、Ri、...等表示命題2023/7/23定義：1.1.1命題聯(lián)結(jié)詞設(shè)命題P,Q表示任意兩個(gè)命題,則最常見的命題聯(lián)結(jié)詞有：聯(lián)接詞記號(hào)復(fù)合命題讀法記法真值結(jié)果

3.析取

P或者QP與Q的析取PQP∨Q<=>1P<=>1或Q<=>12.合取

∧P并且QP與Q的合取P∧QP∧Q<=>1P<=>1且Q<=>11.否定

┐非PP的否定┐P┐P<=>1

P<=>04.蘊(yùn)涵→若P,則QP蘊(yùn)涵QP→QP→Q<=>0

P<=>1,Q<=>0?5.等價(jià)

P當(dāng)且僅當(dāng)QP等價(jià)于QP?QPQ<=>1P<=>1,Q<=>1或P<=>0,Q<=>02023/7/23總結(jié)PQ┐PP∧QP∨QP→QP?Q00100110110110100010011011112023/7/23說(shuō)明1、聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)，而非單純的名詞、形容詞、數(shù)詞等地聯(lián)結(jié)；2、聯(lián)結(jié)詞是兩個(gè)句子真值之間的聯(lián)結(jié)，而非句子的具體含義的聯(lián)結(jié)，兩個(gè)句子之間可以無(wú)任何地內(nèi)在聯(lián)系；2023/7/23說(shuō)明3、聯(lián)結(jié)詞與自然語(yǔ)言之間的對(duì)應(yīng)并非一一對(duì)應(yīng)；聯(lián)結(jié)詞自然語(yǔ)言∧既…又…、不僅…而且…、雖然…但是…、并且、和、與，等等；P→Q若P則Q、只要P就Q、P僅當(dāng)Q、只有Q才P、除非Q否則P，等等?等價(jià)、當(dāng)且僅當(dāng)、充分必要、等等；相容（可兼）的或1.否定式與否定聯(lián)結(jié)詞“”記作p，符號(hào)稱作否定聯(lián)結(jié)詞，并規(guī)定p

為真當(dāng)且僅當(dāng)p為假.2.合取式與合取聯(lián)結(jié)詞“∧”

使用合取聯(lián)結(jié)詞時(shí)要注意兩點(diǎn)：(1)描述合取式的靈活性與多樣性

(2)分清簡(jiǎn)單命題與復(fù)合命題例將下列命題符號(hào)化.吳穎既用功又聰明.吳穎不僅用功而且聰明.吳穎雖然聰明，但不用功.張輝與王麗都是三好生.張輝與王麗是同學(xué).（1）－（3）說(shuō)明描述合取式的靈活性與多樣性（4）－（5）要求分清聯(lián)結(jié)詞“與”，聯(lián)結(jié)的復(fù)合命題與簡(jiǎn)單命題將各命題符號(hào)化3.析取式與析取聯(lián)結(jié)詞“∨”記作p∨q，∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假.

注意：此“或”，稱作相容或，也稱可兼或。還有一種“或”，稱作排斥或，也稱作不可兼或。例將下列命題符號(hào)化（1）2或4是素?cái)?shù).（2）2或3是素?cái)?shù).（3）4或6是素?cái)?shù).（4）小元元只能拿一個(gè)蘋果或一個(gè)梨.（5）王小紅生于1975年或1976年.（1）—（3）為相容或（4）—（5）為排斥或4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“”定義1.4設(shè)p,q為二命題，復(fù)合命題“如果p,則q”稱作p與q的蘊(yùn)涵式，記作pq，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，稱作蘊(yùn)涵聯(lián)結(jié)詞，并規(guī)定，pq為假當(dāng)且僅當(dāng)p為真q為假.說(shuō)明：（1）pq的邏輯關(guān)系：q為p的必要條件（2）“如果p,則q的不同表述法很多：若p，就q；只要p，就q；p僅當(dāng)q；只有q，才p；除非q，才p；除非q，否則非p，…．

（3）當(dāng)p為假時(shí)，pq為真，可稱為空證明（4)常出現(xiàn)的錯(cuò)誤：不分充分與必要條件例設(shè)p：天冷，q：小王穿羽絨服，將下列命題符號(hào)化（1）只要天冷，小王就穿羽絨服.（2）因?yàn)樘炖?，所以小王穿羽絨服.（3）若小王不穿羽絨服，則天不冷.（4）只有天冷，小王才穿羽絨服.（5）除非天冷，小王才穿羽絨服.（6）除非小王穿羽絨服，否則天不冷.（7）如果天不冷，則小王不穿羽絨服.（8）小王穿羽絨服僅當(dāng)天冷的時(shí)候.注意：pq與qp等值（真值相同）（1），（2），（3），（6）符號(hào)化為pq其余的符號(hào)化為qp思考，為什么？？5.等價(jià)式與等價(jià)聯(lián)結(jié)詞“”定義1.5設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq，稱作等價(jià)聯(lián)結(jié)詞.并規(guī)定為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假.（1）pq的邏輯關(guān)系：p與q互為充分必要條件（2）pq為真當(dāng)且僅當(dāng)p與q同真或同假例符號(hào)化，并求下列復(fù)合命題的真值（1）2+2＝4當(dāng)且僅當(dāng)3+3＝6.（2）2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).（3）2+2＝4當(dāng)且僅當(dāng)太陽(yáng)從東方升起.（4）2+2＝4當(dāng)且僅當(dāng)美國(guó)位于非洲.（5）函數(shù)f(x)在x0

可導(dǎo)的充要條件是它在x0連續(xù).它們的真值是顯而易見的.什么是必要條件，充分條件，充分必要條件。必要：P→Q

字面理解很容易，沒它不行的意思。用你的題目，P要成立，Q必須要成立，可能還需要其他的條件，P才能成立，但是沒有Q，P肯定是不成立。比如，人活著，喝水這兩件事，喝水就是人活著的必要條件，沒水不行活不了，有水也不一定能活著（必要條件強(qiáng)調(diào)必須要有，沒有不成立，至于有了以后的事情就不關(guān)心了）。

人活著－>要喝水充分：P→Q

P是Q的充分條件，字面去理解（有它就行），有P就一定會(huì)有Q發(fā)生。聯(lián)想：人活著－>要喝水

首先，對(duì)以下三個(gè)詞的釋意要有所明確:(摘自金山詞霸)。

只要：表示具有充分的條件,正句常用“就”、“也”、“都”、“便”相呼應(yīng),表明由這種條件產(chǎn)生的一種結(jié)果。只有：表示必需的條件,下文常用“才”、“方”呼應(yīng)。除非：表示唯一的條件,常跟“才”、“否則”、“不然”等合用,相當(dāng)于“只有”。繼續(xù)解釋：由于“只要”表充分條件（即前件），相當(dāng)于“如果”，根據(jù)定義：

“只要p就q”的數(shù)理邏輯表示是p->q，而“只有”表必要條件（即后件），根據(jù)命題邏輯中相關(guān)的證明（如形式系統(tǒng)N）:p->q等價(jià)于!q->!p（!表聯(lián)結(jié)詞非┐），你也可以通過(guò)真值表進(jìn)行驗(yàn)證。

從而，“只有q才p”的表示是：p->q根據(jù)“除非”與“只有”的等價(jià)性即“除非q，否則p”等價(jià)于“只有q,才p”。

再根據(jù)“除非”與“如果不”、“否則”與否“則”的等價(jià)性（unless<=>ifnot），“除非q，否則p”即可表為!q-->!p，那么，“只有q，才p”也可以表示為!q-->!p，這就證明了“只要p就q”和“只有q才p”的等價(jià)性。

至于“p僅當(dāng)q”它是“只有q才p”的另一種表述，自然也等價(jià)了。

符號(hào)化：A：下雨，B：騎車上班。1、只有不下雨，我才騎自行車上班。

B->┐A2、如果下雨，我就不騎自行車上班。

A->┐B3、除非下雨，否則我騎自行車上班。

B->┐A2023/7/23符號(hào)化下列命題（1）四川不是人口最多的省份；（2）王超是一個(gè)德智體全面發(fā)展的好學(xué)生；（3）教室的燈不亮可能是燈管壞了或者是停電了；（4）如果周末天氣晴朗，那么學(xué)院將組織我們到石像湖春游；（5）兩個(gè)三角形全等當(dāng)且僅當(dāng)三角形的三條邊全部相等。例1.1.42023/7/23例1.1.4解（1）設(shè)Ｐ：四川是人口最多的省份。則命題（1）可表示為┐Ｐ。（2）設(shè)Ｐ：王超是一個(gè)思想品德好的學(xué)生；Ｑ：王超是一個(gè)學(xué)習(xí)成績(jī)好的學(xué)生；

R：王超是一個(gè)體育成績(jī)好的學(xué)生。則命題（2）可表示為Ｐ∧Ｑ∧R。（3）設(shè)Ｐ：教室的燈不亮可能是燈管壞了Ｑ：教室的燈不亮可能是停電了則命題（3）可表示為Ｐ∨Ｑ。2023/7/23（4）設(shè)Ｐ：周末天氣晴朗；Ｑ：學(xué)院將組織我們到石像湖春游。則命題（4）可表示為Ｐ→Ｑ。（5）設(shè)Ｐ：兩個(gè)三角形全等；Ｑ：三角形的三條邊全部相等。則命題（5）可表示為ＰＱ。例1.1.4解(續(xù))2023/7/23

為了不使句子產(chǎn)生混淆，作如下約定，命題聯(lián)結(jié)詞之優(yōu)先級(jí)如下：否定→合取→析取→蘊(yùn)涵→等價(jià)同級(jí)的聯(lián)結(jié)詞，按其出現(xiàn)的先后次序(從左到右)若運(yùn)算要求與優(yōu)先次序不一致時(shí)，可使用括號(hào)；同級(jí)符號(hào)相鄰時(shí)，也可使用括號(hào)。括號(hào)中的運(yùn)算為最優(yōu)先級(jí)。約定2023/7/23設(shè)命題 P：明天上午七點(diǎn)下雨；

Q：明天上午七點(diǎn)下雪； R：我將去學(xué)校。符號(hào)化下述語(yǔ)句：如果明天上午七點(diǎn)不是雨夾雪，則我將去學(xué)校如果明天上午七點(diǎn)不下雨并且不下雪，則我將去學(xué)校如果明天上午七點(diǎn)下雨或下雪，則我將不去學(xué)校明天上午我將雨雪無(wú)阻一定去學(xué)?？煞?hào)化為：

(P∧Q∧R)∨(┐P∧Q∧R)∨

(P∧┐Q∧R)∨(┐P∧┐Q∧R)。

或((P∧Q)∨(┐P∧Q)∨(P∧┐Q)

∨(┐P∧┐Q))∧R。例1.1.5可符號(hào)化為：┐(P∧Q)→R?？煞?hào)化為:(┐P∧┐Q)→R?？煞?hào)化為:(P∨Q)→┐R。2023/7/23例1.1.6設(shè)命題P：你陪伴我；

Q：你代我叫車子；

R：我將出去。

符號(hào)化下述語(yǔ)句：

⑴．除非你陪伴我或代我叫車子，否則我將不出去

⑵．如果你陪伴我并且代我叫輛車子，則我將出去

⑶．如果你不陪伴我或不代我叫輛車子，我將不出去R→(P∨Q)或┐(P∨Q)→┐R(P∧Q)→R(┐P∨┐Q)→┐R2023/7/23例設(shè)P:雪是白色的;Q:2+2<=>4。將下列命題符號(hào)化：（1）因?yàn)檠┦前咨?，所?+2<=>4；（2）如果2+2<=>4，則雪是白色的；（3）只有雪是白色的，才有2+2<=>4；（4）只有2+2<=>4，雪才是白色的；（5）只要雪不是白色的，就有2+2<=>4；（6）除非雪是白色的，否則2+2≠4；（7）雪是白色的當(dāng)且僅當(dāng)2+2<=>4；2023/7/23例設(shè)P:雪是白色的;Q:2+2<=>4。將下列命題符號(hào)化：（1）因?yàn)檠┦前咨?，所?+2<=>4；P→Q（2）如果2+2<=>4，則雪是白色的；Q→P（3）只有雪是白色的，才有2+2<=>4；Q→P（4）只有2+2<=>4，雪才是白色的；P→Q（5）只要雪不是白色的，就有2+2<=>4；

P→Q（6）除非雪是白色的，否則2+2≠4；

P→Q或Q→P（7）雪是白色的當(dāng)且僅當(dāng)2+2<=>4；PQ2023/7/231.1.4命題聯(lián)結(jié)詞的應(yīng)用例1.2.7

用復(fù)合命題表示如下圖所示的開關(guān)電路：

圖1.2.1

圖1.2.2圖1.2.3A∧BA∨BA設(shè)：Ａ：開關(guān)Ｐ閉合；Ｂ：開關(guān)Ｑ閉合。

第一節(jié)小結(jié)1.本小節(jié)中p,q,r,…A,B,C,…均表示命題.2.聯(lián)結(jié)詞集為{,,,,}，每個(gè)聯(lián)結(jié)詞聯(lián)結(jié)的p,pq,pq,pq,pq為基本復(fù)合命題.其中pq最難理解，要特別注意.反復(fù)使用{,,,,}中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.3.設(shè)p:是無(wú)理數(shù)，q:3是奇數(shù)，

r:蘋果是方的，s:太陽(yáng)繞地球轉(zhuǎn)則復(fù)合命題(pq)((rs)p)是假命題.4.聯(lián)結(jié)詞的運(yùn)算順序：,,,,,同級(jí)按先出現(xiàn)者先運(yùn)算.練習(xí)： 課本P12-141～14題2023/7/23第一章第二節(jié)命題公式及其賦值定義1.2.0

一個(gè)特定的命題是一個(gè)命題常項(xiàng)，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一個(gè)任意的沒有賦予具體內(nèi)容的原子命題是一個(gè)變量命題，常稱它為命題變項(xiàng)(或命題變?cè)?，該命題變量無(wú)具體的真值，它的變域是集合{T，F(xiàn)}(或{0，1})注意(1)常項(xiàng)與變項(xiàng)均用p,q,r,…,pi,qi,ri,…,等表示.

(2)復(fù)合命題為命題變?cè)摹昂瘮?shù)”,其函數(shù)值仍為"真"或“假”值。(3)真值函數(shù)或命題公式，沒有確切真值。真值函數(shù)2023/7/231.2.1命題公式定義1.2.1(命題公式/合式公式)1.命題變?cè)旧硎且粋€(gè)公式；2.如G是公式，則(┐G)也是公式；3.如G，H是公式，則(G∧H)、(G∨H)、(G→H)、(GH)也是公式；4.有限次地應(yīng)用（1）-（3）形成的符號(hào)串是公式。2023/7/23符號(hào)串：((P∧(Q∨R))→(Q∧(┐S∨R))))；

(┐P∧Q)；(P→(┐(P∧Q)))；

(((P→Q)∧(R→Q))(P→R))。等都是命題公式。例1.2.1例1.2.2符號(hào)串： (P→Q)∧┐Q)； (P→Q； (┐P∨Q∨(R；

P∨Q∨。等都不是合法的命題公式。2023/7/23例1.2.3試用符號(hào)形式寫出下列命題：（1）雖然今天天氣晴朗，老陳還是不來(lái)；（2）除非你陪伴我或代我叫車子，否則我將不出去；（3）停機(jī)的原因在于語(yǔ)法錯(cuò)誤或者程序錯(cuò)誤；（4）若a和b是偶數(shù)，則a+b是偶數(shù)；（5）我們要做到身體好、學(xué)習(xí)好、工作好，為祖國(guó)四化建設(shè)而奮斗。

2023/7/23例1.2.3解（1）P：今天天氣晴朗,Q：老陳要來(lái),則有：P∧Q；（2）P：你陪伴我；Q：你代我叫車子；R：我出去。則有：R→P∨Q或P∧Q→R；（3）P：停機(jī)的原因在于語(yǔ)法錯(cuò)誤，Q：停機(jī)的原因在于程序錯(cuò)誤，則有：P∧Q；（4）P：a是偶數(shù)；Q：b是偶數(shù)，R：a+b是偶數(shù)，則有：P∧Q→R；（5）P：我們要做到身體好,Q：我們要做到學(xué)習(xí)好,R：我們要做到工作好，S：我們要為祖國(guó)四化建設(shè)而奮斗，則有：P∧Q∧R S。

2023/7/23公式(P∧(Q∨R))→(Q∧(┐S∨R))可表示如下：

(P∧(Q∨R))→(Q∧(┐S∨R))P∧(Q∨R)Q∧(┐S∨R)P

Q∨RQ┐S∨RQ

R

┐SRS例1.2.4注意：幾點(diǎn)說(shuō)明：歸納或遞歸定義元語(yǔ)言與對(duì)象語(yǔ)言外層括號(hào)可以省去定義1.2.2：合式公式的層次

（1）若公式A是單個(gè)的命題變項(xiàng)，則稱A為0層合式.（2）稱A是n+1(n≥0)層公式是指下面情況之一：

(a)A=B,B是n層公式；

(b)A=BC,其中B,C分別為i層和j層公式，且n=max(i,j)；

(c)A=BC,其中B,C的層次及n同(b)；

(d)A=BC,其中B,C的層次及n同(b)；

(e)A=BC,其中B,C的層次及n同(b).（3）若公式A的層次為k,則稱A為k層公式.例如：公式A=p,B=p,C=pq,D=(pq)r,E=((pq)r)(rs)分別為0層，1層，2層，3層，4層公式.2023/7/231.2.2公式的解釋與真值表定義1.2.3設(shè)P1、P2、…、Pn是出現(xiàn)在公式G中的所有命題變?cè)?，指定P1、P2、…、Pn一組真值，則這組真值稱為G的一個(gè)賦值或解釋,常記為Ｉ。

一般來(lái)說(shuō)，若有ｎ個(gè)命題變?cè)?，則應(yīng)有2n個(gè)不同的解釋。

如果公式G在解釋Ｉ下是真的，則稱Ｉ成真賦值；如果G在解釋Ｉ下是假的，則稱Ｉ成假賦值。定義1.2.4

將公式G在其所有可能解釋下的真值情況列成的表，稱為G的真值表。易知000,010,101,110是(pq)r的成真賦值，而001,011,100,111是成假賦值.構(gòu)造真值表的方法：見P9,定義1.91）找出所含全部命題變?cè)?，?0…0開始，直到11…1為止，進(jìn)行賦值。2）從低到高順序?qū)懗龉降母鱾€(gè)層次。3）對(duì)應(yīng)各個(gè)賦值，計(jì)算各層次的真值。注意：公式A與公式B最后一列相同，稱兩公式的真值表相同。2023/7/23例1.2.5求下面公式的真值表：Ｇ<=>(P→((PQ)∧R))∨Q其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命題變?cè)QRPPQ((PQ)∧RP→((PQ)∧R)G000

10

0

11001

100

11010

1

1

0

11011

1

1

1

11100

0

1

0

00101

0

1

1

11110

0

0

0

011110

0

0

012023/7/23例1.2.5（續(xù)）PQR(P→((PQ)∧R))∨Q00010011010101111000101111011111進(jìn)一步化簡(jiǎn)為：2023/7/23例1.2.6PQ(Ｐ→Ｑ)→Ｐ

(Ｐ→Ｑ)∧Ｐ(Ｐ∧Ｑ)(Ｐ→Q)00

1

0001

1

00101

00111

10求下面這組公式的真值表： Ｇ1<=>(Ｐ→Ｑ)→Ｐ；Ｇ2<=>(Ｐ→Ｑ)∧Ｐ；Ｇ3<=>(Ｐ∧Ｑ)(Ｐ→Q)。2023/7/23從這三個(gè)真值表可以看到一個(gè)非常有趣的事實(shí)：公式G1對(duì)所有可能的解釋具有“真”值公式G3對(duì)所有可能的解釋均具有“假”值公式G2則具有“真”和“假”值結(jié)論2023/7/23定義1.2.5公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。公式G稱為永假公式(矛盾式),如果在它的所有解釋之下都為“假”。公式G稱為可滿足的，如果它不是永假的。2023/7/23從上述定義可知三種特殊公式之間的關(guān)系：永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可滿足式,可滿足式不一定是永真式可滿足式的否定不一定為不可滿足式(即為矛盾式)結(jié)論問(wèn)題？（1）如何判斷公式的類型？（2）如何求出公式A的全部成真與成假賦值？幾點(diǎn)說(shuō)明1）熟練之后，真值表的中間有些層次可不寫2）真值表的用途有了公式A的真值表就知道了A的一切信息習(xí)題課第一章的內(nèi)容與要求1.主要內(nèi)容命題、真值、命題的分類、命題符號(hào)化聯(lián)結(jié)詞,,,,及復(fù)合命題符號(hào)化命題公式及層次公式的類型真值表及應(yīng)用2.要求深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系會(huì)求復(fù)合命題的真值熟練地將復(fù)合命題符號(hào)化準(zhǔn)確地求公式的真值表，并用它求公式成真與成假賦值及判斷公式類型二、練習(xí)題1.將下列命題符號(hào)化

1）豆沙包是由面粉和紅小豆做成的.

2）蘋果樹和梨樹都是落葉喬木.

3）王小紅或李大明是物理組成員.

4）王小紅或李大明中的一人是物理組成員.

5）由于交通阻塞，他遲到了.

6）如果交通不阻塞，他就不會(huì)遲到.

7）他沒遲到，所以交通沒阻塞.

8）除非交通阻塞，否則他不會(huì)遲到.

9）他遲到當(dāng)且僅當(dāng)交通阻塞.提示：分清復(fù)合命題與簡(jiǎn)單命題分清相容或與排斥或分清必要與充分條件及必要充分條件答案：（1）是簡(jiǎn)單命題（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）請(qǐng)分別寫出（1）-（4）的符號(hào)化形式設(shè)p:交通阻塞，q:他遲到（5）

pq,（6）pq或qp（7）qp

或pq,（8）qp或pq（9）pq

或pq可見（5）與（7），（6）與（8）相同（等值）2.設(shè)p:2是素?cái)?shù)q:北京比天津人口多r:美國(guó)的首都是舊金山求下面命題的真值:(pq)r(qr)(pr)(qr)(pr)(qp)((pr)(rq))提示：p,q為真命題，r是假命題反復(fù)用基本復(fù)合命題的真值求解（心算即可）答案：真值分別為0,1,0,03.用真值表判斷下面公式的類型1）pr(qp)2）((pq)(qp))r3）(pq)(pr)提示：按層次寫真值表，由最后一列判類型答案：（1）為矛盾式，（2）為重言式，（3）為可滿足式第二章命題邏輯等值（等價(jià)）演算1.本章的主要內(nèi)容：等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式，主析取范式與主合取范式聯(lián)結(jié)詞完備集2.本章與其他各章的聯(lián)系是第一章的抽象與延伸是后續(xù)各章的先行準(zhǔn)備第二章命題邏輯等值（等價(jià)）演算2.0

等值式（等價(jià)式）

補(bǔ)充定義：?jiǎn)≡ㄐ露x）設(shè)公式A,B中含有命題變?cè)狿1，P2，…Pn。而A或B不全含有這些變?cè)?，比如，A中不含Pi，Pi+1，…Pn,i≥5，稱這些變?cè)獮锳的啞元。從而，A的取值與啞元無(wú)關(guān)，在討論A與B是否有相同真值表時(shí)，可將A,B都看成P1，P2，…Pn的公式。2023/7/23例2.0寫出下列公式的真值表，并驗(yàn)證其公式是重言式、矛盾式、可滿足公式。（1）G1<=>(Ｐ→Ｑ)(Ｐ∨Ｑ)；（2）G2<=>(ＰQ)((Ｐ→Q)∨(Q→Ｐ))；（3）G3<=>(P→Q)∨Q。2023/7/23例2.0解PQ(Ｐ→Ｑ)(Ｐ∨Ｑ)(Ｐ

Q)(Ｐ→Q)∨(Q→Ｐ)(P→Q)∨Q001

0

1011

0

1101

0

11110

0永真公式永假公式可滿足公式三個(gè)公式的真值表如下：2023/7/23若將其看成兩個(gè)公式，分別令：

Ｇ<=>Ｐ→Ｑ，Ｈ<=>┐Ｐ∨Ｑ。則ＧＨ是一個(gè)永真公式，即這兩個(gè)公式對(duì)任何解釋都必同為真假，此時(shí)，說(shuō)Ｇ和Ｈ相等，記為Ｇ<=>Ｈ。為此可定義：分析公式定義2.1若式AB是重言式，則稱A與B等值（等價(jià)），記作AB，并稱AB是等值式（等價(jià)式）。幾點(diǎn)說(shuō)明：定義中，A,B,均為元語(yǔ)言符號(hào)A或B中可能有啞元出現(xiàn).例如，在

(pq)((pq)(rr))中，r為左邊公式的啞元.

用真值表可驗(yàn)證兩個(gè)公式是否等值。請(qǐng)驗(yàn)證：p(qr)(pq)r

p(qr)?(pq)r2023/7/23

首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式GH是命題公式，其中“”是一種邏輯運(yùn)算，GH的結(jié)果仍是一個(gè)命題公式。而邏輯等價(jià)“<=>”則是描述了兩個(gè)公式G與H之間的一種邏輯等價(jià)關(guān)系，G<=>H表示“命題公式G等價(jià)于命題公式H”，G<=>H的結(jié)果不是命題公式。

其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式G、H是否邏輯等價(jià)，即G<=>H那是辦不到的，然而計(jì)算機(jī)卻可“計(jì)算”公式GH是否是永真公式。

注意：“<=>”

與“”的區(qū)別2023/7/232.1“<=>”的性質(zhì)由于“<=>”不是一個(gè)聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個(gè)性質(zhì)：（1）自反性G<=>G；（2）對(duì)稱性若G<=>H，則H<=>G；（3）傳遞性若G<=>H，H<=>S，則G<=>S。這三條性質(zhì)體現(xiàn)了“<=>”的實(shí)質(zhì)含義?；镜牡戎担ǖ葍r(jià)）式E1雙重否定律AAE2冪等律AAA,AAAE3交換律ABBA,ABBAE4結(jié)合律(AB)CA(BC),(AB)CA(BC)E5分配律A(BC)(AB)(AC),A(BC)(AB)(AC)E6德摩根律(AB)AB

(AB)ABE7吸收律A(AB)A,A(AB)AE8零律A11,A00E9同一律A0A.A1AE10排中律AA1E11矛盾律AA0E12蘊(yùn)涵等值式ABABE13等價(jià)等值式AB(AB)(BA)E14假言易位ABBAE15等價(jià)否定等值式ABABE16歸謬論(AB)(AB)A注意：要牢記各個(gè)等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)。2023/7/23例2.1

證明公式G1=(ＰＱ)與公式G2=(P→Q)∧(Q→P)之間是邏輯等價(jià)的。解：根據(jù)定理3.3.1，只需判定公式G3=(ＰＱ)((P→Q)∧(Q→P))為永真公式。PQG3<=>(ＰＱ)((Ｐ→Q)∧(Q→Ｐ))00

1111101

0110010

0100111

111112023/7/23這種圖是將G，H理解為某總體論域上的子集合，而規(guī)定G∧H為兩集合的公共部分（交集合），G∨H為兩集合的全部（并集合），┐G為總體論域（如矩形域）中G的補(bǔ)集，將命題中的真值“1”理解為集合中的總體論域（全集），將命題中的真值“0”理解為集合中的空集，則有：

G∧HG∨H┐GUABUABUA命題與集合之間的關(guān)系，加深演算的理解“∪”對(duì)“∨”與“∩”對(duì)“∧”的對(duì)比等冪律Ａ∪Ａ<=>Ａ;Ａ∩Ａ<=>Ａ

G∨G<=>G；G∧G<=>G交換律Ａ∪Ｂ<=>Ｂ∪ＡＡ∩Ｂ<=>Ｂ∩Ａ

G∨H<=>H∨GG∧H<=>H∧G結(jié)合律A∪(B∪C)<=>(A∪B)∪CA∩(B∩C)<=>(A∩B)∩CG∨(H∨S)<=>(G∨H)∨SG∧(H∧S)<=>(G∧H)∧S恒等律Ａ∪Φ<=>Ａ；Ａ∩Ｕ<=>Ａ；G∨０<=>G；G∧１<=>G零律Ａ∪Ｕ<=>Ｕ；Ａ∩Φ<=>ΦG∨１<=>１；G∧０<=>０吸收律A∩(A∪B)<=>AA∪(A∩B)<=>AG∨(G∧H)<=>G；G∧(G∨H)<=>G；否定律┐(┐G)<=>G分配律A∩(B∪C)<=>(A∩B)∪(A∩C)A∪(B∩C)<=>(A∪B)∩(A∪C)G∨(H∧S)<=>(G∨H)∧(G∨S)G∧(H∨S)<=>(G∧H)∨(G∧S)2.2等值演算與置換規(guī)則1.等值演算——由已知的等值式推演出新的等值式的過(guò)程2.等值演算的基礎(chǔ)：（1）等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞性（2）基本的等值式（3）置換規(guī)則（見3）3．置換規(guī)則設(shè)(A)是含公式A的命題公式，(B)是用公式B置換了(A)中的所有的A后得到的命題公式，若BA，則(B)(A)2.3等值演算的應(yīng)用舉例1．證明兩個(gè)公式等值（等價(jià)）例證明p(qr)(pq)r證p(qr)

p(qr)（蘊(yùn)涵等值式，置換規(guī)則）

(pq)r

（結(jié)合律，置換規(guī)則）

(pq)r

（德摩根律，置換規(guī)則）

(pq)r

（蘊(yùn)涵等值式，置換規(guī)則）幾點(diǎn)說(shuō)明：也可以從右邊開始演算因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出用等值演算不能直接證明兩個(gè)公式不等值例證明p(qr)?(pq)r證方法一真值表法（自己證）方法二觀察賦值法.易知000,010等是左邊的成真賦值，是右邊的成假賦值方法三用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察

2.判斷公式類型例用等值演算法判斷下列公式的類型（1）q(pq)（2）(pq)(qp)（3）((pq)(pq))r)解（1）q(pq)

q(pq)（蘊(yùn)涵等值式）

q(pq)（德摩根律）

p(qq)（交換律，結(jié)合律）

p0（矛盾律）

0（零律）由最后一步可知，（1）為矛盾式.（2）(pq)(qp)

(pq)(qp)（蘊(yùn)涵等值式）

(pq)(pq)（交換律）

1由最后一步可知，（2）為重言式.問(wèn)：最后一步為什么等值于1？說(shuō)明：（2）的演算步驟可長(zhǎng)可短，以上演算最省.

（3）((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可滿足式，其實(shí)101,111是成真賦值，000,010等是成假賦值.總結(jié)：從此例可看出A為矛盾式當(dāng)且僅當(dāng)A0A為重言式當(dāng)且僅當(dāng)A13．解判定問(wèn)題見書上P21，例2.62023/7/23例

利用基本的等價(jià)關(guān)系，完成如下工作：（1）判斷公式的類型：證明((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)是一個(gè)永真公式。（2）證明公式之間的等價(jià)關(guān)系：證明Ｐ→(Ｑ→Ｒ)<=>(Ｐ∧Ｑ)→Ｒ（3）化簡(jiǎn)公式：證明(P∧(Ｑ∧R))∨((Ｑ∧R)∨(P∧R))<=>R2023/7/23證明（1）((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)<=>((Ｐ∨Ｑ)∧(Ｐ∨(Ｑ∧Ｒ)))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))<=>((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))<=>((Ｐ∨Ｑ)∧(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨(

(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))<=>((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))<=>T

即:((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)為永真公式；

2023/7/23證明（續(xù)）（2）P→(Q→R)<=>P∨(Q→R)<=>P∨(Q∨R)<=>(P∨Q)∨R<=>(P∧Q)∨R<=>(P∧Q)→R

即有:P→(Q→R)<=>(P∧Q)→R；

（3）(P∧(Q∧R))∨((Q∧R)∨(P∧R))<=>(P∧Q)∧R)∨((Q∨P)∧R)<=>((P∨Q)∧R)∨((Q∨P)∧R)<=>((P∨Q)∨(Q∨P))∧R<=>T∧R<=>R

即有:(P∧(Q∧R))∨((Q∧R)∨(P∧R))<=>R。2023/7/23實(shí)際應(yīng)用舉例例

利用基本的等價(jià)關(guān)系，化簡(jiǎn)下列電路圖RPSQPSPQRP解：上述電路圖可描述為：（1）((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S))2023/7/23例（續(xù)）利用基本等價(jià)關(guān)系，化簡(jiǎn)公式(1)可得：（1）((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S))<=>((P∧Q∧(R∨S))∧(P∧(R∨S))<=>P∧Q∧(R∨S)；

SRQP2023/7/23例

將下面程序語(yǔ)言進(jìn)行化簡(jiǎn)。IfAthenifBthenXelseYelseifBthenXelseY

TFFTFTStartAXYEndBB

解：執(zhí)行X的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)執(zhí)行Y的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)2023/7/23例(續(xù)）執(zhí)行X的條件可化簡(jiǎn)為：(Ａ∧Ｂ)∨(Ａ∧Ｂ)<=>Ｂ∧(Ａ∨Ａ)<=>Ｂ執(zhí)行Y的條件可化簡(jiǎn)為：(Ａ∧Ｂ)∨(Ａ∧Ｂ)<=>Ｂ∧(Ａ∨Ａ)<=>ＢTXYEndStartAF程序可簡(jiǎn)化為：IfBthenXelseY

2023/7/232.4析取范式與合取范式一、析取范式與合取范式1.基本概念（1）文字——命題變項(xiàng)及其否定的總稱（2）簡(jiǎn)單析取式——有限個(gè)文字構(gòu)成的析取式p,q,pq,pqr,…（3）簡(jiǎn)單合取式——有限個(gè)文字構(gòu)成的合取式p,q,pq,pqr,…（4）析取范式——由有限個(gè)簡(jiǎn)單合取式組成的析取式

A1A2Ar(r1)（5）合取范式——由有限個(gè)簡(jiǎn)單析取式組成的合取式

A1A2Ar(r1)（6）范式——析取范式與合取范式的總稱說(shuō)明：?jiǎn)蝹€(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式形如pqr,pqr的公式既是析取范式，又是合取范式主要性質(zhì)：簡(jiǎn)單析取式與簡(jiǎn)單合取式的性質(zhì)，見定理2.1析取范式與合取范式的性質(zhì)，見定理2.22.命題公式的范式

(1)公式A的析取范式：由有限個(gè)簡(jiǎn)單合取式的析取構(gòu)成的命題公式稱為析取范式

(2)公式A的合取范式：由有限個(gè)簡(jiǎn)單析取式的合取構(gòu)成的命題公式稱為合取范式

(3)公式范式存在定理：定理2.3任何命題公式都存在著與之等值的析取范式與合取范式(4)求公式A的范式的步驟：

a.消去A中的,（若存在）

b.否定聯(lián)結(jié)詞的內(nèi)移或消去

c.使用分配律

對(duì)分配（析取范式）

對(duì)分配（合取范式）(5)公式的范式存在，但不惟一，這是它的局限性3.求公式的范式舉例例求下列公式的析取范式與合取范式（1）A=(pq)r（2）B=(pq)r解（1）(pq)r(pq)r

（消去）

pqr

（結(jié)合律）注意：最后結(jié)果既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）（2）(pq)r(pq)r

（消去第一個(gè)）

(pq)r

（消去第二個(gè)）

(pq)r

（否定號(hào)內(nèi)移——德摩根律）最后一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）繼續(xù)：B(pq)r

(pr)(qr)（對(duì)分配律）最后一步已為合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成）二、主析取范式與主合取范式1.極小項(xiàng)與極大項(xiàng)定義2.4在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式（簡(jiǎn)單析取式）中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）。幾點(diǎn)說(shuō)明：n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示.Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示,mi（Mi）稱為極小項(xiàng)（極大項(xiàng)）的名稱.由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)由下表給出:極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱pqpqpqpq

00011011m0m1m2m3

pq

pqpqpq

00011011M0M1M2M3由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)由下表給出.極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱p

qrp

q

rp

q

rp

q

rp

qrp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7

p

q

r

p

q

r

p

q

r

p

qrp

q

rp

q

rp

q

rp

qr000001010011100101110111M0M1M2M3M4M5M6M7mi與Mi的關(guān)系由書上定理2.4給出，即mi

Mi,Mi

mi

2.主析取范式與主合取范式定義(1)主析取范式——由極小項(xiàng)構(gòu)成的析取范式(2)主合取范式——由極大項(xiàng)構(gòu)成的合取范式例如，n=3,命題變項(xiàng)為p,q,r時(shí)，(p

q

r)(p

q

r)

m1m3—主析取范式(p

q

r)(p

q

r)

M7M1—主合取范式

3.命題公式A的主析取范式與主合取范式(1)與A等值的主析取范式稱為A的主析取范式；(2)與A等值的主合取范式稱為A的主合取范式.(3)主析取范式的存在惟一定理定理2.5：任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的4.用等值演算法求公式的主范式的步驟：（1）先求析取范式（合取范式）（2）將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn)單析取式）化成與之等值的若干個(gè)極小項(xiàng)之析?。O大項(xiàng)之合?。?，利用的等值式為同一律（零律）、排中律（矛盾律）、分配律、冪等律等.（3）極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序.例求公式A=(pq)r的主析取范式與主合取范式.（1）求主析取范式(pq)r

(pq)r

（析取范式）①對(duì)

(pq)

(pq)(rr)(pqr)(pqr)

m6m7②

對(duì)r

(pp)(qq)r

(pqr)(pqr)(pqr)(pqr)

m1m3m5m7③②,③代入①并排序，得(pq)r

m1m3m5m6m7

（主析取范式）（2）求A的主合取范式(pq)r