版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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是什么范式?
注意:
否定只能作用在原子前,絕不能置于括號前![等價演算的范式轉(zhuǎn)換方法](1)聯(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 陜西省2017年中考歷史真題試卷(含答案)
- 2024-2025學(xué)年版塊5 透鏡 專題5-1 透鏡類型判斷 (含答案) 初中物理尖子生自主招生培優(yōu)講義83講
- 出租合住單間合同模板
- 交通標牌案例合同模板
- 多方簽約合同模板
- 招聘高管合同模板
- 生活設(shè)備租賃合同模板
- 公司給個人傭金合同模板
- 小廠平房出售合同模板
- 裝修合同賠償返工合同模板
- 初中生物中考復(fù)習策略與方法交流課件
- 藥品電子監(jiān)管碼賦碼系統(tǒng)操作規(guī)程
- 實驗心理學(xué)速度知覺
- 《沉淀溶解平衡》說課課件(全國優(yōu)質(zhì)課獲獎案例)
- 中藥飲片生產(chǎn)設(shè)備清潔驗證報告
- 浙江省溫州市各縣區(qū)鄉(xiāng)鎮(zhèn)行政村村莊村名居民村民委員會明細及行政區(qū)劃代碼
- 知法守法依法維權(quán)課件
- 小學(xué)英語人教PEP新版六年級上冊Unit3B-Let-s-learn課件
- 維修工具管理新版制度
- 幼兒園《保護牙齒》課件
- 信息技術(shù)與教育教學(xué)融合課評價表
評論
0/150
提交評論