版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 期貨市場綠色金融產(chǎn)品開發(fā)與推廣考核試卷
- 海洋生物多樣性保護(hù)與監(jiān)測考核試卷
- 四年級(jí)數(shù)學(xué)(四則混合運(yùn)算)計(jì)算題專項(xiàng)練習(xí)與答案匯編
- 污染源監(jiān)測與調(diào)查考核試卷
- 棉麻企業(yè)人力資源選拔與培訓(xùn)效果評(píng)估考核試卷
- 電機(jī)在電力能效管理的應(yīng)用考核試卷
- 2025年二苯醚項(xiàng)目建議書
- 2025年人造崗石樹脂項(xiàng)目發(fā)展計(jì)劃
- 營養(yǎng)學(xué)概論練習(xí)試題及答案
- 2025年文化科技主題公園項(xiàng)目合作計(jì)劃書
- 建筑垃圾清運(yùn)投標(biāo)方案(技術(shù)方案)
- 紅色文化知識(shí)題【小學(xué)低齡組(408題)】附有答案
- 安防個(gè)人工作總結(jié)
- JTG F40-2004 公路瀝青路面施工技術(shù)規(guī)范
- JTG D50-2017公路瀝青路面設(shè)計(jì)規(guī)范
- 鄉(xiāng)鎮(zhèn)衛(wèi)生院管理制度及細(xì)則
- 天津市河北區(qū)2022-2023學(xué)年七年級(jí)上學(xué)期期末生物試題【帶答案】
- 2024年輔警招聘考試試題庫附完整答案(必刷)
- 伴瘤內(nèi)分泌綜合征課件
- 2023-2024學(xué)年福建福州延安中學(xué)中考數(shù)學(xué)押題試卷含解析
- 二次函數(shù)整章復(fù)習(xí) 教案
評(píng)論
0/150
提交評(píng)論