離散數(shù)學(xué)：第一章 命題邏輯

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

DiscreteMathematics2離散數(shù)學(xué)的特點(diǎn)離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程。1976年美國(guó)IEEE計(jì)算機(jī)協(xié)會(huì)典型課程分委員會(huì)把離散數(shù)學(xué)列為計(jì)算機(jī)科學(xué)中專業(yè)基礎(chǔ)理論的核心課程。又稱計(jì)算機(jī)數(shù)學(xué)。離散數(shù)學(xué)有別于一般的工程數(shù)學(xué)。傳統(tǒng)的數(shù)學(xué)分析、微分方程、復(fù)變函數(shù)、泛函分析等課程以連續(xù)變量作為研究對(duì)象。離散數(shù)學(xué)是以研究各種各樣的離散量的結(jié)構(gòu)及離散量之間的關(guān)系為主要研究目標(biāo)。研究對(duì)象一般是有限個(gè)或可數(shù)個(gè)元素。這充分描述了計(jì)算機(jī)科學(xué)離散性的特點(diǎn)。3離散數(shù)學(xué)把計(jì)算機(jī)科學(xué)中所涉及到的研究離散量的數(shù)學(xué)綜合在一起，為研究計(jì)算機(jī)科學(xué)的相關(guān)問(wèn)題提供了有力的數(shù)學(xué)工具。換句話說(shuō)，離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中起到了工具性的作用，等同于高等數(shù)學(xué)在其他工程技術(shù)科學(xué)中的作用。離散數(shù)學(xué)的產(chǎn)生對(duì)計(jì)算機(jī)科學(xué)的發(fā)展具有重大影響和推動(dòng)作用，而計(jì)算機(jī)科學(xué)的發(fā)展又不斷地充實(shí)和豐富了離散數(shù)學(xué)的內(nèi)容。特別是在被譽(yù)為計(jì)算機(jī)科學(xué)時(shí)代的今天，離散數(shù)學(xué)以它獨(dú)特的魅力為越來(lái)越多的人們所矚目，并已經(jīng)成為了計(jì)算機(jī)科學(xué)工作者、應(yīng)用計(jì)算機(jī)的工程技術(shù)人員以及信息科學(xué)工作者等必備的數(shù)學(xué)工具之一。離散數(shù)學(xué)是數(shù)學(xué)工具4離散數(shù)學(xué)的任務(wù)通過(guò)離散數(shù)學(xué)知識(shí)的學(xué)習(xí)和訓(xùn)練，一方面可以幫助學(xué)生掌握證明問(wèn)題的方法，培養(yǎng)抽象思維的能力、符號(hào)演算和慎密概括的能力以及嚴(yán)密的邏輯推理的能力。另一方面使學(xué)生具有良好的專業(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ǔ)。通過(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ǔ)。5離散數(shù)學(xué)是建立在大量定義、定理之上的邏輯推理學(xué)科，因此對(duì)概念的理解是學(xué)習(xí)這門課程的核心。學(xué)習(xí)概念的基礎(chǔ)上，要特別注意概念之間的聯(lián)系，而描述這些聯(lián)系的實(shí)體是大量的定理和性質(zhì)。因此，深入地理解和掌握離散數(shù)學(xué)的基本概念、基本定理和結(jié)論，是學(xué)好離散數(shù)學(xué)的重要前提之一。離散數(shù)學(xué)的基本概念、思想方法，大量地應(yīng)用到邏輯電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、人工智能、數(shù)據(jù)庫(kù)原理等計(jì)算機(jī)科學(xué)專業(yè)課程。這些課程都要用到集合、關(guān)系、代數(shù)系統(tǒng)、圖的理論等基本概念進(jìn)行描述。離散數(shù)學(xué)課程學(xué)習(xí)的特點(diǎn)6離散數(shù)學(xué)的內(nèi)容：

數(shù)理邏輯（MathematicsLogic)

集合論(Sets)

組合論（Combination)

圖論（GraphTheory)

代數(shù)結(jié)構(gòu)（AlgbraStructure)7教學(xué)內(nèi)容：數(shù)理邏輯集合論圖論代數(shù)系統(tǒng)謂詞邏輯集合關(guān)系圖的基本概念幾個(gè)特殊圖代數(shù)系統(tǒng)的基本概念特殊代數(shù)系統(tǒng)離散數(shù)學(xué)函數(shù)圖的連通性代數(shù)系統(tǒng)的基本概念特殊代數(shù)系統(tǒng)代數(shù)系統(tǒng)的基本概念命題邏輯代數(shù)系統(tǒng)的同態(tài)與同構(gòu)8邏輯學(xué)（Logic）

邏輯學(xué)是研究人的思維形式結(jié)構(gòu)和規(guī)律的科學(xué)。由于研究對(duì)象和方法各有側(cè)重而又分為辯證邏輯、形式邏輯和數(shù)理邏輯。辯證邏輯：以辯證法認(rèn)識(shí)論的世界觀為基礎(chǔ)的邏輯學(xué)。形式邏輯：主要對(duì)人的思維形式結(jié)構(gòu)和規(guī)律進(jìn)行研究的類似于語(yǔ)法的一門工具性學(xué)科。思維的形式結(jié)構(gòu)包括概念、判斷和推理之間的結(jié)構(gòu)和聯(lián)系，其中概念是思維的基本單位，通過(guò)概念對(duì)事物是否具有某種屬性進(jìn)行肯定或否定的回答就是判斷；由一個(gè)或者幾個(gè)判斷推出另一個(gè)判斷的思維形式就是推理。

