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

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

東北大學(xué)離散數(shù)學(xué)課程組2023最新整理收集do

something什么是離散數(shù)學(xué)？數(shù)學(xué)的研究對象根據(jù)其數(shù)據(jù)類型可以分為兩種：

連續(xù)對象，如長度、溫度、面積等。

離散對象，如商店商品，學(xué)生所學(xué)課程等。離散數(shù)學(xué)是研究離散對象的結(jié)構(gòu)以及它們之間相互關(guān)系的科學(xué)。為什么學(xué)習(xí)離散數(shù)學(xué)？離散數(shù)學(xué)是計算機科學(xué)與技術(shù)的理論基礎(chǔ)。計算機正是在離散數(shù)學(xué)中的圖靈機的理論指導(dǎo)下誕生的(1936提出圖靈機---1946誕生計算機)?，F(xiàn)代計算機理論與技術(shù)的許多分支，比如：數(shù)據(jù)結(jié)構(gòu)、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程、網(wǎng)絡(luò)等都用到離散數(shù)學(xué)中的基本概念、基本思想、基本方法。培養(yǎng)學(xué)生的數(shù)學(xué)修養(yǎng)和邏輯思維能力。正如著名的物理學(xué)家勞厄所說：“重要的不是獲得知識，而是發(fā)展思維能力?！钡谝黄獢?shù)理邏輯

邏輯學(xué)起源于2000多年前的古希臘，按其發(fā)展過程可分為傳統(tǒng)邏輯與現(xiàn)代邏輯。許多著名人物都對邏輯學(xué)的發(fā)展做出過杰出貢獻。亞里士多德和弗朗西斯·培根是傳統(tǒng)邏輯的代表，分別創(chuàng)立了演繹推理和歸納推理。

什么是邏輯？“邏輯”是英語Logic的譯音，源于古希臘文，原意主要指言語、思想、理性、規(guī)律性等。邏輯學(xué)起源于2000多年前的古希臘。邏輯學(xué)也稱為形式邏輯，是關(guān)于思維形態(tài)的結(jié)構(gòu)及其規(guī)律的科學(xué)。也就是說，邏輯學(xué)研究人思維的形態(tài)結(jié)構(gòu)和一般規(guī)律。什么是思維的形態(tài)結(jié)構(gòu)？思維形態(tài)是人們在思維過程中用以反映客觀現(xiàn)實的具體形式，即概念、判斷、推理。人們思維的形態(tài)結(jié)構(gòu)：概念

判斷

推理

人的思維形態(tài)主要表現(xiàn)為推理推理：

由若干個已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。如何能正確的思維？

概念清楚，判斷正確，推理合乎邏輯。比如：王剛問李明：“學(xué)離散數(shù)學(xué)有用嗎？”李明說：“當(dāng)然有用了，離散數(shù)學(xué)是計算機學(xué)科的理論基礎(chǔ)嘛。”李明的回答實際上包含了三句話的推理：計算機學(xué)科的理論基礎(chǔ)是有用的，離散數(shù)學(xué)是計算機學(xué)科的理論基礎(chǔ)，所以，離散數(shù)學(xué)是有用的?！坝嬎銠C學(xué)科的理論基礎(chǔ)是有用的”這句話對交際雙方來說是不言而喻的，所以在表達中被省略。

邏輯學(xué)可分為傳統(tǒng)邏輯與現(xiàn)代邏輯。

亞里士多德和弗朗西斯·培根是傳統(tǒng)邏輯的代表，分別創(chuàng)立了演繹推理和歸納推理。歸納推理：由若干個別事實推出一般結(jié)論。如：銅能導(dǎo)電，鐵能導(dǎo)電，錫能導(dǎo)電，鉛能導(dǎo)

電，……

一切金屬都導(dǎo)電。演繹推理：由一般規(guī)律推出個別事實。如：所有的金屬都導(dǎo)電。(一般規(guī)律，大前提)銅是金屬。(個別事實，小前提)銅能導(dǎo)電。(個別結(jié)論，結(jié)論)我們主要研究演繹推理?，F(xiàn)代邏輯的開創(chuàng)者是德國的萊布尼茲，在十八世紀(jì)初，他提出要把邏輯處理成演算，即數(shù)理邏輯。又過了二百多年，羅素與懷特?？偨Y(jié)了現(xiàn)代邏輯的發(fā)展，建立了命題演算與謂詞演算兩個完整的體系。

什么是數(shù)理邏輯？數(shù)理邏輯是用數(shù)學(xué)的方法研究邏輯。

“數(shù)學(xué)方法”：建立一套有嚴格定義的符號體系，即建立一套形式語言，來研究邏輯。所以數(shù)理邏輯也稱為“符號邏輯”。

數(shù)理邏輯分為命題邏輯和謂詞邏輯兩部分。第一章命題邏輯

第一節(jié)命題與命題真值什么是命題？

命題是表達判斷的陳述句。一個判斷只有兩種可能：正確的判斷或者錯誤的判斷。把這種“正確”或者“錯誤”賦予命題，就得到命題的真值。命題的真值：命題的真值只有兩個：“真”或“假”。命題的真值為真：一個命題所表達的判斷與客觀情況一致，記作T(True)。命題的真值為假：一個命所題表達的判斷與客觀情況不一致，記作F

