湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯_第1頁(yè)
湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯_第2頁(yè)
湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯_第3頁(yè)
湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯_第4頁(yè)
湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯_第5頁(yè)
已閱讀5頁(yè),還剩77頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯第一章命題邏輯引言邏輯學(xué)是推理的基礎(chǔ),在社會(huì)學(xué)、自然科學(xué)尤其計(jì)算機(jī)學(xué)科中得到普遍應(yīng)用。數(shù)理邏輯是邏輯學(xué)的一個(gè)分支,也是數(shù)學(xué)的分支,它用數(shù)學(xué)方法研究推理規(guī)律,它采用符號(hào)的方法來(lái)描述和處理思維形式、思維過(guò)程和思維規(guī)律,它在程序設(shè)計(jì)、數(shù)字電路設(shè)計(jì)、計(jì)算機(jī)原理、人工智能等計(jì)算機(jī)課程得到了廣泛應(yīng)用。命題邏輯是數(shù)理邏輯的基礎(chǔ)部分,但究竟什么是命題?如何表示命題?如何構(gòu)造出復(fù)雜的命題?在本章將討論這些問(wèn)題。1.1命題及聯(lián)結(jié)詞對(duì)錯(cuò)確定的陳述語(yǔ)句稱為命題。如:(1)湖南大學(xué)是一本學(xué)校。(2)命題邏輯是計(jì)算機(jī)科學(xué)的基礎(chǔ)課程。(3)命題及聯(lián)結(jié)詞是命題邏輯的最基礎(chǔ)的內(nèi)容。(4)4是素?cái)?shù)。(5)湖南大學(xué)坐落于湘江以東。(6)2011年湖南長(zhǎng)沙輕軌通車。其中(1)、(2)、(3)與事實(shí)相符,是對(duì)的、正確的,稱為真命題,或者稱命題的值為“真”,簡(jiǎn)記為T或數(shù)字1。而(4)、(5)明顯與事實(shí)不相符,是錯(cuò)的、不正確,稱為假命題,或稱命題的值為“假”,簡(jiǎn)記為F或數(shù)字0。陳述句(6)的正確性,到2011年12月時(shí)能確定的,若屆時(shí)開通了則它是對(duì)的、為真命題,否為假命題。1.1命題及聯(lián)結(jié)詞對(duì)錯(cuò)確定的陳述語(yǔ)句稱為命題。如:(7)x與y之和為100,其中x為整數(shù),y為整數(shù)(8)1加1等于10(7)的對(duì)錯(cuò)不確定的。當(dāng)x為50、y為50時(shí)是對(duì)的,當(dāng)x為51、y為52時(shí)是錯(cuò)的。(8)的對(duì)錯(cuò)是不確定的,為二進(jìn)制時(shí)正確,當(dāng)為八進(jìn)制、十進(jìn)制時(shí)是錯(cuò)的,因此這兩個(gè)陳述句不是命題。(9)岳麓山的紅葉真美呀!(10)動(dòng)作快點(diǎn)!(11)你是離散數(shù)學(xué)老師嗎?這三個(gè)語(yǔ)句不是陳述語(yǔ)句,因此不是命題。1.1命題及聯(lián)結(jié)詞對(duì)錯(cuò)確定的陳述語(yǔ)句稱為命題。如:(12)我在說(shuō)假話。(13)我只給自己不能理發(fā)的人理發(fā)。(14)派出所說(shuō):必須先房子再能上戶口單位后勤說(shuō):必須先有戶口才能分房你能上到戶口與要到房子嗎?這是一個(gè)悖論,其真值不能確定,故不是命題。1.1命題及聯(lián)結(jié)詞對(duì)錯(cuò)確定的陳述語(yǔ)句稱為命題。如:(13)我既要學(xué)程序設(shè)計(jì),又要學(xué)離散數(shù)學(xué)。(14)我們?cè)绮驮诠⑹程没蛲饷嬖琰c(diǎn)攤上吃。(15)我不是數(shù)學(xué)院的學(xué)生這三個(gè)陳述句都與事實(shí)相符,是對(duì)的,是真命題,其值為真(T/1)。其中(13)與(14)可分解為另外二句話的組合,而(15)是對(duì)“我是數(shù)學(xué)院學(xué)生”的否定,這些語(yǔ)句稱為“復(fù)合命題”,不能再分解的語(yǔ)句稱為“簡(jiǎn)單命題”或“原子命題”,為了便于推理與書寫,常用小寫字母表示簡(jiǎn)單命題或原子命題。1.1命題及聯(lián)結(jié)詞簡(jiǎn)單命題組合成復(fù)雜命題時(shí)所使用的輔助詞稱為“聯(lián)結(jié)詞”。命題邏輯中的聯(lián)結(jié)詞歸納為以下5種。合取:C語(yǔ)言中&&and并且析取:C語(yǔ)言中||or或否定:C語(yǔ)言中!not非,不是,否定條件式:C語(yǔ)言中if()如果…那么如p則q雙條件式:如p則q且如q則p,當(dāng)且僅當(dāng)1.1命題及聯(lián)結(jié)詞定義1.1合?。寒?dāng)p、q都對(duì),即取值為真(T或1)時(shí),“p合取q”的值為真.1.1命題及聯(lián)結(jié)詞定義1.1合?。寒?dāng)p、q都對(duì),即取值為真(T或1)時(shí),“p合取q”的值為真,其他情況為假。邏輯運(yùn)算符“合取”,與漢語(yǔ)中“并且、而且、同時(shí)”含義相當(dāng)1.1命題及聯(lián)結(jié)詞定義1.2析?。寒?dāng)p、q都不對(duì),即取值為假(F或0)時(shí),“p析取q”的值為假,其他情況為真。邏輯運(yùn)算符“析取”,與漢語(yǔ)中“或”含義相當(dāng),但有細(xì)微的區(qū)別1.1命題及聯(lián)結(jié)詞邏輯運(yùn)算符“析取”與漢語(yǔ)的“或”幾乎一致但有區(qū)別:(16)“講離散數(shù)學(xué)的老師是楊老師或劉老師”,可以表示為“講離散數(shù)學(xué)的老師是楊老師”“講離散數(shù)學(xué)的老師是劉老師”,這兩個(gè)原子命題有可能都是對(duì)的,這種“或”稱為“可同時(shí)為真的或”,或簡(jiǎn)稱為“可兼或”。(17)“離散數(shù)學(xué)的教室是102或302”,不可以表示為“離散數(shù)學(xué)的教室是102”“離散數(shù)學(xué)的教室是302”,因?yàn)檫@兩個(gè)原子命題不可能都對(duì),只能這二種情況之一,這種“或”稱為“不可同時(shí)為真的或”,或簡(jiǎn)稱為“不可兼或”、“排斥或”.這種“或”表示不能簡(jiǎn)單表示為“析取”,需要聯(lián)合使用下面將要介紹的“否定”與“析取”符號(hào),才能準(zhǔn)確表達(dá)。1.1命題及聯(lián)結(jié)詞定義1.3否定:當(dāng)p是1,p的否定p即為0。邏輯運(yùn)算符“否定”,與漢語(yǔ)中“否定”含義相當(dāng).“我不是數(shù)學(xué)院的學(xué)生”可表示為“我是數(shù)學(xué)院的學(xué)生”“離散數(shù)學(xué)的教室是102或302”,表示離散數(shù)學(xué)的教室是102不是302"或"離散數(shù)學(xué)的教室是302不是102"p:離散數(shù)學(xué)的教室是102q:離散數(shù)學(xué)的教室是302上面的語(yǔ)句表示:(pq)(pq)1.1命題及聯(lián)結(jié)詞定義1.4條件:當(dāng)p是1,q是0時(shí),pq為0,即10為0,其他情況為1。邏輯運(yùn)算符“如果…那么”,它是用單個(gè)運(yùn)算符表示一個(gè)復(fù)合語(yǔ)句。如老媽說(shuō):“如果期終考了年級(jí)前10名,那么獎(jiǎng)勵(lì)1000元”。p:期終考了年級(jí)前10名q:獎(jiǎng)勵(lì)1000元?jiǎng)t上面的語(yǔ)句表示為pq。當(dāng)p為1即“期終考了年級(jí)前10”,且q為0即“沒(méi)有獎(jiǎng)勵(lì)1000元”這時(shí)老媽的話是假話空話,故pq為01.1命題及聯(lián)結(jié)詞定義1.4條件式(蘊(yùn)含式):當(dāng)p是1,q是0時(shí),pq為0,即10為0,其他情況為1。p為前件,q為后件(1)當(dāng)p為1即“我期終考了年級(jí)前10”q為0即“我老媽沒(méi)有獎(jiǎng)勵(lì)1000元”這時(shí)老媽的話為假,即pq為0(2)當(dāng)p為1即“我期終考了年級(jí)前10”q為1即“我老媽獎(jiǎng)勵(lì)1000元”這時(shí)媽媽的話就對(duì)了,即pq為1(3)至于p為0即“我期終考了年級(jí)不是前10”時(shí),無(wú)論q為1或?yàn)?,即無(wú)論"我老媽獎(jiǎng)勵(lì)1000元"或不獎(jiǎng)勵(lì),都不能說(shuō)老媽的話是假的,故可善意的認(rèn)為pq為1均為11.1命題及聯(lián)結(jié)詞定義1.5雙條件:當(dāng)p與q值相同0時(shí),pq為1,不同為0。稱p與q的等價(jià)式“我明年賺了10萬(wàn)當(dāng)且僅當(dāng)我買彩票中了大獎(jiǎng)”,可以表示為“我明年賺了10萬(wàn)我買彩票中了大獎(jiǎng)”1.2公式及其賦值對(duì)錯(cuò)明確的陳述語(yǔ)句稱為命題,其真值確定,又稱為命題常元或命題常項(xiàng),相當(dāng)于初等數(shù)學(xué)中的“常數(shù)”。數(shù)學(xué)的運(yùn)算符號(hào)為“加+、減-、乘x、除、冪”,命題邏輯的符號(hào)“合取、析取、否定、條件、雙條件”數(shù)學(xué)中用變量x表示某些數(shù),如x2+x+10是代數(shù)式,命題邏輯用變量表示任意一個(gè)命題,如p,q,r,這時(shí)由符號(hào)與變量所構(gòu)成命題表達(dá)式,簡(jiǎn)稱為“命題公式”。代數(shù)式的書寫有規(guī)律,命題公式也有規(guī)律與約束,稱滿足這些規(guī)則的公式為“合式公式”,也稱為“命題公式”,簡(jiǎn)稱為“公式”。1.2公式及其賦值定義1.2.1合式公式的生成規(guī)則(1)單個(gè)命題變?cè)?、命題常元為合式公式(原子公式)。(2)若A是合式公式,則A、(A)也是合式公式。(3)若A、B是合式公式,則AB、AB、AB、AB是合式公式。(4)有限次使用(2)~(3)形成的字符串均為合式公式。如:(p1)q是合式公式。因?yàn)閜、1是合公式,則(p1)是合式公式,而r是合式公式,故(p1)q是合式公式。(p1)r不是合式公式。因?yàn)閜、1是合公式,則(p1)是合式公式,而r是合式公式,但(p1)r不是合法公式。1.2公式及其賦值