數(shù)理邏輯：用數(shù)學(xué)方法研究推理，是研究推理中前提和結(jié)論之間的形式關(guān)系的科學(xué)，又稱其為符號(hào)邏輯。9數(shù)理邏輯數(shù)理邏輯包括命題邏輯和謂詞邏輯。為了研究形式邏輯中的推理規(guī)律，數(shù)學(xué)家為其設(shè)計(jì)了一套表意符號(hào)體系，用人工符號(hào)來(lái)書(shū)寫邏輯法則，使形式邏輯數(shù)學(xué)化。萊布尼茲是數(shù)理邏輯的首席創(chuàng)始人，力主“思維計(jì)算化”正是應(yīng)用了一整套數(shù)學(xué)符號(hào)組成的形式系統(tǒng)來(lái)研究邏輯問(wèn)題，才使得邏輯學(xué)有了脫胎換骨的進(jìn)步，具備表達(dá)簡(jiǎn)潔、推理嚴(yán)謹(jǐn)、易于分析等優(yōu)點(diǎn)。音樂(lè)里有簡(jiǎn)譜和五線譜等人工符號(hào)，記錄音樂(lè)中音韻的節(jié)律和高低；化學(xué)中用分子式和反應(yīng)方程等人工符號(hào)記錄物質(zhì)的分子結(jié)構(gòu)和反應(yīng)過(guò)程。解:邏輯學(xué)家手指一門問(wèn)身旁一名戰(zhàn)士甲說(shuō)：“這扇門是死亡門，他(指另一名戰(zhàn)士乙)將回答‘是’，對(duì)嗎？”

當(dāng)被問(wèn)戰(zhàn)士甲回答“對(duì)”，則邏輯學(xué)家開(kāi)啟所指的門從容離去。

當(dāng)被問(wèn)戰(zhàn)士甲回答“否”，則邏輯學(xué)家開(kāi)啟另一門從容離去。例子：有一個(gè)邏輯學(xué)家誤入某部落，被拘于牢獄，酋長(zhǎng)意欲放行，他對(duì)邏輯學(xué)家說(shuō)：“今有兩門，一為自由，一為死亡，你可任意開(kāi)啟一門。為協(xié)助你脫逃，現(xiàn)今加派兩名戰(zhàn)士負(fù)責(zé)解答你所提的任何問(wèn)題。惟可慮者，此兩戰(zhàn)士中一名天性誠(chéng)實(shí)，一名說(shuō)謊成性，今后生死由你自己選擇。”邏輯學(xué)家沉思片刻，即向一戰(zhàn)士發(fā)問(wèn)，然后開(kāi)門從容離去。該邏輯學(xué)家應(yīng)如何發(fā)問(wèn)？設(shè)P：被問(wèn)戰(zhàn)士甲是誠(chéng)實(shí)人。

Q

：被問(wèn)戰(zhàn)士甲的回答是“對(duì)”。

R

：另一戰(zhàn)士乙的回答是“是”。

S

：這扇門是死亡門。則有

RP

Q且有

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

┐P)∧┐Q┐Q11例子：設(shè)有下列情況，結(jié)論是否有效。

(1)

或者是天晴，或者是下雨；

(2)

如果是天晴，我去看電影；

(3)

如果我去看電影，我就不看書(shū)。結(jié)論：如果我在看書(shū)，則天在下雨。解:令W：天晴；Q：下雨；

S：我去看電影；R：我在看書(shū)。前提：WQ,

WS，S┐R

結(jié)論：RQ解：演繹法推理過(guò)程如下：{1}(1)R

P（附加前提）{2}(2)S┐RP

{1,2}(3)┐ST，(1)(2)I9{4}(4)WS

P{1,2,4}(5)┐W

T，(3)(4)I9

{6}(6)WQP{6}(7)┐WQT,(6)E12{6}(8)┐W

QT,(7)I1{1,2,4,6}(9)QT,(5)(8)I8{2,4,6}(10)RQCP,(1)(9)例子：設(shè)有下列情況，結(jié)論是否有效。

(1)

或者是天晴，或者是下雨；

(2)

如果是天晴，我去看電影；

(3)

如果我去看電影，我就不看書(shū)。結(jié)論：如果我在看書(shū)，則天在下雨。解:令W：天晴；Q：下雨；

S：我去看電影；R：我在看書(shū)。前提：WQ,

WS，S┐R

結(jié)論：RQ例子：設(shè)有下列情況，結(jié)論是否有效。

(1)

或者是天晴，或者是下雨；

(2)

如果是天晴，我去看電影；

(3)

如果我去看電影，我就不看書(shū)。結(jié)論：如果我在看書(shū)，則天在下雨。12命題邏輯（PropositionalLogic）也稱命題演算或語(yǔ)句演算，它研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系。

原子命題是命題邏輯中研究的基本單位，即對(duì)原子命題不再分解，只有真、假二個(gè)真值，所以命題邏輯也稱二值邏輯。謂詞邏輯（PredicateLogic）謂詞邏輯是比命題邏輯更加廣泛的推理形式；謂詞邏輯對(duì)命題做進(jìn)一步的分析，把原子命題分解為謂詞和個(gè)體兩部分，進(jìn)一步揭示分析前提和結(jié)論在形式結(jié)構(gòu)方面的聯(lián)系。13第1章命題邏輯1.1命題與聯(lián)結(jié)詞1.2命題公式、翻譯和真值表1.3公式分類與等價(jià)式1.4對(duì)偶式與蘊(yùn)含式1.5聯(lián)結(jié)詞的擴(kuò)充與功能完全組1.6公式標(biāo)準(zhǔn)型----范式1.7公式的主范式1.8命題邏輯的推理理論141.1命題與聯(lián)結(jié)詞

一、命題的概念命題：非真必假的陳述句。

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

不是命題我所說(shuō)的是假的16例：判斷下列語(yǔ)句哪些是命題。若是命題，指出真值巴黎在法國(guó)請(qǐng)勿喧嘩！明天去哪里？有外星人曹操是明朝人6+8>14今天下雨今天我休息11+1=100是命題，真不是命題不是命題是，不確定真值是，假是，假是，真值不確定是，真值不確定是，真值不確定17二、命題標(biāo)識(shí)符命題標(biāo)識(shí)符：表示原子命題的符號(hào)稱為命題標(biāo)識(shí)符，簡(jiǎn)稱命題符。原子命題的符號(hào)表示：大小寫英文字母：P、Q、R、p、q、r、……