(False)。例如：“這面旗幟是紅色的。”是命題，并且與客觀事實相符，所以該命題真值為T。判斷一句話是否是命題有兩個關(guān)鍵：（1）是陳述句；（2）有且只有一個真值。例:判定下面這些句子哪些是命題?⑴2是個素數(shù)。⑵雪是黑色的。⑶2020年人類將到達火星。⑷如果天不下雨并且我有時間，我就去看電影。⑸x+y<5⑹請打開書?、四?？⑻我正在說謊。

從這句話引出一個問題：說自己正在說謊這句話本身是不是謊話？若真值為T，那么他就正在說謊話，“我正在說謊”這話就是假的；若真值為F，那么他就沒有說謊，“我正在說謊”這句話就是真的。所以這句話沒有真值，不是命題。

“我正在說謊”這句話是在邏輯學(xué)上稱為“悖論”，從它的真可以推斷它的假，從它的假又可以推斷它的真。命題的種類：原子命題(簡單命題)：不能再分解成更簡單陳述句的命題。復(fù)合命題(分子命題)：由若干個連結(jié)詞、標(biāo)點符號及原子命題復(fù)合構(gòu)成的命題。命題的表示：在本課程的系統(tǒng)里，用大寫字母表示。例：

P：今天下雨。

Q1：小王是大學(xué)生。作業(yè)第8頁:(1)(3)(5)(6)

第二節(jié)邏輯聯(lián)結(jié)詞簡單命題可以用大寫字母表示，復(fù)合命題如何表示？復(fù)合命題由若干個連結(jié)詞、標(biāo)點符號及原子命題復(fù)合構(gòu)成的命題復(fù)合命題用“邏輯聯(lián)結(jié)詞”將原子命題聯(lián)結(jié)起來表達。歸納自然語言中的聯(lián)結(jié)詞，定義了六個邏輯聯(lián)結(jié)詞，分別是：

(1)否定“”(2)合取“∧”

(3)析取“∨”(4)異或“”

(5)蘊涵“”(6)等價“”（1）否定“”表示：“并非…”，“不…”等。用于對一個命題P的否定，寫成

P，并讀成“非P”。例：P：2是素數(shù)。

P：2不是素數(shù)。定義：設(shè)P為一命題，P

的否定是一個新命題，記作

P。

P的真值與P的真值相反。

真值表：

PPTFFT因為數(shù)理邏輯研究的是人的思維規(guī)律，所以在規(guī)定邏輯連結(jié)詞的真值表的時候，一定要符合人的語言與思維的習(xí)慣。（2）合取“∧”表示：“并且”、“不但…而且...”、“既…又...”、“盡管…還…”等。例：P：小王能唱歌。Q：小王能跳舞。P∧Q：小王能歌善舞。

真值表應(yīng)該如何規(guī)定？PQP∧QTTTTFFFTFFFF定義：兩個命題P和Q的合取是一個復(fù)合命題，記作P∧Q。當(dāng)且僅當(dāng)P和Q的真值均為T時，P∧Q的真值為T，其它情況下，P∧Q的真值均為F。

連接詞“或者”的表達分為兩種情況：可兼取的或，即兩件事情可以同時發(fā)生。用析取“∨”表達。不可兼取的或，即兩件事情不能同時發(fā)生。用異或（也稱排斥或）“

”表達。（3）

析取“∨”例：P：小王能唱歌。Q：小王能跳舞。

P∨Q：小王能唱歌或者能跳舞。小王能唱歌與小王能跳舞可以同時發(fā)生，我們用析取“∨”表達?！啊拧钡恼嬷等绾我?guī)定？真值表：PQP∨QTTTTFTFTT

FFF定義：兩個命題P和Q的析取是一個復(fù)合命題，記作P∨Q。當(dāng)且僅當(dāng)P和Q的真值均為F

時，P∨Q的真值為F

，其它情況下，P∨Q的真值均為T。

（4）異或“”例：P：十二次列車早晨8:30開。

Q：十二次列車早晨9:00開。

PQ：十二次列車早晨8:30或者9:00開。兩件事不能同時發(fā)生，用“異或”。P∨Q與PQ的真值表應(yīng)該有什么不同？

PQPQFFFFTTTFT

TTF當(dāng)且僅當(dāng)P與Q的真值相同時，PQ的真值為F

，真值不同時為T。

（5）條件“”表示“如果…那么…”，“若…則…”等。例：P：土壤缺少水分。Q：這顆植物會死亡。

P

Q：

如果土壤缺少水分，這顆植物就會死亡。稱P是P

Q的前件，Q是P

Q的后件。也可以說P是Q的充分條件，Q是P的必要條件。P

Q的真值應(yīng)該如何定義？P：土壤缺少水分。Q：這顆植物會死亡。

PQP

Q

TTT

TFF

FTTFFT善意規(guī)定當(dāng)且僅當(dāng)

P為T，Q為F時，P

Q的真值為F；而在其它情況下，P

Q的真值均為T。注意“善意規(guī)定”。

例：P：天氣好。Q：我去公園。1.如果天氣好,我就去公園。P

Q2.只要天氣好,我就去公園。P

Q3.天氣好,我就去公園。P

Q4.僅當(dāng)天氣好,我才去公園。Q

P5.只有天氣好,我才去公園。Q

P6.我去公園,僅當(dāng)天氣好。Q

P

用“”表達必須前件是后件的充分條件，即若前件成立，后件一定成立。這一點要特別注意!!!它決定了哪個作為前件，哪

