第五章推理與證明技術(shù)_第1頁
第五章推理與證明技術(shù)_第2頁
第五章推理與證明技術(shù)_第3頁
第五章推理與證明技術(shù)_第4頁
第五章推理與證明技術(shù)_第5頁
已閱讀5頁,還剩76頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡介

離散數(shù)學(xué)15十二月20232023/12/15第5章推理與證明技術(shù)命題邏輯的推理理論

1謂詞邏輯的推理理論

22023/12/155.1本章學(xué)習(xí)要求1掌握各種不同類型的規(guī)則和公理,特別是命題邏輯和謂詞邏輯的推理規(guī)則和公理3理解謂詞邏輯的精髓,將其思想貫穿于所有的證明之中

2熟練掌握不同證明方法的證明原理、不同的應(yīng)用場景

重點(diǎn)掌握一般掌握了解2023/12/155.2命題邏輯的推理理論概念描述問題的句子;AddYourText判斷對(duì)概念的肯定與否定的判斷;推理從一個(gè)或多個(gè)前提推出結(jié)論的思維過程。 命題演算的一個(gè)主要任務(wù)在于提供一種正確的思維規(guī)律,即推理規(guī)則,應(yīng)用此規(guī)則從一些前提中推導(dǎo)出一個(gè)結(jié)論來,這種推導(dǎo)過程稱為演繹或形式證明。2023/12/15推理的有效性和結(jié)論的真實(shí)性有效的推理不一定產(chǎn)生真實(shí)的結(jié)論;而產(chǎn)生真實(shí)結(jié)論的推理過程未必是有效的。有效的推理中可能包含為“假”的前提,而無效的推理卻可能得到為“真”的結(jié)論。2023/12/15推理的有效性和結(jié)論的真實(shí)性所謂推理有效,指的是它的結(jié)論是它前提的合乎邏輯的結(jié)果。即,如果它的前提都為真,那么所得的結(jié)論也必然為真,而并不是要求前提或結(jié)論一定為真或?yàn)榧?;如果推理是有效的話,那么不可能它的前提都為真時(shí),而它的結(jié)論為假。2023/12/155.2.1推理的基本概念和推理形式定義5.2.1

設(shè)G1,G2,…,Gn,H是公式,稱H是G1,G2,…,Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊(yùn)涵H),當(dāng)且僅當(dāng)H是G1∧G2∧…∧Gn的邏輯結(jié)果(logicconclusion)。記為G1,G2,…,Gn

H,此時(shí)稱G1,G2,…,Gn

H為有效的(efficacious),否則稱為無效的(inefficacious)。G1,G2,…,Gn稱為一組前提(Premise),有時(shí)用集合Г來表示,記Г={G1,G2,…,Gn}。H稱為結(jié)論(conclusion)。又稱H是前提集合的邏輯結(jié)果。記為Г

H。2023/12/15判定定理定理5.2.1

公式H是前提集合Г={G1,G2,…,Gn}的邏輯結(jié)果當(dāng)且僅當(dāng)G1∧G2∧…∧Gn→H為永真公式。證明:“

”若G1,G2,…,Gn

H,但G1∧G2∧…∧Gn→H不是永真式。于是,必存在G1,G2,…,Gn,H的一個(gè)解釋I,使得G1∧G2∧…∧Gn為真,而H為假,因此對(duì)于該解釋I,有G1,G2,…,Gn都為真,而H為假,這就與推理形式G1,G2,…,Gn

H是有效的相矛盾,故:G1∧G2∧…∧Gn→H是永真公式。2023/12/15判定定理(續(xù))

”若G1∧G2∧…∧Gn→H是永真式,但G1,G2,…,Gn

H不是有效的推理形式,故存在G1,G2,…,Gn,H的一個(gè)解釋I,使得G1,G2,…,Gn都為真,而H為假,故G1∧G2∧…∧Gn為真,而H為假,即是說G1∧G2∧…∧Gn→H為假,這就與G1∧G2∧…∧Gn→H是永真式相矛盾,所以G1,G2,…,Gn

H是有效的推理形式。2023/12/15“

”與“→”的不同1.“→”僅是一般的蘊(yùn)涵聯(lián)結(jié)詞,G→H的結(jié)果仍是一個(gè)公式,而“

”卻描述了兩個(gè)公式G,H之間的一種邏輯蘊(yùn)涵關(guān)系,G

H的“結(jié)果”,是非命題公式;2.

