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

iS離散數(shù)學(xué)DiscreteMathematicsrCDDiscretemathematicsisthestudyofmathematicalstructuresthatarefundamentallydiscreteratherthancontinuous.Incontrasttorealnumbersthathavethepropertyofvarying"smoothly",theobjectsstudiedindiscretemathematics–suchasintegers,graphs,andstatementsinlogic–donotvarysmoothlyinthisway,buthavedistinct,separatedvalues..ete工科目錄08圖論06運算與代數(shù)系統(tǒng)02謂詞邏輯03集合的概念與運算04關(guān)系05函數(shù)01命題邏輯07環(huán)、域、格、布爾代數(shù)索引第一章命題邏輯命題，邏輯聯(lián)結(jié)詞，命題公式的翻譯，命題公式的值與等價，范式，推理理論1.1

命題1.2

邏輯聯(lián)結(jié)詞1.3

命題公式與真值表1.4

命題翻譯1.6

范式1.7

推理理論1.5

命題翻譯1.1

命題

概念：是指反映事物的本質(zhì)屬性的思維形式，是思維的基本單位。判斷：是指對事物是否具有某種屬性，即是否符合某概念進行肯定或否定的回答。推理：是指由一個或幾個判斷推出另一個判斷的思維形式。兩類邏輯：邏輯分為辯證邏輯和形式邏輯兩種。形式邏輯所研究的思維的形式結(jié)構(gòu)，就是指概念、判斷和推理之間的結(jié)構(gòu)和關(guān)系?，F(xiàn)代形式邏輯利用數(shù)學(xué)方法或者說借助符號體系進行推理規(guī)律的研究，因此，也稱其為數(shù)理邏輯或符號邏輯，是指利用數(shù)學(xué)方法或者說借助符號體系研究推理規(guī)律的科學(xué)，目的就是利用計算的方法來代替人們思維中的邏輯推理過程。

1.1命題[定義1-1：命題]表達判斷的可判別真假的陳述句稱為命題(proposition,statement)。一個命題所表達判斷的或“真”、“假”結(jié)果稱為命題的值或真值(truth)。命題一般用字母表示，如p或P。如，p：沈陽是一個大城市。若命題的值為真，可用T、1或“真”表示；若值為假用F、0或“假”表示。代表一個固定的命題的p是命題常量（propositionconstant）。在p可以任意指代時稱為命題變元（propositionvariable）。不可再拆分的命題稱為原子命題（atom）或簡單命題，由原子命題與聯(lián)結(jié)詞構(gòu)成的命題稱為復(fù)合命題（compoundproposition）。

1.1命題[例1-1]將下述命題用符號表示：(1)日本人民是偉大的。(2)雪是黑的。(3)1+101=110。(4)火星上有生物。(5)一個偶數(shù)可表示成兩個素數(shù)之和。

(6)x+y=z。(7)(a)動作快點！

(b)天安門真雄偉啊！(c)請給我一杯茶。

(d)你掌握命題的概念了嗎？(8)我正在說謊。

(9)我只給不給自己刮胡子的人刮胡子。(10)如果天氣好，我就去散步。解：(1)是，1；(2)是，0；(3)是，？；(4)是，？；(5)是，？；(6)否；(7)、(8)、(9)否，悖論；(10)是，復(fù)合命題。

1.1命題在邏輯學(xué)中，命題與判斷是兩個既有聯(lián)系又有區(qū)別的概念，命題是對事物情況的陳述，判斷是對思維對象有所斷定的思維形式，是斷定者在一定時空條件下對一個命題是真或假的斷言。因此，判斷一定是命題，而命題不一定是判斷。例如，“火星上有生物。”是命題，但沒有經(jīng)過證實，不是判斷。1.2

邏輯聯(lián)結(jié)詞

[否定┐]。若p為命題，新命題┐p是對p的否定（negation，not）。┐p的值與p相反，讀作“非P”。1.2.1

基本聯(lián)結(jié)詞[例1-2]令p：沈陽是一個大城市。則p的否定為┐p。可以敘述為：(a)沈陽不是一個大城市。

(b)沈陽是一個不大的城市。(c)沈陽是一個大城市不真。思考：自然語言表示不唯一，符號表示才是唯一的。C語言中的!1.2.1

基本聯(lián)結(jié)詞

[否定┐]。若p為命題，新命題┐p是對p的否定（negation，not）。┐p的值與p相反，讀作“非p”。[例1-2]令p：沈陽是一個大城市。則p的否定為┐p。可以敘述為：(a)沈陽不是一個大城市。

(b)沈陽是一個不大的城市。(c)沈陽是一個大城市不真。思考：自然語言表示不唯一，符號表示才是唯一的。C語言中的!

1.2.1基本聯(lián)結(jié)詞[合取∧]（邏輯積）。命題p和q的合?。╟onjunction，and）構(gòu)成新命題p∧q，讀作“p與q”或“p與q的合取”。當且僅當p和q都為1時，p∧q為1，否則為0。

p∧q表示按邏輯求積，即p∧q=p×q，規(guī)則是：1×1=1，1×0=0，0×1=1，0×0=0[例1-3]令p：sinx是奇函數(shù)，q：ex是奇函數(shù)。p：道路曲折，q：前途光明。（轉(zhuǎn)折）則命題“不僅sinx是奇函數(shù)，ex也是奇函數(shù)”、“道路雖然曲折，但前途光明”可表示為p∧q。C語言中的&&