帶下標(biāo)的大寫字母：Pi，Qi，Ri，……例如：P：北京是中國(guó)的首都。命題常元：一個(gè)命題標(biāo)識(shí)符P，如果表示一個(gè)確定的命題，則稱P

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

合取聯(lián)結(jié)詞——∧

析取聯(lián)結(jié)詞——∨條件聯(lián)結(jié)詞——→

雙條件聯(lián)結(jié)詞——19（1）否定聯(lián)結(jié)詞

設(shè)P是一個(gè)命題，由聯(lián)結(jié)詞┐和命題P構(gòu)成┐P，讀“非P”。┐P為命題P的否定式復(fù)合命題。聯(lián)結(jié)詞┐是自然語(yǔ)言中的“非”、“不”和“沒(méi)有”等的邏輯抽象。P┐PTFFT

P：上海是一個(gè)大城市。┐P：上海并不是一個(gè)大城市。┐P：上海是一個(gè)不大的城市。20(2)合取聯(lián)結(jié)詞

令P和Q是兩個(gè)命題，由聯(lián)結(jié)詞∧把P，Q連接成P∧Q，讀做“P與Q”，或“P合取Q”。稱P∧Q為P和Q的合取式復(fù)合命題。聯(lián)結(jié)詞∧是自然語(yǔ)言中的“并且”，“既…又…”等的邏輯抽象。PQP∧QQ∧PTTTTTFFFFTFFFFFFP：今天下雨。Q：明天下雨。P∧Q：今天下雨而且明天下雨。P∧Q：今天與明天都下雨。P∧Q：這兩天都下雨。21(3)析取聯(lián)結(jié)詞

設(shè)P和Q是兩個(gè)命題，由聯(lián)結(jié)詞∨把P，Q連接成P∨Q，讀做“P或Q”。稱P∨Q為P，Q的析取式復(fù)合命題。析取聯(lián)結(jié)詞是“或”、“或者”的邏輯抽象。析取聯(lián)結(jié)詞是表示可兼或，即二者可同時(shí)發(fā)生，不排斥二者發(fā)生的情況。析取聯(lián)結(jié)詞不表示不可兼或排斥或，即非此即彼。PQP∨QQ∨PTTTTTFTTFTTTFFFF今天晚上我在家看電視或去劇場(chǎng)看戲。（排斥或）----不是命題聯(lián)結(jié)詞他可能是100米或400米賽跑的冠軍。（可兼或）----是命題聯(lián)結(jié)詞他昨天做了二十或三十道題。（表示近似數(shù)）----不是聯(lián)結(jié)詞22(4)條件聯(lián)結(jié)詞設(shè)P和Q是兩個(gè)命題，由聯(lián)結(jié)詞→把P，Q連接成P→Q，讀做“如果P，則Q”或者“P條件Q”。稱P→Q為P和Q的條件式復(fù)合命題，把P和Q分別稱為P→Q的前件和后件，或者前提和結(jié)論。聯(lián)結(jié)詞→是自然語(yǔ)言中“如果…，則…”，“若…，才能…”等的邏輯抽象，是充分條件。在自然語(yǔ)言中，前件為假，不管結(jié)論真假，整個(gè)語(yǔ)句的意義往往無(wú)法判斷。在命題邏輯中，當(dāng)P為F，P→Q為T，稱為“善意推定”。在命題邏輯中允許前件和后件間無(wú)必然的因果關(guān)系。23(4)條件聯(lián)結(jié)詞PQP→QQ→PTTTTTFFTFTTFFFTTP：天下雨；Q：馬路濕；

P→Q：如果天下雨，則馬路濕。下面討論P(yáng)→Q的真值：如果天下雨，則馬路濕；如果天下雨，則馬路不濕；如果天不下雨，則馬路濕；(善意推斷)如果天不下雨，則馬路不濕；P：2+2=4；Q：雪是黑的；P→Q：如果2+2=4，則雪是黑的。24(5)雙條件聯(lián)結(jié)詞令P和Q是兩個(gè)命題，由聯(lián)結(jié)詞把P，Q連接成P

Q，讀做“P當(dāng)且僅當(dāng)Q”。稱P

Q為P和Q的雙條件式復(fù)合命題。雙條件聯(lián)結(jié)詞又常稱為同或，并用符號(hào)⊙表示。雙條件聯(lián)結(jié)詞是自然語(yǔ)言中的“充分必要條件”、“當(dāng)且僅當(dāng)”等的邏輯抽象。PQPQQ

PTTTTTFFFFTFFFFTT三角形是等邊三角形當(dāng)且僅當(dāng)三角形的三個(gè)內(nèi)角相等。2+2=4當(dāng)且僅當(dāng)太陽(yáng)是恒星。25四、命題分類命題分兩類：原子命題和復(fù)合命題復(fù)合命題：由原子命題和聯(lián)結(jié)詞復(fù)合而成判斷一個(gè)命題是否為復(fù)合命題，其關(guān)鍵是聯(lián)結(jié)詞是否出現(xiàn)，出現(xiàn)聯(lián)結(jié)詞則是復(fù)合命題，不出現(xiàn)聯(lián)結(jié)詞則是原子命題。復(fù)合命題的真值只取決于構(gòu)成它們的各原子命題的真值，與它們的內(nèi)容、含義無(wú)關(guān)?！?、∨、

具有對(duì)稱性；而┐、→沒(méi)有對(duì)稱性；聯(lián)結(jié)詞都有從已知命題得到新的命題的作用，它們具有操作或運(yùn)算的意義。聯(lián)結(jié)詞可以被看做是一、二元運(yùn)算或一、二元函數(shù)?？偨Y(jié)261.2命題公式、翻譯和真值表