用計(jì)算機(jī)來判斷G

H是辦不到的。然而計(jì)算機(jī)卻可“計(jì)算”公式G→H是否為永真公式。2023/12/155.2.2判斷有效結(jié)論的常用方法要求Г={G1,G2,…,Gn}Г

H也就是G1∧G2∧…∧Gn→H為永真公式因而真值表技術(shù)、演繹法和間接證明方法2023/12/151、真值表技術(shù)設(shè)P1,P2,…,Pn是出現(xiàn)在前提G1,G2,…,Gn和結(jié)論H中的一切命題變元,如果將P1,P2,…,Pn中所有可能的解釋及G1,G2,…,Gn,H的對(duì)應(yīng)真值結(jié)果都列在一個(gè)表中,根據(jù)“→”的定義,則有判斷方法如下:對(duì)所有G1,G2,…,Gn都具有真值T的行(表示前提為真的行),如果在每一個(gè)這樣的行中,H也具有真值T,則H是G1,G2,…,Gn的邏輯結(jié)果。對(duì)所有H具有真值為F的行(表示結(jié)論為假的行),如果在每一個(gè)這樣的行中,G1,G2,…,Gn中至少有一個(gè)公式的真值為F(前提也為假),則H是G1,G2,…,Gn的邏輯結(jié)果.2023/12/15例5.2.1判斷下列H是否是前提G1,G2的邏輯結(jié)果(1)

H:Q; G1:P;G2:P→Q;(2)

H:┐P; G1:P→Q;G2:┐Q;(3)

H:Q; G1:┐P;G2:P→Q。解PQG1G2H00010010111010011111(1)PQG1G2H00111011011001011100(2)PQG1G2H00110011111000011011(3)2023/12/152推理定律設(shè)G,H,I,J是任意的命題公式,則有:I1:G∧H

G

(簡化規(guī)則)I2:G∧H

HI3:G

G∨H

(添加規(guī)則)I4:H

G∨HI5:┐G

G→HI6:H

G→HI7:┐(G→H)

GI8:┐(G→H)

┐HI9:G,H

G∧H2023/12/152推理定律(續(xù))6)I10:┐G,G∨H

H

(選言三段論)I11:┐G,GH

H

7)I12:G,G→H

H

(分離規(guī)則)8)I13:┐H,G→H

┐G

(否定后件式)9)I14:G→H,H→I

G→I

(假言三段論)10)I15:G∨H,G→I,H→I

I

(二難推論)2023/12/15例子1)、前提:

1.如果明天天晴,我們準(zhǔn)備外出旅游。

P→Q

2.明天的確天晴。

P

結(jié)論:我們外出旅游。

Q可描述為:P→Q,P

Q

(分離規(guī)則)2)、前提:

1.如果一個(gè)人是單身漢,則他不幸福。

P→Q2.如果一個(gè)人不幸福,則他死得早。

Q→R

結(jié)論:單身漢死得早。

P→R可描述為:P→Q,Q→R

P→R

(假言三段論)2023/12/15例子(續(xù)1)3)、某女子在某日晚歸家途中被殺害,據(jù)多方調(diào)查確證,兇手必為王某或陳某,但后又查證,作案之晚王某在工廠值夜班,沒有外出,根據(jù)上述案情可得前提:1.兇手為王某或陳某。

P∨Q

2.如果王某是兇手,則他在作案當(dāng)晚必外出

P→R3.王某案發(fā)之晚并未外出。

┐R結(jié)論:陳某是兇手。

Q則可描述為:P→R,┐R

┐P

(否定后件式)

P∨Q,┐P

Q

(選言三段論)2023/12/15例子(續(xù)2)4)、前提:

1.如果某同學(xué)為省二級(jí)以上運(yùn)動(dòng)員,則他將被大學(xué)錄取。

P→R

2.如果某同學(xué)高考總分在560分以上,則將被大學(xué)錄取。

Q→R

3.某同學(xué)高考總分在560分以上或者是省二級(jí)運(yùn)動(dòng)員。

P∨Q

結(jié)論:該同學(xué)被大學(xué)錄取。

R

則上述例子可描述為:

P∨Q,P→R,Q→R

R

(二難推論)2023/12/153演繹法