1.2.1基本聯(lián)結(jié)詞[析取?]（邏輯和）。命題p和q的(可兼)析?。╥nclusiveor）構(gòu)成新命題p∨q，讀作“p或q”或“p與q的析取”。當且僅當p和q都為0時，p∨q為0，否則為1。

p∨q表示按邏輯求和，即p∨q=p+q，規(guī)則是：1+1=2（邏輯意義仍是1），1+0=1，0+1=1，0+0=0[例1-4]令p：馬云是阿里巴巴集團主席，q：馬云是阿里巴巴集團首席執(zhí)行官。則命題“馬云是阿里巴巴集團主席或首席執(zhí)行官”可表示為p∨q。C語言中的||

1.2.1基本聯(lián)結(jié)詞[不可兼析取ˉ

∨]。命題p和q的不可兼析取（exclusiveor，或不可兼或、排斥或）構(gòu)成新命題

pˉ

∨q

，用于描述兩者不能兼有的情況，即p、q都為1或0時，pˉ

∨

q

為0。否則為1。[應(yīng)用]

繪圖軟件中拉伸線條的橡皮筋等功能。例=>明天晴天或下雨。

不可兼析取ˉ?與著名的異或運算（XOR）相對應(yīng)，也可用?表示。對于任意的命題P，它有非常好的性質(zhì)：pˉ

∨

0=p，p

ˉ

∨

1=┐p，pˉ

∨

p=0

1.2.1基本聯(lián)結(jié)詞[條件→]。命題p條件q（conditional）構(gòu)成新命題p→q。讀作“p則q”，或“p條件q“，或“如果p那么q“，或“只要p就q“。當且僅當p為1而q為0時，p→q為0，否則為1。例=>

令p：函數(shù)f(x)在x0處可導(dǎo)，q：f(x)在x0處連續(xù)。則命題“如果函數(shù)f(x)在x0處可導(dǎo)，則f(x)在x0處連續(xù)”表示成p→q。思考：

真值的規(guī)定被稱為善意的推斷：前件為0時，不須考慮后件。[示例]“如果我中了彩票，我把一半獎金分給你”。當我沒中彩票時，無論分給你與否都不食言。假設(shè)不成立，一切休提。

1.2.1基本聯(lián)結(jié)詞[雙條件?]。命題p雙條件q（biconditional）構(gòu)成新命題p?q。讀作“p雙條件q“或“p當且僅當q“。當且僅當p和q的值相同時p

?q為1，否則為0。

命題p?q表示p和q互為充分必要條件。[例1-6]>令：p：你可以坐飛機，q：你買了機票。則命題“你可以坐飛機當且僅當你買了機票”可表示為p?q。

1.2.1基本聯(lián)結(jié)詞

在以上6個聯(lián)結(jié)詞中，┐、∧、∨是最基本的聯(lián)結(jié)詞，其他聯(lián)結(jié)詞都可由它們表示出來。兩種重要的轉(zhuǎn)換關(guān)系是：試一試：

邏輯聯(lián)結(jié)詞的用處廣泛，網(wǎng)頁中普遍采用邏輯運算進行信息檢索，也稱作布爾邏輯搜索。

pˉ

∨

q=(p?┐q)?(┐p?q)

pˉ

∨

q

=┐(p?q)

[與非↑]命題p與非q(notand)構(gòu)成新命題p↑q，含義是p↑q=┐(p?q)。[或非↓]命題p與或q（notor）構(gòu)成新命題p↓q，含義是p↓q=┐(p?q)。[條件否定

→C

]命題p條件否定q（notifthen）為新命題

p

→C

q，含義是：

p

→C

q

?┐(p→q)分析真值的情況可說明，合取、析取、不可兼析取、與非、或非都滿足交換律和結(jié)合律。1.2.2

其他聯(lián)接詞1.3

命題公式與真值表

1.3.1命題公式

[定義]命題演算的合式公式（well-formedformula，wff）定義為：(1)單個命題變元或常量本身是一個合式公式。(2)如果

A是合式公式，那么是合式公式。(3)如果

A和

B是合式公式，那么

A?B、A?B、

Aˉ?

B

、A→B和A?B、A↑B、A↓B和A

→C

B都是合式公式。(4)當且僅當能夠有限次地應(yīng)用(1)、(2)、(3)所得到的包含命題變元、聯(lián)結(jié)詞和括號的符號串是合式公式。組成合式公式的命題變元可稱為公式的“分量”。

1.3.1命題公式

[不嚴格解釋]由命題常量、變元和聯(lián)結(jié)詞組成的有意義式子就是合式公式。[聯(lián)結(jié)詞（運算符）的優(yōu)先次序]┐優(yōu)先于?優(yōu)先于?優(yōu)先于→優(yōu)先于?。比較：因為含有值未知的命題變元，導(dǎo)致命題公式的值不確定，不能稱為命題。一個含有n個原子變元的命題公式A與n元數(shù)學(xué)函數(shù)f意義相同：A(p1,p2,…,pn)=(p1?p2)→?f(x1,x2,…,xn)=(x1+x2)*?它們沒有本質(zhì)區(qū)別，但x1~xn通常取連續(xù)區(qū)間的實數(shù)，f亦然。相對地，p1~pn僅取值為1或0，A本身亦如此。