一、命題公式定義1.2.1原子命題公式：命題常元、命題變?cè)y(tǒng)稱為原子命題公式，簡(jiǎn)稱原子公式。定義1.2.2

合式公式是由下列規(guī)則形成的字符串：

(1)真值T和F是合式公式。

(2)原子命題公式是一個(gè)合式公式。

(3)若A是合式公式，則┐A是合式公式。

(4)若A和B是合式公式，則A∧B、A∨B、A→B和AB都是合式公式。

(5)經(jīng)過(guò)有限次地使用(1)(2)(3)(4)所得到的結(jié)果，都是合式公式。定義1.2.3

如果A1是公式A的一部分，且A1是一個(gè)公式，稱A1是A的子公式。27定義補(bǔ)充(A∧B∧C)、(A∨B∨C)也是合式公式；(A∧B)、(A∨B)、(A→B)和(A

B)也被稱為合取式、析取式、條件式和雙條件式；A，B分別為(A∧B)、(A∨B)的合取項(xiàng)和析取項(xiàng)。(┐P)∨Q，(P→(Q∧R))都是合式公式；(P→Q，(P→Q)

(∧R)都不是合式公式。28聯(lián)結(jié)詞的優(yōu)先級(jí)

公式最外層的圓括號(hào)可省略，如把(P→(Q∨R))寫成P→(Q∨R)。┐只作用于鄰接后的原子命題變?cè)?，例如?┐P)∨Q寫成┐P∨Q。聯(lián)結(jié)詞的優(yōu)先級(jí)從高到低是：┐，∧，∨，→，。例：設(shè)公式A為(P→Q)→(Q∨R)，則P→Q，Q∨R都是A的子公式。29二、命題的翻譯

命題的符號(hào)化要注意下列事項(xiàng)：確定給定句子是否為命題。句子中連詞是否為命題聯(lián)結(jié)詞。要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合式公式，稱為翻譯，也稱符號(hào)化。

命題的符號(hào)化在數(shù)理邏輯中很重要！30例：符號(hào)化下列命題：他既聰明又用功。他雖聰明但不用功。除非你努力，否則你將失敗。除非天氣好，我才騎自行車上班。小王晚上要回家，除非下大雨。只有睡覺(jué)才能恢復(fù)疲勞。只要我還有口氣，我就要戰(zhàn)斗。A中沒(méi)有元素，A就是空集。張明或者李強(qiáng)都可以做這件事。張明和李強(qiáng)都做這件事了。僅當(dāng)你走，我將留下。P∧Q，P:他聰明Q：他用功P∧┐Q，P:他聰明Q：他用功┐P→Q，

P:你努力

Q:你失敗

Q→P,

P:天氣好

Q:我騎自行車上班┐Q→P,P:小王晚上回家

Q:下大雨Q→P，P：睡覺(jué)

Q：恢復(fù)疲勞P∧Q,P:張明做這件事

Q:李強(qiáng)做這件事P→Q，P：我還有口氣

Q：我要戰(zhàn)斗P

Q，P:A中沒(méi)有元素

Q:A是空集P∨Q,P:張明做這件事

Q:李強(qiáng)做這件事Q→P,P:你走了

Q:我留下31例：符號(hào)化下列命題：鐵和氧化合，但鐵和氮不化合。如果我下班早，就去商店看看，除非我很累。李四是計(jì)算機(jī)系的學(xué)生，他選修了日語(yǔ)課或法語(yǔ)課。李四是計(jì)算機(jī)系的學(xué)生，他住在312室或313室。除非天氣好，否則我是不會(huì)去公園的。如果晚上做完作業(yè)且沒(méi)有其他的事，他就會(huì)去看電視或聽(tīng)音樂(lè)。P∧┐Q,P:鐵和氧化合Q:鐵和氮化合┐P→(Q→R),P:我很累Q:我下班早

R:我去商店看看P∧(Q∨R),P:李四是計(jì)算機(jī)系的學(xué)生

Q:他選修日語(yǔ)課R:他選修法語(yǔ)課P∧((Q∧┐R)∨(┐Q∧R)),P:李四是計(jì)算機(jī)系的學(xué)生Q:他住312R:他住313

Q→P,P:天氣好Q:我去公園(P∧Q)→((L∧┐M)∨(┐L∧M))P:他晚上做完作業(yè)，Q：他沒(méi)有其他事L：他看電視M：他聽(tīng)音樂(lè)32三、真值表

定義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)稱為A的一個(gè)真值指派，或稱為A的一種解釋，記為S(A)或I(A)。若S(A)或I(A)為T，稱S(A)或I(A)為A的成真指派或說(shuō)A的解釋為真。A的成假指派的定義類似。為方便計(jì)，有時(shí)將S(Pi)=1或S(Pi)=0記為Pi/1或Pi/0，1≤i≤n。顯然，若公式A中有n個(gè)不同命題變?cè)?，便?n組真值指派。33真值表定義1.2.5

設(shè)A為一命題公式，對(duì)其中出現(xiàn)的命題變?cè)鏊锌赡艿拿恳唤M真值指派S，連同公式A的相應(yīng)的S(A)匯列成表，稱為A的真值表。

真值表由兩部分組成：表的左部分列出公式的每一種解釋；表的右部分給出相應(yīng)每種解釋公式得到的真值。真值表的約定：命題變?cè)醋值湫蚺帕小?duì)公式每個(gè)解釋，以二進(jìn)制數(shù)從小到大或者從大到小順序列出。若公式復(fù)雜，可先列出各子公式的真值(若有括號(hào)，則應(yīng)從里層向外層展開(kāi))，最后列出所給公式的真值。34P┐PTFFTPQP∧QQ∧PTTTTTFFFFTFFFFFFPQP∨QQ∨PTTTTTFTTFTTTFFFFPQP→QQ→PTTTTTFFTFTTFFFTTPQPQQ