演繹法是從前提(假設(shè))出發(fā),依據(jù)公認(rèn)的推理規(guī)則和推理定律,推導(dǎo)出一個(gè)結(jié)論來。YN觸發(fā)規(guī)則新事實(shí)事實(shí)=結(jié)論?事實(shí)庫規(guī)則匹配公理庫將事實(shí)加入到事實(shí)庫中結(jié)束引入事實(shí)2023/12/15引入推理規(guī)則在數(shù)理邏輯中,主要的推理規(guī)則有:①P規(guī)則(稱為前提引用規(guī)則):在推導(dǎo)的過程中,可隨時(shí)引入前提集合中的任意一個(gè)前提;②規(guī)則T(邏輯結(jié)果引用規(guī)則):在推導(dǎo)的過程中,可以隨時(shí)引入公式S,該公式S是由其前的一個(gè)或多個(gè)公式推導(dǎo)出來的邏輯結(jié)果。③規(guī)則CP(附加前提規(guī)則):如果能從給定的前提集合Г與公式P推導(dǎo)出S,則能從此前提集合Г推導(dǎo)出P→S。2023/12/15演繹的定義定義5.2.2

從前提集合Г推出結(jié)論H的一個(gè)演繹是構(gòu)造命題公式的一個(gè)有限序列:

H1,H2,……,Hn

其中,Hi或者是Г中的某個(gè)前提,或者是前面的某些Hj(j<i)的有效結(jié)論,并且Hn就是H,則稱公式H為該演繹的有效結(jié)論,或者稱從前提Г能夠演繹出結(jié)論H來。2023/12/15例5.2.2證明1

⑴P∨QP

⑵┐P→QT,(1),E

⑶Q→SP

⑷┐P→ST,⑵,⑶,I⑸┐S→P

T,⑷,E⑹P

R

P⑺(P→R)

(R→P)T,⑹,E⑻P→RT,⑺,I⑼┐S→R

T,⑸,⑻,I⑽S∨R

T,⑺,E設(shè)前提Г={P∨Q,P

R,Q→S},G=S∨R。證明Г

G。2023/12/15例5.2.2(續(xù))證明2⑴┐S P(附加前提)⑵

Q→S P⑶┐Q T,⑴,⑵,I⑷

P∨Q P⑸

P T,⑶,⑷,I⑹P

R

P⑺(P→R)

(R→P)T,⑹,E⑻P→R T,⑺,I⑼R T,⑸,⑻,I⑽┐S→R CP,⑴,⑼⑾S∨RT,⑽,E2023/12/15例5.2.3證

⑴R

P(附加前提)⑵┐R∨P

P⑶P

T,⑴,⑵,I⑷P→(Q→S)

P

⑸Q→S T,⑶,⑷,I⑹Q P⑺S T,⑸,⑹,I⑻R→S CP,⑴,⑺設(shè)Г={P→(Q→S),┐R∨P,Q},

G=R→S。證明:Г

G。2023/12/154間接證明法(反證法)前面使用過的一些證明方法都是正向推理。但在數(shù)學(xué)領(lǐng)域中,經(jīng)常會(huì)遇到一些問題,當(dāng)采用正向推理時(shí)很難從前提為真推出結(jié)論為真。P

Q等價(jià)于

Q

P,因此,為了間接地證明PQ,可以假設(shè)Q為假(

Q),然后證明P為假(

P)。2023/12/15例5.2.4設(shè)n是一個(gè)整數(shù),證明:如果n2是奇數(shù),那么n是奇數(shù)。

證明設(shè)n是偶數(shù),則n=2k,這里k是一個(gè)整數(shù)。于是有:

n2=(2k)2=4k2=2(2k2)所以n2是偶數(shù)。因而證明了若n是偶數(shù),則n2是偶數(shù),它是已知命題的逆否式。因此,證明了所給的命題。

2023/12/15定義5.2.3

假設(shè)G1,G2,…,Gn是一組命題公式,P1,P2,…,Pn是出現(xiàn)在中的一切命題變元,I是它的任意解釋,若有解釋I使G1∧G2∧…∧Gn取值為“真”,則稱公式G1,G2,…,Gn是一致的,或者說是相容的。如對(duì)任意的解釋I,都有G1∧G2∧…∧Gn取值為“假”,則稱公式G1,G2,…,Gn是不一致的?;蛘哒fG1∧G2∧…∧Gn是一個(gè)矛盾式。

G1∧G2∧…∧Gn是矛盾式當(dāng)且僅當(dāng)G1∧G2∧…∧Gn