從這一點上說，命題公式比一般數(shù)學(xué)表達式更簡單。同時，命題公式也稱為“命題函數(shù)”，公式中的分量就是函數(shù)的自變量。例=>p?q→r等同于(p?q)→r，但不等同于p?(q→r)。1.3.2

真值表

[定義]若p1,p2,...,pn是出現(xiàn)在命題公式A中的所有原子變元，任意指定p1,p2,...,pn的一組真值稱為A的一個解釋（Interpretation），也稱指派或賦值（assign）。簡言之，對一個命題公式的一次解釋就是對其所有原子變元的一次賦值。

n個原子變元組成的命題有2n種賦值。例=>命題公式p?q的2個原子變元共有22=4個解釋，分別是11、10、01和00。

1.3.2真值表

pq┐p┐q┐p→┐q11000101100111000011[定義]將一個命題中原子變元的所有賦值與對應(yīng)命題的真值匯聚成表稱為真值表（truthtable）=>運算表。pqp?q111100010000表1-1公式p?q的真值表表1-2公式┐p→┐q的真值表用于規(guī)定一個聯(lián)結(jié)詞組成的復(fù)合命題公式的真值表就是程序語言中的運算表。

1.3.2

真值表pq┐pp?qp?qp→qp?qpˉ

∨

q

p↑qp↓qp

→C

q11011110000100010011010110110110000100110110注意：

若有

n個命題變元，應(yīng)按2n-1

0或0

2n-1的順序?qū)⑦@些整數(shù)轉(zhuǎn)換為

n位二進制串排列即可，如11、10、01、00。表1-39個聯(lián)接詞的真值表1.4

命題翻譯

1.4.1合取命題

自然語言中的典型合取聯(lián)接詞：和、且、既-又、不但-而且、并列句、轉(zhuǎn)折句等。[例1-7]將下述命題用符號表示。(1)黃渤既聰明又勤學(xué)苦練。 (2)黃渤聰明，而且勤學(xué)苦練。(3)中國人民是勤勞和勇敢的。 (4)你是好人，他不是好人。(并列)(5)他雖然聰明但不用功。(6)我努力了，可是沒有達到理想的效果。(轉(zhuǎn)折)(7)張三或李四都可以做這件事。(用“或”，但重在“都”，不規(guī)范說法)

1.4.1合取命題解：均應(yīng)表示為兩個命題的合取。如(3)，令p：中國人民是勤勞的，q：中國人民是勇敢的。則原命題表示為：p?q。注意：原子命題中不能含聯(lián)結(jié)詞，且需要根據(jù)上下文補足句子中省略的成分。

1.4.1合取命題注意：漢語的“和”、“與”有特殊用法，僅表示原子命題，不能用合取表示。例=>(1)中國和巴基斯坦是全天候戰(zhàn)略合作伙伴。(2)吾與汝畢力平險。思考：怎么衡量“p與q”、“p和q”這樣的命題是原子還是復(fù)合命題呢？

如果句子的謂語部分反映的是人或物（如

p和q）之間的關(guān)系或者共同完成的事情則是原子命題，否則是復(fù)合命題。思考：“科比和詹姆斯都是NBA明星。”是什么命題？1.4.2析取命題

自然語言中的典型析取聯(lián)接詞：或、或者、亦或等。[例1-8]將下述命題用符號表示。(1)王學(xué)東愛聽音樂或愛看電影。(2)張朝陽昨天一口氣做了20或30道習題。解：(1)可表示為兩個原子命題p和q的析取p?q。(2)這里的“或”表示不確定估計，代表一個模糊的量，視為原子命題更合適。注意：在遇到聯(lián)接詞“或”時，第一件要做的事情不是符號表示，而是分析它是可兼或還是不可兼或。

1.4.2析取命題[例1-9]將下述命題用符號表示：(1)馬拉松比賽在明天上午9點或者下午2點舉行。(2)我要出去看電影或者在家看電視。(3)黃渤可能是100米賽跑或400米賽跑的冠軍（如果每人只限于一項）。(4)黃渤住在202或203房間。解：

因為兩個原子命題不能同時為真，應(yīng)表示為兩原子p和q的不可兼析取pˉ

∨

q

從意義或值的角度出發(fā)，也可以表示為(p?┐q)?(┐p?q)，或┐(p?q)。1.4.3條件命題

[自然語言中的典型條件分兩類](1)只要-就型。聯(lián)接詞有：當、如果-那么、因為-所以等，表示充分條件。(2)只有-才型。聯(lián)接詞有：僅當、除非等，表示必要條件。1.只要-就型[例1-10]將下述命題用符號表示：(1)因為感染了病毒，所以系統(tǒng)運行不正常。(2)只要努力，就一定會成功。 (3)當山花開的時候，你爹就回來了。解：

若p表示前件，分別是：(1)p：感染了病毒，(2)p：努力，(3)p：山花開的時候。q表示后件，分別是：(1)q：系統(tǒng)運行不正常，(2)q：一定會成功，(3)q：你爹回來了。上述復(fù)合命題均可符號表示為：p→q。

1.4.3條件命題[例]將下述命題用符號表示：(1)只有通過基礎(chǔ)測試才能參加正式比賽。

(2)愛拼才會贏。(3)僅當你盡了全力，才能打贏這一仗。

(4)除非你盡了全力，才能打贏這一仗。(5)除非你盡了全力，否則不能打贏這一仗。2.只有-才型解：若p表示后件，分別是：(1)通過基礎(chǔ)測試，(2)愛拼，(3)盡了全力。令q表示前件，分別為：(1)才能參加正式比賽，(2)會贏，(3)打贏這一仗。符號化為：q→p。