PTTTTTFFFFTFFFFTT35例子：求(P→Q)(┐P∨Q)的真值表

PQ(P→Q)(┐P∨Q)

001111011111100100111101步驟

①

③

①

②36例子：求(P→Q)∧┐R的真值表

PQR(P→Q)∧┐R

000111001100010111011100100001101000110111111100步驟①

②

①此真值表有3個(gè)成真指派：(P/0,Q/0,R/0),(P/0,Q/1,R/0),(P/1,Q/1,R/0)。37例：作出下列命題的真值表:并非“室內(nèi)很冷或很亂”，

也不是“室外暖和且室內(nèi)太臟”PQRS┐(P∨Q)∧┐（R∧S）000011100011110010111001110001000010101001解：P：室內(nèi)很冷Q：室內(nèi)很亂

R：室外暖和S：室內(nèi)太臟

本題可用符號(hào)表示為：┐(P∨Q)∧┐（R∧S）381.3公式分類一、公式分類定義1.3.1

設(shè)A為一個(gè)命題公式，對(duì)A做所有可能的解釋I，對(duì)于這些解釋I：若I(A)皆為成真，稱A為永真式；若I(A)皆為成假，稱A為永假式；若至少存在一個(gè)I(A)為真，稱A為可滿足式。永真式也稱重言式，常用T表示；永假式也稱矛盾式，常用F表示。判定給定公式是否為永真式，永假式或可滿足式的問(wèn)題，稱為給定公式的判定問(wèn)題。判定方法有真值表法和公式推演法。39二、等價(jià)公式定義1.3.2

設(shè)A和B是兩個(gè)命題公式，如果A、B在其任意解釋下，其真值都是相同的，則稱A和B是等價(jià)的，或邏輯相等.

記作AB，讀作A等價(jià)B，稱AB為等價(jià)式。若公式A和B的真值表是相同的，則A和B等價(jià)。因此驗(yàn)證兩公式是否等價(jià)，只需做出它們的真值表即可。40是邏輯雙條件聯(lián)結(jié)詞，屬于對(duì)象語(yǔ)言(命題邏輯)中的符號(hào)，它出現(xiàn)在命題公式中；不是邏輯聯(lián)結(jié)詞，屬于元語(yǔ)言(描述對(duì)象語(yǔ)言的語(yǔ)言)中的符號(hào)，表示兩個(gè)命題公式之間的一種充分必要(記為iff)關(guān)系，它不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)。與iff可通用。自反性：對(duì)任意公式A，有AA。對(duì)稱性：對(duì)任意公式A和B，若AB，則BA。傳遞性：對(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。ABABB

ATTTTTFFFFTFFFFTT42例1：（1）如果A∨CB∨C，是否有AB

？（2）如果A∧CB∧C，是否有AB

？（3）如果┐A┐B，是否有AB?解：（1）若有真值指派使得S(A)=T,S(B)=F,S(C)=T

則A∨CB∨C成立，但AB

不成立（2）若有真值指派使得S(A)=T,S(B)=F,S(C)=F

則A∧CB∧C成立，但AB不成立（3）┐A┐B，則┐A

┐

B是永真式，即

A

B是永真式，所以

AB成立43三、基本等價(jià)式—命題定律(1)雙否律：┐┐AA。(2)交換律：A∧BB∧A，A∨BB∨A，A

BB

A

。(3)結(jié)合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，

(A

B)

CA(B

C)。(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

。判斷公式間是否等價(jià)，有一些簡(jiǎn)單而又經(jīng)常使用的等價(jià)式，稱為基本等價(jià)式或命題定律，牢記并熟練運(yùn)用它們是學(xué)好數(shù)理邏輯的關(guān)鍵。44三、基本等價(jià)式—命題定律（二）(8)零律：A∧FF，A∨TT

。(9)吸收律：A∧(A∨B)

A，A∨(A∧B)A

。(10)互補(bǔ)律：A∧┐AF

，(矛盾律)A∨┐AT

。(排中律)(11)條件式轉(zhuǎn)化律：A→B┐A∨B

，A→B┐B→┐A。(12)雙條件式轉(zhuǎn)化律：

A

B(A→B)∧(B→A)(A∧B)∨(┐A∧┐B)，┐A

B┐(A

B)。(13)輸出律：(A∧B)→CA→(B→C)。(14)歸謬律：(A→B)∧(A→┐B)┐A

。由已知的等價(jià)式可以推演出更多的等價(jià)式，稱這一過(guò)程為等價(jià)演算。等價(jià)演算是邏輯代數(shù)或布爾代數(shù)的重要組成部分。

45例1：證明P→(Q→R)Q→(P→R)┐R→(Q→┐P)證明：P→(Q→R)┐P∨(┐Q∨R)┐Q∨(┐P∨R)Q→(P→R)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：求證：

(P→Q)

∨┐(P→Q)

是永真式。定理1.3.2

在一個(gè)永真式A中，任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處，用另一個(gè)公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。

邏輯聯(lián)結(jié)詞能夠從已知公式合并形成新公式，可把邏輯聯(lián)結(jié)詞看成運(yùn)算?！按搿焙汀疤鎿Q”也有從已知公式得到新公式的作用，因此也可以看成運(yùn)算。證明：由排中律知，A∨┐AT，即A∨┐A為永真式。用公式P→Q代入A中，則得(P→Q)

∨┐(P→Q)

根據(jù)代入規(guī)則可知，給定公式是永真式。47（2）替換規(guī)則定理1.3.3

設(shè)A1是合式公式A的子公式，若A1B1，并且將

A中的A1用B1

替換，得到公式B，則AB。本定理稱為替換規(guī)則。這種替換稱為等價(jià)替換。證明：因?yàn)镼→P

Q→P又由吸收律可知，

P∨(P∧Q)P

根據(jù)替換規(guī)則可得，

Q→(P∨(P∧Q))

Q→P例2:

證明：Q→(P∨(P∧Q))

Q→P48代入規(guī)則和替換規(guī)則的區(qū)別:代入是對(duì)原子命題變?cè)缘模欢鎿Q通常是可對(duì)命題公式實(shí)行之；代入規(guī)則必須用于永真式；而替換則不必；代入必須是處處代入；替換則可部分替換，亦可全部替換。491.4對(duì)偶式與蘊(yùn)涵式定義1.4.1