R∧┐R,其中,R可為任意公式,R∧┐R為一矛盾式。2023/12/15間接證明方法將結(jié)論的否定加入到前提集合中構(gòu)成一組新的前提,然后證明這組新的前提集合是不相容的,即蘊(yùn)涵一個(gè)矛盾式。G1,G2,…,Gn,┐H

R∧┐R定理5.2.2設(shè)命題公式集合{G1,G2,…,Gn}是一致的,于是從前提集合出發(fā)可以邏輯地推出公式H的充要條件是從前提集合{G1,G2,…,Gn

,┐H}出發(fā),可以邏輯地推出一個(gè)矛盾(永假)式來。2023/12/15例5.2.5證明不存在有理數(shù)p/q其平方為2,即,證明是無理數(shù)。證明對(duì)某兩個(gè)整數(shù)p和q,假設(shè)(p/q)2=2成立,并且p和q沒有公因子。如果原來選擇的p/q不是最小項(xiàng),則可以用它等價(jià)的最小項(xiàng)形式來取代它。于是p2=2q2,所以p2是偶數(shù),這就推出p是偶數(shù),因?yàn)橐粋€(gè)奇數(shù)的平方是奇數(shù)。2023/12/15例5.2.5證明(續(xù))因此存在某個(gè)整數(shù)n使得p=2n成立。因此

2q2=p2=(2n)2=4n2,即有q2=2n2,所以q2是偶數(shù),從而q是偶數(shù),于是得到p和q都是偶數(shù),故它們有一個(gè)公因子2,這與假設(shè)相矛盾。因此假設(shè)一定為假。2023/12/15例5.2.6用反證法證明二難推論

P∨Q,P→R,Q→R

R證明

⑴P→R P

┐RP(附加前提)⑶┐P T,⑴,⑵,I⑷

Q→R P⑸┐QT,⑵,⑷,I

⑹P∨QP⑺PT,⑸,⑹,I⑻P∧┐P

T,⑶,⑺,I2023/12/15三種證明方法之間的關(guān)系

G1,G2,…,Gn,┐H

R∧┐R

G1,G2,…,Gn

┐H→(R∧┐R)

G1,G2,…,Gn

┐┐H∨(R∧┐R)

G1,G2,…,Gn

H反證法CP規(guī)則證明法直接證明法2023/12/155.2.3命題邏輯推理的難點(diǎn)1、弄清楚蘊(yùn)涵式P→Q的邏輯關(guān)系及其真值,這里Q是P的必要條件。無論蘊(yùn)涵關(guān)系如何表述,都要仔細(xì)地區(qū)分出蘊(yùn)涵式的前件和后件。2、推理過程中推理規(guī)則、基本等值式和邏輯蘊(yùn)涵式的引用要適當(dāng),邏輯思維要清晰。2023/12/155.2.3命題邏輯推理的難點(diǎn)3、弄清楚幾種推理方法的區(qū)別與聯(lián)系,對(duì)于命題邏輯推理而言,任何一個(gè)問題的推理,都可以采取三種推理方法中的任何一種來證明,針對(duì)不同的問題選用不同的推理方法。一般而言,對(duì)于結(jié)論是蘊(yùn)涵式或析取式的,大多可以采取帶CP規(guī)則的直接證明方法。2023/12/155.2.4命題邏輯推理的應(yīng)用例5.2.7

符號(hào)化下面的語句,并用演繹法證明結(jié)論是否有效。

或者明天下午是天晴,或者是下雨;如果明天下午是天晴,則我將去看電影;如果我去看電影,我就不看書。如果我看書,則天在下雨。

設(shè)P:明天下午天晴;Q:明天下午下雨;R:明天下午去看電影;S:明天下午看書。則上述命題可符號(hào)化為:PQ,P→R,R→

S

S→Q。2023/12/15例5.2.7

證明

(1)SP(附加前提)

(2)R→

SP

(3)

RT,(1),(2),I

(4)P→RP

(5)

PT,(3),(4),I

(6)PQP(7)QT,(4),(7),I

2023/12/15例5.2.8一個(gè)公安人員審查一件盜竊案,已知的事實(shí)如下:

A或B盜竊了x;若A盜竊了x,則作案時(shí)間不能發(fā)生在午夜前;若B證詞正確,則在午夜時(shí)屋里燈光未滅;若B證詞不正確,則作案時(shí)間發(fā)生在午夜前;午夜時(shí)屋里燈光滅了。B盜竊了x。