1.4.3條件命題思考：(1)當且僅當（ifandonlyif，或iff）當p就q+僅當p才q=當且僅當p則q當=只要就僅當=只有才(2)除非除非=如果不表述：除非p，否則非q（則q）。直譯為：┐p→┐q等同于q→p1.4.4多聯(lián)結(jié)詞命題

[例1-12(1)]我們要做到身體好、學(xué)習好、工作好，為祖國繁榮昌盛而奮斗。解：記p：我們要做到身體好。q：我們要做到學(xué)習好。r：我們要做到工作好。s：我們要為祖國繁榮昌盛而奮斗。命題可形式化為(p?q?r)?s[例1-12(2)]春天來了，燕子飛回來了。解：

記p：春天來了。q：燕子飛回來了。命題可形式化為p?q

1.4.4多聯(lián)結(jié)詞命題[例1-12(3)]我沒收到他的信。可見，要么他沒給我寫信，要么信在郵寄途中丟失了。[例1-12(4)]假如上午不下雨，我去圖書館，否則就在家里讀書或?qū)懽鳂I(yè)。解：

記p：上午下雨。q：我去圖書館。r：我在家里讀書或?qū)懽鳂I(yè)。符號化為(┐p→q)?(p→r)思考：為什么不能表示成不可兼析取(┐p→q)ˉ

∨

(p→r)呢？解：

記p：我沒收到他的信。q：他沒給我寫信。r：信在郵寄途中丟失了。命題可形式化為p→(pˉ

∨

q

)

1.4.4多聯(lián)結(jié)詞命題[例1-12(5)]人不犯我，我不犯人；人若犯我，我必犯人。解：

記p：人犯我。q：我犯人。命題可形式化為(┐p→┐q)?(p→q)[例1-12(6)]一個人起初說，“占據(jù)空間的、有質(zhì)量的而且不斷變化的叫做物質(zhì)”。后來他改說，“占據(jù)空間的有質(zhì)量的叫做物質(zhì)，而物質(zhì)是不斷變化的”。符號化這兩個命題以反映出二者的差異。解：

記p：某種東西占據(jù)空間。q：某種東西有質(zhì)量。r：某種東西不斷變化。s：某種東西叫做物質(zhì)。兩次說法可分別形式化為

(p?q?r)?s(p?q?s)?(s→r)注意：

給一個概念下定義要用雙條件來形式化，即“描述?概念”。

1.4.4多聯(lián)結(jié)詞命題[例1-12(7)]如果你來了，那么他唱不唱歌將看你是否伴奏而定。解：

記p：你來了。q：他唱歌。r：你伴奏。命題可分別形式化為

p→(q?s)1.5

命題公式的值與等價

1.5.1命題公式的種類

[定義]假設(shè)

A是一個命題公式。若無論原子變元如何賦值，A都為真，則

A是永真式或重言式（tautology）。若對原子變元的任何賦值，A都為假，則

A是永假式或矛盾式（contradiction）。若至少存在一組賦值使A都為真，則A是可滿足式（contingency）。例=>無論p和q表示什么命題，p?┐p、(p?q)?┐(p?q)都是永假式，p?┐p、(p→q)?┐(p→q)都是永真式。比較：

一個命題公式A：A(p1,p2,...,pn)=(p1?p2)→?與一個數(shù)學(xué)函數(shù)f一致：f(x1,x2,...,xn)=(x1+x2)??

1.5.1命題公式的種類[永真式代入定理]若命題A(p1,p2,…,pn)為永真式，則分別用q1,q2,…,qn替換A中的命題變元p1,p2,…,pn，所得到的公式仍為永真式。定理本質(zhì)是反映永真式的真值與命題變元的取值無關(guān)。例=>命題┐(p∧q)?(p∧q)為永真式，用r、s替換p、q得到的命題┐(r∧s)?(r∧s)仍為永真式。1.5.2命題公式的等價

[定義]若命題公式A(p1,p2,…,pn)和B(p1,p2,…,pn)有相同的原子變元，且對p1,p2,…,pn的每組賦值，A和B的值都相同，則公式A和B相等，稱為A和B等價（logicalequivalence）或等值，記做A?B，或A≡B。思考：命題公式等價就是命題函數(shù)相等。[結(jié)果]若A(p1,p2,…,pn)?B(p1,p2,…,pn)，有A(┐p1,┐p2,…,┐pn)?B(┐p1,┐p2,…,┐pn)主要有3種證明兩公式等價的方法。

1.5.2命題公式的等價(1)真值表法[例]

證明公式p→q?┐p∨q和pˉ

∨

q?(p?┐q)?(┐p?q)。pqp→q┐p∨qpˉ

∨

qp?┐q┐p?q(p?┐q)?(┐p?q)11110000100011010111101100110000[說明]利用真值表法很容易驗證一些基本的算律，如交換律、結(jié)合律、分配律，德?摩根律等。

1.5.2命題公式的等價(2)等價變換法如果一個公式中的一部分也是命題公式，一般稱其為原公式的“子公式”。[等價置換規(guī)則]若X是A的子公式，且X?Y。若在A中用Y部分或全部替換X得到B，則A?B。實質(zhì)：利用對命題公式本身或其子公式進行等價替換不改變原公式的值。[例1-13]證明p→(q→r)?q→(p→r)。證明：

