第一章 命題邏輯2013-8-26

1、離散數(shù)學(xué)離散數(shù)學(xué)Discrete Mathematics徐喜榮徐喜榮第一章 命題邏輯2n離散數(shù)學(xué)的特點(diǎn)n離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)基礎(chǔ)理論 的核心課程。n1976年美國(guó)IEEE計(jì)算機(jī)協(xié)會(huì)典型課程分委員會(huì)把離散數(shù)學(xué)列為 計(jì)算機(jī)科學(xué)中專(zhuān)業(yè)基礎(chǔ)理論的核心課程。又稱(chēng)計(jì)算機(jī)數(shù)學(xué)。n離散數(shù)學(xué)有別于一般的工程數(shù)學(xué)。 傳統(tǒng)的數(shù)學(xué)分析、微分方程、復(fù)變函數(shù)、泛函分析等課程以連續(xù) 變量作為研究對(duì)象。n離散數(shù)學(xué)是以研究各種各樣的離散量的結(jié)構(gòu)及離散量之間的關(guān)系為主要目標(biāo)。 n研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素。這充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。第一章 命題邏輯3n離散數(shù)學(xué)把計(jì)算機(jī)科學(xué)中所涉及到的研究

2、離散量的數(shù)學(xué)綜合在一起，為研究計(jì)算機(jī)科學(xué)的相關(guān)問(wèn)題提供了有力的數(shù)學(xué)工具。n換句話說(shuō)，離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中起到了工具性的作用，等同于 高等數(shù)學(xué)在其他工程技術(shù)科學(xué)中的作用。n離散數(shù)學(xué)的產(chǎn)生對(duì)計(jì)算機(jī)科學(xué)的發(fā)展具有重大影響和推動(dòng)作用，而計(jì)算機(jī)科學(xué)的發(fā)展又不斷地充實(shí)和豐富了離散數(shù)學(xué)的內(nèi)容。n特別是在被譽(yù)為計(jì)算機(jī)科學(xué)時(shí)代的今天，離散數(shù)學(xué)以它獨(dú)特的魅力為越來(lái)越多的人們所矚目，并已成為計(jì)算機(jī)科學(xué)工作者、應(yīng)用計(jì)算機(jī)的工程技術(shù)人員以及信息科學(xué)工作者等必備的數(shù)學(xué)工具之一。n離散數(shù)學(xué)是數(shù)學(xué)工具第一章 命題邏輯4離散數(shù)學(xué)的任務(wù)：n通過(guò)離散數(shù)學(xué)知識(shí)的學(xué)習(xí)和訓(xùn)練，一方面可以幫助學(xué)生掌握證明 問(wèn)題的方法，培養(yǎng)抽象思維的能力

3、、符號(hào)演算和慎密概括的能力 以及嚴(yán)密的邏輯推理的能力。n另一方面使學(xué)生具有良好的專(zhuān)業(yè)理論素質(zhì)，有益于培養(yǎng)學(xué)生嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度，提高學(xué)生分析和解決實(shí)際問(wèn)題的能力， 為將來(lái)參與創(chuàng)新性的研究和開(kāi)發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。n通過(guò)離散數(shù)學(xué)的學(xué)習(xí)，可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程（如數(shù)據(jù)結(jié)構(gòu)、編譯理論、操作系統(tǒng)、數(shù)字邏輯理論、密碼學(xué)基礎(chǔ)、邏輯程序設(shè)計(jì)、數(shù)據(jù)庫(kù)原理、人工智能等）的學(xué)習(xí) 創(chuàng)造條件，打下堅(jiān)實(shí)的理論基礎(chǔ)。第一章 命題邏輯5n離散數(shù)學(xué)是建立在大量定義、定理之上的邏輯推理學(xué)科，因此對(duì)概念的理解是學(xué)習(xí)這門(mén)課程的核心。n學(xué)習(xí)概念的基礎(chǔ)上，要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的實(shí)體

4、是大量的定理和性質(zhì)。n因此，深入地理解和掌握離散數(shù)學(xué)的基本概念、基本定理和結(jié)論，是學(xué)好離散數(shù)學(xué)的重要前提之一。n離散數(shù)學(xué)中的基本概念、思想方法，大量地應(yīng)用到邏輯電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、人工智能、數(shù)據(jù)庫(kù)原理等計(jì)算機(jī)科學(xué)專(zhuān)業(yè)課程中。這些課程都要用到集合、關(guān)系、代數(shù)系統(tǒng)、圖的理論等基本概念進(jìn)行描述。離散數(shù)學(xué)課程學(xué)習(xí)的特點(diǎn)：第一章 命題邏輯6離散數(shù)學(xué)的內(nèi)容：n 數(shù)理邏輯（Mathematics Logic)n 集合論(Sets)n 組合論（Combination)n 圖論（Graph Theory)n 代數(shù)結(jié)構(gòu)（Algbra Structure)第一章 命題邏輯7教學(xué)內(nèi)容：數(shù)理邏輯集集 合

5、合 論論圖圖 論論代數(shù)系統(tǒng)代數(shù)系統(tǒng)謂詞邏輯謂詞邏輯集合集合關(guān)系關(guān)系圖的基本概念圖的基本概念幾個(gè)特殊圖幾個(gè)特殊圖代數(shù)系統(tǒng)的基本概念代數(shù)系統(tǒng)的基本概念特殊代數(shù)系統(tǒng)特殊代數(shù)系統(tǒng)離離 散散 數(shù)數(shù) 學(xué)學(xué)函數(shù)函數(shù)圖的連通性圖的連通性代數(shù)系統(tǒng)的基本概念代數(shù)系統(tǒng)的基本概念特殊代數(shù)系統(tǒng)特殊代數(shù)系統(tǒng)代數(shù)系統(tǒng)的基本概念代數(shù)系統(tǒng)的基本概念命題邏輯命題邏輯代數(shù)系統(tǒng)的同態(tài)與同構(gòu)代數(shù)系統(tǒng)的同態(tài)與同構(gòu)第一章 命題邏輯8邏輯學(xué)（Logic） 邏輯學(xué)是研究人的思維形式和規(guī)律的科學(xué)。由于研究的對(duì)象和方法各有側(cè)重而又分為辯證邏輯、形式邏輯和數(shù)理邏輯。n辯證邏輯： 以辯證法認(rèn)識(shí)論的世界觀為基礎(chǔ)的邏輯學(xué)。n形式邏輯： 主要對(duì)人的思維形式

6、結(jié)構(gòu)和規(guī)律進(jìn)行研究的類(lèi)似于語(yǔ)法 的一門(mén)工具性學(xué)科。思維的形式結(jié)構(gòu)包括概念、判斷和推理之間的 結(jié)構(gòu)和聯(lián)系，其中概念是思維的基本單位，通過(guò)概念對(duì)事物是否具 有某種屬性進(jìn)行肯定或否定的回答就是判斷；由一個(gè)或幾個(gè)判斷推 出另一個(gè)判斷的思維形式就是推理。 n 數(shù)理邏輯： 用數(shù)學(xué)方法研究推理，是研究推理中前提和結(jié)論之間 的形式關(guān)系的科學(xué)，又稱(chēng)其為符號(hào)邏輯。第一章 命題邏輯9數(shù)理邏輯n 數(shù)理邏輯包括命題邏輯和謂詞邏輯。n為了研究形式邏輯中的推理規(guī)律，數(shù)學(xué)家為其設(shè)計(jì)了一套表意符號(hào) 體系，用人工符號(hào)來(lái)書(shū)寫(xiě)邏輯法則，使形式邏輯數(shù)學(xué)化。 n萊布尼茲是數(shù)理邏輯的首席創(chuàng)始人，力主“思維計(jì)算化”正是應(yīng)用 了一整套數(shù)學(xué)符號(hào)