個作為后件。（6）等價(雙條件）“

”

表示“當(dāng)且僅當(dāng)”、“充分必要”等。例：P：⊿ABC是等邊三角形。

Q：⊿ABC是等角三角形。

PQ

：⊿ABC是等邊三角形當(dāng)且僅當(dāng)它是等角三角形。PQ的真值表：按思維習(xí)慣，PQ，QP應(yīng)同時成立。

PQP

Q

TTT

FFTTFFFTF

當(dāng)且僅當(dāng)P與Q的真值相同時，PQ的真值為T，否則為F。PQPQFFFFTTTFTTTFPQP

QFFTFTFTFFTTTPQ?

(P

Q)比較下面二表：可以把這6種邏輯聯(lián)結(jié)詞看成是6種運算，因為有運算結(jié)果；其運算的對象是命題；運算規(guī)則是每個連結(jié)詞的真值表。在后面的代數(shù)系統(tǒng)部分大家可以看到，運算的概念是很廣的，運算實際上是一種映射。邏輯聯(lián)結(jié)詞看成是6種運算，其運算的對象是命題；運算規(guī)則是每個連結(jié)詞的真值表。PQ

PP∧QP∨QPQP

QP

QFFTFFFTTFTTFTTTFTFFFTTFFTTFTTFTT“”為一元運算；

因為一個命題P可以確定P的真值。

“∧，∨，，

，

”

均為二元運算。

因為它們的真值必須由兩個運算對象確定。練習(xí)：填空已知P∧Q為T，則P為()，Q為()。已知P∨Q為F，則P為()，Q為()。已知P為F，則P∧Q為()。已知P為T，則P∨Q為()。已知P∨Q為T，且P為F，則Q為()。已知P

Q為F，則P為()，Q為()。已知P為F，則P

Q為()。已知Q為T，則P

Q為()。已知

P

Q為F，則P為()，Q為()。已知P為T，P

Q為T，則Q為()。已知

Q為T,P

Q為T，則P為()。已知PQ為T，P為T,則Q為().已知PQ為F，P為T,則Q為().PP的真值為().P

P的真值為()。第三節(jié)命題符號化

命題符號化，就是將自然語言表達的句子用符號化的命題公式來表達。命題符號化的步驟：

(1)先將語句分解成原子命題。(2)將每個原子命題用大寫字母表示。注意每個原子命題都必須是一個完整的句子。(3)用確切的邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題，構(gòu)成給定命題的符號表達式。例1將下列命題符號化，并討論它們的真值：⑴是無理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。

解：令P：是無理數(shù)，真值為T；Q：加拿大位于亞洲，真值為F；符號化為：P

Q，真值為F。⑵除非a能被2整除，否則a不能被4整除。

其中a是一給定正整數(shù)。解：令P：a能被2整除；Q：a能被4整除；

“除非a能被2整除，否則a不能被4整除”的含義與“如果a不能被2整除，則a不能被4整除”一樣，也等價于說“如果a能被4整除，則a一定能被2整除”。

所以⑵表達為：

P

Q，也即QP。

當(dāng)Q為T，P一定為T。也即沒有Q為T，P為F的情況發(fā)生，所以其真值為T。例2符號化下列命題

⑴如果小張與小王都不去，則小李去。

⑵如果小張與小王不都去，則小李去。解：令P：小張去。Q：小王去。R：小李去。

⑴命題符號化為：(P∧

Q)

R⑵命題符號化為：

(P∧Q)

R

或(P∨

Q)

R例3符號化下面命題：僅當(dāng)天不下雨且我有時間，才上街。

解：令

P：天下雨。Q：我有時間。R：我上街。

分析：由于“僅當(dāng)”是表示的是“必要條件”。即我上街，一定是天不下雨且我有時間時；而天不下雨且我有時間時我不一定上街。

所以該命題表達為：R(P∧Q)例4

符號化下面命題：

若天不下雨，我就上街；否則在家。解：令P：天下雨。Q：我上街。R：我在家。該命題可符號化為：(PQ)(PR)∧

注意：中間的聯(lián)結(jié)詞一定是“∧”，不能是“∨”，也不是“”。

在考慮用什么聯(lián)結(jié)詞時，一定要考慮哪種邏輯聯(lián)結(jié)詞的真值表最符合命題描述的情況。因為原命題表示：“天不下雨時我做什么，天下雨時我又做什么”這兩種情況，其中有一種情況是假的，則題中的說法就不正確，所以中間的聯(lián)結(jié)詞一定是“∧”。例5

一個人起初說，“占據(jù)空間的有質(zhì)量的而且不斷變化的叫物質(zhì)”；后來他改說，“占據(jù)空間的有質(zhì)量的叫物質(zhì)，而物質(zhì)是不斷變化的?！眴査昂笾鲝埖牟町愒谑裁吹胤剑囈悦}形式進行分析。解：令P：某物占據(jù)空間；Q：某物有質(zhì)量；R：某物不斷變化；S：某物叫物質(zhì)。

起初：(P∧Q∧R)

S

后來：((P∧Q)

S)∧(S→R)

例5令P：北京比天津人口多。Q：2+2=4。R：烏鴉是白色的。求下面復(fù)合命題的真值：(P(Q∨R))∧((Q∨

R)

P)解：P的真值為T，Q的真值為T，R的真值為F。(P(Q∨R))∧((Q∨

R)

P)的真值

為T作業(yè)第11頁：（1）第12頁：（5）（6）（7）第4節(jié)

命題公式及其賦值

一、命題公式