對(duì)于代數(shù)式x2+y+10,當(dāng)x與y的值不確定時(shí),該代數(shù)式的值是不確定的。對(duì)于公式(p1)q,由于p與q值不確定時(shí),公式(p1)q的值不確定,因而不是命題。只有當(dāng)p與q的值確定后,公式(p1)q的值才能確定,我們可能像表1.2到表1.5一樣,給出公式在各種情況下的取值,即得到這個(gè)公式的真值表。p與q每一種取值稱為p、q的一種解釋1.2公式及其賦值

公式(pq)、pq的真值表如下表。真值表的構(gòu)造方法:(1)命題變?cè)娜≈祻娜?開始,依次加1,直到全1,當(dāng)有n個(gè)變?cè)獣r(shí),則共有2n種不同的取值情況。(2)分步驟計(jì)算公式的值(3)見黑板上寫成真賦值:如pq為(0,0),(0,1),(1,1)成假賦值:如pq為(1,0)1.2公式及其賦值

公式(pq)(qp)、pq的真值表。無(wú)論p/q取何值,這兩個(gè)公式的值總相等。1.2公式及其賦值

公式(pq)、pq的真值表。無(wú)論p/q取何值,這兩個(gè)公式的值總相等。1.2公式及其賦值

公式pq、pq的真值表。無(wú)論p/q取何值,這兩個(gè)公式的值總相等。11.2公式及其賦值