7、組成的形式系統(tǒng)來(lái)研究邏輯問(wèn)題，才使得邏輯學(xué) 有了脫胎換骨的進(jìn)步，具備表達(dá)簡(jiǎn)潔、推理嚴(yán)謹(jǐn)、易于分析等優(yōu)點(diǎn)。n音樂(lè)里有簡(jiǎn)譜和五線譜等人工符號(hào)，記錄音樂(lè)中音韻的節(jié)律和高低； n化學(xué)中用分子式和反應(yīng)方程等人工符號(hào)記錄物質(zhì)的分子結(jié)構(gòu)和反應(yīng) 過(guò)程。第一章 命題邏輯10例子：設(shè)有下列情況，結(jié)論是否有效。 (1) 或者是天晴，或者是下雨； (2) 如果是天晴，我去看電影； (3) 如果我去看電影，我就不看書(shū)。結(jié)論：如果我在看書(shū)，則天在下雨。解: 令W：天晴；Q：下雨； S：我去看電影；R：我在看書(shū)。 前提：W Q, W S， S R 結(jié)論：R Q第一章 命題邏輯11命題邏輯（Proposition Logic

8、）n也稱(chēng)命題演算或語(yǔ)句演算，它研究由命題為基本單位構(gòu)成的前提 和結(jié)論之間的可推導(dǎo)關(guān)系。 n原子命題是命題邏輯中研究的基本單位，即對(duì)原子命題不再分解，只有真、假二個(gè)真值，所以命題邏輯也稱(chēng)二值邏輯。謂詞邏輯（Proposition Logic）n謂詞邏輯是比命題邏輯更加廣泛的推理形式；n謂詞邏輯對(duì)命題做進(jìn)一步的分析，把原子命題分解為謂詞和個(gè)體 兩部分，進(jìn)一步揭示分析前提和結(jié)論在形式結(jié)構(gòu)方面的聯(lián)系。第一章 命題邏輯12第1章 命題邏輯n1.1 命題與聯(lián)結(jié)詞n1.2 命題公式、翻譯和真值表n1.3 公式分類(lèi)與等價(jià)式n1.4 對(duì)偶式與蘊(yùn)含式n1.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組n1.6 公式標(biāo)準(zhǔn)型-范式n1

9、.7 公式的主范式n1.8 命題邏輯的推理理論第一章 命題邏輯131.1 命題與聯(lián)結(jié)詞 一、命題的概念n 命題：非真必假的陳述句。n 具有真假意義的陳述句，且真或者假二者必居其一， 也只居其一。n命題的真或假稱(chēng)為命題的真值。n真用T或1表示 n假用F或0表示第一章 命題邏輯14 自然語(yǔ)言中的感嘆句、疑問(wèn)句 和祈使句不是命題。n 這真開(kāi)心！ n 你聽(tīng)懂了嗎？n 請(qǐng)止步！命題的注意事項(xiàng)： 判定命題的真值會(huì)因人、因時(shí)、因地、因標(biāo)準(zhǔn)而異。n A:1+1=2 B:1+1=10 C:1+1=1 n 現(xiàn)在是六點(diǎn)鐘 一個(gè)陳述句能否分辨其真假與 是否現(xiàn)在能判斷它是真是假是 兩件事。n 張校長(zhǎng)的頭發(fā)有一萬(wàn)根 “自

10、指謂”的陳述句 （結(jié)論是對(duì)自身而言） 不是命題n 我所說(shuō)的是假的 第一章 命題邏輯15例：判斷下列語(yǔ)句哪些是命題。若是命題，指出真值n巴黎在法國(guó)n請(qǐng)勿喧嘩n明天去哪里？n有外星人n曹操是明朝人n6+814n今天下雨n今天我休息n11+1=100n是命題 Tn不是命題n不是命題n是，不確定真值n是，假n是，假n是，真值不確定n是，真值不確定n是，真值不確定第一章 命題邏輯16二、命題標(biāo)識(shí)符 n 命題標(biāo)識(shí)符：表示原子命題的符號(hào)稱(chēng)為命題標(biāo)識(shí)符，簡(jiǎn)稱(chēng)命題符。n 原子命題的符號(hào)表示：大小寫(xiě)英文字母：P、Q、R、 p 、q 、r、 帶下標(biāo)的大寫(xiě)字母：Pi，Qi，Ri， n 例如： P：北京是中國(guó)的首都。

11、n 命題常元：一個(gè)命題標(biāo)識(shí)符P，如果表示一個(gè)確定的命題，則稱(chēng) P 為原子命題常元，簡(jiǎn)稱(chēng)命題常元；n 命題變?cè)喝鬚只表示任意命題的位置標(biāo)志，或表示不確定的命題，或以原子命題為值的變?cè)狿，稱(chēng)P為原子命題變?cè)?，?jiǎn)稱(chēng)命題變?cè)?命題變?cè)且悦}的真值為值的變?cè)Ｃ}變?cè)皇敲}。n 命題指派：將一個(gè)命題變?cè)?P 用一特定命題去代替，它才能確定 真值，叫做對(duì) P 的指派或解釋?zhuān)洖?S(P) 或 I(P)。第一章 命題邏輯17三、聯(lián)結(jié)詞 聯(lián)結(jié)詞是邏輯聯(lián)結(jié)詞或命題聯(lián)結(jié)詞的簡(jiǎn)稱(chēng)，它是自然語(yǔ)言中連詞的邏輯抽象，用它和原子命題構(gòu)成復(fù)合命題。n否定聯(lián)結(jié)詞 n合取聯(lián)結(jié)詞 n析取聯(lián)結(jié)詞 n條件聯(lián)結(jié)詞 n 雙條件聯(lián)結(jié)

12、詞 第一章 命題邏輯18（1）否定聯(lián)結(jié)詞 n 設(shè)P是一個(gè)命題，由聯(lián)結(jié)詞 和命題P 構(gòu)成 P，P為命題P的 否定式復(fù)合命題。P讀“非P ”。n 聯(lián)結(jié)詞 是自然語(yǔ)言中的“非”、“不”和“沒(méi)有”等的邏輯抽象。 PPTFFTn P：上海是一個(gè)大城市。n P：上海并不是一個(gè)大城市。n P：上海是一個(gè)不大的城市。 第一章 命題邏輯19(2) 合取聯(lián)結(jié)詞 n 令P和Q是兩個(gè)命題，由聯(lián)結(jié)詞把P，Q 連接成PQ ，稱(chēng)PQ為 P和Q的合取式復(fù)合命題，PQ 讀做“P與Q ”，或“P合取Q ”。n 聯(lián)結(jié)詞是自然語(yǔ)言中的“并且”，“既又”等的邏輯抽象。PQPQ QPTTTTTFFFFTFFFFFFnP：今天下雨。nQ：

13、明天下雨。nPQ：今天下雨而且明天下雨。nPQ：今天與明天都下雨。 nPQ：這兩天都下雨。 第一章 命題邏輯20(3)析取聯(lián)結(jié)詞 n 設(shè)P 和Q是兩個(gè)命題，由聯(lián)結(jié)詞把P，Q 連接成PQ，稱(chēng)PQ為 P，Q 的析取式復(fù)合命題，PQ讀做“P或Q ”。n 析取聯(lián)結(jié)詞是“或”、“或者”的邏輯抽象。n 析取聯(lián)結(jié)詞是表示可兼或，即二者可同時(shí)發(fā)生，不排斥二者發(fā)生的 情況。n 析取聯(lián)結(jié)詞不表示不可兼或排斥或，即非此即彼。PQPQ QPTTTTTFTTFTTTFFFFn今天晚上我在家看電視或去劇場(chǎng)看戲。 （排斥或）-不是命題聯(lián)結(jié)詞n他可能是100米或400米賽跑的冠軍。 （可兼或）-是命題聯(lián)結(jié)詞n他昨天做了二十或