p→(q→r)?(原公式等價變換)┐p∨(q→r) ?(子公式等價變換)┐p∨(┐q∨r)?(交換律、結(jié)合律)┐q∨(┐p∨r)?(子公式等價變換、原公式等價變換)q→(p→r)

1.5.2命題公式的等價(3)雙條件式永真法[定理]對于命題公式A和B，A?B當且僅當A?B為永真式。

A?B只在A與B具有相同值時為真，結(jié)論顯然。

這是一個需要熟悉的定理，可以作為“命題公式等價的判定定理”。[定理的等價描述]由于A?B?(A→B)?(B→A)，定理可等價敘述為：

A?B當且僅當A→B和B→A均為永真式。

1.5.2命題公式的等價序號等價關(guān)系含義E1┐┐p

p對合律（雙重否定律）E2p∧q

q∧p交換律E3p∨q

q∨pE4(p∧q)∧r

p∧(q∧r)結(jié)合律E5(p∨q)∨r

p∨(q∨r)E6p∧(q∨r)

(p∧q)∨(p∧r)分配律E7p∨(q∧r)

(p∨q)∧(p∨r)E8┐(p∧q)

┐p∨┐q德?摩根律E9┐(p∨q)

┐p∧┐q基本等價關(guān)系表1-5

1.5.2命題公式的等價

序號等價關(guān)系含義（續(xù)表）E10p∨p

p等冪律E11p∧p

pE12q∨(p∧┐p)

q同一律E13q∧(p∨┐p)

qE14q∨(p∨┐p)

1零律E15q∧(p∧┐p)

0E16p

q

┐p∨q蘊含等值E17┐(p

q)

p∧┐qE18p

q

┐q

┐p假言易位E19p

(q

r)

(p∧q)

r

1.5.2命題公式的等價

序號等價關(guān)系含義（續(xù)表）E20p?q

(p

q)∧(q

p)等價等值E21p?q

(p∧q)∨(┐p∧┐q)E22┐(p?q)

p?┐qE23p?q

┐p?┐q等價否定等值E24(p

q)∧(p

┐q)

┐p歸謬論E25pˉ

∨

q

┐(p?q)E26pˉ

∨

q

(p∧┐q)∨(┐p∧q)1.5.3聯(lián)結(jié)詞功能完備集

因為2個原子變元有4種賦值，而對應(yīng)每組賦值，命題的值有2種可能，故共有24種可能。通過列表可說明，9個聯(lián)結(jié)詞組成的聯(lián)結(jié)詞集合是聯(lián)結(jié)詞功能完備集（completegroupofconnectives）。聯(lián)結(jié)詞功能完備集就是指任何命題可以由此集合中的聯(lián)結(jié)詞表示出來。

由p→q?┐p?q，p

→C

q?┐(p→q)，

pˉ

∨

q?┐(p?q)，

p?q?(p→q)?(q→p)，p↑q?┐(p?q)，p↓q?┐(p?q)說明其他聯(lián)結(jié)詞均可由┐、?、?表示，故{┐,?,?}是功能完備的。

由p↑p?┐p，(p↑p)↑(q↑q)?p?q，(p↑q)↑(p↑q)?p?q，

p↓p?┐p，(p↓p)↓(q↓q)?p?q，(p↓q)↓(p↓q)?p?q說明{↑}、{↓}都是聯(lián)結(jié)詞功能完備集。1.5.4由德?摩根律到對偶原理

命題運算中的德?摩根律：┐(p?q)?┐p?┐q，┐(p?q)?┐p?┐q思考：公式成對，變元也不止2個，下述公式會如何？┐((p?q)?r)??，┐((p?q)?r)??[定義]將一個公式A中所有的∧換成∨，∨換成∧，1換成0，0換成1，得到的公式A*稱為A的對偶式。其實，A和A*互為對偶。例=>1與0互為對偶，(p?q)?r與(p?q)?r互為對偶，p↑q?┐(p?q)與┐(p?q)?p↓q互為對偶。實質(zhì)：求對偶式?jīng)]有否定什么事！

1.5.4由德?摩根律到對偶原理[對偶原理]設(shè)A和A*是對偶式，p1，p2，...，pn是公式中包含的原子變元，則┐A(p1，p2，...，pn)?A*(┐p1，┐p2，...，┐pn)。[定理]若A?B，則A*?B*。證明：因為A?B，有A(┐p1，┐p2，...，┐pn)?B(┐p1，┐p2，...，┐pn)，于是，有┐A(┐p1，┐p2，...，┐pn)?┐B(┐p1，┐p2，...，┐pn)，即A*?B*。定理說明，同一個公式不可能有兩個不一樣的對偶式，換言之，兩個公式相等則它們的對偶式相等。推廣的德摩根律1.6

范式

有一種重要的衡量公式是否等價的方法是將各公式轉(zhuǎn)換成標準形式，這種標準形式稱為“范式”（normalform）。1.6.1簡單的范式

[定義：文字]原子命題變元或它的否定稱為文字。如

p和

┐p。例=>(p?┐q?r)?(┐p?q)?┐q)為合取范式，┐p?(p?q)?(p?┐q?r)是析取范式。[定義：合取范式]一個命題公式稱為合取范式，如果它具有形式：A1?A2???An，n≥1其中，每個Ai都是由文字組成的析取式。[定義：析取范式]一個命題公式稱為析取范式，如果它具有形式：A1?A2???An，n≥1其中，每個Ai都是由文字組成的合取式。積范式和范式

