版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
11級專業(yè)選修課程授課人:王薇信息與計算教研室本教材離散數(shù)學知識結(jié)構(gòu)離散數(shù)學前言PowerPointTemplate_Sub
邏輯學是一門非常古老的學科,它是研究人類推理過程的科學。到現(xiàn)在已經(jīng)有了兩千多年的歷史。古典邏輯學主要起源于古希臘學者亞里士多德的邏輯學說,他創(chuàng)作的《工具論》一書是古代一部最完備的邏輯學著作。古典邏輯學的基本特點是用自然語言描述對邏輯的研究,而一旦超出這個范圍,引入數(shù)學的方法來研究邏輯,就產(chǎn)生了遠遠優(yōu)于古典邏輯學的現(xiàn)代邏輯學。
數(shù)理邏輯也稱符號邏輯,是現(xiàn)代邏輯學研究的主體部分,是一門運用數(shù)學方法研究思維規(guī)律的邊緣性學科。將推理變成數(shù)學演算,這是數(shù)理邏輯的指導思想,并且已經(jīng)成為這門學科的主要特征
。數(shù)理邏輯是用形式化(符號化)方法來研究推理的科學。*
命題邏輯研究命題和命題連接詞的邏輯結(jié)構(gòu)以及命題之間的推理關(guān)系。命題邏輯:推理的基本要素是命題.
引言
先看著名物理學家愛因斯坦出過的一道題:
一個土耳其商人想找一個十分聰明的助手協(xié)助他經(jīng)商,有兩人前來應聘,這個商人為了試試哪個人更聰明些,就把兩個人帶進一間漆黑的屋子里,他打開燈后說:“這張桌子上有五頂帽子,兩頂是紅色的,三頂是黑色的,現(xiàn)在,我把燈關(guān)掉,而且把帽子擺的位置弄亂,然后我們?nèi)齻€人每人摸一頂帽子戴在自己頭上,在我開燈后,請你們盡快說出自己頭上戴的帽子是什么顏色的。”說完后,商人將電燈關(guān)掉,然后三人都摸了一頂帽子戴在頭上,同時商人將余下的兩頂帽子藏了起來,接著把燈打開。這時,那兩個應試者看到商人頭上戴的是一頂紅帽子,其中一個人便喊道:“我戴的是黑帽子?!?/p>
請問這個人說得對嗎?他是怎么推導出來的呢?
要回答這樣的問題,實際上就是看由一些諸如“商人戴的是紅帽子”這樣的前提能否推出“猜出答案的應試者戴的是黑帽子”這樣的結(jié)論來。這又需要經(jīng)歷如下過程:
(1)什么是前提?有哪些前提?
(2)結(jié)論是什么?
(3)根據(jù)什么進行推理?
(4)怎么進行推理?學習命題邏輯將回答這幾個問題。-8-第9講命題與邏輯聯(lián)結(jié)詞PowerPointTemplate_Sub
1命題與邏輯聯(lián)結(jié)詞2邏輯等價式和邏輯蘊涵式3范式4證明技術(shù)(補充)命題與邏輯聯(lián)結(jié)詞《離散數(shù)學》第9講Page56to78-10-第9講命題與邏輯聯(lián)結(jié)詞內(nèi)容提要命題的概念命題、命題真值表示原子命題和復合命題、命題常元、命題變元邏輯聯(lián)結(jié)詞┐、∧、∨、→、
命題公式
公式的歸納定義指派自然語句的形式化-11-第9講命題與邏輯聯(lián)結(jié)詞命題(proposition或statement)命題:是一句有確定真假值的陳述句。命題只有兩個結(jié)果,或是真,或是假,但二者不能得兼(排中律),也不能不真又不假。真、假常被稱為命題的真值。
命題的真值
作為命題的陳述句所表達的判斷結(jié)果稱為命題的真值,
真值只有2個:真或假。用T,F或1,0表示。
當判斷正確或符合客觀實際時,稱該命題真(true),
否則稱該命題假(false)。任何命題的真值都是唯一的.判斷給定句子是否為命題的步驟:首先判定它是否為陳述句判斷它是否有唯一的真值.疑問句、祈使句、感嘆句和悖論等都不是命題。悖論:由真推出假又由假推出真的陳述句稱為悖論。即自相矛盾的句子。-14-第9講命題與邏輯聯(lián)結(jié)詞命題舉例雪是白的半徑為1的圓的周長為2π2是偶數(shù)且3也是偶數(shù)陳勝起義那天杭州下雨大于2的偶數(shù)均可以分解為兩個質(zhì)數(shù)的和數(shù)學多美啊!X+Y=4
“我正在說謊?!蔽抑唤o那些不給自己刮胡子的人刮胡子√T√T√F√√T××××-15-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題原子命題:一個不能再分解成更簡單語句的命題原子命題是最簡單的陳述句(1)雪是白的。(T)
(2)2+2=5(F)
(3)2是素數(shù)。(T)
(4)北京是中國的首都。(T)上述命題都是簡單陳述句,他們都不能分解為更簡單的陳述句了,稱這樣的命題為原子命題.-16-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題原子命題通常記為p、q、r等小寫字母,f表示恒假命題,t表示恒真命題。例:p:2000年4月5日是星期一。q:星期二的前一天是星期一。恒真
-17-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題命題常元和變元原子命題有確定的真值,又稱為命題常元。命題變元是指一個未確定真值的任意命題,其值在{0,1}上變化。例p:x+y=5不是命題,但x,y一旦確定,它的真值就確定了。這種真值可以變化的簡單陳述句稱為命題變元。命題變元也用p、q、r等小寫字母表示。-18-第9講命題與邏輯聯(lián)結(jié)詞原子命題和復合命題復合命題:相對于原子命題的是復合命題,它是由原子命題通過邏輯聯(lián)結(jié)詞進行適當?shù)慕M合而成的。復合命題的真值不僅依賴于這兩個組成它的命題,而且還依賴于這個聯(lián)結(jié)詞的意義。-19-第9講命題與邏輯聯(lián)結(jié)詞舉例p:3是素數(shù);q:3是偶數(shù)利用聯(lián)結(jié)詞“不”、“或”、“且”等可分別構(gòu)成新命題:“非p”:3不是素數(shù)“p或q”:3是素數(shù)或偶數(shù)“p并且q”:3是素數(shù)且是偶數(shù)帶連接詞的命題:1)并非2是無理數(shù)。(T)2)4是偶數(shù)且4也是素數(shù)。(F)3)2或4是素數(shù)。(T)4)如果角A和角B是對頂角,則角A=角B。(T)5)兩個三角形全等當且僅當它們的3組對應邊相等。(T)
這幾個命題的真值不僅依賴于這兩個組成它的命題,而且還依賴于這些聯(lián)結(jié)詞的意義。像這樣的聯(lián)結(jié)詞稱為邏輯聯(lián)結(jié)詞(logicalconnectives)。練習
所以復合命題是由若干個簡單命題和若干個連接詞構(gòu)成的。
下面我們將連接詞也符號化。-22-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞一.否定詞(negation):┐“┐P
表示P不成立”、“并非P”否定詞是一元運算。否定的是整個命題,并不是否定命題中個別的詞。“A和B都大于0”的否定:“A和B都不大于0”“A和B不都大于0”“A和B至少有一個不大于0”“A和B至少有一個小于等于0”“A大于0”的否定:“A不大于0”“A小于等于0”×-23-第9講命題與邏輯聯(lián)結(jié)詞常用的5個邏輯聯(lián)結(jié)詞真值表將復合命題的所有變元的所有取值列成表,就構(gòu)成真值表P┐P0110真值表*練習1:設(shè)P:今天是周三。則┐P表示什么?練習2:設(shè)Q:所有的自然數(shù)都是偶數(shù)。則┐Q表示什么?-25-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞二.合取詞(conjunction):∧
p∧q表示“p并且q”、“p和q都成立”合取詞是二元運算只有當p和q均為真時,p∧q才是真的,否則,p∧q是假的∧是可交換的pqp∧q000010100111p:今天是星期四;q:今天上離散數(shù)學課;p∧q:今天是星期四并且上離散數(shù)學課;*例1.
如果P表示命題“你去了學?!?Q表示命題“我去了工廠”,那么P∧Q表示命題”你去了學校并且我去了工廠“。
P∧Q為真,當且僅當你、我分別去了學校和工廠。注:使用合取聯(lián)結(jié)詞時,不要求兩命題間一定有任何關(guān)系。例2:P:今天下雨了。
Q:教室里有100把椅子。則,P∧Q:今天下雨了且教室里有100把椅子。離散數(shù)學
第一章:命題邏輯對∧的說明∧是二元連接詞P∧Q中的P,Q可以沒有內(nèi)在聯(lián)系(如例2)∧具有對稱性,P∧Q與Q∧P的真值相同P∧┐P=F∧可以把若干個命題連接在一起.如,
P∧Q∧R∧S
補充練習:
將下列命題符號化。
(1)吳穎既用功又聰明。
(2)吳穎不僅用功而且聰明。
(3)吳穎雖然聰明,但不用功。
(4)張輝和王麗都是三好學生。
(5)張輝與王麗是同學。
步驟:先找原子命題并符號化再找連接詞將原命題符號化解
:首先將原子命題符號化:
p:吳穎用功。,
q:吳穎聰明。
r:張輝是三好學生。
s:王麗是三好學生。
u
:張輝與王麗是同學。
則(1)到(4)分別符號化為
p∧q,p∧q,q∧┐p,r∧s.
(5)是原子命題,符號化為u.補充練習:將下列命題符號化。
(1)吳穎既用功又聰明。
(2)吳穎不僅用功而且聰明。
(3)吳穎雖然聰明,但不用功。
(4)張輝和王麗都是三好學生。
(5)張輝與王麗是同學。
(1)到(4)都是復合命題,它們使用的聯(lián)結(jié)詞表面看來各不相同,但都是合取聯(lián)結(jié)詞,都應符號化為∧,在(5)中,雖然也使用了聯(lián)結(jié)詞“與”,但這個聯(lián)結(jié)詞“與”是聯(lián)結(jié)該句主語的,而整個句子仍是簡單陳述句,所以(5)是原子命題,-30-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞析取詞(disjunction):∨
p∨q,“p成立或者q成立”、“p或q”析取詞是二元運算只有當p和q的真值均為假時,p∨q才是假的,否則,
p∨q總是真的pqp∨q000011101111p:我上午上離散數(shù)學;q:我上午上概率統(tǒng)計;p∨
q:我上午或者上離散數(shù)學,或者上概率統(tǒng)計;p:我上午一二節(jié)課上離散數(shù)學;q:我上午一二節(jié)課上概率統(tǒng)計;p∨
q:我上午一二節(jié)課要么上離散數(shù)學,要么上概率統(tǒng)計(不會上兩門);同或異或
總結(jié):析取∨一般代表漢語中的“或”,但漢語中的“或”是多含義的,見下表:或的含義例子說明可兼或晚會上她唱歌或跳舞二者均發(fā)生或二者之一發(fā)生排斥或
他上“師大”或“南開”非此即彼,不可兼得表示近似值的或他休息5或10分鐘近似數(shù),5至10分鐘由析取的定義可知,∨表示可兼或。例1:
如果p,q分別表示“今晚我看書”和“今晚我看電視”,那么p∨q表示“今晚我看書或者看電視”。當我今晚看了書,或者看了電視,或者既看了書又看了電視時,p∨q為真,只是在我既不看書也不看電視時p∨q為假。
值得注意的是,這里的“或”是所謂可兼的,即當p和q有一為真時,確認p∨q為真。則原命題可表示為:例2.一晚上他在家看書或出去散步。解:不可兼或
P:他一晚上在家看書。Q:他一晚上出去散步。
不可兼或也稱排斥或,它表示這一新命題當P為真且Q為假時成真,或反過來,當P為假且Q為真時成真。P和Q均為真或均為假時,這一命題為假。即當P和Q中恰有一個為真時它成真,否則它為假。對∨的說明∨是二元連接詞P∨Q中的P,Q可以沒有內(nèi)在聯(lián)系(如例2)∨具有對稱性,P∧Q與Q∧P的真值相同P∨┐P=T∨可以把若干個命題連接在一起.如,
P∨Q∨R∨S-35-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞蘊涵詞(implication):→
p→q,“如果p,那么q”、“p蘊涵q”、“p是q的充分條件”從真值表可以看出,只有當前提為真,而結(jié)論是假時,p→q才是假的pqp→q001011100111逆命題:q→p;否命題:┐p→┐q逆否命題:┐q→┐p命題和逆否命題有相同的真值(驗證一下)“如果今天是星期三,那么2+3=6”:前提為假,蘊涵命題為真;前提和結(jié)論之間可以沒有關(guān)系,稱為實質(zhì)蘊涵p:天晴;q:我爬山;只要天晴,我就爬山:
p→
q
只有天晴,我才爬山:q
→p
注意:在使用聯(lián)結(jié)詞→時,要特別注意以下幾點:
1.在自然語言中,“如果p,則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中,p與q可以無任何內(nèi)在聯(lián)系。
2.在數(shù)學或其它自然科學中,“如果p,則q”往往表達的是前件p為真,后件q也為真的推理關(guān)系。但在數(shù)理邏輯中,作為一種規(guī)定,當p為假時,無論q是真是假,p→q均為真。也就是說,只有p為真q為假這一種情況使得復合命題p→q為假。
例1
將命題“如果天氣好,那么我去接你?!狈柣?。解:設(shè)p表示“天氣好”,q表示“我去接你”,那么,p→q表示原命題。
當天氣好時,
我去接了你,這時諾言p→q真;
我沒去接你,則諾言p→q假。
當天氣不好時,我無論去或不去接你均未食言,此時認定p→q為真是適當?shù)摹?/p>
注:較三個聯(lián)結(jié)詞難理解,但若要對命題間因果關(guān)系進行表達,則必須引用。例2:令P:天氣好,Q:我去公園試將下列命題符號化1)若天氣好,我就去公園。符號化為:2)僅當天氣好,我才去公園。符號化為:-39-第9講命題與邏輯聯(lián)結(jié)詞常用5個邏輯聯(lián)結(jié)詞雙向蘊涵詞(two-wayimplication)pq,“p當且僅當q”、
“如果p,那么q;反之亦然”只有當p和q的真值相同時,pq才取真的真值pq與(p→q)∧(q→p)有完全相同的真值。(驗證一下)pqpq001010100111“只有你健康,你才會感到快樂;只有感覺快樂你才健康”*例1
如果p表示命題“△ABC△A‘B’C‘”,
q表示命題“△ABC與△A‘B’C‘的三邊對應相等”,那么pq表示平面幾何中的一個真命題,因為p真時q顯然真,p假時q亦必然假,故p與q同真值。若q表示命題“△ABC與△A‘B’C‘的三內(nèi)角對應相等”那么pq不再是恒真的了,因p假時q未必為假。離散數(shù)學
第一章:命題邏輯練習:
將下列命題符號化,并討論它們的真值。
(1)根號5是無理數(shù)當且僅當加拿大位于亞洲。
(2)2+3=5的充要條件是根號5是無理數(shù)。
(3)若兩圓A,B的面積相等,則它們的半徑相等;反之亦然。
(4)當王小紅心情愉快時,她就唱歌;反之,當她唱歌時,一定心情愉快。解
(1):令p:根號5是無理數(shù),真值為1,
q:加拿大位于亞洲,真值為0,
則將(1)符號化為pq,其真值為0.
(2):令r:2+3=5,其真值為1,則將(2)符號化為rp,真值為1.
(3):令s:兩圓A,B面積相等,
t:兩圓A,B的半徑相等,
則將(3)符號化為st,雖然不知道s,t的真值,但由s與t的內(nèi)在聯(lián)系可知,st的真值為1.
(4):令u:王小紅心情愉快,
v:王小紅唱歌,
則將(4)符號化為uv.其真值要由具體情況而定。練習:填空已知為T,則P為(),Q為()。已知為F,則P為(),Q為()。已知P為F,則為()。已知P為T,則為()。已知為T,且P為F,則Q為()。已知為F,則P為(),Q為()。已知P為F,則為()。已知Q為T,則為()。已知為F,則P為(),Q為()。已知P為T,為T,則Q為()。TTTTTFFFFFTTTT
以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞┐,∧,∨,→,,將它們組成一個集合{┐,∧,∨,→,
},稱為一個聯(lián)結(jié)詞集。其中┐為一元聯(lián)結(jié)詞,其余的都是二元聯(lián)結(jié)詞。
使用這些聯(lián)結(jié)詞有什么好處呢?可以將復雜命題表示成簡單的符號公式。注意:4個聯(lián)接詞構(gòu)成的復合命題均可不顧及命題間是否有內(nèi)在聯(lián)系,而只是根據(jù)聯(lián)接詞和原子命題的真值確定它們的真值。-45-第9講命題與邏輯聯(lián)結(jié)詞命題公式(propositionformula)命題公式:是一個表達式,它是由命題常元、命題變元、聯(lián)結(jié)詞符號和圓括號所組成的一個字符串
歸納定義:(看16頁歸納定義)命題常元和命題變元是命題公式,也稱為原子公式或原子如果A,B是命題公式,那么(┐A)、(A∧B)、
(A∨B)、(A→B)、(AB)也是命題公式只有有限步引用條款(1)、(2)所組成的符號串是命題公式-46-第9講命題與邏輯聯(lián)結(jié)詞簡寫約定為了減少圓括號的使用,我們約定:省掉最外面的括號聯(lián)結(jié)詞的優(yōu)先級從高到低是┐、(∧、∨)、→、結(jié)合能力平等的聯(lián)結(jié)詞從左到右運算((┐p)→(q∨((r∧q)s)))┐p→q∨(r∧qs)-47-第9講命題與邏輯聯(lián)結(jié)詞指派(assignment)設(shè)公式A含有n個命題變元p1,p2
,…,pn記為A(p1,…,pn)給定這n個變元任意一組確定的值(每一變元都有取真或假兩種可能),公式A得到一個確定的值(1或0),我們稱這一組確定的值為公式A的一組完全指派常用表示指派,若在某一指派下A取真的真值,則稱弄真A,記為
(A)=1,反之稱弄假A,記為
(A)=0
-48-第9講命題與邏輯聯(lián)結(jié)詞指派舉例使公式A:((p∧q)∨┐r)p為真的指派(A)=11.((p∧q)∨┐r)=1,
(p)=1,2.((p∧q)∨┐r)=0,
(p)=0(┐r)=0,(r)=11.1.(q)=11.1.1.(r)=01.1.2.(r)=11.2.(q)=01.2.1.(r)=02.1.(q)=02.2.(q)=1(1,1,0)(1,1,1)(1,0,0)(0,0,1)(0,1,1)-49-第9講命題與邏輯聯(lián)結(jié)詞復合命題公式的真值表首先確定在公式中出現(xiàn)的命題變元的個數(shù)。寫出公式A的所有指派,一個指派為一行,若有n個命題變元,則有2n組指派,也就是說真值表有2n+1行。確定公式中聯(lián)結(jié)詞的個數(shù),寫出單個聯(lián)結(jié)詞的真值,一般講,一個聯(lián)結(jié)詞對應著一列。
((p∧q)∨┐r)p的真值表pqrp∧q┐r(p∧q)∨┐r((p∧q)∨┐r)p00001100010001010011001100011000111101000011011111111011┐(PQ)0110原命題QP011111100000000000001111例2:上海到北京的14次列車是下午五點半開或六點開。復合命題的真值表
-51-第9講命題與邏輯聯(lián)結(jié)詞語句形式化舉例設(shè)p:a是偶數(shù)q:a是奇數(shù)r:a是質(zhì)數(shù)s:a=2,如何理解下述命題公式p∨q
p∧r→sp→(r→s)r∧┐s→q┐(q∨s)→┐rr→(q∨s)rq∨s-52-第9講命題與邏輯聯(lián)結(jié)詞語句形式化舉例我和他既是兄弟又是同學p∧q,其中:p:我和他是兄弟,q:我和他是同學我和他至少有一個要去外地p∨q,其中:p:我去外地,q:他去外地狗急跳墻p→q,其中:p:狗急了,q:狗跳墻除非他來,否則我不同他和解pq,(p→q)∧(┐p→┐q),其中:p:他來,q:我同他和解-53-第9講命題與邏
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 門窗簽約合同模板
- 傳承創(chuàng)新:DIY陶藝店的創(chuàng)業(yè)之旅
- 購物品合同模板
- 農(nóng)場異地建設(shè)合同模板
- 產(chǎn)地出租合同模板
- 一汽大眾新車銷售合同模板
- 土地耕種租賃合同模板
- 鏟車司機雇傭 合同模板
- 日產(chǎn)新車購車合同模板
- 建筑預算托管合同模板
- 四線制方向電路詳解
- 工行對賬單模版xls
- 維修確認單(共4頁)
- 河北中小學學籍管理
- 四年級數(shù)學上冊脫式計算100題
- 村鎮(zhèn)銀行防詐騙應急預案及處置流程
- 細胞標準化纖體資料終打印稿
- DB1310∕T 233-2020 地下管線數(shù)據(jù)規(guī)范
- 特種設(shè)備檢驗檢測人員執(zhí)業(yè)注冊管理辦法標準版
- 數(shù)字文化產(chǎn)業(yè)園項目可行性研究報告-完整可修改版
- 少先隊鼓號隊總譜0—10套
評論
0/150
提交評論