公式pq、qp的真值表。無(wú)論p/q取何值,這兩個(gè)公式的值總相等,若前者稱為原命題,后者為逆否命題11.2公式及其賦值

公式p(qr)、(pq)(pr)的真值表。無(wú)論p/q取何值,這兩個(gè)公式的值,與前面各例不同,此表是將運(yùn)算結(jié)果寫在聯(lián)結(jié)詞的下方!1.3等值式一、復(fù)習(xí)由前節(jié)可知:pq與pq、qppq與(pq)(qp)、(pq)(pq)(pq)與pqp(qr)、(pq)(pr)的真值表完全一樣,稱為等值。定義設(shè)A、B是兩個(gè)合法的命題公式,無(wú)論其中的命題變?cè)『沃?,這兩個(gè)公式的總相等,稱為兩個(gè)公式等值,記為AB由定義及前節(jié)習(xí)題有:(1)pqpqqp 條件式的等值式(2)pq(pq)(qp)(pq)(pq)雙條件(3)pp 雙重否定律(4)ppppp 冪等律(5)pqqp,pqqp 交換律(6)p(qr)(pq)r 結(jié)合律p(qr)(pq)r(7)p(qr)(pq)(pr) 分配律p(qr)(pq)(pr)(8)p(pr)p 吸收律(多吃少)p(pr)p(9)(pq)pq 德摩律(pq)pq

將以上等值式中的變?cè)獡Q成合式公式仍等值!如:pqpq則有ABAB盡管A/B可能很復(fù)雜,但是公式值也只有0、1二種可能,公式A/B的組合只有0/0,0/1,1/0,1/1四種,如下表所示顯然有ABAB置換規(guī)則:當(dāng)將公式A中的子公式B換成C得到公式D后,若BC,那么AD。因?yàn)锳、D除了“A中B所在之處、D中C所在之處”外,其他地方均相同,而不同之處的B與C等值,所以公式A、公式D的真值表應(yīng)該完全他相同,故AD。當(dāng)將一個(gè)公式的局部進(jìn)行等值替換后,仍與原公式等值,這也是數(shù)學(xué)中最常見的方法,不斷對(duì)局部進(jìn)行等值替換的操作,稱為“等值演算”。利用該規(guī)則及前述的等值式,可進(jìn)行等值演算,從而推導(dǎo)出新的公式。求證(pq)r(pr)(qr)(pq)r(pq)r條件式的等值式(pq)r利用德摩律r(pq)交換律(rp)(rq)分配律(pr)(qr)交換律(pr)(qr)條件式等值式等值演算的基本套路(1)轉(zhuǎn)換:ABAB(2)恰當(dāng)轉(zhuǎn)換:AB(AB)(AB)(AB)(AB)確保公式只保留聯(lián)結(jié)詞(3)否定到底:A,(AB),(AB)(4)恰當(dāng)使用分配律、吸收律。