1.6.1簡單的范式思考：單個文字如p和┐p，單個合取式p∧q或析取式p∨┐q是什么范式？

注意：

否定只能作用在原子前，絕不能置于括號前聯(lián)結(jié)詞轉(zhuǎn)換為∧、∨及┐；(2)用德?摩根律（對偶原理）將否定符號

┐直接移到各個命題變元之前；(3)用分配律、結(jié)合律歸約為合取范式或析取范式。

1.6.1簡單的范式[例1-16]求(p∧(q→r))→s的合取范式。解：

(p?(q→r))→s?(規(guī)范聯(lián)結(jié)詞)┐(p?(┐q?r))?s ?(否定深入)┐p?(q?┐r)?s ?(交換律、結(jié)合律、分配律)(┐p?s?q)?(┐p?s?┐r))

一個命題公式的合取范式與析取范式是唯一的嗎？答：否。例如：A=p?p?(q?┐q)?(p?q)?(p?┐q)

不唯一的原因是？答：組成合取式或析取式的原子變元不全。1.6.2小項與大項

[定義：小項]n個命題變元的合取式稱作（極）小項或布爾合取(minimalterm)，如果它包含每個變元的文字一次且僅一次。

n個命題變元有2n個小項。如兩個命題變元的小項為p∧q、┐p∧q、p∧┐q、┐p∧┐q[編碼]由于每個小項只有一種賦值使其為1，可用其作對它的編碼，如：m11=p?q=m3、m10=p?┐q=m2、m01=┐p?q=m1、m00=┐p?┐q=m0[性質(zhì)]

每個小項，只有變元賦值與其二進制編碼相同時小項為真，其余全假；任何一組賦值，能使唯一的一個小項為真，其余全假，即2個小項不能同時為真。有：(1)mi?mj=0，0≤i，j≤2n-1； (2)∑ni=1

mi=1。

1.6.2小項與大項[定義：大項]n個命題變元的析取式稱作（極）大項或布爾析取(maximalterm)，如果它包含每個變元的文字一次且僅一次。

n個命題變元有2n個大項。如兩個命題變元的大項為p?q、┐p?q、p?┐q、┐p?┐q[編碼]由于每個大項只有一種賦值使其為0，可用其作對它的編碼，如：M11=┐p

?┐q=M3、M10=┐p?q=M2、M01=p?┐q=M1、M00=p?q=M0[性質(zhì)]每個大項，只有變元賦值與其二進制編碼相同時其值為假，其余全真；任何一組賦值，能使唯一的一個大項為假，其余全真，即2個大項不能同時為假。有：(1)Mi?Mj=1，0≤i，j≤2n-1； (2)∏ni=1

Mi=0。

1.6.2小項與大項[定理]┐mi=Mi，┐Mi=mi，0

i

2n-1。

如何計算小項或大項呢？答：添加與1的合取、與0的析取，再將1和0用缺少的變元替換，施以分配律就可以了。例=>共3個變元p、q和r。A=p?┐q是析取式，但不是小項，缺少r。添上：A

=p?┐q?(p?┐q)?1?(p?┐q)?(r?┐r)?(p?┐q?r)?(p?┐q?┐r)這就將A

轉(zhuǎn)換成了2個小項的析取。1.6.3主析取范式與主合取范式

[定義]

僅由小項的析取所組成的命題公式稱為主析取范式(majordisjunctiveform)，僅由大項的合取所組成的命題公式稱為主合取范式（majorconjunctiveform）。[簡化記法]通常，主析取范式

mi1?mi2

?…?

mit

簡記為

∑i1,i2,…,it或

∑{i1,i2,…,it}

主合取范式

Mi1?Mi2

?…

?Mit簡記為

∏i1,i2,…,it或

∏{i1,i2,…,it}

1.6.3主析取范式與主合取范式[例1-17]求p→((p→q)?┐(┐q?┐p))的主析取范式和主合取范式。解：原式?┐p?((┐p?q)?(q?p))?┐p?((┐p?q?p)?(q?q?p)) ?┐p?(p?q) （注：析取范式） ?(┐p?(q?┐q))?(p?q) （注：缺q的項上添加1=q?┐q） ?(┐p?q)?(┐p?┐q))?(p?q) （注：主析取范式）原式?┐p?((┐p?q)?(q?p))?┐p?(p?q)?1?(┐p?q)?┐p?q（注：主合取范式）

1.6.3主析取范式與主合取范式[定理]在真值表中，使公式值為1的賦值作編碼對應(yīng)小項的析取是公式的主析取范式，使公式值為0的賦值作編碼對應(yīng)大項的合取是公式的主合取范式。證明：對公式A，假設(shè)使A為1的賦值對應(yīng)的小項為mi1、mi2、…

、mit，記B=∑i1,i2,…,it則A

B。

因為若一組賦值使A為1，則對應(yīng)的小項在B中，B也為1。若一組賦值使A為0，則B中的小項都為0，故B為0。

主合取范式的證明類似。

1.6.3主析取范式與主合取范式例=>計算公式A=p→((p→q)?┐(┐q?┐p))的主范式。解：pqp→q┐q?┐p(p→q)?┐(┐q?┐p)Am或M001101M00011101m01100000m10111111M11表1-7公式A=p→((p→q)?┐(┐q?┐p))的真值表主析取范式為：m00?m01?m11=Σ{0,1,3}。主合取范式為：M10=Π{2}。