14、三十道題。 （表示近似數(shù)）-不是聯(lián)結(jié)詞 第一章 命題邏輯21(4) 條件聯(lián)結(jié)詞 n設(shè)P和Q是兩個(gè)命題，由聯(lián)結(jié)詞把P，Q連接成PQ，稱(chēng)PQ為 P 和Q的條件式復(fù)合命題，把P和Q分別稱(chēng)為PQ 的前件和后件， 或者前提和結(jié)論。PQ讀做： “如果P，則Q ” 或者 “P條件Q ”。n聯(lián)結(jié)詞是自然語(yǔ)言中“如果，則”，“若，才能”等邏輯 抽象，是充分條件。n在自然語(yǔ)言中，前件為假，不管結(jié)論真假，整個(gè)語(yǔ)句的意義往往 無(wú)法判斷。在命題邏輯中，當(dāng)P為F，PQ為T(mén)，稱(chēng)為“善意推定”。n在命題邏輯中允許前件和后件間無(wú)必然的因果關(guān)系。第一章 命題邏輯22(4)條件聯(lián)結(jié)詞 PQPQQPTTTTTFFTFTTFFFTTn

15、P：天下雨；Q：馬路濕； PQ：如果天下雨，則馬路濕。n下面討論P(yáng)Q 的真值：n如果天下雨，則馬路濕；n如果天下雨，則馬路不濕；n如果天不下雨，則馬路濕；(善意推斷)n如果天不下雨，則馬路不濕；nP：2+2=4；Q：雪是黑的；nPQ：如果2+2=4，則雪是黑的。第一章 命題邏輯23(5)雙條件聯(lián)結(jié)詞n令P和Q是兩個(gè)命題，由聯(lián)結(jié)詞把P，Q連接成P Q，稱(chēng)P Q為 P和Q的雙條件式復(fù)合命題，P Q讀做： “P當(dāng)且僅當(dāng)Q ”。n雙條件聯(lián)結(jié)詞又常稱(chēng)為同或，并用符號(hào)表示。n雙條件聯(lián)結(jié)詞是自然語(yǔ)言中的“充分必要條件”、“當(dāng)且僅當(dāng)”等的 邏輯抽象。PQP QQ PTTTTTFFFFTFFFFTTn三角形是等

16、邊三角形當(dāng)且僅當(dāng)三角形的三個(gè)內(nèi)角相等。n2+2=4當(dāng)且僅當(dāng)太陽(yáng)是恒星。第一章 命題邏輯24四、命題分類(lèi) n命題分兩類(lèi)：原子命題和復(fù)合命題n復(fù)合命題：由原子命題和聯(lián)結(jié)詞復(fù)合而成 n判斷一個(gè)命題是否為復(fù)合命題，其關(guān)鍵是聯(lián)結(jié)詞是否出現(xiàn)，出現(xiàn) 聯(lián)結(jié)詞則是復(fù)合命題，不出現(xiàn)聯(lián)結(jié)詞則是原子命題。n注意： 復(fù)合命題的真值只取決于構(gòu)成它們的各原子命題的真值，與它們 的內(nèi)容、含義無(wú)關(guān)。 n 、 、 具有對(duì)稱(chēng)性；而 、 沒(méi)有對(duì)稱(chēng)性；n聯(lián)結(jié)詞可以被看做是一、二元運(yùn)算或一、二元函數(shù)。第一章 命題邏輯25總 結(jié)n復(fù)合命題的真值只取決于構(gòu)成它們的各原子命題的真值，而與它們的內(nèi)容、含義無(wú)關(guān)，與聯(lián)結(jié)詞所連接的兩原子命題之間是否

17、有關(guān)系無(wú)關(guān)。n，和具有對(duì)稱(chēng)性，而 ，沒(méi)有。n 聯(lián)結(jié)詞都有從已知命題得到新的命題的作用，從這個(gè)意義上講， 它們具有操作或運(yùn)算的意義?？梢?jiàn)，它們可以被看作是一、二元 運(yùn)算，或一、二元函數(shù)。第一章 命題邏輯261.2 命題公式、翻譯和真值表 一、命題公式n 定義1.2.1 原子命題公式：命題常元、命題變?cè)y(tǒng)稱(chēng)為原子命題公式， 簡(jiǎn)稱(chēng)原子公式。n 定義1.2.2 合式公式是由下列規(guī)則形成的字符串： (1)真值 T 和 F 是合式公式。 (2)原子命題公式是一個(gè)合式公式。 (3)若 A 是合式公式，則 A 是合式公式。 (4)若A和B是合式公式，則AB、AB、 AB和AB都是合式公式。 (5)經(jīng)過(guò)有限次地

18、使用(1)(2)(3)所得到的結(jié)果，都是合式公式。n定義1.2.3 如果A1是公式 A 的一部分，且A1是一個(gè)公式，稱(chēng)A1 是 A 的 子公式。 第一章 命題邏輯27定義補(bǔ)充n(AB C) 、(AB C)也是合式公式；n(AB)、(AB)、(AB) 和(A B)也被稱(chēng)為合取式、 析取式、條件式和雙條件式；nA，B 分別為(AB)、(AB)的合取項(xiàng)和析取項(xiàng)。n(P)Q，(P(QR)都是合式公式；n(PQ，(PQ) (R)都不是合式公式。第一章 命題邏輯28聯(lián)結(jié)詞的優(yōu)先級(jí) n公式最外層的圓括號(hào)可省略，如把(P(QR)寫(xiě)成P(QR)。n只作用于鄰接后的原子命題變?cè)?，例如?P)Q寫(xiě)成 PQ。n聯(lián)結(jié)詞

19、的優(yōu)先級(jí)從高到低是： ， 。例：例： 設(shè)公式 A 為(PQ)(QR)，則PQ，QR 都是A的 子公式。第一章 命題邏輯29二、命題的翻譯 命題的符號(hào)化要注意下列事項(xiàng)：n 確定給定句子是否為命題。n 句子中連詞是否為命題聯(lián)結(jié)詞。n 要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫(xiě)成由命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合式公式，稱(chēng)為翻譯，也稱(chēng)符號(hào)化。 命題的符號(hào)化在數(shù)理邏輯中很重要！第一章 命題邏輯30例：符號(hào)化下列命題：n他既聰明又用功。n他雖聰明但不用功。n除非你努力，否則你將失敗。n除非天氣好，我才騎自行車(chē)上班。n小王晚上要回家，除非下大雨。n只有睡覺(jué)才能恢復(fù)疲勞。n只

20、要我還有口氣，我就要戰(zhàn)斗。nA中沒(méi)有元素，A就是空集。n張明或者李強(qiáng)都可以做這件事。n張明和李強(qiáng)都做這件事了。 P QP QPQQ PQ PQPP QPQP QPQ第一章 命題邏輯31例：符號(hào)化下列命題：n鐵和氧化合，但鐵和氮不化合。n如果我下班早，就去商店看看，除非我很累。n李四是計(jì)算機(jī)系的學(xué)生，他選修了日語(yǔ)課或法語(yǔ)課。n李四是計(jì)算機(jī)系的學(xué)生，他住在312室或313室。n除非天氣好，否則我是不會(huì)去公園的。n如果晚上做完作業(yè)且沒(méi)有其他的事， 他就會(huì)去看電視或聽(tīng)音樂(lè)。P Q P (Q R)P (Q R)P (QR) (Q R)Q P(P Q) (L M) (LM)第一章 命題邏輯32三、 真值表

21、n 定義1.2.4 對(duì)于命題公式A中每個(gè)命題變?cè)狿i，任給一個(gè)指派 S(Pi) 或解釋I (Pi)，得到一種真值的組合S(P1) S(P2)S(Pn) 或 I(P1) I(P2)I(Pn) 稱(chēng)為A的一個(gè)真值指派，或稱(chēng)為A的一種解釋?zhuān)?記為S(A)或I(A)。若S(A)或I(A)為T(mén)，稱(chēng)S(A)或I(A)為A的成真指派 或說(shuō)A的解釋為真。nA的成假指派的定義類(lèi)似。n為方便計(jì)，有時(shí)將S(Pi) = 1或S(Pi) = 0記為Pi /1或Pi /0，1in。n顯然，若公式 A 中有n個(gè)不同命題變?cè)阌?n組真值指派。第一章 命題邏輯33真值表n定義1.2.5 設(shè)A為一命題公式，對(duì)其中出現(xiàn)的命題變?cè)?/p>