利用等值演算,判斷公式的類型((pq)p)q

((pq)p)q((pq)p)q(條件式的等值式)((pq)p)q(條件式的等值式)((pq)p)q(德摩律)((pq)p)q(德摩律)(pq)(pq)(結(jié)合律)(pq)(pq)(逆用德摩律)AA (A=(pq))1

稱為永真式或重言式,即利用等值演算,可以判斷公式的類型。利用等值演算判斷公式類型:(p(pq))r解:(p(pq))r(p(pq))r(條件式的等值式)((pp)q)r(結(jié)合律)(1q)r(析取的性質(zhì)即析取定義真值表)1r(析取的性質(zhì)即析取定義真值表)0r (否定的定義)0 (析取的性質(zhì)即析取定義真值表)

永假式或矛盾式。問(wèn)題:盡管有套路可行,但是隨意性還是比較大,能否有某種方式肯定能成功呢?1.4析取范式與合取范式文字:命題變項(xiàng)(變?cè)?及其否定稱為文字.如:p,q,r,p,q,r簡(jiǎn)單析取式:僅由有限個(gè)文字構(gòu)成的析取式.如:pq,pq,pq,pq,pqr簡(jiǎn)單合取式:僅由有限個(gè)文字構(gòu)成的合取式.如:pq,pq,pq,pq,pqr定理:簡(jiǎn)單析取式與簡(jiǎn)單合取式(1)一個(gè)簡(jiǎn)單析取式Ai是重言式含有某個(gè)命題變?cè)捌浞穸ㄊ?,如Ai=pp…(2)一個(gè)簡(jiǎn)單合取式Ai是矛盾式含有某個(gè)命題變?cè)捌浞穸ㄊ?,如Ai=pp…1.4析取范式與合取范式析取范式:由有限個(gè)簡(jiǎn)單合取式的析取構(gòu)成的命題公式稱為析取范式??傮w是析取式,每對(duì)括號(hào)內(nèi)是合取式A=(pq)(pr)合取范式:由有限個(gè)簡(jiǎn)單析取式的合取構(gòu)成的命題公式稱為合取范式??傮w是合取式,每對(duì)括號(hào)內(nèi)是析取式A=(pq)(pr)1.4析取范式與合取范式總體是析取式,每對(duì)括號(hào)內(nèi)是合取式A=(pq)(pr)析取范式總體是合取式,每對(duì)括號(hào)內(nèi)是析取式A=(pq)(pr)合取范式定理:析取范式與合取范式(1)一個(gè)析取范式A是矛盾式每個(gè)簡(jiǎn)單合取式是矛盾式。A=(pq)(pr)(2)一個(gè)合取范式A是重言式每個(gè)簡(jiǎn)單析取式是重言式。A=(pq)(pr)1.4析取范式與合取范式(1)轉(zhuǎn)換:ABAB(2)恰當(dāng)轉(zhuǎn)換:AB(AB)(AB)(AB)(AB)(3)否定到底:A,(AB),(AB)(4)適當(dāng)使用分配律:A(BC),A(BC).經(jīng)過(guò)第1步、第2步轉(zhuǎn)換后,公式中只有、、三種運(yùn)算符。經(jīng)過(guò)第3步后,從括號(hào)外深入到變?cè)那懊?,與變?cè)Y(jié)合成文文字,文字之間只有、。1.4析取范式與合取范式(1)轉(zhuǎn)換:ABAB(2)恰當(dāng)轉(zhuǎn)換:AB(AB)(AB)(AB)(AB)(3)否定到底:A,(AB),(AB)(4)適當(dāng)使用分配律:A(BC),A(BC).如果外層運(yùn)算符全部是,而內(nèi)層子公式全部是簡(jiǎn)單析取式,則已經(jīng)是合取范式。如果內(nèi)層某子公式形如A(BC),不是簡(jiǎn)單析取式,則轉(zhuǎn)換為(AB)(AC)。

1.4析取范式與合取范式(1)轉(zhuǎn)換:ABAB(2)恰當(dāng)轉(zhuǎn)換:AB(AB)(AB)(AB)(AB)(3)否定到底:A,(AB),(AB)(4)適當(dāng)使用分配律:A(BC),A(BC).如果外層運(yùn)算符全部是,而內(nèi)層子公式全部是簡(jiǎn)單合取式,則已經(jīng)是析取范式。如果內(nèi)層某子公式形如A(BC),不是簡(jiǎn)單合取式,則轉(zhuǎn)換為(AB)(AC)。因此有:(1)不是永假的命題公式,存在析取范式。(2)不是永真的命題公式,存在合取范式。