在給定的僅使用聯(lián)結(jié)詞┐、∧和∨的命題公式

A中，若把∧和∨互換，F(xiàn)和T互換而得到一個(gè)命題公式A*，則稱A*為A的對(duì)偶式，同時(shí)A也是A*的對(duì)偶式。

A與A*互為對(duì)偶式。一、對(duì)偶式50例：寫出下列公式的對(duì)偶式（1）(P∧

Q)∨┐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=P1∧P2或A=P1∨P2或A=┐P1，即:┐A=┐P1∨┐P2，或┐A=┐P1∧┐P2，或┐A=┐┐P1

=P1,結(jié)論成立。假設(shè)當(dāng)L<=k-1時(shí)結(jié)論成立，可以證明當(dāng)L=k時(shí)結(jié)論也成立。（略）①表明，公式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)锳(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，P2，…，Pn)53例試證明：（1）┐(P∧

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

（2）(P∨Q)∧(┐P∧

Q)┐P

∧

Q證明：（1）┐(P∧Q)→(┐P∨Q)

(P∧Q)

∨(┐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è)命題公式，若A→B是永真式，則稱A蘊(yùn)涵B，記作AB，稱AB為蘊(yùn)涵式或永真條件式。

符號(hào)→和的區(qū)別與聯(lián)系類似于和的關(guān)系。區(qū)別：→是邏輯聯(lián)結(jié)詞，屬于對(duì)象語(yǔ)言(命題邏輯)中的符號(hào)，是公式中的符號(hào)；不是聯(lián)結(jié)詞，屬于元語(yǔ)言(描述對(duì)象語(yǔ)言的語(yǔ)言)中的符號(hào)，表示兩個(gè)公式間的關(guān)系，不是兩公式中符號(hào)。聯(lián)系：AB成立，其充要條件A→B是永真式。55蘊(yùn)涵式性質(zhì)①自反性，即對(duì)任意公式A，有AA。②傳遞性，即對(duì)任意公式A、B和C，若AB，BC，則AC。③對(duì)任意公式A、B和C，若AB，AC，則AB∧C。④對(duì)任意公式A、B和C，若AC，BC，則A∨BC。56蘊(yùn)涵式性質(zhì)定理1.4.3

設(shè)A和B是兩命題公式，AB的充要條件是：

AB

且BA。證明：（1）必要性：若AB成立，則AB是永真式，即A→B且B→A均是永真式，所以AB且BA成立。（2）充分性：若AB且BA成立，則A→B且B→A均是永真式，即AB是永真式，故AB成立。57三、蘊(yùn)涵式證明方法證明AB是蘊(yùn)涵式即證A→B是永真式。（1）當(dāng)A為T，B為T時(shí)，則A→B為T；（2）A→B┐B→┐A，即B為F，A為F時(shí)，則A→B為T。蘊(yùn)涵式證明方法：真值表法前件真推導(dǎo)后件真方法設(shè)公式的前件A為真，若能推導(dǎo)出后件B也為真，則條件式A→B是永真式，故蘊(yùn)涵式AB成立。后件假推導(dǎo)前件假方法設(shè)公式的后件B為假，若能推導(dǎo)出前件A也為假，則條件式A→B是永真式，故蘊(yùn)涵式AB成立。58例子：┐Q∧(P→Q)┐P

證明：（1）前件真推導(dǎo)后件真方法：

前件為真：┐Q∧(P→Q)為真，則┐Q和(P→Q)都為真，即┐Q和(┐P∨Q)都為真.于是Q

為F，P為F，得┐P

為真，即后件為真；（2）后件假推導(dǎo)前件假方法：

后件為假：┐P

為假，則P

為真，

(a)若Q

為F，則(P→Q)為F，前件為假；

(b)若Q

為T，則┐Q為F，前件為假。59四、基本蘊(yùn)涵式(1)A∧BA化簡(jiǎn)式(2)A∧BB化簡(jiǎn)式(3)AA∨B附加式(4)┐AA→B附加式變形(5)BA→B附加式變形(6)┐(A→B)A化簡(jiǎn)式變形(7)┐(A→B)┐B化簡(jiǎn)式變形(8)A∧(A→B)B假言推論(9)┐B∧(A→B)┐A拒取式下面給出常用的蘊(yùn)涵式，稱為基本蘊(yùn)涵式，它們的正確性可用上述方法或歸納法證明之。60四、基本蘊(yùn)涵式（續(xù)）(10)┐A∧(A∨B)B析取三段論(11)(A→B)∧(B→C)A→C

條件三段論(12)(AB)∧(BC)AC

雙條件三段論(13)(A→B)∧(C→D)∧(A∧C)B∧D合取構(gòu)造二難(14)(A→B)∧(C→D)∧(A∨C)B∨D析取構(gòu)造二難特別當(dāng)B=D時(shí)，有

(A→B)∧(C→B)∧(A∧C)B二難推論

(A→B)∧(C→B)∧(A∨C)B二難推論(15)A→B(A∨C)→(B∨C)前后件附加

A→B

(A∧C)→(B∧C)(16)A∧

BA∧B合取引入611.5聯(lián)結(jié)詞的擴(kuò)充與功能完全組一、聯(lián)結(jié)詞的擴(kuò)充

為了簡(jiǎn)潔而直接地表達(dá)命題間的聯(lián)系，尚需定義4個(gè)聯(lián)結(jié)詞，它們分別是：合取非聯(lián)結(jié)詞↑析取非聯(lián)結(jié)詞↓條件非聯(lián)結(jié)詞雙條件非聯(lián)結(jié)詞62(一)合取非聯(lián)結(jié)詞定義1.5.1

設(shè)P和Q是任兩個(gè)原子命題，由合取非聯(lián)結(jié)詞↑把P，Q連接成P↑Q，讀作“P合取非Q”，稱它為P和Q的合取非式復(fù)合命題。

P↑Q的真值由命題P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為T時(shí)，P↑Q為F，否則P↑Q為T。

“合取非”又常稱為“與非”。P↑Q

┐(P∧Q)63（二）析取非聯(lián)結(jié)詞定義1.5.1

設(shè)P和Q是任意兩個(gè)原子命題，由析取非聯(lián)結(jié)詞↓把P，Q連接成P↓Q，讀作“P析取非Q“，稱它為P和Q的析取非式復(fù)合命題。

P↓Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q均為F時(shí)，P↓Q為T，否則P↓Q為F?！拔鋈》恰庇殖７Q為“或非”。P↓Q┐(P∨Q)64（三）條件非聯(lián)結(jié)詞定義1.5.1

設(shè)P和Q是任意兩個(gè)原子命題，由條件非聯(lián)結(jié)詞把P，Q連接成P

Q，讀作“P條件非Q“，稱它為P和Q的條件非式復(fù)合命題。

P

Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P為T而Q為F時(shí)，P

Q為T；否則P

Q為F。有時(shí)也把條件非聯(lián)結(jié)詞記為“→′“

P

Q

┐(P→Q)65（四）雙條件非聯(lián)結(jié)詞定義1.5.1

設(shè)P和Q是任兩個(gè)原子命題，由雙條件非聯(lián)結(jié)詞把P，Q連接成P

Q，讀作“P雙條件非Q“

，稱它為P和Q的雙條件非式復(fù)合命題。

P

Q的真值由P和Q的真值確定：當(dāng)且僅當(dāng)P和Q的真值不同時(shí)，P

Q為T，否則P

Q為F?！半p條件非”又常稱為“異或”，常用符號(hào)“”或“

′”表示之。P

Q

┐(PQ)P

QP↑Q

P↓Q

P

Q

P

Q

00011011110010011011000066P↑Q

┐(P∧Q)P↓Q┐(P∨Q)P

Q

┐(P→Q)P

Q

┐(PQ)上述4個(gè)聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值表如下：由真值表可知：67二、與非、或非和異或的性質(zhì)(a)P↑QQ↑P(b)P↑P┐P(c)(P↑Q)↑(P↑Q)P∧Q(d)(P↑P)↑(Q↑Q)P∨Q（一）與非的性質(zhì)

與非、或非以及異或在計(jì)算機(jī)科學(xué)中是經(jīng)常使用的三個(gè)聯(lián)結(jié)詞。因此掌握它們的性質(zhì)是十分必要的。

令P,Q,R是原子命題變?cè)?a)P↓QQ↓P(b)P↓P┐P(c)(P↓Q)↓(P↓Q)P∨Q(d)(P↓P)↓(Q↓Q)P∧Q（二）或非的性質(zhì)68（三）異或的性質(zhì)(a)P