2023/12/15例5.2.8證明設(shè)P:A盜竊了x;Q:B盜竊了x;R:作案時(shí)間發(fā)生在午夜前;S:B證詞正確;

T:在午夜時(shí)屋里燈光未滅。則上述命題可符號(hào)化為: P∨Q,P→

R,S→T,

S→R,

T

Q2023/12/15例5.2.8證明(續(xù))證明1采用直接證明方法(反證法請(qǐng)學(xué)生完成)(1)

TP(2)S→TP(3)

ST,(1),(2),I

(4)

S→RP(5)RT,(3),(4),I

(6)P→┐RP

(7)

PT,(5),(6),I

(8)P∨QP(9)QT,(7),(8),I2023/12/15證明令P:馬會(huì)飛; Q:羊吃草;R:母雞是飛鳥; S:烤熟的鴨子還會(huì)跑。符號(hào)化上述語句為:Г={P∨Q→R,R→S,┐S},G=┐Q。證明Г

G。如果馬會(huì)飛或羊吃草,則母雞就會(huì)是飛鳥;如果母雞是飛鳥,那么烤熟的鴨子還會(huì)跑;烤熟的鴨子不會(huì)跑。所以羊不吃草。例5.2.82023/12/15例5.2.8證明

(續(xù))⑴┐S

P⑵R→S

P⑶┐R

T,⑴,⑵,I⑷P∨Q→R P⑸┐(P∨Q) T,⑶,⑷,I⑹┐P∧┐Q T,⑸,E⑺┐Q T,⑹,I2023/12/155.3謂詞邏輯的推理理論5.3.1謂詞演算的演繹與推理

定義5.3.1設(shè)G1,G2,…,Gn,H是公式,稱H是G1,G2,…,Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊(yùn)涵H),當(dāng)且僅當(dāng)H是G1∧G2∧…∧Gn的邏輯結(jié)果(logicconclusion)。記為G1,G2,…,Gn

H,此時(shí)稱G1,G2,…,Gn

H為有效的(efficacious),否則稱為無效的(inefficacious)。G1,G2,…,Gn稱為一組前提(Premise),有時(shí)用集合Г來表示,記Г={G1,G2,…,Gn}。H稱為結(jié)論(conclusion)。又稱H是前提集合的邏輯結(jié)果。記為Г

H。2023/12/15定理5.3.1定理5.3.1

公式H是前提集合Г={G1,G2,…,Gn}的邏輯結(jié)果當(dāng)且僅當(dāng)G1∧G2∧…∧Gn→H為有效公式。2023/12/15一推理規(guī)律(1)I16:(

x)G(x)

(

x)G(x);(2)I17:(

x)G(x)∨(

x)H(x)(

x)

(G(x)∨H(x))

I18:(

x)(G(x)∧H(x))

(

x)G(x)∧(

x)H(x)(3)I19:(

x)(G(x)→H(x))

(

x)G(x)→(

x)H(x)I20:(

x)(G(x)→H(x))

(

x)G(x)→(

x)H(x)2023/12/15推理規(guī)律(續(xù))(4)I21:(

x)(

y)G(x,y)

(

y)(

x)G(x,y);

I22:(

x)(

y)G(x,y)

(

y)(

x)G(x,y);

I23:(

y)(

x)G(x,y)

(

x)(

y)G(x,y);

I24:(

y)(

x)G(x,y)

(

x)(

y)G(x,y);

I25:(

x)(

y)G(x,y)

(

y)(

x)G(x,y);2023/12/15二推理規(guī)則1、US(全稱特指規(guī)則,UniversalSpecify):

(

x)G(x)

G(y),其中G(x)對(duì)y是自由的推廣:(

x)G(x)

G(c),其中c為任意個(gè)體常量2、ES(存在特指規(guī)則,ExistentialSpecify):

(

x)G(x)

G(c),其中c為特定個(gè)體常量2023/12/15推理規(guī)則(續(xù))3、UG(全稱推廣規(guī)則,UniversalGeneralize):

G(y)(

x)

G(x),其中G(y)對(duì)x是自由的4、EG(存在推廣規(guī)則,ExistentialGeneralize):

G(c)(

x)

G(x),其中c為特定個(gè)體常量推廣:G(y)(

x)

G(x),其中G(y)對(duì)x是自由的2023/12/15推理規(guī)則的正確使用(1)例5.3.1