1.4析取范式與合取范式(1)轉(zhuǎn)換:ABAB(2)恰當(dāng)轉(zhuǎn)換:AB(AB)(AB)(AB)(AB)(3)否定到底:A,(AB),(AB)(4)適當(dāng)使用分配律:A(BC),A(BC).如析取式范式:(pq)r(pq)r((pq)r)((pq)r)(pr)(qr)(pqr)1.4析取范式與合取范式求(pq)r的析取范式、合取范式解:(1)求析取范式。即外層是,內(nèi)層是,所以轉(zhuǎn)換模式為AB(AB)(AB)(pq)r((pq)r)((pq)r)(整體為析取)((pq)r)((pq)r)(ABAB)((pq)r)((pq)r)(德摩律)((pr)(qr))((pq)r)(分配律)(pr)(qr)(pqr)(結(jié)合律)1.4析取范式與合取范式解:(1)求合取范式。所以轉(zhuǎn)換模式為AB(AB)(AB)(pq)r((pq)r)((pq)r)(整體為合取)((pq)r)((pq)r)(條件等價(jià)式)((pq)r)((pq)r)(德摩律)((pr)(qr))((pq)r)(分配律)(pr)(qr)(pqr)(結(jié)合律)

1.4析取范式與合取范式小項(xiàng):在含有n個(gè)變?cè)暮?jiǎn)單合取式中,每個(gè)命題變?cè)蚱浞穸▋H出現(xiàn)一次,且各變?cè)雌渥帜疙樞虺霈F(xiàn),則該簡(jiǎn)單合取式為(極)小項(xiàng)。如:pqr,pqr,pqr,pqr(pr),(qr)非小項(xiàng)大項(xiàng):在含有n個(gè)變?cè)暮?jiǎn)單析取式中,每個(gè)命題變?cè)蚱浞穸▋H出現(xiàn)一次,且各變?cè)雌渥帜疙樞虺霈F(xiàn),則該簡(jiǎn)單析取式為(極)大項(xiàng)。如:pqr,pqr,pqr,pqr(pr),(qr)非大項(xiàng)1.4析取范式與合取范式主析取范式:一個(gè)析取范式中,如果所有簡(jiǎn)單合取式均為(極)小項(xiàng),則稱為主析取范式。(pq)r(pr)(qr)(pqr)不是(pqr)(pqr)(pqr)(pqr) 是主析取范式 1.4析取范式與合取范式主合取范式:一個(gè)合取范式中,如果所有簡(jiǎn)單析取式均為(極)大項(xiàng),則稱為主合取范式。(pq)r(pr)(qr)(pqr)不是(pqr)(pqr)(pqr)(pqr)是主合取范式

1.4析取范式與合取范式—獲取方法通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞、“到底”及適當(dāng)使用分配律,可以得到合取范式與析取范式,這時(shí)可能還缺少某個(gè)變?cè)?,因?yàn)閜p1,1r1,可在缺少變?cè)男№?xiàng)中加入形如“pp”的公式。如小項(xiàng)(pr)缺少變?cè)猶,加入qq,即prp1rp(qq)r(pqr)(pqr)。

1.4析取范式與合取范式—獲取方法通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞、“到底”及適當(dāng)使用分配律,可以得到合取范式與析取范式,這時(shí)可能還缺少某個(gè)變?cè)驗(yàn)閜p1,1r1,可在缺少變?cè)男№?xiàng)中加入形如“pp”的公式。(pq)r(pr)(qr)(pqr)(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)1.4析取范式與合取范式—獲取方法通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞、“到底”及適當(dāng)使用分配律,可以得到合取范式與析取范式,這時(shí)可能還缺少某個(gè)變?cè)?,因?yàn)閜p0,0pp,可在缺少變?cè)拇箜?xiàng)中加入形如“pp”的公式。如prp0rp(qq)r(pqr)(pqr)

1.4析取范式與合取范式—獲取方法通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞、“到底”及適當(dāng)使用分配律,可以得到合取范式與析取范式,這時(shí)可能還缺少某個(gè)變?cè)驗(yàn)閜p0,0pp,可在缺少變?cè)拇箜?xiàng)中加入形如“pp”的公式。

(pq)r(pr)(qr)(pqr)(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)1.4析取范式與合取范式

當(dāng)一個(gè)公式比較復(fù)雜時(shí),得到其析取范式、合取范式的演算量比較大,再將簡(jiǎn)單析取式轉(zhuǎn)換為大項(xiàng),或簡(jiǎn)單合取式轉(zhuǎn)換為小項(xiàng),又需要進(jìn)一步演算,能否直接基于原公式,不進(jìn)行等值演算直接得到,或者能按某種統(tǒng)一的方式得到其主析取范式、主合取范式呢?通過(guò)真值表可以實(shí)現(xiàn)!為此先研究小項(xiàng)與大項(xiàng)的性質(zhì)。1.4析取范式與合取范式通過(guò)真值表可以實(shí)現(xiàn)!為此先研究小項(xiàng)與大項(xiàng)的性質(zhì),下表是各小項(xiàng)的真值表。1.3個(gè)變?cè)男№?xiàng)共有8個(gè),它們各不相同。2.從每一行來(lái)看,命題變?cè)拿總€(gè)指派中,只有一個(gè)小項(xiàng)的值為1。3.從每一列來(lái)看,每個(gè)小項(xiàng)僅在一個(gè)指派中值為1,其余7種指派中均為0。