Q

Q

P交換律(b)P(Q

R)(P

Q)R結(jié)合律(c)P∧(Q

R)(P∧Q)(P∧R)分配律(d)P

PF，F(xiàn)

PP，T

P┐P(e)若P

QR，則Q

RP，R

PQ，且P

Q

RF。69例2.把P↑Q表示為只含有↓的等價(jià)公式，

把P↓Q表示為只含有↑的等價(jià)公式。解：

P↑Q

┐(P

∧Q)

┐P∨┐Q

(P↓P)∨(Q↓Q)

((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q))

P↓Q

┐(P∨Q)

┐P∧

┐Q

(P↑P)∧

(Q↑Q)

((P↑P)↑(Q↑Q))↑((P↑P)↑(Q↑Q))

70例3.聯(lián)接詞

↑

和↓

服從結(jié)合律嗎？解：聯(lián)接詞↑和

↓

不滿足結(jié)合律。舉例如下：

(a)

給出一組指派：P為F,Q為T,R為T，則

(P↑Q)↑R為F，但P↑(Q↑R)為T

故

(P↑Q)↑RP↑(Q↑R)

不成立(b)給出一組指派：P為T,Q為F,R為F，則

(P↓Q)↓R為T

，但P↓(Q↓R)為F

故

(P↓Q)↓R

P↓(Q↓R)

不成立71例4.如果A(P,Q,R)由R↑(Q∧┐(R↓P))給出，求它的對(duì)偶式A*(P,Q,R),并求出與A及A*等價(jià)且僅包含聯(lián)結(jié)詞“∧”“∨”

和“┐”的公式。解：AR↑(Q∧┐(R↓P))，則A*R↓(Q∨┐(R↑P))A

R↑(Q∧┐(R↓P))R↑(Q∧

(R∨

P))

┐(R∧(Q∧

(R∨

P)))

┐(R∧Q)∨┐(R∨

P)A*R↓(Q∨┐(R↑P))R↓(Q∨(R∧P))┐(

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

R∨Q)∧┐(R∧P)72三、聯(lián)結(jié)詞功能完全組P↑Q┐(P∧Q)P↓Q┐(P∨Q)P

Q┐(PQ)P

Q

┐(P

Q)P

Q(┐P∨Q)∧(┐Q∨P)P→Q┐P∨QP∧Q┐(┐P∨┐Q)P∨Q┐(┐P∧┐Q)

即擴(kuò)充的4個(gè)聯(lián)結(jié)詞↑↓能由原有5個(gè)聯(lián)結(jié)詞分別替代之，而原有5個(gè)聯(lián)結(jié)詞┐∧∨→又能由聯(lián)結(jié)詞組{┐，∧

}或{┐，∨

}取代。73定義1.5.2