22、做所有可能 的每一組真值指派 S，連同公式A的相應(yīng)的S(A)匯列成表，稱(chēng)為A 的真值表。 n真值表由兩部分組成：表的左部分列出公式的每一種解釋?zhuān)槐淼挠也糠纸o出相應(yīng)每種解釋公式得到的真值。n真值表的約定：命題變?cè)醋值湫蚺帕小?duì)公式的每個(gè)解釋?zhuān)远M(jìn)制數(shù)從小到大或者從大到小順序 列出。若公式復(fù)雜，可先列出各子公式的真值(若有括號(hào)，則應(yīng)從里 層向外層展開(kāi))，最后列出所給公式的真值。第一章 命題邏輯34PPTFFTPQPQQPTTTTTFFFFTFFFFFFPQPQQPTTTTTFTTFTTTFFFFPQPQQ PTTTTTFFTFTTFFFTTPQP QQ PTTTTTFFFFTFFFFTT第一章

23、 命題邏輯35例子：求(PQ) ( P Q)的真值表 P Q(PQ) ( P Q ) 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 0 1步驟 第一章 命題邏輯36例子：求例子：求( (PQ) ) R 的真值表的真值表 P Q R(PQ) R 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 10 1 1 1 0 01 0 0 0 0 11 0 1 0 0 01 1 0 1 1 11 1 1 1 0 0步驟 n此真值表有此真值表有3 3個(gè)個(gè)成真指派成真指派：(P/0, Q/0, R/0), (P/0, Q/1, R/0), (P/1,

24、 Q/1, R/0)。第一章 命題邏輯37例：作出下列命題的真值表: 并非“室內(nèi)很冷或很亂”， 也不是“室外暖和且室內(nèi)太臟”P(pán) Q R S (P Q) （R S）0 0 0 0 0 0 00 0 0 1 0 0 00 0 1 0 0 0 00 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 解：P：室內(nèi)很冷 Q：室內(nèi)很亂 R：室外暖和 S：室內(nèi)太臟 本題可用符號(hào)表示為： (P Q) （R S）第一章 命題邏輯381.3 公式分類(lèi)一、 公式分類(lèi)定義1.3.1 設(shè)A為一個(gè)命題公式，對(duì)A做所有可能的解釋I，對(duì)于這些解釋I：n若I(A)皆為成真，稱(chēng)A為永真式；n若I(A

25、)皆為成假，稱(chēng)A為永假式；n若至少存在一個(gè)I(A)為真，稱(chēng)A為可滿足式。n永真式也稱(chēng)重言式，常用 T 表示；n永假式也稱(chēng)矛盾式， 常用 F 表示。判定給定公式是否為永真式，永假式或可滿足式的問(wèn)題，稱(chēng)為給定公式的判定問(wèn)題。判定方法有真值表法和公式推演法。 第一章 命題邏輯39二、等價(jià)公式定義1.3.2 設(shè)A和B是兩個(gè)命題公式，如果A、B在其任意解釋下，其真值都是相同的，則稱(chēng) A A和B B是等價(jià)的，或邏輯相等. . 記作AB，讀作A等價(jià)B，稱(chēng)AB為等價(jià)式。若公式 A 和 B 的真值表是相同的，則A和B等價(jià)。因此驗(yàn)證兩公式是否等價(jià)，只需做出它們的真值表即可。 第一章 命題邏輯40n是邏輯雙條件聯(lián)結(jié)

26、詞，屬于目標(biāo)語(yǔ)言中的符號(hào)，它出現(xiàn)在命題公式中；n不是邏輯聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)命題公式之間的一種充分必要(記為 iff )關(guān)系，它不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)。n 與 iff 可通用。n自反性：對(duì)任意公式A，有AA。n對(duì)稱(chēng)性：對(duì)任意公式A和B，若AB，則BA。n傳遞性：對(duì)任意公式A、B和C，若AB、BC，則AC。等價(jià)式有下列性質(zhì)：第一章 命題邏輯41定理1.3.1 AB當(dāng)且僅當(dāng)A B是永真式。證明：（1）必要性：若AB，則A B是永真式。 （2）充分性：若A B是永真式，則AB。PQP QQ PTTTTTFFFFTFFFFTT第一章 命題邏輯42例1：（1）如果 AC

27、BC ，是否有 AB ？ （2）如果 AC BC ，是否有 AB ？ （3）如果 A B， 是否有 AB ?解： （1）若有真值指派使得 S(A)=T, S(B)=F, S(C)=T （2）若有真值指派使得 S(A)=T, S(B)=F, S(C)=F （3） A B，則 A B是永真式，即 A B是永真式， B A是永真式第一章 命題邏輯43三、基本等價(jià)式命題定律(1)雙否定：A A 。(2)交換律：ABBA ，ABBA ，A BB A 。(3)結(jié)合律：(AB)CA(BC)，(AB)CA(BC)， (A B) CA (B C) 。(4)分配律：A(BC)(AB)(AC) ， A(BC)(AB

28、) (AC) 。(5)德摩根律：(AB)AB ， (AB) AB。(6)等冪律：AAA ，AAA 。(7)同一律：ATA ，AFA 。n判斷公式間是否等價(jià)，有一些簡(jiǎn)單而又經(jīng)常使用的等價(jià)式，稱(chēng)為基本 等價(jià)式或命題定律，牢記并熟練運(yùn)用它們是學(xué)好數(shù)理邏輯的關(guān)鍵。第一章 命題邏輯44三、基本等價(jià)式命題定律（二）(8)零 律： AFF ，ATT 。(9)吸收律： A(AB) A ，A(AB)A 。(10)互補(bǔ)律：AA F ，( 矛盾律 ) AA T 。 ( 排中律 )(11)條件式轉(zhuǎn)化律：AB AB ，AB B A。(12)雙條件式轉(zhuǎn)化律： A B (AB)(BA)(AB)(AB) ， A B (A B

29、) 。(13)輸出律：(AB)C A(BC) 。(14)歸謬律：(AB)(A B) A 。n由已知的等價(jià)式可以推演出更多的等價(jià)式，稱(chēng)這一過(guò)程為等價(jià)演算。n等價(jià)演算是邏輯代數(shù)或布爾代數(shù)的重要組成部分。 第一章 命題邏輯45例1：證明 P(QR)Q(PR) R(Q P) 證明：P(QR) P ( Q R) Q ( P R) Q(PR) R (Q P)例2：證明 ( P Q ) ( P Q ) P證明： ( P Q ) ( P Q ) P (Q Q) P T P R(Q P) 第一章 命題邏輯46四、代入規(guī)則和替換規(guī)則（1）代入規(guī)則例1：求證： (PQ) (PQ) 是永真式。定理1.3.2 在一個(gè)永