4.小項(xiàng)值為1(如pqr=1)時(shí),p,q,r均為1,即(p,q,r)=(0,0,0),取該值為小項(xiàng)編號(hào),如最后一行。(5)根據(jù)小項(xiàng)的編號(hào),可寫出小項(xiàng)的具體形式。如小項(xiàng)m101,其編號(hào)為101,表示(p,q,r)=(1,0,1)時(shí)該小項(xiàng)的值為1,而小項(xiàng)是文字的合取,故小項(xiàng)的各個(gè)文字必須為1,則文字只能是p、q、r,故該小項(xiàng)為pqr。規(guī)則:1對(duì)應(yīng)變?cè)旧?如p),0對(duì)應(yīng)其否定(如p)。如m00為pq、m01為pq、m10為pq、m11為pq。很重要!(1)三個(gè)變?cè)拇箜?xiàng)共有8個(gè)。(2)每一行:每個(gè)指派中,只有一個(gè)大項(xiàng)的值為0。(3)每一列:每個(gè)大項(xiàng)僅在一個(gè)指派下值為0。(4)大項(xiàng)值為0(如pqr=0)時(shí),p、q、r均為0,則(p,q,r)=(1,1,1),將其記為大項(xiàng)編號(hào),如表最后行。(5)根據(jù)大項(xiàng)的編號(hào),可寫出大項(xiàng)的具體形式。如大項(xiàng)M101,其編號(hào)為101,表示(p,q,r)=(1,0,1)時(shí)該大項(xiàng)的值為0,而大項(xiàng)是文字的析取,故各個(gè)文字必須為0,文字只能是p、q、r,故該大項(xiàng)為pqr。規(guī)則:1對(duì)應(yīng)變?cè)姆穸?如p),0對(duì)應(yīng)變?cè)?如p)如M00為pq,M01為pq,M10為pq,M11為pq。1.4析取范式與合取范式—獲取方法1、先轉(zhuǎn)換析取式或合取式,再合取1或析取0。2、先建立真值表,取出所有成真賦值對(duì)應(yīng)的小項(xiàng),析取所有小項(xiàng)得主析取范式。小項(xiàng)與成真賦值對(duì)應(yīng)。取出所有成假賦值對(duì)應(yīng)的大項(xiàng),合取所有大項(xiàng)得主合取范式。大項(xiàng)與成假賦值對(duì)應(yīng)。如用真值表求主范式:(pq)r,pq,pq,(pq)q,p(pq)(pq)r的主析取范式、主合取范式

主析取范式公式值為1的指派對(duì)應(yīng)小項(xiàng)的析取m001m011m100m1111變?cè)?0變?cè)穸?使小項(xiàng)=1(pqr)(pqr)(pqr)(pqr)

(pq)r的主析取范式、主合取范式

主合取式范式公式值為0的指派對(duì)應(yīng)大項(xiàng)的合取M000M010M101M110

1變?cè)穸?變?cè)?使大項(xiàng)=0(pqr)(pqr)(pqr)(pqr)

(pq)r、與其主析取范式、主合取范式的真值完全一樣,說(shuō)明三者互相等值,一般情況下有如下定理:(1)不是永假的命題公式,有等值的主析取范式。(2)不是永真的命題公式,有等值的主合取范式。由于永假?zèng)]有取值為1的解釋,故無(wú)相應(yīng)小項(xiàng),故沒(méi)有主析取范式。永真無(wú)取值為0的解釋,故沒(méi)有主合取范式.設(shè)計(jì)一個(gè)電子評(píng)分系統(tǒng),3位專家打分,如果有2位以上專家打分為“通過(guò)”,則總成績(jī)?yōu)椤巴ㄟ^(guò)”。對(duì)應(yīng)的主析取范式值為1的指派對(duì)應(yīng)的小項(xiàng)的析取m011m101m110m111(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)((x1x2x3)(x1x2x3))((x1x2x3)(x1x2x3))(((x1x2)(x1x2))x3)(((x1x2(x3x3)))(((x1x2)(x1x2))x3)(x1x2)((x1x2)(x1x2)x3)(x1x2)與非或門表示

某公司要從曹、喬、宋、黎、鄒5人中,選擇一些人承包一項(xiàng)工程,考慮到人與人組合優(yōu)化的問(wèn)題,需滿足如下約束條件:(1)如果曹去,那么喬也去;(2)黎、鄒兩人中必有一人去;(3)喬、宋兩人中去且僅去一人;(4)宋、黎兩人同去或同時(shí)不去;(5)若鄒去,則曹、喬也同去;解:用小寫字母表示:c:曹去,q:?jiǎn)倘:宋去l:黎去z:鄒去時(shí),以上5句話可表示為如下的公式:(cq)、(lz)、((qs)(qs))、(sl)、(z(qc)),5句話同時(shí)成立即每句話的值均為1,也即其合取式(cq)(lz)((qs)(qs))(sl)(z(qc))為1

(cq)(lz)((qs)(qs))(sl)(z(qc))

(cq)(lz)((qs)(qs))((sl)(sl))(z(qc))(cq)(lz)(z(qc))((qssl)(qssl)(qssl)(qssl))(cq)(lz)(z(qc))((qsl)(qsl))