先看一個命題公式：P：3是素數(shù)。(P

F)∨(QR)∧T在命題公式中有三種數(shù)據(jù)類型：命題常項：即命題的真值。常值命題：即具體命題。命題變元：用大寫字母表示的任一命題。命題變元本身不是命題，因為它沒有固定真值，只有給它賦值，才變成命題。將一個命題常項或常值命題賦予命題變元的過程稱為給命題變元賦值，也稱為對命題變元作指派。合式公式（合法的命題公式）定義：⑴單個命題變元、常值命題及命題常項是合式公式。⑵若A是合式公式，則

A是合式公式。⑶若A和B是合式公式，則(A∧B)，(A∨B)，(A

B)

(A

B)都是合式公式。⑷

當(dāng)且僅當(dāng)有限次地應(yīng)用⑴，⑵，⑶所得到的符號串是合式公式。合式公式也稱為命題公式，簡稱為公式。例：下面的式子是合式公式：

(P∧Q)，(PR)，((P∧Q)∨R)下面的式子不是合式公式(P∧Q，PR，P∧Q∨R為了簡化命題公式，約定：

(1)最外層括號可??；

(2)不影響運算次序的括號可省。運算次序由高到低為:,∧,∨,,

合式公式：

(P∧Q)，(PR)，((P∧Q)∨R)可以簡化成：

P∧Q，

PR，

(P∧Q)∨R，

P∧Q∨R二、命題公式的真值表一個含有命題變元的命題公式不是命題，因為它沒有固定真值，但是給其中的所有命題變元賦值以后它就有了唯一的真值。

將所有各種賦值情況匯列成表，即為該命題公式的真值表。例：命題公式(PQ)∨Q的真值表如下所示：PQP

P

Q(PQ)∨QFFTTFTFTTTFFFTTTFTTT構(gòu)造真值表的步驟：由于每個命題變元都有兩種賦值可能性(T,F)，所以含有n(n≥1)個命題變元的命題公式真值表有2n行。將n個命題變元按字母次序排列。將F記為0，T記為1，按照二進制數(shù)的次序賦值。賦值從00…0開始，然后按二進制加法依次加1，直到11…1為止。對每個賦值，計算命題公式的真值。例：構(gòu)造P(Q

R)的真值表PQRQ

RP(Q

R)000FFFTT001FFTTT010FTFFT011FTTTT100TF

F

T

T101TF

T

T

T110TT

F

F

F111TT

T

T

T第5節(jié)

命題公式的等價

看下面三個公式的真值表：PQP

Q

P∨Q

Q

PFFTTFTFTTTFTTTFTTTFT從真值表可以看出，不論對P、Q作何種賦值，P

Q、

P∨Q和

Q

P的真值都相同。

P

Q

P∨Q

Q

P等價定義：A、B是含有命題變元P1,P2,…,

Pn

的命題公式，如不論給P1,P2,…,

Pn

何種賦值，A和B的真值均相同，則稱命題公式A與B等價，記作A

B。若兩個命題公式的真值表相同，

則它們等價?；A(chǔ)等價公式：

⑴對合律

P

P⑵冪等律P∨P

PP∧P

P⑶交換律P∨Q

Q∨PP∧Q

Q∧P⑷結(jié)合律P∨(Q∨R)(P∨Q)∨RP∧(Q∧R)(P∧Q)∧R⑸分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)

PP∧(P∨Q)

P⑺底·摩根定律

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q⑻同一律P∨F

PP∧T

P⑼零律P∨T

TP∧F

F⑽互補律P∨

PTP∧

P

F⑾P

Q

P∨Q

⑿

P

Q

Q

P⒀

PQ(P

Q)∧(Q

P)⒁PQ(P∨Q)∧(P∨

Q)

⒂

PQ(P∧Q)∨(

P∧

Q)PQP∨Q

(P∨Q)

P

Q

P∧

QFFFTTTTFTTFTFFTFTFFTFTTTFFFF例：證明底·摩根定律

(P∨Q)

P∧

Q證明：構(gòu)造兩個命題公式的真值表：因為(P∨Q)與

P∧

Q的真值表相同，所以等價。等價公式的證明方法：方法1：列真值表。方法2：用等價公式變換。(用置換定律)置換定律：A是一個命題公式，X是A中的一部分且也是合式公式，如果X

Y，用Y代替A中的X得到公式B，則A

B。例1：

求證(

P∨Q)→(P∧Q)

P證明：(

P∨Q)→(P∧Q)

(

P∨Q)∨(P∧Q)(公式E11)

(

P∧

Q)∨(P∧Q)(底·摩根定律)

(P∧

Q)∨(P∧Q)(對合律)

P∧(

Q∨Q)(分配律)

P∧T(互補律)

P(同一律)公式E11

：P

Q

P∨Q例題2.求證吸收律P∧(P∨Q)

P證明P∧(P∨Q)

(P∨F)∧(P∨Q)(同一律)

P∨(F∧Q)(分配律)

P∨F(零律)

P(同一律)例題3.化簡

(P∧Q)→(

P∨(

P∨Q))解:

(P∧Q)→(

P∨(

P∨Q))

(P∧Q)∨((

P∨

P)∨Q)(E16,結(jié)合)

(P∧Q)∨(

P∨Q)(對合律，冪等律)

(P∧Q)∨(Q∨

P)(交換律)

((P∧Q)∨Q)∨

P(結(jié)合律)

Q∨

P(吸收律)公式

：P

Q