30、真式 A中，任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處，用另一個(gè)公式代入，所得公式B 仍是永真式。本定理稱(chēng)為代入規(guī)則。 邏輯聯(lián)結(jié)詞能夠從已知公式合并形成新公式，可把邏輯聯(lián)結(jié)詞看成運(yùn)算。“代入”和“替換”也有從已知公式得到新公式的作用，因此也可以看成運(yùn)算。證明：由排中律知，A A T ，即 A A 為永真式。 用公式PQ 代入A中，則得(PQ) (PQ) 根據(jù)代入規(guī)則可知，給定公式是永真式。第一章 命題邏輯47（2）替換規(guī)則 定理1.3.3 設(shè)A1是合式公式A的子公式，若A1B1，并且將 A 中的 A1用 B1 替換，得到公式B，則 AB。本定理稱(chēng)為 替換規(guī)則。這種替換稱(chēng)為等價(jià)替換。 證明：因?yàn)镼P Q

31、P 又由吸收律吸收律可知， P(PQ) P 根據(jù)替換規(guī)則替換規(guī)則可得， Q(P(PQ) QP例2: 證明：Q(P(PQ) QP 第一章 命題邏輯48代入和替換的區(qū)別:n代入是對(duì)原子命題變?cè)缘模?而替換通常是可對(duì)命題公式實(shí)行之；n代入規(guī)則必須用于永真式； 而替換則不必；n代入必須是處處代入； 替換則可部分替換，亦可全部替換。第一章 命題邏輯491.4 對(duì)偶式與蘊(yùn)涵式定義1.4.1 在給定的僅使用聯(lián)結(jié)詞 、和的命題公式 A 中，若把和互換，F(xiàn) 和T 互換而得到一個(gè)命題公式A*，則稱(chēng)A*為A的對(duì)偶式，同時(shí)A也是A*的對(duì)偶式。 A 與A*互為對(duì)偶式。一、對(duì)偶式第一章 命題邏輯50例：寫(xiě)出下列公式的

32、對(duì)偶式（1）(PQ) R（2）P T解： （1）(P Q) R（2）P F（3） ( P Q) (P (Q S) （3）( P Q) (P (Q S)第一章 命題邏輯51定理1.4.1(對(duì)偶定理)(德摩根律的推廣)設(shè)A和A*互為對(duì)偶式，P1，P2，Pn是出現(xiàn) A 和 A* 中的原子命題變?cè)?，則： A(P1，P2，Pn) A*(P1，P2，Pn) A(P1，P2，Pn) A*(P1，P2，Pn)證明：令公式A(P1，P2，Pn)中含有聯(lián)結(jié)詞，的數(shù)目為L(zhǎng)， 對(duì) L 施行歸納法證明之。 當(dāng)L=0時(shí)，A=P1， (P1) P1，結(jié)論成立。 當(dāng)L=1 時(shí)，A=P1P2，或A=P1P2， 或A= P1，結(jié)

33、論成立。表明，公式A的否定等價(jià)于其命題變?cè)穸ǖ膶?duì)偶式；表明，命題變?cè)穸ǖ墓降葍r(jià)于對(duì)偶式之否定。 第一章 命題邏輯52定理1.4.2 設(shè)A和B為兩個(gè)命題公式，若AB，則 A* *B* *。 證明：令P1，P2，Pn是A 和 B中的所有的命題變?cè)?因?yàn)?A(P1，P2，Pn) B(P1，P2，Pn) 所以 A(P1，P2，Pn) B(P1，P2，Pn)根據(jù)定理1.4.1 (1)可知， A(P1，P2，Pn) A*(P1，P2，Pn) B(P1，P2，Pn) B*(P1，P2，Pn)則A*(P1，P2，Pn) B*(P1，P2，Pn)利用代入規(guī)則，得 A*(P1，P2，Pn) B*(P1，P

34、2，Pn)第一章 命題邏輯53例 試證明： （1） ( P Q) (PQ) PQ （2）( P Q) (P Q) P Q證明：（1） ( P Q) (PQ) (PQ) (P Q) (P (P Q) (Q P Q) T (P Q) P Q （2）是（1）的對(duì)偶式， 根據(jù)定理1.4.2，即證得結(jié)論。 第一章 命題邏輯54二、蘊(yùn)涵式定義1.4.2 設(shè)A和B是兩個(gè)命題公式，若 AB是永真式，則稱(chēng)A蘊(yùn)涵B，記作AB，稱(chēng)AB為蘊(yùn)涵式或永真條件式。 符號(hào)和的區(qū)別與聯(lián)系類(lèi)似于和的關(guān)系。區(qū)別：是邏輯聯(lián)結(jié)詞，屬于對(duì)象語(yǔ)言中的符號(hào)，是公式 中的符號(hào)； 不是聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)公式 之間的關(guān)系，不是兩

35、公式中符號(hào)。聯(lián)系：AB成立，其充要條件AB是永真式。 第一章 命題邏輯55蘊(yùn)涵式性質(zhì) 自反性，即對(duì)任意公式A，有AA。 傳遞性，即對(duì)任意公式A、B和C，若AB，BC， 則AC。 對(duì)任意公式A、B和C，若AB，AC，則A(BC)。 對(duì)任意公式A、B和C，若AC，BC，則ABC。第一章 命題邏輯56蘊(yùn)涵式性質(zhì)定理1.4.3 設(shè)A和B是兩命題公式，AB的充要條件是： AB 且 BA。證明：（1）必要性：若AB成立，則AB是永真式 （2）充分性： 若AB 且 BA成立， 則AB且BA均是永真式， 即AB是永真式，故AB成立。第一章 命題邏輯57三、蘊(yùn)涵式證明方法n證明AB是蘊(yùn)涵式即證AB是永真式。 （

36、1）當(dāng)A為T(mén)，B為T(mén)時(shí)，則AB為T(mén)； （2）AB B A。蘊(yùn)涵式證明方法：n真值表法n前件真推導(dǎo)后件真方法設(shè)公式的前件A為真，若能推導(dǎo)出后件B也為真，則條件式AB是永真式，故蘊(yùn)涵式AB成立。n后件假推導(dǎo)前件假方法設(shè)公式的后件B為假，若能推導(dǎo)出前件A也為假，則條件式AB是永真式，故蘊(yùn)涵式AB成立。第一章 命題邏輯58例子：Q(PQ) P 證明：（1）前件真推導(dǎo)后件真方法： 前件為真：Q(PQ)為真，則Q和 (PQ)都為真， 于是 Q 為F ，P 為F ，得P 為真，即后件為真；（2）后件假推導(dǎo)前件假方法： 后件為假： P 為假，則P 為真， (a)若Q 為F ，則(PQ)為F ，前件為假； (b

37、)若Q 為T(mén) ，則Q為F ，前件為假。第一章 命題邏輯59四、基本蘊(yùn)涵式(1)ABA 化簡(jiǎn)式(2)ABB 化簡(jiǎn)式(3)AAB 附加式(4)AAB 附加式變形(5)BAB 附加式變形(6)(AB)A 化簡(jiǎn)式變形(7)(AB) B 化簡(jiǎn)式變形(8)A(AB)B 假言推論(9)B(AB) A 拒取式下面給出常用的蘊(yùn)涵式，稱(chēng)為基本蘊(yùn)涵式，它們的正確性可用上述方法或歸納法證明之。第一章 命題邏輯60四、基本蘊(yùn)涵式（續(xù)）(10) A(AB)B 析取三段論(11) (AB)(BC)AC 條件三段論(12) (AB)(BC) AC 雙條件三段論(13) (AB)(CD)(AC) BD 合取構(gòu)造二難(14) (

38、AB)(CD)(AC) BD 析取構(gòu)造二難 特別當(dāng)B = D時(shí)，有 (AB)(CB)(AC) B 二難推論 (AB)(CB)(AC) B 二難推論(15) AB (AC)(BC ) 前后件附加 AB (AC)(BC)(16) A，BAB 合取引入第一章 命題邏輯611.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組一、聯(lián)結(jié)詞的擴(kuò)充 為了簡(jiǎn)潔而直接地表達(dá)命題間的聯(lián)系，尚需定義4個(gè)聯(lián)結(jié)詞，它們分別是：n合取非聯(lián)結(jié)詞n析取非聯(lián)結(jié)詞 n條件非聯(lián)結(jié)詞 n雙條件非聯(lián)結(jié)詞第一章 命題邏輯62(一) 合取非聯(lián)結(jié)詞 定義1.5.1 設(shè)P和Q是任兩個(gè)原子命題， 由合取非聯(lián)結(jié)詞 把P，Q連接成PQ，稱(chēng)它為P和Q的合取非式復(fù)合命題，讀