設(shè)實(shí)數(shù)集中,語句“不存在最大的實(shí)數(shù)”可符號(hào)化為:

(

x)(

y)G(x,y)。其中:G(x,y):y>x。推導(dǎo)1:(1)(

x)(

y)G(x,y)P

(2)(

y)G(y,y)US,(1)分析:推導(dǎo)1是錯(cuò)誤的。正確的推導(dǎo)如下:(1)(

x)(

y)G(x,y)P

(2)(

y)G(z,y)US,(1)注意:使用US規(guī)則來消去量詞時(shí),所選用取代x的變元y在公式中必須是自由的。2023/12/15推理規(guī)則的正確使用(2)推導(dǎo)2:(1)(

x)(

y)G(x,y)P(2)(

y)G(z,y)US,(1)(3)G(z,c)ES,(2)

分析:推導(dǎo)2是錯(cuò)誤的。正確的推導(dǎo)如下:(1)(

x)(

y)G(x,y)P

(2)(

y)G(z,y)US,(1)(3)G(z,f(z))ES,(2)注意:使用ES規(guī)則來消去量詞時(shí),若還有其它自由變元時(shí),則必須用關(guān)于自由變元的函數(shù)符號(hào)來取代常量符號(hào).2023/12/15推理規(guī)則的正確使用(3)推導(dǎo)3:(1)(

y)G(z,y)P

(2)(

y)(

y)G(y,y)UG,(1)分析:推導(dǎo)3是錯(cuò)誤的。正確的推導(dǎo)如下:

(1)(

y)G(z,y)P(2)(

z)(

y)G(z,y)UG,(1)注意:使用UG規(guī)則來添加量詞時(shí),所使用的變元符號(hào)不能與轄域內(nèi)的變元符號(hào)相同.2023/12/15推理規(guī)則的正確使用(4)推導(dǎo)4:(1)G(x,c)P

(2)(

x)G(x,x)EG,(2)分析:推導(dǎo)4是錯(cuò)誤的。正確的推導(dǎo)如下:

(1)G(x,c)P(2)(

y)G(x,y)EG,(2)注意:使用EG規(guī)則來添加量詞時(shí),所使用的變元符號(hào)不能與轄域內(nèi)的變元符號(hào)相同.2023/12/155.3.2謂詞演算的綜合推理方法(1)推導(dǎo)過程中可以引用命題演算中的規(guī)則P和規(guī)則T

。(2)如果結(jié)論是以條件的形式(或析取形式)給出,我們還可以使用規(guī)則CP。(3)若需消去量詞,可以引用規(guī)則US和規(guī)則ES。(4)當(dāng)所要求的結(jié)論可能被定量時(shí),此時(shí)可引用規(guī)則UG和規(guī)則EG將其量詞加入。2023/12/15謂詞演算的綜合推理方法(續(xù))(5)證明時(shí)可采用如命題演算中的直接證明方法和間接證明方法。(6)在推導(dǎo)過程中,對(duì)消去量詞的公式或公式中不含量詞的子公式,完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。(7)在推導(dǎo)過程中,對(duì)含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。2023/12/15例5.3.1解設(shè)H(x):x是人;M(x):x是要死的;s:蘇格拉底。則符號(hào)化為:(x)(H(x)M(x)),H(s)M(s)證明蘇格拉底三段論:“所有的人都是要死的;蘇格拉底是人。所以蘇格拉底是要死的?!弊C明:(1)(x)(H(x)M(x)) P (2)H(x)M(x) US,(1) (3)H(s) P (4)M(s) T,(2),(3),I證明:(1)

(x)(H(x)M(x)) P (2)

H(s)M(s) US,(1) (3)

H(s) P (4)

M(s) T,(2),(3),I(4)錯(cuò)了!正確的為2023/12/15例5.3.2證明:

(x)(P(x)Q(x)),(

x)P(x)(

x)Q(x)有下面的推導(dǎo):

(1)(x)(P(x)Q(x)) P(2)(P(x)Q(x)) US,(1)(3)

(

x)P(x) P(4)

P(c) ES,(3)(5)Q(c) T,(2),(4),I(6)(

x)Q(x) EG,(5)2023/12/15例5.3.2(2)推導(dǎo)可修改為:(1)(x)(P(x)Q(x)) P(2)(P(c)Q(c)) US,(1)(3)

(

x)P(x) P(4)