P∨Q對偶式：在一個只含有聯(lián)結(jié)詞

、∨、∧的公式A中，將∨換成∧，∧換成∨，T換成F，F(xiàn)換成T，其余部分不變，得到另一個公式A*，稱A與A*互為對偶式。

例如：AA*PPQ∧RQ∨R(P∨T)∧Q(P∧F)∨Q定理

令A(yù)(P1,P2,…,Pn)是一個只含有聯(lián)結(jié)詞

、∨、∧的命題公式，則

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

此定理可以反復(fù)地使用底-摩根定律證明。

推論：A(

P1,

P2,…,

Pn)

A*(P1,

P2,…,

Pn)

應(yīng)用上述定理可以直接將“”放到命題變元的前面。

例如：

(((P∧Q)∨(P∧Q))∨R)((P∨Q)∧(P∨Q))∧R等價“”是關(guān)系符號，不是運算符號，它表明的是兩個命題公式之間的關(guān)系。等價的性質(zhì)：

1)有自反性：對任何命題公式A，均有A

A。

2)有對稱性：若AB，則BA。3)有傳遞性：若AB且BC，則AC。作業(yè)第17頁：（1）b)c)d)

（2）題改為化簡第18頁：（6）第19頁：（7）（8）

畫真值表證明：PQ(P∧Q)∨(

P∧

Q)

第6節(jié)重言式與重言蘊涵式PP∨PP∧PFTFTTF

P∨P為重言式(永真式)；

P∧P為矛盾式(永假式)。重言式(矛盾式)定義：若公式A

T，則A為重言式或永真式。若公式A

F，則A為矛盾式或永假式。例：證明(P∧(PQ))Q

為重言式。方法1：列真值表PQ

PQP∧(PQ)

P∧(PQ))QFFTFTFTTFTTFFFTTTTTT永真公式真值表的最后一列全是“T”。方法2：等價公式變換(P∧(PQ))Q

(P∧(P∨Q))Q

((P∧P)∨(P∧Q))Q

(F∨(P∧Q))Q

(P∧Q)Q

(P∧Q)∨Q

(P∨

Q)∨Q

P∨(

Q∨Q)

P∨T

T定理

設(shè)A,B為兩個命題公式，A?B當(dāng)且僅當(dāng)A?B是一個重言式。證明：若A?B，則不論對A、B做何種賦值，A與B的真值都相同，于是A?B?T，即A?B是一個重言式。若A?B是一個重言式，則A?B?T，于是不論在何種賦值下，A與B的真值均相同，即A?B。重言蘊涵式定義：當(dāng)且僅當(dāng)A

B是重言式，則稱A重言(永真)蘊涵B，記作A

B。

即當(dāng)且僅當(dāng)A

BT，則A

B。

AB可以理解成由A可推出B，即

由A為真，可以推出B也為真。重言蘊涵式的兩種基本證明方法：考察A

B的真值表，如果A

B為永真式，則前件A為真，后件B為假的情況就不會出現(xiàn)。

PQP

Q

TTT

TFF

FTTFFT所以只要證明前件為真，后件為假的情況不發(fā)生，A

B即為永真式。有下面兩種證明方法：例1求證P∧(P→Q)Q證明：

假設(shè)P∧(P→Q)為T，

則P為T并且(P→Q)為T，于是Q為T，

所以P∧(P→Q)Q成立。1.假設(shè)前件A為真，若在此假設(shè)下能推出后件B也為真，則AB成立。例2求證：

((A∧B)

C)∧

D∧(

C∨D)

A∨

B證明：設(shè)前件((A∧B)

C)∧

D∧(

C∨D)為真。則

((A∧B)

C)、

D、(

C∨D)均為真。

D為T，則D為F，由

C∨D為T，于是

C為T，即C為F，再由((A∧B)

C為T，則(A∧B)為F，即

(A∧B)為T，于是

A∨

B為T，因此

((A∧B)

C)∧

D∧(

C∨D)

A∨

B。例：求證PP∨Q，QP∨Q證明：

假設(shè)P∨Q為F，則P為F，Q為F，所以

PP∨Q，QP∨Q成立。2.假設(shè)后件B為假，若在此假設(shè)下能推出前件A也為假，則AB成立。例2求證：((A∧B)

C)∧

D∧(

C∨D)

A∨

B證明：假設(shè)后件A∨

B為F，則A與B均為T。1.如C為F，則(A∧B)

C為F，所以前件((A∧B)

C)∧

D∧(

C∨D)為F2.如C為T，則⑴若D為T，則

D為F，所以前件((A∧B)

C)∧

D∧(

C∨D)為F。

⑵若D為F，則

C∨D為F，

所以前件((A∧B)

C)∧

D∧(

C∨D)為F。綜上((A∧B)

C)∧

D∧(

C∨D)

A∨

B成立。基礎(chǔ)的重言蘊涵公式：I1P∧Q

PI2P∧Q

QI3P

P∨QI4Q

P∨QI5

P

P

QI6Q

P

QI7

(P

Q)

PI8

(P

Q)

QI9P,Q

P∧QI10

P∧(P∨Q)

QI11P∧(P

Q)

QI12

Q∧(P

Q)

PI13(P

Q)∧(Q

R)

P

RI14A

B(A∨C)(B∨C)I15A

B

(A∧C)(B∧C)重言蘊含“

”是關(guān)系符，不是運算符。重言蘊含的性質(zhì)：

1)有自反性：對任何命題公式A，有A