1.6.3主析取范式與主合取范式[析取與合取轉(zhuǎn)換定理]若公式A的主析取范式為

∑{i1,i2,…,ik}，主合取范式為

∏{0,

1,…,2n-1}-{i1,i2,…,ik}反之亦然。證明：若A=

∑{i1,i2,…,ik}，因A與┐A的值相反，故┐A=∑{0,

1,…,2n-1}-{i1,i2,…,ik}有A=┐┐A=∏{0,

1,…,2n-1}-{i1,i2,…,ik}。對右端取非后，∧與∨互換，Σ與Π

互換，┐mi恰好轉(zhuǎn)換為Mi，結(jié)論成立。[范式存在定理]任一命題公式的主析取范式和主合取范式都存在且唯一。注意：Σ{0,1,2,…,2n-1}和Π{0,1,2,…,2n-1}分別用1和0表示，稱為空范式。

1.6.3主析取范式與主合取范式[例*]利用范式解決有限情況的判定問題。若有一次競賽，要求在p、q、r和s這4人中指派兩人參加，但必須滿足如下條件：(1)p和q僅一個人參加； (2)若r參加，則s也參加；(3)q和s至多參加一人； (4)若s不參加，則p也不參加。問應(yīng)如何指派？解：令p、q、r和s分別表示命題p參加、q參加、r參加和s參加，約束條件為C=(pˉ

∨

q)∧(r→s)∧┐(q∧s)∧(┐s→┐q)計算命題C的主析取范式：C=m1000∨m1001∨m1011∨m1011

由于哪個mi為1都能保證C為1，故每個mi都代表一種可能的選擇。因指派2人參加，故只有m1001=p∧┐q∧┐r∧s是正確選派方式，即派p和s參加。1.7推理理論

從假設(shè)前提（條件、定理和定律）得到另外的命題，即形成結(jié)論的過程就是推理，這是研究邏輯的主要目標。1.7.1蘊含與論證

1.推理的含義與形式[定義]當且僅當p

q時，稱為p蘊含q（logicalimplication），記作p?q。此時，稱p為前提，q為p的有效結(jié)論或邏輯結(jié)論，也稱為q可由p邏輯推出。得出此邏輯關(guān)系的過程稱為論證。

所有邏輯推理的實質(zhì)就是證明p?q，也就是證明p

q為永真式。通常的邏輯推理問題都會由一組前提H1，H2，...，Hn來推斷一個邏輯結(jié)論，論證要求可寫作H1?H2???Hn?C，或H1,H2,...,Hn?C，或H1,H2，...,Hn?C

1.7.1蘊含與論證[比較示例]一個簡單的初等數(shù)學(xué)證明題目：已知a、b、c為實數(shù)，且a2-b2=bc，c≠0，證明a2/c=b(b/c+1)。如果記p：a2-b2=bc，q：c≠0，r：a2/c=b(b/c+1)上述論證要求可描述為：p?q?r證明的目的就是說明：若前提p?q正確，則結(jié)論r也正確，即證明p?q→r為永真式。

1.7.1蘊含與論證2.常規(guī)的推理方法真值表法列出公式H1?H2???Hn

C的真值表。若表中所有行全為1則得證。變元較多時較麻煩。(2)敘述型推理說明不存在H1?H2???Hn為1且C為0的情況?？梢杂袃煞N敘述形式：(a)假定H1?H2???Hn為1推導(dǎo)C必為1。(b)假定C為0推導(dǎo)H1?H2???Hn必為0。

1.7.1蘊含與論證

證法(a)：若前件┐q?(p

q)為1。那么，┐q和p

q都為1，從而q為0。因此，p為0，故┐p為1。結(jié)論成立。[例1-20]證明┐q?(p

q)?┐p。證法(b)：

若假定后件┐p為0。于是，有p為1。若q為1，則┐q為0，故┐q?(p→q)為0。若q為0，則p→q為0，故┐q?(p→q)為0?？傊?，前件┐q?(p→q)為0。結(jié)論成立。

1.7.1蘊含與論證[例1-21]用符號描述推理過程并驗證論證的有效性：如果6是偶數(shù)，則7被2除不盡?；?不是素數(shù)，或7被2除盡。但5是素數(shù)。所以6是奇數(shù)。解：記p：6是偶數(shù)，q：7被2除盡，r：5是素數(shù)，則原推理過程符號化為：p→┐q，┐r?q，r?┐p

假定前提為1。則p→┐q，┐r?q，r都為1，知┐r為0。再由q為1知┐q為0，故p為0。于是，┐p為1。論證有效。注意：論證有效并不代表結(jié)論是客觀真實的，因為并不研究前提是否具有客觀真實性，僅假定其邏輯意義為真，從而進行形式上的推導(dǎo)。

1.7.1蘊含與論證(3)等值演算法利用等價變換說明條件式為永真式。例如，通過演算可推出((p→┐q)∧p)→┐q?1這說明((p→┐q)∧p)?┐q。(4)主析取范式法說明條件式的主析取范式包含所有的小項。例如，由((p→┐q)∧p)→┐q?Σ0,1,2,3?1同樣可說明((p→┐q)∧p)?┐q。注意：條件式是非對稱性的：(1)q→p：p→q的逆換式（逆命題）；(2)┐p→┐q：p→q的反換式（反命題）；(3)┐q→┐p：p→q的逆反式（逆否命題），且p→q?┐q→┐p。