P(c) ES,(3)(5)Q(c) T,(2),(4),I(6)(

x)Q(x) EG,(5)2023/12/15例5.3.2(3)正確地推導(dǎo)如下:(1)

(

x)P(x) P(2)

P(c) ES,(1)(3)(x)(P(x)Q(x)) P(4)(P(c)Q(c)) US,(3)(5)Q(c) T,(2),(4),I(6)(

x)Q(x) EG,(5)2023/12/15例5.3.3

證明:1)(

x)(P(x)∧Q(x)) P 2)(P(c)∧Q(c)) ES,1) 3)P(c) T,2),I 4)Q(c) T,2),I 5)(

x)P(x) EG,3) 6)(

x)Q(x) EG,4) 7)(

x)P(x)∧(

x)Q(x) T,5),6),I證明:(

x)(P(x)∧Q(x))(

x)P(x)∧(

x)Q(x)2023/12/15例5.3.3(續(xù)1)1)(

x)P(x)∧(

x)Q(x) P2)(

x)P(x) T,1),I3)P(c) ES,2)4)(

x)Q(x) T,1),I5)Q(c) ES,4)6)(P(c)∧Q(c)) T,3),4),I7)(

x)(P(x)∧Q(x)) EG,6)請(qǐng)看上述推論的逆推導(dǎo):2023/12/15例5.3.3(續(xù)2)正確地推導(dǎo):1)(

x)P(x)∧(

x)Q(x) P2)(

x)P(x) T,1),I3)P(c) ES,2)4)(

x)Q(x) T,1),I5)Q(b) ES,4)6)(P(c)∧Q(b)) T,3),4),I7)(

x)(

y)(P(x)∧Q(y)) EG,6)2023/12/15例5.3.4證明(采用反證法,CP規(guī)則的方法由學(xué)生完成):1)((x)P(x)∨(

x)Q(x)) P(附加前提)2)

(x)P(x)∧

(

x)Q(x) T,1),E3)(x)P(x)

T,2),I4)(

x)Q(x) T,2),I5)(

x)P(x) T,3),E6)P(c) ES,5)證明(x)(P(x)∨Q(x))(x)P(x)∨(

x)Q(x)2023/12/15例5.3.4證明(續(xù))

7)(x)Q(x)

T,4),E8)Q(c)

US,7)9)P(c)∧Q(c)

T,6),8),I10)(P(c)∨Q(c))

T,9),E11)(x)(P(x)∨Q(x))

P12)(P(c)∨Q(c))

US,11)13)(P(c)∨Q(c))∧(P(c)∨Q(c))T,10),12)2023/12/155.3.3謂詞邏輯推理的難點(diǎn)(1)在推導(dǎo)過程中,如既要使用規(guī)則US又要使用規(guī)則ES消去公式中的量詞,而且選用的個(gè)體是同一個(gè)符號(hào),則必須先先使用規(guī)則ES,再使用規(guī)則US。然后再使用命題演算中的推理規(guī)則,最后使用規(guī)則UG或規(guī)則EG引入量詞,得到所要的結(jié)論。(2)如一個(gè)變量是用規(guī)則ES消去量詞,對(duì)該變量在添加量詞時(shí),則只能使用規(guī)則EG,而不能使用規(guī)則UG;如使用規(guī)則US消去量詞,對(duì)該變量在添加量詞時(shí),則可使用規(guī)則EG和規(guī)則UG。2023/12/15謂詞邏輯推理的難點(diǎn)(續(xù))(3)如有兩個(gè)含有存在量詞的公式,當(dāng)用規(guī)則ES消去量詞時(shí),不能選用同樣的一個(gè)常量符號(hào)來取代兩個(gè)公式中的變元,而應(yīng)用不同的常量符號(hào)來取代它們。(4)在用規(guī)則US和規(guī)則ES消去量詞時(shí),此量詞必須位于整個(gè)公式的最前端。2023/12/15謂詞邏輯推理的難點(diǎn)(續(xù))(5)在添加量詞(

x)、(

x)時(shí),所選用的x不能在公式G(c)或G(y)中以任何約束出現(xiàn)。(6)在使用EG規(guī)則引入存在量詞(

x),此x不得僅為G(c)或G(y)中的函數(shù)變元。在使用UG規(guī)則引入全稱量詞(

x)時(shí),此x不得為G(y)中的函數(shù)變元(因該函數(shù)變元不得作為自由變元)。2023/12/155.3.4謂詞邏輯推理的應(yīng)用例5.3.5