A。

2)有傳遞性：若AB且BC，則AC。

3)有反對稱性：若AB且BA，則

AB。

4)若AB且AC，則AB∧C。

5)若AB且CB，則A∨CB。定理：設(shè)A，B為任意兩個命題公式，A

B的

充要條件是A

B且B

A。證明：若A

B，則ABT，而

AB(A→B)∧(B→A)，于是A→BT且

B→AT，即A

B且B

A成立。

若A

B且B

A，則A→BT且B→AT，

于是(A→B)∧(B→A)T。而

AB(A→B)∧(B→A)，于是ABT，

即知A

B成立。思考：⑴若

AB是否有AB?解：若

AB則A→BT而

A→BB→A，于是B→AT，

即BA而不是AB

⑵若AB是否有AB?

解：若

AB則ABT而

AB(A→B)∧(B→A)(B→A)∧(A→B)AB

于是ABT，

即AB作業(yè)一、用證明永真蘊涵的兩種基本方法證明：I10

P∧(P∨Q)

QI11P∧(P

Q)

QI12

Q∧(P

Q)

PI13(P

Q)∧(Q

R)

P

RI14A

B(A∨C)(B∨C)I15A

B

(A∧C)(B∧C)作業(yè)第19頁（9）第23頁（1）a)b)c)

（6）、（7）證明：

若AB且AC，則AB∧C。

若AB且CB，則A∨CB。作業(yè)思考：永真蘊涵是否有置換定律？即：A是一個命題公式，X是A中的一部分且也是合式公式，如果X

Y，用Y代替A中的X得到公式B，則A

B。是否成立？第7節(jié)范式

范式就是命題公式的規(guī)范形式，分為析取范式與合取范式。1.析取范式定義：

命題公式A如果可等價地寫成如下形式：

A1∨A2∨...∨An(n≥1)，

其中每個項Ai(i=1,2,…,n)是命題變元或其

否定形式的合取式，稱該公式為A的析取

范式。

因PQ(P∧Q)∨(

P∧

Q)

(P∧Q)∨(

P∧

Q)是PQ的析取范式。2.合取范式定義：

命題公式A如果可等價地寫成如下形式：

A1∧A2∧...∧An(n≥1)，

其中每個項Ai(i=1,2,…,n)是命題變元或其否

定形式的析取式，稱該公式為A的合取范式。

因PQ(P∨Q)∧(P∨

Q)

(P∨Q)∧(P∨

Q)是PQ的合取范式。從定義可以看出：在析取范式與合取范式中只含有聯(lián)結(jié)詞“

,∧,∨”。“”在命題變元之前。

求一個公式的析取范式或合取范式的步驟：⑴去掉“”和“”。⑵將“”移到命題變元前。

用公式

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)⑶用分配律、冪等律等公式進行整理，使之

成為所要求的形式。例：求(P

Q)

R的析取范式與合取范式。先求析取范式：

(P

Q)

R

(P

Q)∨R---去掉其它連結(jié)詞((P∨Q)∧(P∨Q))∨R

---去掉其它連結(jié)詞(P∧Q)∨(P∧Q)∨R

---“

”移到命題變元前面例：求(P

Q)

R的析取范式與合取范式。再求合取范式：

(P

Q)

R

(P

Q)∨R

---去掉其它連結(jié)詞((P∧Q)∨(P∧Q))∨R

---去掉其它連結(jié)詞((P∨Q)∧(P∨Q))∨R

---“

”移到命題變元前面(P∨Q∨R)∧(P∨Q∨R)

---整理注：P∧Q既是合取范式，也是析取范式。

主析取范式與主合取范式一、主析取范式

小項：是n個命題變元的合取式，其中每個變元必出現(xiàn)且僅出現(xiàn)一次(以本身或否定形式)，稱這個合取式為小項。例如，含有兩個變元的小項：

P∧Q、P∧Q、P∧Q、P∧Q若有n個變元，則有2n個小項。小項編碼：含有n個變元的小項的角標(biāo)用n位二進制碼表示。變元按字母次序排列。用1表示變元本身，0表示變元的否定形式。例：m00

P∧Q

，m01

P∧Q

，

m10

P∧Q

，

m11

P∧Q

m101

P∧Q

∧R，m100

P∧Q

∧

R考察含有兩個變元的所有小項的真值表：m00m01m10m11PQP∧QP∧QP∧QP∧Q00011011FFFTTFTTTFFFFTFFFFTFFFFT每個小項當(dāng)且僅當(dāng)其賦值與編碼相同時，其真值為T；而其余2n-1組賦值均使該小項的真值為F。全體小項的析取式為永真式，記為：∑mi?m0∨m1∨…∨m2n-1

?T主析取范式定義：若一個命題公式的析取范式為A1∨A2∨...∨An(n≥1)，其中每個Ai(i=1,2,...,n)都是小項，則稱之為該命題公式的主析取范式。主析取范式的求法：⑴先寫出給定公式的析取范式

A1∨A2∨...∨An

。⑵為使每個Ai都變成小項，對缺少變元的項

Ai要補全變元，比如缺變元R，就用

“∧(R∨

R)”的形式補R。⑶用分配律等公式加以整理。例：求PQ的主析取范式。解：PQP∨Q---去掉其它連結(jié)詞(P∧(Q∨

Q))∨((P∨

P)∧Q)---補變元(P∧Q)∨(P∧

Q)∨(P∧Q)∨(

P∧Q)