稱G為聯(lián)結(jié)詞功能完全組(最小聯(lián)結(jié)詞組)，如果G滿足下列兩個(gè)條件：①由G中聯(lián)結(jié)詞構(gòu)成的公式能等價(jià)表示任意命題公式；②G

中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價(jià)表示?？梢宰C明以下都是聯(lián)結(jié)詞功能完全組：{┐，∨}，{┐，∧}，{┐，→}，{↑}，{↓}可以證明以下不是聯(lián)結(jié)詞功能完全組：{┐，

},{∧}，{∨}，{∧，∨}74例1.證明任意命題公式都可由僅包含{┐，∨}，{┐，∧}的命題公式代換，且它們是最小聯(lián)結(jié)詞組。證明：因?yàn)椋?）P

Q(┐P∨Q)∧(┐Q∨P)，故可把包含“”的公式等價(jià)變換為包含“∧”和“→”的公式。（2）P→Q┐P∨Q

說(shuō)明包含“→”的公式可變換為包含“┐”和“∨”的公式。（3）P∧Q┐(┐P∨┐Q)

和P∨Q┐(┐P∧┐Q)說(shuō)明“∧”和“∨”可以互換。故由┐∧∨→這五個(gè)聯(lián)結(jié)詞組成的命題公式，必可由{┐，∨}，{┐，∧}組成的命題公式所替代。（4）P↑Q┐(P∧Q)

（5）P↓Q┐(P∨Q)（6）P

Q┐(PQ)

（7）P

Q

┐(P

Q)因此，任意命題公式都可由僅包含{┐，∨}，{┐，∧}的命題公式代換，且它們是最小聯(lián)結(jié)詞組。75例5.證明{∨}，{∧}，{→}不是最小聯(lián)結(jié)詞組。證明：若{∨}或{∧}是最小聯(lián)結(jié)詞組，則

┐P(P∨……)┐P(P∧……)

對(duì)所有命題變?cè)概蒚，則等價(jià)式左邊為F,右邊為T,

與等價(jià)表達(dá)式矛盾!。若{→}是最小聯(lián)結(jié)詞組，則┐PP→(P→(P→…)…)

對(duì)所有命題變?cè)概蒚，則等價(jià)式左邊為F，右邊為T，與等價(jià)表達(dá)式矛盾！761.7公式標(biāo)準(zhǔn)型——范式一、簡(jiǎn)單合取式與簡(jiǎn)單析取式定義1.7.1命題變?cè)兔}變?cè)姆穸?，稱為文字。如果一個(gè)文字恰為另一個(gè)文字的否定，則稱它們?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)題。77定義1.7.2

設(shè)L1，L2，······，

Lk都是文字，其中1≤i≤k，稱L1∨L2∨······∨Lk為簡(jiǎn)單析取式，并稱Li為析取項(xiàng)；稱L1∧L2∧······∧Lk為簡(jiǎn)單合取式，并稱Li為合取項(xiàng)。公式P，┐Q，P∧Q和┐P∧Q∧P等都是簡(jiǎn)單合取式，其中P，Q和┐P為相應(yīng)的簡(jiǎn)單合取式的合取項(xiàng)；公式P，┐Q，P∨Q，┐P∨Q∨P等都是簡(jiǎn)單析取式，其中P，Q和┐P為相應(yīng)簡(jiǎn)單析取式的析取項(xiàng)。一個(gè)命題變?cè)蚱浞穸瓤梢允呛?jiǎn)單合取式也可以是簡(jiǎn)單析取式，如P,┐Q等。78定理1.7.1

簡(jiǎn)單合取式為永假式的充要條件是：它至少含有相反文字出現(xià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è)概烧嬷礣，而各帶否定的命題變?cè)概烧嬷礔，則使簡(jiǎn)單合取式取真值T，這與原假設(shè)矛盾！79二、析取范式與合取范式定義1.7.3

設(shè)A1，A2，·····Am為簡(jiǎn)單合取式，稱A1∨A2∨······∨Am為析取范式，其中1≤m。定義1.7.4

設(shè)B1，B2，·····Bn為簡(jiǎn)單析取式，稱B1∧B2∧······∧Bn為合取范式，其中1≤n。(P∧Q)∨

(┐P∧Q)∨

(P∧Q∧┐Q)是析取范式P∧

(┐P∨┐Q)是合取范式P∧Q既是析取范式又是合取范式

例子：80定理1.7.3

對(duì)于任何一個(gè)命題公式，都存在與其等價(jià)的析取范式和合取范式。求范式算法：①使用命題定律，消去公式中除∧、∨和┐以外的公式中出現(xiàn)的所有聯(lián)結(jié)詞；②使用┐(┐P)P

和德?摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞┐都移到命題變?cè)埃虎劾媒Y(jié)合律、分配律等將公式化成析取范式或合取范式。81例子：求(P∧(QR))S

的析取范式和合取范式。

解：(P∧(QR))S┐(P∧(┐Q∨R))∨S(┐P∨(Q∧

┐R))

∨S┐P∨(Q∧┐R)∨S析取范式(┐P∨Q∨S)∧(┐P∨┐R∨S)合取范式82三、范式的應(yīng)用利用析取范式和合取范式可對(duì)公式進(jìn)行判定。定理1.7.4公式A為永假式的充要條件是A

的析取范式中每個(gè)簡(jiǎn)單合取式至少包含一對(duì)相反文字。定理1.7.5公式A為永真式的充要條件是A

的合取范式中每個(gè)簡(jiǎn)單析取式至少包含一對(duì)相反文字。83例：判定下面公式為何種公式：(1)P∨(QR)∨┐(P∨R)(2)(PQ)P解:(1)

P∨(QR)∨┐(P∨R)

P∨(┐Q∨

R)∨