1.7.1蘊含與論證3.等價與蘊含的關(guān)系[定理]對任意的命題公式

p和

q，p

q的充分必要條件是

p

q且

q

p。證明：p

q等同于p?q是永真式，等同于(p→q)?(q→p)是永真式，等同于p→q和q→p都是永真式，等同于p?q且q?p。[例1-22]設(shè)A、B、C是任意命題公式，證明：(1)若A?B且A是永真式，則B為永真式。(2)若A?B且B?C，則A?C。(3)若A?B且A?C，則A?(B?C)，A?(B?C)。(4)若A?C且B?C，則(A?B)?C。略證(4)：

由條件，A→C和B→C永真，┐A?C和┐B?C永真，(┐A?C)?(┐B?C)?(┐A?┐B)?C?(A?B)→C永真，結(jié)論成立。1.7.2自然推理系統(tǒng)

嚴格的論證過程可以采用自然推理系統(tǒng)或公理推理系統(tǒng)。自然推理系統(tǒng)是指不引入公理，僅確定一些推理規(guī)則，從前提出發(fā)，利用推理規(guī)則構(gòu)造出嚴格的命題序列，推導(dǎo)出最終的結(jié)論。稱為“自然推理”、“構(gòu)造證明法”、“演繹法”或“形式證明”。1.推理定律可以將基本等價關(guān)系和蘊含關(guān)系稱為推理定律，或稱前者為推理定律，后者為推理規(guī)則。

如果你有口令(p)，那么，你就能登錄網(wǎng)絡(luò)(q)。

你有了口令。

因此，你能登錄網(wǎng)絡(luò)?！遬→q

p

∴qp→q,p?q，

(p→q)?p?q

1.7.2自然推理系統(tǒng)序號蘊含關(guān)系含義I1p?q?p

化簡律I2p?q?q

I3p?p?q附加律I4q?p?qI5┐p?p→qI6q?p→qI7┐(p→q)?pI8

┐(p→q)?┐qI9p,q?p?q

I10┐p,p?q?q析取三段論序號蘊含關(guān)系含義I11p,p→q?q

假言推理I12┐q,p→q?┐p

拒取式I13p→q,q→r?p→r假言三段論I14p?q,q?r?p?r等價三段論I15p?q,p→r,q→r?rI16p→q?(p?r)→(q?r)I17p→q?(p?r)→(q?r)I18p→q,p→r?p→(q?r)I19p→q,p→r?p→(q?r)表1-8注意：肯定形式與否定形式同樣有效!

1.7.2自然推理系統(tǒng)2.利用推理定律實現(xiàn)形式證明

形式邏輯推理的本質(zhì)是說明一個蘊含關(guān)系，或者說，總是假定前提是真的，利用表1-5和1-8所示的基本等價和蘊含關(guān)系，說明結(jié)論也為真即告完成。這種推理就是“因為+所以”組成的步驟，只是每次的“所以”都要由推理定律來保證。

推理形式描述為以下2條規(guī)則：

(1)P規(guī)則：前提引入規(guī)則，指在證明的任何步驟都可引入前提；

(2)T規(guī)則：推理定律引用規(guī)則，指在證明中，如一個或幾個公式滿足推理定律，則其結(jié)論或等價公式可引入。

利用P（premise）規(guī)則和T（tautology）規(guī)則實現(xiàn)的證明方法稱為“直接證明法”。

1.7.2自然推理系統(tǒng)[例]已知a、b、c為實數(shù)，且a2-b2=bc，c≠0，證明a2/c=b(b/c+1)。證明：(1)∵a2-b2=bc

P前提

(2)∴(a2-b2)+b2=bc+b2

T推理定律：x=y?x+z=y+z

(3)∴a2+(-b2+b2)=b2+bc

T推理定律：(x+y)+z=x+(y+z)，x+y=y+x

(4)∴a2+0=b(b+c) T推理定律：x+(-x)=0，x(y+z)=xy+xz

(5)∴a2=b(b+c) T推理定律：x+0=x

(6)∵c≠0 P前提

(7)∴a2/c=b(b+c)/c

T推理定律：x=y?z≠0?x/z=y/z。

(8)∴a2/c=b(b/c+1) T推理定律：(x+y)/z=x/z+y/z，x/x=1

代之以說明采用的定律和原因!

1.7.2自然推理系統(tǒng)3.直接證法的形式推理證明示例[例1-24]證明(p?q)?(p→r)?(q→s)?s?r。證明：(1)p?q

P

∵(2)┐p→q

T(1)E∴(3)q→s

P

∵(4)┐p→s

T(2),(3)I∴(5)┐s→p

T(4)E∴(6)p→r

P

∵(7)┐s→r

T(5),(6)I∴(8)s?r

T(7)E∴存在問題的證法：(1)p→r

P(2)(p?q)→(r?q)

T(1)I(3)q→s

P(4)(q?r)→(s?r)

T(3)I(5)(p?q)→(s?r) T(2),(4)I(6)p?q

P(7)s?r

T(5),(6)I

1.7.2自然推理系統(tǒng)[例1-25]證明(p?q)→v,v→(r?s),s→u,┐r?┐u?┐p。證明：(1)┐r?┐u

P(2)┐u

T(1)I(3)s→u

P(4)┐s

T(2),(3