39、作“P合取非Q”。 PQ的真值由命題P和Q的真值確定：當(dāng)且僅當(dāng)P和 Q均為T(mén) 時(shí)，PQ為 F，否則PQ為T(mén)。 “合取非”又常稱(chēng)為“與非”。第一章 命題邏輯63（二）析取非聯(lián)結(jié)詞 定義1.5.1 設(shè)P和Q是任意兩個(gè)原子命題， 由析取非聯(lián)結(jié)詞 把P，Q連接成PQ，稱(chēng)它為P和Q的析取非式復(fù)合命題，讀作“P析取非Q”。 PQ的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為F時(shí)，PQ為T(mén)，否則PQ為F。 “析取非”又常稱(chēng)為“或非”。 第一章 命題邏輯64（三）條件非聯(lián)結(jié)詞 定義1.5.1 設(shè)P和Q是任意兩個(gè)原子命題， 由條件非聯(lián)結(jié)詞 把P，Q連接成P Q，稱(chēng)它為P和Q的條件非式復(fù)合命題，讀作“P條件非Q”。

40、 P Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P為T(mén)而Q為F時(shí)，P Q為T(mén)；否則P Q為F。 有時(shí)也把條件非聯(lián)結(jié)詞記為“ ” 第一章 命題邏輯65（四）雙條件非聯(lián)結(jié)詞 定義1.5.1 設(shè)P 和Q是任兩個(gè)原子命題， 由雙條件非聯(lián)結(jié)詞 把P，Q連接成 P Q，稱(chēng)它為P和Q的雙條件非式復(fù)合命題，讀作“P雙條件非Q”。 P Q的真值由P 和 Q的真值確定：當(dāng)且僅當(dāng)P和Q的真值不同時(shí)， P Q為T(mén)，否則P Q為F。 “雙條件非”又常稱(chēng)為“異或”，也常用符號(hào)“”或“ ”表示之。 第一章 命題邏輯66nP Q (PQ)nP Q (PQ)nP Q (PQ)nP Q (P Q)上述4個(gè)聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值表

41、如下：P QP Q P Q P Q P Q 0 0 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0由真值表可知：第一章 命題邏輯67二、與非、或非和異或的性質(zhì)(a) P Q QP(b) P P P(c) (PQ)(PQ)PQ(d) (PP)(QQ)PQ（一）與非的性質(zhì) 與非、或非以及異或在計(jì)算機(jī)科學(xué)中是經(jīng)常使用的三個(gè)聯(lián)結(jié)詞。因此掌握它們的性質(zhì)是十分必要的。 令P, Q, R是原子命題變?cè)?a) P Q Q P(b) P P P(c) (PQ)(PQ)PQ(d) (PP)(QQ)PQ（二）或非的性質(zhì)第一章 命題邏輯68（三）異或的性質(zhì) (a) P Q Q

42、 P 交換律(b) P (Q R) (P Q) R 結(jié)合律(c) P(Q R) (PQ) (PR) 分配律(d) P P F，F(xiàn) P P，T P P(e) 若P Q R，則 Q R P，R P Q， 且P Q R F。第一章 命題邏輯69三、聯(lián)結(jié)詞功能完全組nP Q (PQ)nP Q (PQ)nP Q (PQ)nP Q (P Q)nP Q (PQ)(QP)nP Q PQnP Q (PQ)nP Q (PQ) 即擴(kuò)充的4個(gè)聯(lián)結(jié)詞 能由原有5個(gè)聯(lián)結(jié)詞分別替代之，而原有5個(gè)聯(lián)結(jié)詞 又能由聯(lián)結(jié)詞組， 或， 取代。第一章 命題邏輯70定義1.5.2 稱(chēng)G為聯(lián)結(jié)詞功能完全組(最小聯(lián)結(jié)詞組)，如果G滿足下列兩

43、個(gè)條件： 由G中聯(lián)結(jié)詞構(gòu)成的公式能等價(jià)表示任意命題公式； G 中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價(jià)表示?？梢宰C明以下都是聯(lián)結(jié)詞功能完全組：n， 可以證明以下不是聯(lián)結(jié)詞功能完全組：n， , ， ， ， 第一章 命題邏輯71例1. 證明任意命題公式都可由僅包含，的命題公式代換，且它們是最小聯(lián)結(jié)詞組。證明：因?yàn)椋?）P Q (PQ)(QP)，故可把包含“”的公式等價(jià)變換為包含“”和“”的公式。（2）由P Q PQ 說(shuō)明包含“”的公式可以變換為包含“”和“”的公式。（3）由P Q (PQ) 和P Q (PQ)說(shuō)明“”和“”可以相互代換。故由 這五個(gè)聯(lián)結(jié)詞組成的命題公式，必可由，組成的命題公式所替代。（

44、4）P Q (PQ) （5）P Q (PQ)（6）P Q (PQ) （7）P Q (P Q)因此，任意命題公式都可由僅包含，的命題公式代換，且它們是最小聯(lián)結(jié)詞組。第一章 命題邏輯72例2. 證明， ， 不是最小聯(lián)結(jié)詞組。證明：若或是最小聯(lián)結(jié)詞組，則 P (P) P (P ) 對(duì)所有命題變?cè)概蒚，則等價(jià)式左邊為F,右邊為T(mén), 與等價(jià)表達(dá)式矛盾!。 若 是最小聯(lián)結(jié)詞組，則 P P (P (P ) 對(duì)所有命題變?cè)概蒚，則等價(jià)式左邊為F，右邊為T(mén)， 矛盾！第一章 命題邏輯731.7 公式標(biāo)準(zhǔn)型范式一、簡(jiǎn)單合取式與簡(jiǎn)單析取式 定義1.7.1 命題變?cè)兔}變?cè)姆穸?，稱(chēng)為文字。如果一個(gè)文字恰為另一個(gè)