---用分配律展開

(P∧Q)∨(P∧

Q)∨(P∧Q)求主析取范式的真值表法：⑴列出給定公式的真值表。⑵找出該公式真值表中每個為“T”行的賦值

所對應(yīng)的小項。

⑶用“∨”聯(lián)結(jié)上述小項，即可。例：求PQ和P

Q的主析取范式

PQm00∨m01∨m11

(P∧Q)∨(P∧Q)∨(P∧Q)

P

Q

m00∨m11

(P∧Q)∨(P∧Q)PQPQP

Q00TT01TF10FF11TT定理

在真值表中，一個使公式的真值為T的賦值所對應(yīng)的小項的析取，即為此公式的主析取范式。思考：永真公式的主析取范式是什么樣的？二、主合取范式大項定義：是n個命題變元的析取式，其中每個變元必出現(xiàn)且僅出現(xiàn)一次(以本身或否定形式)，稱該析取式為大項。有n個變元，則有2n個大項。大項的編碼：

大項的編碼正好與小項相反。0表示變元本身，1表示變元的否定形式。如：M00P∨QM01P∨Q

M10P∨QM11P∨Q顯然，Mi

mi例：

M011P∨Q∨R(P∧Q∧R)

m011

考察含有兩個變元的所有大項的真值表：每個大項當(dāng)且僅當(dāng)其賦值與編碼相同時，其真值為

F；其余2n-1組賦值均使該大項的真值為T。2.全體大項的合取式必為永假式。M00M01M10M11PQP∨QP∨QP∨QP∨Q00011011FFFTTFTTFTTTTFTTTTFTTTTF主合取范式定義：若一個命題公式的合取范式為A1∧A2∧...∧An(n≥1)，其中每個Ai(i=1,2,…,n)都是大項，則稱之為該命題公式的主合取范式。求主合取范式的步驟：⑴先寫出給定公式的合取范式A1∧A2∧...∧An。⑵為使每個Ai變成大項，對缺少變元的項Ai補全變元，比如缺變元R，用“∨(R∧

R)”的形式補R。⑶用分配律等公式加以整理。例：求(PQ)R的主合取范式(PQ)R(P∨Q)∨R------去掉其它連結(jié)詞(P∧

Q)∨R------“

”移到命題變元前面(P∨R)∧(

Q∨R)------化成合取范式(P∨(Q∧Q)∨R)∧((P∧P)∨

Q∨R)---補變元(P∨Q∨R)∧(P∨Q∨R)∧

(P∨

Q∨R)∧(P∨

Q∨R)---用分配率整理(P∨Q∨R)∧(P∨Q∨R)∧(P∨

Q∨R)主合取范式的真值表求法：⑴列出給定公式的真值表。⑵找出該公式真值表中的每個為“F”行的賦值所對應(yīng)的大項。⑶用“∧”聯(lián)結(jié)上述大項，即可。定理

在真值表中，一個使公式的真值為F的賦值所對應(yīng)的大項的析取，即為此公式的主合取范式。例：求PQ和P

Q的主合取范式

PQM10P∨QP

Q

M01∧M10

(P∨Q

)∧(P∨Q)PQPQP

Q00TT01TF10FF11TT思考:1.永真公式的主析取范式是什么樣？是否有主合取范式？2.永假公式的主合取范式是什么樣？是否有主

析取范式？3.若已知主合取范式，能否直接寫出主析取范

式？例：已知A(P,Q,R)的主析取范式中含有下面小項m1，m3，m5，m7，求它的和主合取范式。解：

在真值表中，除了使命題公式A為真的賦值，其余的就是使A為假的賦值。而主析取范式中包含的小項的編碼，就是使命題公式A為真的賦值

所以賦值1，3，5，7，即001，011，101，111就是使A為真的賦值。0，2，4，6，即000，010，100，110是使A為假的賦值。A(P,Q,R)

m1∨m3∨m5∨m7

M0∧M2∧M4∧M6

M000∧M010∧M100∧M110(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

∧(P∨Q∨R)例：A，B，C，D四個人中要派兩個人出差，按下述三個條件有幾種派法？

①

若A去則C和D中要去一個人。②B和C不能都去。

③C去則D要留下。解：令A(yù)，B，C，D分別表示A去，B去，C去，D去。①A

(CD)

A

((C∧

D)∨(

C∧D))

A∨(C∧

D)∨(

C∧D)②(B∧C)B∨C③C

DC∨D總的條件為：(A∨(C∧

D)∨(

C∧D))∧(B∨C)∧(C∨D)將幾個條件的合取式化成析取范式：(A∨(C∧

D)∨(

C∧D))∧(B∨C)∧(C∨D)

(

A∨(C∧

D)∨(

C∧D))∧

(C∨(B∧D))(A∧C)∨(C∧

D∧C)∨(

C∧D∧C)

∨

(A∧B∧D)∨(C∧

D∧B∧D)∨(

C∧D∧B∧D)

(A∧C)∨(

C∧D)∨(A∧B∧D)∨(C∧

D∧B)

最后的派法要使得

(A∧C)∨(

C∧D)∨(A∧B∧D)∨(C∧

D∧B)為T。

可以取

A∧C為T，得B和D去?？梢匀∧D為T，得A和D去，或者B和D去?？梢匀∧

D∧B為T，得A和C去。最后得到三種派法：A和C去、A和D去、B和D去。作業(yè)

第39頁：(2)c)、d),(3)b)、d),(4)a)、d)、e),(5)b)、d)(7)作業(yè)