(cq)(lz)((zqsl)(zqsl)(qcsl))(cq)((zqsl)(zqcsl))(czqsl)(zqcsl)因(cq)(lz)((qs)(qs))(sl)(z(qc))為1,故1(czqsl)(zqcsl),故1(czqsl)或1(zqcsl)故方案一是:曹不去、鄒不去、喬不去,宋與黎去。方案二是:曹去、喬去、鄒去,宋與黎均不去在某班班委的選舉中,該班的甲、乙、丙學(xué)生預(yù)言:甲說(shuō):王娟為班長(zhǎng)、劉強(qiáng)為生活委員;乙說(shuō):金鑫為班長(zhǎng)、王娟為生活委員;丙說(shuō):劉強(qiáng)為班長(zhǎng)、王娟為學(xué)習(xí)委員;結(jié)果公布后,發(fā)現(xiàn)甲、乙、丙三人都恰好對(duì)了一半,請(qǐng)問(wèn)王娟、劉強(qiáng)、金鑫各任何職?解:p1,q1,r1:表示王娟,劉強(qiáng),金鑫是班長(zhǎng);p2,q2,r2:分別表示王娟,劉強(qiáng),金鑫是學(xué)習(xí)委員;p3,q3,r3:分別表示王娟,劉強(qiáng),金鑫是生活委員;“每個(gè)人說(shuō)法對(duì)一半”將是一個(gè)非常復(fù)雜的公式(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2),要構(gòu)造這9個(gè)變?cè)恼嬷当?,將需?9=512行,工作量實(shí)在太大了,!參考“真值表”,設(shè)計(jì)如下的判斷表1.6推理理論從已知條件、假設(shè)、前提或公理出發(fā),根據(jù)推理規(guī)則推出結(jié)論、定理的過(guò)程,稱為推理。定義1設(shè)A與C是兩個(gè)命題公式,若AC為永真式(重言式),則稱C是A的有效結(jié)論,或稱A可以邏輯推出C,記為AC.由“”的定義可知,當(dāng)A為假時(shí),AC肯定為真,故只要考慮A為真時(shí)C是否為真即可,故有:定義2設(shè)A與C是兩個(gè)命題公式,若當(dāng)A為真時(shí)C也為真,則稱C是A的有效結(jié)論,或稱A可以邏輯推出C,記為AC。一般情況下,利用定義2去證明要簡(jiǎn)單些,我們?cè)谄渌麑W(xué)科中遇到的證明都是基于定義2的。判斷AC為永真可用等值演算、真值表等方法例題求證:A

(A

B)

B

(A

(A

B))

B

(A

(A

B))

B (

的等值式)

(A

(

A

B))

B (

的等值式)

((A

A)

(A

B))

B (分配律)

(0

(A

B))

B (合取的性質(zhì))

(A

B)

B (析取的性質(zhì))

(

A

B)

B (德摩律)

A

(

B

B) (結(jié)合律)

A

1 (析取的性質(zhì))

1 (析取的性質(zhì))所以(A

(A

B))

B是重言式,真值表也證永真所以A

(A

B)

B。這是有名的“假言推理(modusponens)”,或“分離原則”

假如我今年進(jìn)入年級(jí)前10名老爸給我買iphone4;期末考試后我為年級(jí)第8名,所以老爸應(yīng)該給我買iphone4。這是假言推理。A

(A

B)

B從形式上看,結(jié)論B是A

B的后件,推導(dǎo)的結(jié)果是將后件分離出來(lái),故也稱為分離原則。利用假言推理規(guī)則或分離規(guī)則,結(jié)合析取、合取、否定的定義,只要不歉麻煩,幾乎可推出所有的結(jié)論。為了提高推理效率,還需要學(xué)習(xí)、掌握某些推理規(guī)則。

例題求證A

A

B

采用定義1來(lái)證明,即證明A

A

B為永真式。 A

A

B

A

(A

B)(

的等值式)

(

A

A)

B(結(jié)合律)

1

B(析取的性質(zhì))

1(析取的性質(zhì)) 所以A

A

B

例題求證A

B

AA

B

A

(A

B)

A(

的等值式)

(

A

B)

A(德摩律)

A

B

A(結(jié)合律)

1

B(析取的性質(zhì))

1(析取的性質(zhì))

類似A

B

B根據(jù)的定義可知A

B為真時(shí),A與B均為真,因此由推理定義2可知A

B

A,A

B

B。

同樣由的定義可知A為真時(shí)A

B為真,故由推理定義2可知A

A

B。然這3個(gè)推理式不必記憶!推理定義2效率較高

例題求證(A

B)

(B

C)

(A

C)

根據(jù)定義1,要證明下式為永真式。

(AB)(BC)(AC)((AB)(BC))(AC) (的等值式)((AB)(BC))(AC) (的等值式)((AB)(BC))(AC) (德摩律)((AB)(AC)(BB)(BC))(AC)(分配律)((AB)(AC)1(BC))(AC) (析取的性質(zhì))((AB)(AC)(BC))(AC) (析取的性質(zhì))(ABAC)(ACAC)(BCAC)(分配律)(1BC)(1CC)(BA1) (析取的性質(zhì))111 (析取的性質(zhì))1 (析取的性質(zhì))判斷公式的類型,除等值演算外,還有真值表與范式等方法。

例題求證(A

B)