45、文字的否定，則稱(chēng) 它們?yōu)橐粚?duì)相反文字。例如：P和P都是文字，并且是一對(duì)相反文字； P不是文字； P和Q都是文字，但不是一對(duì)相反文字。對(duì)于給定公式的判定問(wèn)題，可用真值表方法加以解答。當(dāng)公式中命題變?cè)臄?shù)目較大時(shí)，真值表很麻煩。增加一個(gè)命題變?cè)?，真值表的行?shù)目比原來(lái)增加一倍。為解決這一問(wèn)題，需要研究公式標(biāo)準(zhǔn)型問(wèn)題。第一章 命題邏輯74定義1.7.2 設(shè) L1，L2，Lk 都是文字， 稱(chēng) L1L2Lk 為 簡(jiǎn)單析取式，并稱(chēng) Li 為析取項(xiàng)； 稱(chēng) L1L2Lk 為 簡(jiǎn)單合取式，并稱(chēng) Li 為合取項(xiàng)， 其中 1ik。n公式P，Q，PQ 和PQP 等都是簡(jiǎn)單合取式，其中P，Q 和 P 為相應(yīng)的簡(jiǎn)單合取式的

46、合取項(xiàng)；n公式P，Q，P Q，P Q P 等都是簡(jiǎn)單析取式，其中P，Q和 P 為相應(yīng)簡(jiǎn)單析取式的析取項(xiàng)。n一個(gè)命題變?cè)蚱浞穸瓤梢允呛?jiǎn)單合取式也可以是簡(jiǎn)單析取式，如P, Q等。第一章 命題邏輯75n定理1.7.1 簡(jiǎn)單合取式為永假式的充要條件是：它至少含有相反文字出現(xiàn)。n定理1.7.2 簡(jiǎn)單析取式為永真式的充要條件是：它至少含有相反文字出現(xiàn)。證明：充分性：因?yàn)閷?duì)于任何命題變?cè)狿, 有P P為 F, 所以， 若P P 在簡(jiǎn)單合取式中出現(xiàn)，根據(jù)定義 1.7.1, 它必是永假式 F。 必要性：假設(shè)某個(gè)簡(jiǎn)單合取式為永假式F， 但該簡(jiǎn)單 合取式中不同時(shí)包含相反文字。對(duì)這個(gè)簡(jiǎn)單合取式中 各命題變?cè)概烧?/p>

47、值T，而各帶否定的命題變?cè)概?真值F， 則使簡(jiǎn)單合取式取真值T，這與原假設(shè)矛盾！第一章 命題邏輯76二、析取范式與合取范式 n定義1.7.3 設(shè)A1，A2，Am為簡(jiǎn)單合取式，稱(chēng)A1A2Am為 析取范式，其中1m。n定義1.7.4 設(shè)B1，B2，Bn為簡(jiǎn)單析取式，稱(chēng)B1B2Bn為 合取范式，其中1n。n(PQ)(PQ)(PQQ)是析取范式nP(PQ)是合取范式nPQ 既是析取范式又是合取范式 例子：第一章 命題邏輯77定理1.7.3 對(duì)于任何一個(gè)命題公式，都存在與其等價(jià)的析取范式和合取范式。求范式算法： 使用命題定律，消去公式中除 、 和 以外的公式中出現(xiàn)的所有聯(lián)結(jié)詞； 使用 (P) P 和

48、德 摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞 都移到命題變?cè)埃?利用結(jié)合律、分配律等將公式化成析取范式或合取 范式。第一章 命題邏輯78例子：求(P(QR)S 的析取范式和合取范式。 解：(P(QR)S (P (Q R) ) S(P ( Q R) SP( QR)S 析取范式析取范式(PQS) (PRS)合取范式合取范式第一章 命題邏輯79三、范式的應(yīng)用 n利用析取范式和合取范式可對(duì)公式進(jìn)行判定。定理1.7.4 公式A為永假式的充要條件是A 的析取范式 中每個(gè)簡(jiǎn)單合取式至少包含一對(duì)相反文字。定理1.7.5 公式A為永真式的充要條件是A 的合取范式中每個(gè)簡(jiǎn)單析取式至少包含一對(duì)相反文字。第一章 命題邏輯80

49、例：判定下面公式為何種公式： (1) P(QR)(PR) (2) (PQ)P解: (1) P(QR)(PR) P(Q R)(P R) (PQ R P ) (PQ R R) T 為永真式 (2) (PQ)P (P Q) P (P Q) P (P P) (Q P) 為可滿足式第一章 命題邏輯81范式不惟一性 例 求(PQ)P 的析取范式和合取范式。解： (PQ)P (PQ)P (PQ)P 析取范式 P 析取范式 (PQ)P (PQ)P (PP)(QP) 合取范式 P(QP) 合取范式 P 合取范式第一章 命題邏輯821.8 公式的主范式 范式基本解決了公式的判定問(wèn)題。但由于范式不唯一性，對(duì)識(shí)別公式

50、間是否等價(jià)帶來(lái)不便和困難，公式的主范式解決了這個(gè)問(wèn)題。 一、主析取范式 （1）小項(xiàng)的概念和性質(zhì) 定義1.8.1 在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中， 若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)該簡(jiǎn)單合取式為小項(xiàng)，或布爾積。第一章 命題邏輯83（1）小項(xiàng)的概念和性質(zhì) 例如：n 兩個(gè)命題變?cè)狿和Q，其構(gòu)成的小項(xiàng)有： PQ，PQ，PQ和PQ；n 三個(gè)命題變?cè)狿、Q和R，其構(gòu)成的小項(xiàng)有： PQR，PQR，PQR， PQR， PQR ，PQR， PQR，PQR。 n n個(gè)命題變?cè)錁?gòu)成的小項(xiàng)有： 共形成 2n 個(gè)小項(xiàng)。 第一章 命題邏輯84小項(xiàng)編碼：n目的：簡(jiǎn)化小項(xiàng)的書(shū)寫(xiě)和表示

51、。n如果將命題變?cè)醋值湫蚺帕校⑶野衙}變?cè)c 1 對(duì)應(yīng)，命題變?cè)姆穸ㄅc 0 對(duì)應(yīng)，則可對(duì) 個(gè)小項(xiàng) 依二進(jìn)制數(shù)編碼，記為 mi ，其下標(biāo) i 是由二進(jìn)制數(shù) 轉(zhuǎn)化的十進(jìn)制數(shù)。n用這種編碼所求得 個(gè)小項(xiàng)的真值表，可明顯地反 映出小項(xiàng)的性質(zhì)。 n2n2第一章 命題邏輯85 2個(gè)命題變?cè)?P 和 Q 的小項(xiàng)真值表如下：m(二) m00 m01 m10 m11 P Q PQ PQ PQ PQ 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 01 1 0 0 0 1m(+) m0 m1 m2 m3第一章 命題邏輯86小項(xiàng)的性質(zhì):(a) 沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，即是說(shuō)各小項(xiàng)的真值表都是

52、 不同的；(b) 任意兩個(gè)不同的小項(xiàng)的合取式是永假的：mimj F， ij。(c) 所有小項(xiàng)之析取為永真： miT。(d) 每個(gè)小項(xiàng)只有一個(gè)成真指派，且其真值1位于主對(duì)角線上。這表明每個(gè)小項(xiàng)與其成真指派之間建立了一一對(duì)應(yīng)關(guān)系。ni 1第一章 命題邏輯87（2）主析取范式定義與存在定理 定義1.8.2 在給定公式的析取范式中，若其簡(jiǎn)單合取式都是小項(xiàng)， 則稱(chēng)該范式為主析取范式。定理1.8.1 任意含 n 個(gè)命題變?cè)姆怯兰倜}公式 A 都存在與其等價(jià)的主析取范式。 證明：首先求出公式A的所有小項(xiàng)，再列出各小項(xiàng)和公式A 的真值表。對(duì)A的每個(gè)解釋為真且取真值為1的小項(xiàng)， 這些小項(xiàng)的析取范式，即A的主析

