離散數(shù)學(xué)教案

離散數(shù)學(xué)教案PAGEPAGE10《離散數(shù)學(xué)》教學(xué)教案第一部分課程總論一、課程簡介課程名稱：離散數(shù)學(xué)英文名稱：DiscreteMathematics離散數(shù)學(xué)：離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，是計算機(jī)科學(xué)的核心課程。以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對象是有限個或無限個元素。離散數(shù)學(xué)與計算機(jī)科學(xué)中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯理論、算法分析、邏輯設(shè)計、系統(tǒng)結(jié)構(gòu)、容錯診斷、機(jī)器定理證明等課程緊密相關(guān)。是一門重要的基礎(chǔ)課程。教學(xué)內(nèi)容：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)與布爾代數(shù)、圖論和在計算機(jī)中的應(yīng)用共五部分。其中第五部分不做考試要求，不占計劃內(nèi)學(xué)時，可在第三學(xué)期安排講座課講授。教學(xué)要求：通過該課程的學(xué)習(xí)，培養(yǎng)和鍛煉抽象思維和縝密概括的能力，為專業(yè)基礎(chǔ)課和專業(yè)課的學(xué)習(xí)打下堅實的理論基礎(chǔ)。授課總學(xué)時：3學(xué)時/周18周=54學(xué)時二、適用對象本課程教學(xué)教案主要針對計算機(jī)科學(xué)與技術(shù)本科專業(yè)三、學(xué)習(xí)要領(lǐng)概念（正確）：必須掌握好離散數(shù)學(xué)中大量的概念判斷（準(zhǔn)確）：根據(jù)概念對事物的屬性進(jìn)行判斷推理（可靠）：根據(jù)多個判斷推出一個新的判斷四、離散數(shù)學(xué)與計算機(jī)的關(guān)系第一部分?jǐn)?shù)理邏輯計算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物第二部分集合論集合：一種重要的數(shù)據(jù)結(jié)構(gòu)關(guān)系：關(guān)系數(shù)據(jù)庫的理論基礎(chǔ)函數(shù)：所有計算機(jī)語言中不可缺少的一部分第三部分代數(shù)系統(tǒng)計算機(jī)編碼和糾錯碼理論數(shù)字邏輯設(shè)計基礎(chǔ)計算機(jī)使用的各種運(yùn)算第四部分圖論數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計算機(jī)網(wǎng)絡(luò)原理的基礎(chǔ)五、教材及主要參考書教材：離散數(shù)學(xué)（第四版）耿素云曲婉玲張立昂參考書：[1] 王元元、張桂蕓，離散數(shù)學(xué)導(dǎo)論，科學(xué)出版社，2002[2] 左孝凌、李為鑑、劉永才，離散數(shù)學(xué)，上海科學(xué)技術(shù)出版社，1982年9月第1版。[3] 王元元、張桂蕓，計算機(jī)科學(xué)中的離散結(jié)構(gòu)，機(jī)械工業(yè)出版社，2004[4]BernardKolman,RobertC.Busby,SharonRoss,DiscreteMathematicalStructures(FourthEdition),高等教育出版社，2001[5] 孫吉貴楊鳳杰歐陽丹彤李占山，離散數(shù)學(xué)，高等教育出版社，2002[6] 馬振華，離散數(shù)學(xué)導(dǎo)引，清華大學(xué)出版社，1993[7] 王樹禾，離散數(shù)學(xué)引論，中國科技大學(xué)出版社，2001[8]AndrewSimpon著馮速譯離散數(shù)學(xué)導(dǎo)學(xué)機(jī)械工業(yè)出版社2005第二部分課程內(nèi)容與要求《離散數(shù)學(xué)》為計算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要基礎(chǔ)理論課。它以研究離散量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)。離散數(shù)學(xué)的內(nèi)容十分豐富和廣泛，本課程選擇與計算機(jī)科學(xué)中相關(guān)的最基本最重要的數(shù)學(xué)課題進(jìn)行系統(tǒng)的論述，為研究計算機(jī)科學(xué)提供理論基礎(chǔ)和工具，為學(xué)習(xí)有關(guān)專業(yè)課，如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、人工智能等，作必要的數(shù)學(xué)準(zhǔn)備。同時，通過離散數(shù)學(xué)的學(xué)習(xí)，培養(yǎng)學(xué)生抽象思維和邏輯推理的能力。課程內(nèi)容對每一個從事計算機(jī)技術(shù)的人都要求掌握和了解。因為在形式證明、驗證、密碼學(xué)的研究與學(xué)習(xí)中要有理解形式證明的能力；圖論的概念被用于計算機(jī)網(wǎng)絡(luò)、操作系統(tǒng)和程序設(shè)計語言的編譯系統(tǒng)等領(lǐng)域；集合論的概念、關(guān)系代數(shù)等在軟件工程和數(shù)據(jù)庫中也會用到?？傊?，為了適應(yīng)計算技術(shù)的要求及將來的發(fā)展，學(xué)生需要對離散結(jié)構(gòu)有比較深入的理解。000本課程教學(xué)內(nèi)容注重培養(yǎng)學(xué)生抽象思維能力和邏輯推理的能力。在教學(xué)中把教改、教研最新的研究成果及本學(xué)科最新發(fā)展成果引入教學(xué)，不斷地修改和調(diào)整教學(xué)內(nèi)容，取得了良好的效果。第一篇數(shù)理邏輯邏輯學(xué)（logic）是一門研究思維形式及思維規(guī)律的科學(xué)。數(shù)理邏輯（mathematicallogic)是用數(shù)學(xué)的方法來研究人類推理過程的一門數(shù)學(xué)學(xué)科。其顯著特征是符號化和形式化，即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公理體系來刻劃,并基于符號串形式的演算來描述推理過程的一般規(guī)律。數(shù)理邏輯又稱符號邏輯、現(xiàn)代邏輯。命題邏輯一、學(xué)習(xí)目的與要求本章目的是介紹命題邏輯的基本概念。掌握利用命題邏輯表示自然語言，描述概念、判斷和推理。建立初步的語言形式化方法。二、知識點(diǎn)1．命題的概念、表示方法；聯(lián)結(jié)詞的邏輯意義。2．命題公式的遞歸定義，自然語言翻譯成命題公式3．真值表的構(gòu)造、命題公式等價的概念。4．重言式與蘊(yùn)涵式的定義、邏輯意義，邏輯等價與邏輯蘊(yùn)涵的意義和證明方法。常用的邏輯等價公式和邏輯蘊(yùn)涵公式。5．命題公式的對偶式、合取范式、析取范式、主合取范式、主析取范式。邏輯小項、邏輯大項。任給公式化為析取范式、任給公式化為主析取范式、任給公式化為合取范式、任給公式化為主合取范式。6．命題邏輯的推理理論，主要的推理方法：真值表法、直接證明法、間接證明法。常用推理規(guī)則：P規(guī)則、T規(guī)則、CP規(guī)則。7．命題邏輯的應(yīng)用示例。三、要求1．識記命題表示方法、真值判斷、命題公式的遞歸定義。2．領(lǐng)會聯(lián)結(jié)詞真值確定、翻譯、命題公式的等價性和蘊(yùn)涵性證明、任給公式化為析取范式、任給公式化為主析取范式、任給公式化為合取范式、任給公式化為主合取范式。3．簡單應(yīng)用命題邏輯推理規(guī)則，命題邏輯設(shè)計簡單的開關(guān)電路。四、主要內(nèi)容第1章 命題邏輯命題邏輯，也稱命題演算，記為Ls。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)學(xué)方法即通過引入表意符號研究推理的學(xué)問。因此，數(shù)理邏輯又名為符號邏輯。命題邏輯是研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系。1.1 命題與聯(lián)結(jié)詞１.命題的概念所謂命題，是指具有非真必假的陳述句。而疑問句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。命題僅有兩種可能的真值—真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命題只有兩種真值，所以稱這種邏輯為二值邏輯。命題的真值是具有客觀性質(zhì)的，而不是由人的主觀決定的。如果一陳述句再也不能分解成更為簡單的語句，由它構(gòu)成的命題稱為原子命題。原子命題是命題邏輯的基本單位。命題分為兩類：第一類是原子命題，原子命題用大寫英文字母P，Q，R…及其帶下標(biāo)的Pi，Qi，Ri，…表示。第二類是復(fù)合命題，它由原子命題、命題聯(lián)結(jié)詞和圓括號組成。２.命題聯(lián)結(jié)詞定義1.1.1 設(shè)P表示一個命題，由命題聯(lián)結(jié)詞┐和命題P連接成┐P，稱┐P為P的否定式復(fù)合命題，┐P讀“非P”。稱┐為否定聯(lián)結(jié)詞。┐P是真，當(dāng)且僅當(dāng)P為假；┐P是假，當(dāng)且僅當(dāng)P為真。否定聯(lián)結(jié)詞“┐”的定義可由表1.1.1表示之。由于否定”修改了命題，它是對單個命題進(jìn)行操作，稱它為一元聯(lián)結(jié)詞。定義1.1.2 設(shè)P和Q為兩個命題，由命題聯(lián)結(jié)詞∧將P和Q連接成P∧Q，稱P∧Q為命題P和Q的合取式復(fù)合命題，P∧Q讀做“P與Q”，或“P且Q”。稱∧為合取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q的真值同為真，命題P∧Q的真值才為真；否則，P∧Q的真值為假。合取聯(lián)結(jié)詞∧的定義由表1.1.2表示之。定義1.1.3 設(shè)P和Q為兩個命題，由命題聯(lián)結(jié)詞∨把P和Q連接成P∨Q，稱P∨Q為命題P和Q的析取式復(fù)合命題，P∨Q讀做“P或Q”。稱∨為析取聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P和Q的真值同為假，P∨Q的真值為假；否則，P∨Q的真值為真。析取聯(lián)結(jié)詞∨的定義由表1.1.3表示之。由定義可知，析取聯(lián)結(jié)詞表示“可兼和”，“不可兼和”另有別的聯(lián)結(jié)詞定義之。與合取聯(lián)結(jié)詞一樣，使用析取聯(lián)結(jié)詞時，也不要求兩命題間一定有任何關(guān)系，有關(guān)例子就不再給出了。定義1.1.4 設(shè)P和Q為兩個命題，由命題聯(lián)結(jié)詞→把P和Q連接成P→Q，稱P→Q為命題P和Q的條件式復(fù)合命題，簡稱條件命題。P→Q讀做“P條件Q”或者“若P則Q”。稱→為條件聯(lián)結(jié)詞。當(dāng)P的真值為真而Q的真值為假時，命題P→Q的真值為假；否則，P→Q的真值為真。條件聯(lián)結(jié)詞→的定義由表1.1.4表示之。在條件命題P→Q中，命題P稱為P→Q的前件或前提，命題Q稱為P→Q的后件或結(jié)論。條件命題P→Q有多種方式陳述：“如果P，那么Q”；“P僅當(dāng)Q”；“Q每當(dāng)P”；“P是Q的充分條件”；“Q是P的必要條件”等。在日常生活中，用條件式表示前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系，如例1.1.4中的①，這種條件式稱為形式條件命題。然而在命題邏輯中，一個條件式的前提并不要求與結(jié)論有任何關(guān)系，這種條件式稱為實質(zhì)條件命題。采用實質(zhì)條件式作定義，不單是出于“善意推斷”，主要是因為前提與結(jié)論間有無因果和實質(zhì)關(guān)系難以區(qū)分，而且實質(zhì)條件式已包含了形式條件式，更便于應(yīng)用。定義1.1.5 令P、Q是兩個命題，由命題聯(lián)結(jié)詞把P和Q連接成PQ，稱PQ為命題P和Q的雙條件式復(fù)合命題，簡稱雙條件命題，PQ讀做“P當(dāng)且僅當(dāng)Q”，或“P等價Q”。稱為雙條件聯(lián)結(jié)詞。當(dāng)P和Q的真值相同時，PQ的真值為真；否則，PQ的真值為假。雙條件聯(lián)結(jié)詞的定義由表1.1.5表示之。在本節(jié)結(jié)束時，應(yīng)強(qiáng)調(diào)指出的是：復(fù)合命題的真值只取決于各原子命題的真值，而與它們的內(nèi)容、含義無關(guān)，與原子命題之間是否有關(guān)系無關(guān)。理解和掌握這一點(diǎn)是至關(guān)重要的，請讀者認(rèn)真去領(lǐng)會。1.2命題變元和合式公式１.命題變元在命題邏輯中，命題又有命題常元和命題變元之分。一個確定的具體的命題，稱為命題常元；一個不確定的泛指的任意命題，稱為命題變元。顯然，命題變元不是命題，只有用一個特定的命題取代才能確定它的真值：真或假。這時也說對該命題變元指派真值。命題常元和命題變元均可用字母P等表示。由于在命題邏輯中并不關(guān)心具體命題的涵義，只關(guān)心其真值，因此，可以形式地定義它們?nèi)缦拢憾x1.2.1 以真或1、假或0為其變域的變元，稱為命題變元；真或1、假或0稱為命題常元。2. 合式公式通常把含有命題變元的斷言稱為命題公式。但這沒能指出命題公式的結(jié)構(gòu)，因為不是所有由命題變元、聯(lián)結(jié)詞和括號所組成的字符串都能成為命題公式。為此常使用歸納定義命題公式，以便構(gòu)成的公式有規(guī)則可循。由這種定義產(chǎn)生的公式稱為合式公式。定義1.2.2 單個命題變元和命題常元稱為原子命題公式，簡稱原子公式。定義1.2.3 合式公式是由下列規(guī)則生成的公式：①單個原子公式是合式公式。②若A是一個合式公式，則(lA)也是一個合式公式。③若A、B是合式公式，則(A∧B)、(A∨B)、(A→B)和(AB)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。當(dāng)合式公式比較復(fù)雜時，常常使用很多圓括號，為了減少圓括號的使用量，可作以下約定：①規(guī)定聯(lián)結(jié)詞的優(yōu)先級由高到低的次序為：┐、∧、∨、→、②相同的聯(lián)結(jié)詞按從左至右次序計算時，圓括號可省略。③最外層的圓括號可以省略。為了方便計，合式公式也簡稱公式。３. 公式真值表定義1.2.4 對于公式中命題變元的每一種可能的真值指派，以及由它們確定出的公式真值所列成的表，稱為該公式的真值表。定義1.2.5 如果B是公式A中的一部分，且B為公式，則稱B是公式A的子公式。用歸納法不難證明，對于含有n個命題變元的公式，有2n個真值指派，即在該公式的真值表中有2n行。為方便構(gòu)造真值表，特約定如下：①命題變元按字典序排列。②對每個指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。③若公式較復(fù)雜，可先列出各子公式的真值(若有括號，則應(yīng)從里層向外層展開)，最后列出所求公式的真值。4. 命題的符號化把一個用文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識符、聯(lián)結(jié)詞和圓括號表示的合式公式，稱為命題的符號化。符號化應(yīng)該注意下列事項:①確定給定句子是否為命題。②句子中連詞是否為命題聯(lián)結(jié)詞。③要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。命題符號化是很重要的，一定要掌握好，在命題推理中常常最先遇到的就是符號化一個問題，解決不好，等于說推理的首要前提沒有了。1.3公式分類與等價公式１.公式分類定義1.3.1 設(shè)A為任意公式，則①對應(yīng)每一個指派，公式A均相應(yīng)確定真值為真，稱A為重言式，或永真式。②對應(yīng)每一個指派，公式A均相應(yīng)確定真值為假，稱A為矛盾式，或永假式。③至少存在一個指派，公式A相應(yīng)確定真值為真，稱A為可滿足式。由定義可知，重言式必是可滿足式，反之一般不真。重點(diǎn)將研究重言式，它最有用，因為它有以下特點(diǎn)：①重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。②兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)雜的重言式。③由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價式和蘊(yùn)涵式。判定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。在Ls中，由于任何一個命題公式的指派數(shù)目總是有限的，所以Ls的判定問題是可解的。其判定方法有真值表法和公式推演法。２. 等價公式定義1.3.2 設(shè)A和B是兩個命題公式，如果A、B在其任意指派下，其真值都是相同的，則稱A和B是等價的，或邏輯相等，記作AB，讀作A等價B，稱AB為等價式。顯然，若公式A和B的真值表是相同的，則A和B等價。因此，驗證兩公式是否等價，只需做出它們的真值表即可。在這里，請讀者注意和的區(qū)別與聯(lián)系。區(qū)別：是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語言中的符號，它出現(xiàn)在命題公式中；不是邏輯聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個命題公式的一種關(guān)系，不屬于這兩個公式的任何一個公式中的符號。聯(lián)系：可用下面定理表明之。定理1.3.1 AB當(dāng)且僅當(dāng)AB是永真式。有時也稱AB是永真雙條件式。等價式有下列性質(zhì)：①自反性，即對任意公式A，有AA。②對稱性，即對任意公式A和B，若AB，則BA。③傳遞性，即對任意公式A、B和C，若AB、BC，則AC。３.基本等價式——命題定律在判定公式間是否等價，有一些簡單而又經(jīng)常使用的等價式，稱為基本等價式或稱命題定律。牢固地記住它并能熟練運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀者應(yīng)該注意到這一點(diǎn)?，F(xiàn)將這些命題定律列出如下：(1)雙否定：AA。(2)交換律：A∧BB∧A，A∨BB∨A，ABBA。(3)結(jié)合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)等冪律：A∧AA，A∨AA。(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互補(bǔ)律：A∧AF，(矛盾律)，A∨AT。(排中律)(11)條件式轉(zhuǎn)化律：A→BA∨B，A→BB→A。(12)雙條件式轉(zhuǎn)化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)(13)輸出律：(A∧B)→CA→(B→C)。(14)歸謬律：(A→B)∧(A→B)A。上面這些定律，即是通常所說的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。４.代入規(guī)則和替換規(guī)則在定義合成公式時，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用，因此有人也將它們看成運(yùn)算，這不無道理，而且在今后討論中，它的作用也是不容忽視的。(1)代入規(guī)則定理1.3.2在一個永真式A中，任何一個原子命題變元R出現(xiàn)的每一處，用另一個公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。(2)替換規(guī)則定理1.3.3設(shè)A1是合式公式A的子公式，若A1B1，并且將A中的A1用B1替換得到公式B，則AB。稱該定理為替換規(guī)則。滿足定理1.3.3條件的替換，稱為等價替換。代入和替換有兩點(diǎn)區(qū)別：①代入是對原子命題變元而言的，而替換可對命題公式實行。②代入必須是處處代入，替換則可部分替換，亦可全部替換。1.4對偶式與蘊(yùn)涵式１. 對偶式在上節(jié)介紹的命題定律中，多數(shù)是成對出現(xiàn)的，這些成對出現(xiàn)的定律就是對偶性質(zhì)的反映，即對偶式。利用對偶式的命題定律，可以擴(kuò)大等價式的個數(shù)，也可減少證明的次數(shù)。定義1.4.1在給定的僅使用聯(lián)結(jié)詞、∧和∨的命題公式A中，若把∧和∨互換，F(xiàn)和T互換而得到一個命題公式A*，則稱A*為A的對偶式。顯然，A也是A*的對偶式?？梢夾與A*互為對偶式。定理1.4.1(對偶定理)設(shè)A和A*互為對偶式，P1，P2，…，Pn是出現(xiàn)A和A*中的原子命題變元，則①A(P1，P2，…，Pn)A*(P1，P2，…，Pn)②A(P1，P2，…，Pn)A*(P1，P2，…，Pn)①表明，公式A的否定等價于其命題變元否定的對偶式；②表明，命題變元否定的公式等價于對偶式之否定。定理1.4.2設(shè)A和B為兩個命題公式，若AB則A*B*。有了等價式、代入規(guī)則、替換規(guī)則和對偶定理，便可以得到更多的永真式，證明更多的等價式，使化簡命題公式更為方便。２.蘊(yùn)涵式定義1.4.2設(shè)A和B是兩個命題公式，若A→B是永真式，則稱A蘊(yùn)涵B，記作AB，稱AB為蘊(yùn)涵式或永真條件式。符號→和的區(qū)別與聯(lián)系類似于和的關(guān)系。區(qū)別：→是邏輯聯(lián)結(jié)詞，屬于對象語言中的符號，是公式中的符號；而不是聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個公式之間的關(guān)系，不是兩公式中符號。聯(lián)系：AB成立，其充要條件A→B是永真式。蘊(yùn)涵式有下列性質(zhì)：①自反性，即對任意公式A，有AA。②傳遞性，即對任意公式A、B和C，若AB，BC，則AC。③對任意公式A、B和C，若AB，AC，則A(B∧C)。④對任意公式A、B和C，若AC，BC，則A∨BC。下面給出等價式與蘊(yùn)涵式之間的關(guān)系。定理1.4.3設(shè)A和B是兩命題公式，AB的充要條件是AB且BA。３.蘊(yùn)涵式證明方法除真值表外，還有兩種方法：①前件真導(dǎo)后件真方法設(shè)公式的前件為真，若能推導(dǎo)出后件也為真，則條件式是永真式，故蘊(yùn)涵式成立。因為欲證AB，即證AB是永真式。對于AB，除在A取真和B取假時，AB為假外，余下AB皆為真。所以，若AB的前件A為真，由此可推出B亦為真，則AB是永真式，即AB。②后件假導(dǎo)前件假方法設(shè)條件式后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊(yùn)涵式成立。因為若A→B的后件B取假，由此可推出A取假，即推證了：BA。又因A→BB→A，故AB成立。1.5聯(lián)結(jié)詞的擴(kuò)充與功能完全組１.聯(lián)結(jié)詞的擴(kuò)充定義1.5.1設(shè)P和Q是任兩個原子命題，①由合取非聯(lián)結(jié)詞↑和P，Q連接成P↑Q，稱它為P和Q的合取非式復(fù)合命題，讀作“P合取非Q”。P↑Q的真值由命題P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為Ｔ時，P↑Q為Ｆ，否則P↑Q為Ｔ。“合取非”又常稱為“與非”。②由析取非聯(lián)結(jié)詞↓和P，Q連接成P↓Q，稱它為P和Q的析取非式復(fù)合命題，讀作“P析取非Q”。P↓Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為Ｆ時，P↓Q為Ｔ，否則P↓Q為Ｆ?！拔鋈》恰庇殖７Q為“或非”。③由條件非聯(lián)結(jié)詞和P，Q連接成PQ，稱它為P和Q的條件非式復(fù)合命題，讀作“P條件非Q”。PQ的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P為Ｔ而Q為Ｆ時，PQ為Ｔ；否則PQ為Ｆ。④由雙條件非聯(lián)結(jié)詞把P，Q連接成PQ，稱它為P和Q的雙條件非式復(fù)合命題，讀作“P雙條件非Q”。PQ的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q的真值不同時，PQ為Ｔ，否則PQ為Ｆ?！半p條件非”又常稱為“異或”，也常用符號表示之。上面4個聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值表如下：由表可知，①PQ(PQ) ②PQ(PQ) ③PQ(PQ) ④PQ(PQ)２.與非、或非和異或的性質(zhì)與非、或非以及異或在計算機(jī)科學(xué)中是經(jīng)常使用的3個聯(lián)結(jié)詞，因此，掌握它們的性質(zhì)是十分必要的。令P、Q和R是原子命題變元。①與非的性質(zhì)(a)P↑QQ↑P(b)P↑PP(c)(P↑Q)↑(P↑Q)P∧Q(d)(P↑P)↑(Q↑Q)P∨Q②或非的性質(zhì)(a)P↓QQ↓P(b)P↓PP(c)(P↓Q)↓(P↓Q)P∨Q(d)(P↓P)↓(Q↓Q)P∧Q從上述的性質(zhì)可知，聯(lián)結(jié)詞、和可分別用聯(lián)結(jié)詞或者取代，讀者可以自行驗證，和都不滿足結(jié)合律。③異或的性質(zhì)(a)PQQP(b)P(QR)(PQ)R(c)P∧(QR)(P∧Q)(P∧R)(d)PPF，F(xiàn)PP，TPP(e)若PQR，則QRP，PPQ，且PQRF。以上所有性質(zhì)，用真值表或命題定律都是不難證明的。至此，已有了9個聯(lián)結(jié)詞，是否還需要擴(kuò)充呢？事實上，兩上命題變無P和Q，與9個聯(lián)結(jié)詞一共可構(gòu)成 類命題公式，如下表示之：從列表可知，除命題常元F，T及命題變元本身外，命題聯(lián)結(jié)詞一共有9個就夠了。為了方便，可規(guī)定其優(yōu)先級，由高到低次序為，，，，等。３.聯(lián)結(jié)詞功能完全組已知有9個聯(lián)結(jié)詞就夠用了，能不能少呢？若能少，表明有些聯(lián)結(jié)詞的邏輯功能可由其他聯(lián)結(jié)詞替代。事實上，也確實如此，因為有下列等價式：PQ(PQ)PQ(PQ)PQ(PQ)PQ(PQ)可見，擴(kuò)充的4個聯(lián)結(jié)詞，，和能由原有5個聯(lián)結(jié)詞分別替代之。又由命題定律：PQ(PQ)(QP)PQPQPQ(PQ)PQ(PQ)可知，原有5個聯(lián)結(jié)詞，，，和又能由聯(lián)結(jié)詞組{，}或{，}取代。那么，究竟最少用幾個聯(lián)結(jié)詞？就是說，用最少的幾個聯(lián)結(jié)詞就能等價表示所有的命題公式?；蛘哒f，用最少的幾個聯(lián)結(jié)詞就能替代所有聯(lián)結(jié)詞的功能。這便是所要定義的聯(lián)結(jié)詞功能完全組。定義1.5.2稱G為聯(lián)結(jié)詞功能完全組，如果G滿足下列兩條件：①由G中聯(lián)結(jié)詞構(gòu)成的公式能等價表示任意命題公式；②G中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價表示?？梢宰C明，{，}，{，}，{，}，{}，{}都是聯(lián)結(jié)詞功能完全組；而{，}，{}，{}，{}，{，}都不是聯(lián)結(jié)詞功能完全組，但為了表示方便，仍經(jīng)常使用聯(lián)結(jié)詞組{，，}。1.6公式標(biāo)準(zhǔn)型——范式１.簡單合取式與簡單析取式定義1.6.1在一公式中，僅由命題變元及其否定構(gòu)成的合取式，稱該公式為簡單合取式，其中每個命題變元或其否定，稱為合取項。定義1.6.2在一公式中，僅由命題變元及其否定構(gòu)成的析取式，稱該公式為簡單析取式，其中每個命題變元或其否定，稱為析取項。例如，公式P，Q，PQ和PQP等都是簡單合取式，而P，Q和P為相應(yīng)的簡單合取式的合取項；公式P，Q，PQ，PQP等都是簡單析取式，而P，Q和P為相應(yīng)簡單析取式的析取項。注意，一個命題變元或其否定既可以是簡單合取式，也可是簡單析取式，如例中P，Q等。定理1.6.1簡單合取式為永假式的充要條件是：它同時含有某個命題變元及其否定。定理1.6.2簡單析取式為永真式的充要條件是：它同時含有某個命題變元及其否定。２.析取范式與合取范式定義1.6.3一個命題公式A稱為析取范式，當(dāng)且僅當(dāng)A可表為簡單合取式的析取，即AAi；其中Ai為簡單合取式，i=1，2，…，n。定義1.6.4一個命題公式A稱為合取范式，當(dāng)且僅當(dāng)A可表為簡單析取式的合取，即AAi；其中Ai為簡單析取式，1≤i≤n。定理1.6.3對于任何一命題公式，都存在與其等價的析取范式和合取范式。求范式算法：①使用命題定律，消去公式中除、和以外公式中出現(xiàn)的所有聯(lián)結(jié)詞；②使用(P)P和德·摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞都移到命題變元之前；③利用結(jié)合律、分配律等將公式化成析取范式或合取范式。３.范式的應(yīng)用利用析取范式和合取范式可對公式進(jìn)行判定。定理1.6.4公式A為永假式的充要條件是A的析取范式中每個簡單合取式至少包含一個命題變元及其否定。定理1.6.5公式A為永真式的充要條件是A的合取范式中每個簡單析取式至少包含一個命題變元及其否定。４.范式不唯一性1.7公式的主范式范式基本解決了公式的判定問題。但由于范式不唯一性，對識別公式間是否等價帶來一定困難，而公式的主范式解決了這個問題。下面將分別討論主范式中的主析取范式和主合取范式。１.主析取范式(1)小項的概念和性質(zhì)定義1.7.1在含有n個命題變元的簡單合取式中，若每個命題變元與其否定不同時存在，而二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單合取式為小項，或布爾積。例如，兩個命題變元P和Q，其構(gòu)成的小項有PQ，PQ，PQ和PQ；而三個命題變元P、Q和R，其構(gòu)成的小項有PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR。可以證明，n個命題變元共形成2n個小項。如果將命題變元按字典序排列，并且把命題變元與1對應(yīng)，命題變元的否定與0對應(yīng)，則可對2n個小項依二進(jìn)制數(shù)編碼，記為mi，其下標(biāo)i是由二進(jìn)制數(shù)轉(zhuǎn)化的十進(jìn)制數(shù)。用這種編碼所求得2n個小項的真值表，可明顯地反映出小項的性質(zhì)。表1.7.1和表1.7.2分別給出了2個命題變元P和Q、3個命題變元P、Q和R的小項真值表。從表1.7.1，表1.7.2可看出，小項有如下性質(zhì)：(a)沒有兩個小項是等價的，即是說各小項的真值表都是不同的；(b)任意兩個不同的小項的合取式是永假的：mi∧mjＦ，i≠j。(c)所有小項之析取為永真：miＴ。(d)每個小項只有一個解釋為真，且其真值1位于主對角線上。(2)主析取范式定義與存在定理定義1.7.2在給定公式的析取范式中，若其簡單合取式都是小項，則稱該范式為主析取范式。定理1.7.1任意含n個命題變元的非永假命題公式A都存在與其等價的主析取范式。(3)主析取范式的求法主析取范式求法有兩種：真值表法和公式化歸法。定理1.7.1的證明已給出了用真值表求主析取范式的方法，而公式化歸法給出如下：(a)把給定公式化成析取范式；(b)刪除析取范式中所有為永假的簡單合取式；(c)用等冪律化簡簡單合取式中同一命題變元的重復(fù)出現(xiàn)為一次出現(xiàn)，如P∧PP。(d)用同一律補(bǔ)進(jìn)簡單合取式中未出現(xiàn)的所有命題變元，如Q，則PP∧Q∨Q)，并用分配律展開之，將相同的簡單合取式的多次出現(xiàn)化為一次出現(xiàn)，這樣得到了給定公式的主析取范式。(4)主析取范式的惟一性定理1.7.2任意含n個命題變元的非永假命題公式，其主析取范式是惟一的。２.主合取范式(1)大項的概念和性質(zhì)定義1.7.3在n個命題變元的簡單析取式中，若每個命題變元與其否定不同時存在，而二者之一必出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單析取式為大項，或布爾和。例如，由兩個命題變元P和Q，構(gòu)成大項有PQ，PQ，PQ，PQ；三個命題變元P，Q和R，構(gòu)成PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR。能夠證明，n個命題變元共有2n個大項。如果將n個命題變元排序，并且把命題變元與０對應(yīng)，命題變元的否定與１對應(yīng)，則可對2n個大項按二進(jìn)制數(shù)編碼，記為Mi，其下標(biāo)i是由二進(jìn)制數(shù)化成的十進(jìn)制數(shù)。用這種編碼所求的2n個大項的真值表，能直接反映出大項的性質(zhì)。表1.7.3給出了2個命題變元P和Ｑ構(gòu)成所有大項的真值表。類似可給出３個命題變元Ｐ、Ｑ和Ｒ的所有大項的真值表，留給讀者完成。從表1.7.3可看出大項的性質(zhì)：(a)沒有兩個大項是等價的。(b)任何兩個不同大項之析取是永真的，即Mi∨MjＴ，i≠j。(c)所有大項之合取為永假，即MiＦ。(d)每個大項只有一個解釋為假，且其真值0位于主對角線上。(2)主合取范式的定義與其存在定理定義1.7.4在給定公式的合取范式中，若其所有簡單析取式都是大項，稱該范式為主合取范式。定理1.7.3任意含有n個命題變元的非永真命題公式A，都存在與其等價的主合取范式。定理1.7.4任意含n個命題變元的非永真命題公式A，其主合取范式是唯一的。上述兩定理的證明，類似于定理1.7.1和定理1.7.2。主合取范式的求法也有兩種，類似于主析取范式的求法。３.主析取范式與主合取范式之間的關(guān)系由于主范式是由小項或大項構(gòu)成，從小項和大項的定義，可知兩者有下列關(guān)系：miMiMimi因此，主析取范式和主合取范式有著“互補(bǔ)”關(guān)系，即是由給定公式的主析取范式可以求出其主命取范式。從A的主析取范式求其主合取范式的步驟為：(a)求出A的主析取范式中設(shè)有包含的小項。(b)求出與(a)中小項的下標(biāo)相同的大項。(c)做(b)中大項之合取，即為A的主合取范式。例如，(PQ)Qm1m3，則(PQ)QM４.主范式的應(yīng)用利用主范式可以求解判問題或者證明等價式成立。（1）判定問題根據(jù)主范式的定義和定理，也可以判定含n個命題變元的公式，其關(guān)鍵是先求出給定公式的主范式Ａ；其次按下列條件判定之：(a)若AＴ，或A可化為與其等價的、含2n個小項的主析取范式，則A為永真式。(b)若AＦ，或A可化為與其等價的、含2n個大項的主合取范式，則A為永假式。(c)若A不與Ｔ或者Ｆ等價，且又不含2n個小項或者大項，則A為可滿足的。（2）證明等價式成立由于任一公式的主范式是唯一的，所以將給定的公式求出其主范式，若主范式相同，則給定兩公式是等價的。1.8命題邏輯的推理理論在邏輯學(xué)中，把從前題（又叫公理或假設(shè)）出發(fā)，依據(jù)公認(rèn)的推理規(guī)則，推導(dǎo)出一個結(jié)論，這一過程稱為有效推理或形式證明。所得結(jié)論叫做有效結(jié)論，這里最關(guān)心的不是結(jié)論的真實性而是推理的有效性。前提的實際真值不作為確定推理有效性的依據(jù)。但是，如果前提全是真，則有效結(jié)論也應(yīng)該真而絕非假。在數(shù)理邏輯中，集中注意的是研究和提供用來從前提導(dǎo)出結(jié)論的推理規(guī)則和論證原理，與這些規(guī)則有關(guān)的理論稱為推理理論。提請注意，必須把推理的有效性和結(jié)論的真實性區(qū)別開。有效的推理不一定產(chǎn)生真實的結(jié)論，產(chǎn)生真實結(jié)論的推理過程未必一定是有效的。再說，有效的推理中可能包含假的前提；而無效的推理卻可能包含真的前提?？梢?，推理的有效性是一回事，前提與結(jié)論的真實與否是另一回事。所謂推理有效，指它的結(jié)論是它的前提的合乎邏輯的結(jié)果，也即，如果它的前提都為真，那么所得結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或為假。如果推理是有效的話，那么不可能它的前提都為真時而它的結(jié)論為假。１.推理的基本概念和推理形式推理也稱論證，它是指由已知命題得到新的命題的思維過程，其中已知命題稱為推理的前提或假設(shè)，推得的新命題稱為推理的結(jié)論。在數(shù)理邏輯中，前提H是一個或者n個命題公式H1,H2,···Hn；結(jié)論是一個命題公式C。由前提到結(jié)論的推理形式可表為H1,H2,···,HnC，其中符號表示推出···。可見，推理形式是命題公式的一個有限序列，它的最后一個公式是結(jié)論，余下的為前提或假設(shè)。定義1.8.1如果存在H1，H2，…，Hn，C的一個指派，使得每個Hi(1≤i≤n)為真而C為假推理形式H1，H2，…，HnC是無效的；否則，推理是有效的，此時稱C是H1，H2，…，Hn的有效結(jié)論，或稱C是從前提H1，H2，…，Hn邏輯推出的結(jié)論。定理1.8.1推理形式H1，H2，…，HnC是有效的，當(dāng)且僅當(dāng)命題公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)C。２.推理規(guī)則在數(shù)理邏輯中，從前提推導(dǎo)出結(jié)論，要依據(jù)事先提供的公認(rèn)的推理規(guī)則，它們是：①Ｐ規(guī)則(也稱前提引入規(guī)則)：在推導(dǎo)過程中，前提可視需要引入使用。②Ｔ規(guī)則(也稱結(jié)論引入規(guī)則)：在推導(dǎo)過程中，前面已導(dǎo)出的有效結(jié)論都可作為后續(xù)推導(dǎo)的前提引入。此外，在從前提推出的結(jié)論為條件式時，還需要下面規(guī)則：③ＣＰ規(guī)則(也稱條件證明引入規(guī)則)：若推出有效結(jié)論為條件式R→C時，只需將其前件R加入到前提中作為附加前提且再去推出后件C即可。ＣＰ規(guī)則的正確性可由下面定理得到保證：定理1.8.2若H1，H2，…，Hn，RC，則H1，H2，…，HnR→C。３.推理定律在推理過程中，除使用推理規(guī)則后，還需要使用許多條推理定律，這些定律可由以前講過的命題定律、蘊(yùn)涵式及運(yùn)用定理1.8.1而得到。下面只給出了由蘊(yùn)涵式得出的推理定律，它們是：(1)P，QP(2)P，QQ(3)PP∨Q(4)PP→Q(5)QP→Q(6)(P→Q)P(7)(P→Q)Q(8)P，(P→Q)Q(9)Q，(P→Q)P(10)P，(P∨Q)Q(11)(P→Q)，(Q→R)P→R(12)(PQ)，(QR)PR(13)(P→Q)，(R→S)，(P∧R)Q∧S(14)(P→Q)，(R→S)∧(P∨R)Q∨S特別當(dāng)Q=S時，有(P→Q)，(R→Q)，(P∧R)Q(P→Q)，(R→S)，(P∨R)Q(15)P→