每個(gè)喜歡步行的人都不喜歡坐汽車;每個(gè)人或者喜歡坐汽車或者喜歡騎自行車;有的人不喜歡騎自行車。因而有的人不喜歡步行。證明設(shè)H(x):x是人;P(x):x喜歡坐汽車;Q(x):x喜歡騎自行車;R(x):x喜歡步行。則上述語句可符號(hào)化為:(

x)(H(x)∧R(x)→P(x)),(

x)(H(x)→P(x)∨Q(x)),(

x)(H(x)∧Q(x))

(

x)(H(x)∧R(x))2023/12/15例5.3.5證明(續(xù))

(1)(

x)(H(x)∧Q(x))P(2)H(c)∧Q(c)ES,(1)

(3)H(c)T,(2)

(4)Q(c)T,(2)

(5)(

x)(H(x)→P(x)∨Q(x))P

(6)H(c)→P(c)∨Q(c)US,(5)

(7)P(c)∨Q(c)T,(3),(6),I

(8)P(c)T,(4),(7),I2023/12/15例5.3.5證明(續(xù))

(9)

(

x)(H(x)∧R(x)→P(x))P(10)H(c)∧R(c)→P(c)US,(9)(11)

(H(c)∧R(c))T,(8),(10),I(12)H(c)∨R(c)T,(11),E(13)R(c)T,(3),(12),I(14)H(c)∧R(c)T,(3),(13),I(15)

(

x)(H(x)∧R(x))EG,(14)2023/12/15例5.3.6證明下述論斷的正確性:所有的哺乳動(dòng)物都是脊椎動(dòng)物;并非所有的哺乳動(dòng)物都是胎生動(dòng)物;故有些脊椎動(dòng)物不是胎生的。證明

設(shè)謂詞如下:

P(x):x是哺乳動(dòng)物;

Q(x):x是脊椎動(dòng)物;

R(x):x是胎生動(dòng)物。則有:(x)(P(x)Q(x)),(x)(P(x)R(x))

(

x)(Q(x)∧R(x))2023/12/15請(qǐng)看下面推導(dǎo):1)

(x)(P(x)R(x)) P2)(P(x)R(x)) US,1)3)(P(x)∨R(x))T,2),E4)(P(x)∧R(x)) T,3),E5)P(x) T,4),I6)R(x) T,4),I7)(x)(P(x)Q(x))P8)P(x)Q(x) US,7)9)Q(x) T,(5),(8),I10)Q(x)∧R(x) T,6),9),I11)(

x)(Q(x)∧R(x)) EG,10)12)(x)(Q(x)∧R(x)) UG,10)2023/12/15例5.3.6證明(續(xù))1)

(x)(P(x)R(x)) P2)(

x)(P(x)∨R(x)) T,1),E3)(P(c)∨R(c)) ES,2)4)(P(c)∧R(c)) T,3),E5)P(c) T,4),I6)R(c) T,4),I7)(x)(P(x)Q(x)) P8)P(c)Q(c) US,7)9)Q(c) T,5),8),I10)Q(c)∧R(c) T,6),9),I11)(

x)(Q(x)∧R(x)) EG,10)2023/12/15例5.3.7證明下列論斷的正確性:有些學(xué)生相信所有的教師;任何一個(gè)學(xué)生都不相信騙子;所以,教師都不是騙子。證明

設(shè)謂詞如下:

S(x):x是學(xué)生

T(x):x是教師

P(x):x是騙子

L(x,y):x相信y則可符號(hào)化為:

(

x)(S(x)∧(y)(T(y)L(x,y))),

(x)(y)((S(x)∧P(y))L(x,y))

(x)(T(x)P(x))2023/12/15例5.3.7證明(續(xù))1)(

x)(S(x)∧(y)(T(y)L(x,y)))P2)S(c)∧(y)(T(y)L(c,y))ES,1)3)S(c) T,2),I4)(y)(T(y)L(c,y)) T,2),I5)T(x)L(c,x) US,4)6)(x)(y)((S(x)∧P(y))L(x,y))P7)(y)((S(c)∧P(y))L(c,y))US,6)8)(S(c)∧P(x))L(c,x)US,7)2023/12/15例5.3.7證明(續(xù))9)S(c)(P(x)L(c,x))T,8),E10)P(x)L(c,x) T

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(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)論