53、取范式，顯然與A 等價(jià)。第一章 命題邏輯88公式化歸法： n把給定公式化成析取范式；n刪除析取范式中所有為永假的簡(jiǎn)單合取式；n用等冪律把簡(jiǎn)單合取式中重復(fù)出現(xiàn)的同一命題變?cè)?jiǎn)為一次出現(xiàn)，如PP P。n用同一律補(bǔ)進(jìn)簡(jiǎn)單合取式中未出現(xiàn)的所有命題變?cè)?，如Q，則PP(QQ)，并用分配律展開(kāi)之，將相同的簡(jiǎn)單合取式的多次出現(xiàn)化為一次出現(xiàn)，這樣得到了給定公式的主析取范式。真值表法：n列出真值表；n找出所有真值為1的解釋對(duì)應(yīng)的小項(xiàng)；n將這些小項(xiàng)進(jìn)行析取，即得主析取范式。（3）主析取范式的求法： 第一章 命題邏輯89例1：求(PQ)Q的主析取范式。解：（a）真值表法求之P QPQPQPQPQ(PQ)Q0 010

54、00 1 0 0 101001 11 000100 01 100011 1(PQ)Q (PQ) (PQ) m01 m11 m1 m3第一章 命題邏輯90（b）公式化歸法 (PQ)Q (P Q) Q ( P Q)(Q T) ( P Q)(Q (P P) ( P Q)( P Q) (P Q) ( P Q) (P Q) m1 m3第一章 命題邏輯91(4) 主析取范式的惟一性定理1.8.2 任意含n個(gè)命題變?cè)姆怯兰倜}公式，其主析取范式是惟一的。證明：反證法。假設(shè)一含有n個(gè)命題變?cè)姆怯兰俟紸有兩個(gè)不同的主析取范式 A1 和 A2。顯然， A1 A2 。 由于 A1 和 A2 是不同的主析取范式

55、，故至少存在一個(gè)小項(xiàng)，如mi ，只出現(xiàn)在A1和A2之一中，不妨令mi在A1中而不在A2中，取mi的成真指派S，S 是唯一的成真指派，于是 S(A1)為真，而S(A2)為假，這與已知A1 A2矛盾。第一章 命題邏輯92定義1.8.3 在n個(gè)命題變?cè)暮?jiǎn)單析取式中，若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一必出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)該簡(jiǎn)單析取式為大項(xiàng)，或布爾和。兩個(gè)命題變?cè)狿和Q，構(gòu)成大項(xiàng)有： PQ，PQ，PQ，PQ；n 三個(gè)命題變?cè)狿，Q和R，構(gòu)成大項(xiàng)有： PQR， PQR， PQR， PQR， PQR， PQR， PQR， PQR。 n n個(gè)命題變?cè)残纬蓚€(gè)命題變?cè)残纬?n個(gè)大項(xiàng)個(gè)大項(xiàng)。

56、 二、主合取范式 （1）大項(xiàng)的概念和性質(zhì) 第一章 命題邏輯93大項(xiàng)編碼：n目的：簡(jiǎn)化大項(xiàng)的書(shū)寫(xiě)和表示 。n如果將n個(gè)命題變?cè)判?，并且把命題變?cè)c對(duì)應(yīng)，命題變?cè)姆穸ㄅc對(duì)應(yīng)，則可對(duì) 個(gè)大項(xiàng)按二進(jìn)制數(shù)編碼，記為Mi，其下標(biāo) i 是由二進(jìn)制數(shù)化成的十進(jìn)制數(shù)。n用這種編碼所求的 個(gè)大項(xiàng)的真值表，能直接反映出大項(xiàng)的性質(zhì)。 n2n2第一章 命題邏輯942個(gè)命題變?cè)?P 和Q構(gòu)成所有大項(xiàng)的真值表如下： M(二)M00M01M10M11P QP QP QP QP Q0 00 11 01 1 0111101111011110M(+)M0M1M2M3第一章 命題邏輯95大項(xiàng)的性質(zhì)： (a) 沒(méi)有兩個(gè)大項(xiàng)是等價(jià)的

57、。(b) 任何兩個(gè)不同大項(xiàng)之析取是永真的，即 Mi Mj T，ij。(c) 所有大項(xiàng)之合取為永假，即 Mi F。(d) 每個(gè)大項(xiàng)只有一個(gè)解釋為假，且其真值0位于主對(duì)角線上。這表明每個(gè)大項(xiàng)與其成假指派建立了一一對(duì)應(yīng)關(guān)系。n1i第一章 命題邏輯96（2）主合取范式的定義與其存在定理 定義1.8.4 在給定公式的合取范式中，若其所有簡(jiǎn)單 析取式都是大項(xiàng)， 稱(chēng)該范式為主合取范式。定理1.8.3 任意含有n個(gè)命題變?cè)姆怯勒婷}公式A， 都存在與其等價(jià)的主合取范式。定理1.8.4 任意含n個(gè)命題變?cè)姆怯勒婷}公式A，其主合取范式是惟一的。 第一章 命題邏輯97（3）主合取范式的求法 n真值表法n公式化

58、歸法第一章 命題邏輯98三、主析取范式與主合取范式之間的關(guān)系 n由于主范式是由小項(xiàng)或大項(xiàng)構(gòu)成，兩者有下列關(guān)系： mi Mi Mi min因此，主析取范式和主合取范式有著“互補(bǔ)”關(guān)系。 設(shè)命題公式 A 中含有 n 個(gè)命題變?cè)褹的主析取范式中含有 k 個(gè)小項(xiàng)mi1,mi2,mik，則A的主析取范式中必含有 個(gè)小項(xiàng), 不妨含為 mj1, mj2 , mj(2n-k)。 即： A mj1 mj2 mj(2n-k)于是， A A (mj1 mj2 mj(2n-k) mj1 mj2 mj(2n-k) Mj1 Mj2 Mj(2n-k) kn2第一章 命題邏輯99從 A 的主析取范式求其主合取范式的步驟：

59、 (a) 求出A的主析取范式中沒(méi)有包含的小項(xiàng)。(b) 求出與(a)中小項(xiàng)的下標(biāo)相同的大項(xiàng)。(c) 做(b)中大項(xiàng)之合取，即為A的主合取范式。(PQ)Q m1m3，則 (PQ)Q M0M2。第一章 命題邏輯100（1）判定問(wèn)題 根據(jù)主范式的定義和定理，也可以判定含 n 個(gè)命題變?cè)墓?，其關(guān)鍵是先求出給定公式的主范式；其次按下列條件判定之： (a) 若A ，或A可化為與其等價(jià)的、含 個(gè)小項(xiàng)的主析取范式， 則A為永真式。 (b) 若A，或A可化為與其等價(jià)的、含 個(gè)大項(xiàng)的主合取范式， 則A為永假式。 (c) 若 A 不與或者 等價(jià)，且又不含 個(gè)小項(xiàng)或者大項(xiàng)，則A為 可滿足式。n2n2n2四、主范式的

60、應(yīng)用 第一章 命題邏輯101例1：判定下列公式為何類(lèi)公式：（1） (PQ)Q（2） (PQ)(PQ) （2）(PQ)(PQ) (PQ) (PQ) T 故其為永真式。解 （1）(PQ)Qm1m3 可見(jiàn)，其主范式中，大、小項(xiàng)數(shù)目均不到4，故 其為可滿足式。第一章 命題邏輯102例1：求證(PQ)(PR)P(QR) 證明：(PQ)(PR) (PQ) (PR) (PQ (R R) ) (P (Q Q)R) (PQ R ) (PQR) (P Q R ) (P Q R ) (PQR) (PQR ) (PQR ) M4 M5 M6（2）證明等價(jià)式成立 n若給定兩公式的主范式相同，則給定兩公式是等價(jià)的。 P(