(B

C)

(A

C)

由上表可知,(A

B)

(B

C)

(A

C)為重言式,由定義1可知(A

B)

(B

C)

(A

C)。這是有名的傳遞律,要記住呀!

例題求證(AB)(CD)(AC)BD利用定義1證明了假言推理規(guī)則(AB)AB,傳遞規(guī)則(A

B)

(B

C)

(A

C)。

有了這2條規(guī)則后,可用定義2來(lái)證明推理式了。由于這2條規(guī)則的結(jié)論中沒(méi)有析取式,只有條件式,因此將題中結(jié)論

轉(zhuǎn)換為

BD,題設(shè)中轉(zhuǎn)換為

(1)(AB)(CD)(AC)為真 前提條件(定義2的套路)(2)(AB)為真 (1)及合取的性質(zhì)(3)(CD)為真 (1)及合取的性質(zhì)(4)(AC)為真 (1)及合取的性質(zhì)(5)(BA)為真 (2)及(AB)(BA)(6)(AC)為真 (4)及(AC)(AC)(7)(BC)為真 (5)、(6)及推理傳遞律(8)(BD)為真 (7)、(3)及推理傳遞律(9)BD為真 (8)及(BD)BD

例題求證(AB)(CD)(BD)AC可用傳遞律來(lái)證明,還有更高效的方法由定義1只要證((AB)(CD)(BD))(AC)為重言式,而((AB)(CD)(BD))(AC)((AB)(CD)(BD))(AC)(((AB)(CD)(BD))A)C)((AB)(CD)(BD))A)C)((AB)(CD)(BD))A)C故只需證((AB)(CD)(BD))A)C為重言式即只需證明(AB)(CD)(BD))AC

A從結(jié)論中挪到前提中,這種技巧稱為附加條件(CP)法,適合于結(jié)論為條件式的情形。

例題求證(AB)(CD)(BD)AC(1)(AB)(CD)(BD)A為真CP規(guī)則及前提(2)AB為真 (1)及合取的性質(zhì)(3)A為真 (1)及合取的性質(zhì)(4)B為真 (2)(3)及假言推理式(AB)AB(5)BD為真 (1)及合取的性質(zhì)(6)BD為真 (5)及BDBD(7)D為真 (4)(6)及假言推理式(BD)BD(8)CD為真 (1)及合取的性質(zhì)(9)DC為真 (8)及原命題逆否命題(10)C為真 (7)(9)假言推理式(DC)DC提示:熟練后可不寫(1)式,直接引用(2)(3)(5)(8)!

例題求證(AB)(CD)(BD)AC(1)AB為真 前提條件(2)A為真 附加前提(3)B為真 (1)(2)及假言推理式(AB)AB(4)BD為真 前提條件(5)BD為真 (4)及BDBD(6)D為真 (3)(5)及假言推理式(BD)BD(7)CD為真 前提條件(8)DC為真 (7)及原命題逆否命題(9)C為真 (6)(8)假言推理式(DC)DC

求證

(WR)V,V(CS),SU,C,UW

提示:此處用逗號(hào)簡(jiǎn)寫前述各例中的合取式,從而鼓勵(lì)大家直接引用前提。利用假言推理、傳遞律及前面所學(xué)的等值式,可以推出結(jié)論。在黑板上演示一番考慮到本題的結(jié)論是W,可采用反證法。根據(jù)定義2可知“當(dāng)前提為真時(shí)結(jié)論也為真”,反證法是“前提為真時(shí),假設(shè)結(jié)論不為真即結(jié)論的否定為真”。即基于前提、結(jié)論否定進(jìn)行推理。如果推出了一個(gè)矛盾的結(jié)論出來(lái),則說(shuō)明“假設(shè)結(jié)論不為真”是錯(cuò)誤的,即表示結(jié)論只能為真了

求證

(WR)V,V(CS),SU,C,UW

(1)W為真

假設(shè)結(jié)論W為0即W為1(真)(2)W為真

(1)與否定的性質(zhì)(3)(WR)為真

(2)與析取的性質(zhì)(4)(WR)V為真

前提條件(5)V為真

(4)(3)假言推理((WR)V)(WR)V(6)V(CS)為真

前提條件(7)(CS)為真

(5)(6)假言推理(V(CS))V(CS)(8)CS為真

(7)與條件式的等值式CSCS(9)C為真

前提條件(10)S為真

(8)(9)與假言推理(CS)(C)S(11)SU為真

前提條件(12)U為真

(10)(11)假言推理(SU)SU(13)U為真

前提條件顯然(12)與(13)矛盾,故假設(shè)有誤!

應(yīng)用題天氣情況要么天晴,要么天下雨;如果天晴我去爬山,如果我去爬山那么我回來(lái)后不做飯,結(jié)論是:如果我已做飯那么肯定天下雨了。解:用M表示天晴,R表示天下雨,C表示爬山,F(xiàn)表示做飯,則問(wèn)題可表示為MR,MC,CFFR(MR)(MR),MC,CFFR

應(yīng)用題MR,MC,CFFR(1)F為真 附件前提(2)CF為真 前提條件(3)FC為真 (2)的等值式(4)FC為真 (3)的等值式(5)C

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論