補充題：安排課表，教語言課的教師希望將課程安排在第一或第三節(jié)；教數(shù)學(xué)課的教師希望將課程安排在第二或第三節(jié)；教原理課的教師希望將課程安排在第一或第二節(jié)。如何安排課表，使得三位教師都滿意。第8節(jié)

命題邏輯推理推理就是根據(jù)一個或幾個已知的判斷得出一個新的判斷的思維過程。稱這些已知的判斷為前提。得到的新判斷為前提的有效結(jié)論。推理的過程就是證明永真蘊含式的過程。

令H1,H2,…,Hn是已知的命題公式(前提)，若有H1∧H2∧....∧Hn

C則稱C是H1,H2,…,Hn的有效結(jié)論，簡稱結(jié)論。兩個推理規(guī)則：P規(guī)則(引入前提規(guī)則)：在推理過程中，可以隨時引入前提。T規(guī)則(引入結(jié)論規(guī)則)：在推理過程中，如果前面有一個或幾個公式重言蘊涵公式S，則可將S納入推理過程中?；A(chǔ)重言蘊涵式(I類公式)I1P∧Q

PI2P∧Q

QI3

P

P∨QI4Q

P∨QI5

P

P

QI6Q

P

QI7

(P

Q)

PI8

(P

Q)

QI9P,Q

P∧QI10

P,(P∨Q)

QI11P,(P

Q)

QI12

Q,(P

Q)

PI13P

Q,Q

R

P

RI14P∨Q,P

R,Q

R

RI15A

B(A∨C)(B∨C)I16A

B

(A∧C)(B∧C)基礎(chǔ)等價公式(E類公式):對合律

P

P交換律P∧Q

Q∧P

P∨Q

Q∨P結(jié)合律P∧(Q∧R)(P∧Q)∧RP∨(Q∨R)(P∨Q)∨R分配律

P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)吸收律P∨(P∧Q)

PP∧(P∨Q)

P底-摩根定律

(P∧Q)

P∨

Q

(P∨Q)

P∧

Q冪等律

P∨P

PP∧P

P同一律

P∨F

P

P∧T

P

零律

P∨T

TP∧F

F互補律P∨

PTP∧

P

F

P

Q

P∨Q，

P

Q

Q

PP(QR)(P∧Q)RPQ(P

Q)∧(Q

P)PQ(P∨Q)∧(P∨

Q)PQ(P∧Q)∨(

P∧

Q)

(PQ)P

Q推理方法：

直接推理

間接推理條件論證反證法一.直接推理

直接推理是由一組前提，利用P規(guī)則、T規(guī)則直接推演得到有效結(jié)論的方法。推理實際上就是證明永真蘊含的過程。為了使推理過程更加簡單、明確，推理會采用另外一種書寫格式。例1求證P→Q，Q→R，P

R證明：

序號前提或結(jié)論注釋列

(1)PP(2)P

QP(3)QT(1)(2)I(4)Q→RP(5)RT(3)(4)I（公式：P，P→QQ）推理格式：第一列為步驟號；第二列為給定前提或得出的結(jié)論；第三列為注釋列，標(biāo)明是前提還是得到的結(jié)論，以及此結(jié)論是從哪幾步得到的，所用公式得類型。例2求證：

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

R

P(1)

RP(2)Q∨RP(3)QT(1)(2)I(4)

(P∧Q)P(5)

P∨

QT(4)E(6)

PT(3)(5)I注：公式：

P,P∨Q

Q

，

(P∧Q)

P∨

Q假設(shè)

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

R為T，則

(P∧Q)，(Q∨R)，R均為T，由R，(Q∨R)為T，知Q為T；由

(P∧Q)為T，而

(P∧Q)

P∨

Q，于是

P∨

Q為T，再由Q為T，知

P為T。

例3求證：P→(Q→S)，

R∨P，Q

R→S證明：(1)QP(2)P→(Q→S)P(3)

P∨(

Q∨S)T(1)E(4)

P∨(S∨

Q)T(2)E(5)(

P∨S)∨

QT(3)E(6)

P∨ST(4)(5)I(7)P→ST(6)E(8)

R∨PP(9)R→PT(8)E(10)R→ST(7)(9)I二、條件論證如果要證明的結(jié)論是R→S的形式，則可以把結(jié)論中R→S的前件R作為附加前提，與給定的前提一起推出后件S即可。定理如果H1∧H2∧...∧Hn∧R

S，

則H1∧H2∧...∧Hn

R→S

證明：因為H1∧H2∧...∧Hn∧R

S，則

(H1∧H2∧...∧Hn∧R)

S是永真式。而(H1∧H2∧...∧Hn∧R)

S

(H1∧H2∧...∧Hn∧R)∨S

(H1∧H2∧...∧Hn)∨(

R∨S)

(H1∧H2∧...∧Hn)

(R→S)

所以(H1∧H2∧...∧Hn)

(R→S)是永真式。即H1∧H2∧...∧Hn

R→S，

定理得證。我們把上述定理寫成如下規(guī)則：

CP規(guī)則(ConditionalProof)：

如果H1∧H2∧...∧Hn∧R

S，則

H1∧H2∧...∧Hn

R→S例4

P→(Q→S)，

R∨P，Q

R→S證明：(1)R

P(附加前提)

(2)

R∨P

P

(3)P

T(1)(2)I

(4)P→(Q→S)

P

(5