第一學(xué)期-7講自然推理系統(tǒng)_第1頁(yè)
第一學(xué)期-7講自然推理系統(tǒng)_第2頁(yè)
第一學(xué)期-7講自然推理系統(tǒng)_第3頁(yè)
第一學(xué)期-7講自然推理系統(tǒng)_第4頁(yè)
第一學(xué)期-7講自然推理系統(tǒng)_第5頁(yè)
已閱讀5頁(yè),還剩30頁(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)介

1命題邏輯真值表等值演算范式聯(lián)結(jié)詞完備集推理2推理{A1,A2

,…,An}├B有效當(dāng)且僅當(dāng)形式結(jié)構(gòu)(A1∧A2∧…∧An)→B是重言式。{A1,A2

,…,An}├B有效,記為

{A1,A2

,…,An}╞B,也記為

{A1,A2

,…,An}B3推理舉例(1)如果a能被4整除,那么a能被2整除;a能被4整除,所以a能被2整除。解:p:

a能被4整除

q:

a能被2整除前提:p→q,p

結(jié)論:q

推理形式結(jié)構(gòu):((p→q)∧p)→q

判斷此為永真式

1.真值表法(略)

2.等值演算┐((┐p∨q

)∧p)∨q

┐(┐p∨q

)∨(┐p∨q

)

14常見永真蘊(yùn)含式附加律A(A∨B)化簡(jiǎn)律(A∧B)A假言推理(A→B)∧AB拒取式(A→B)∧?B

?A析取三段論(A∨B)∧?B

A假言三段論(A→B)∧(B→C)(A→C)…………5推理舉例1如果a能被4整除,那么a能被2整除;a能被4整除,所以a能被2整除。解:p:

a能被4整除

q:

a能被2整除前提:p→q,p

結(jié)論:q證明:(1)((p→q)∧p)

q

假言推理6推理舉例2下午小王或去看電影或去游泳。他沒(méi)去看電影。所以,他去游泳了。設(shè):p:小王下午去看電影

q:小王下午去游泳前提:p

q,

?p

結(jié)論:q7推理舉例2前提:p

q,

?p結(jié)論:q(p

q)

∧?p((?p∧q)∨(p∧

q))

∧?p

(?p∨?q)∧(p∨q)

∧?p

分配律

(p∨q)

∧?p

化簡(jiǎn)律

q析取三段論8推理舉例4(2)((p1→(p2→p3))∧p2)→(p1→p3)((p1∨(p2∨p3))∧p2)∨(p1∨p3)((p1∧p2∧

p3)∨

p2)∨(p1∨p3)(p1∧p2∧

p3)∨

p2∨p1∨p3(p1∧p2∧

p3)∨(p1∧p2∧

p3)19推理舉例4(2)(p1→(p2→p3))∧p2(p1∨(p2∨p3))∧p2

蘊(yùn)涵等值(p2∨(p1∨p3))∧p2結(jié)合律,交換律(p2→(p1→p3))∧p2蘊(yùn)涵等值

(p1→p3)假言推理10命題演算的自然推理形式系統(tǒng)P11推理12計(jì)算機(jī)上的有效推理需要13形式系統(tǒng)形式語(yǔ)言形式推理14P的符號(hào)庫(kù)p,q,r,p1,p2,p3,…可數(shù)個(gè)命題變?cè)?hào)∧,∨,?,→,?五個(gè)聯(lián)結(jié)詞符號(hào)(,)輔助符號(hào)15P的公式單個(gè)命題符號(hào)是公式;若是公式,則(?)是公式;若,是公式,則(

∧),(

∨),(

→),(

?)也是公式;只有有限次地應(yīng)用上述規(guī)則形成的符號(hào)串才是公式。16P的公理空集17P的推理規(guī)則前提引入規(guī)則:在證明的任何步驟上都可以引入前提(P規(guī)則)結(jié)論引入規(guī)則:在證明的任何步驟上所得到的結(jié)論都可以做為后繼證明的前提(T規(guī)則)置換規(guī)則:在證明的任何步驟上,命題公式中的子公式都可以用與之等值的公式置換,得到公式序列中又一個(gè)公式18推理規(guī)則(續(xù))附加規(guī)則:A(A∨B)A

————

A∨B化簡(jiǎn)規(guī)則:(A∧B)A19推理規(guī)則(續(xù))假言推理規(guī)則:(A→B)∧ABA→BA

————B拒取式規(guī)則:(A→B)∧?B

?A20推理規(guī)則(續(xù))假言三段論規(guī)則:(A→B)∧(B→C)(A→C)A→BB→C

————

A→C析取三段論規(guī)則:(A∨B)∧?B

A21推理規(guī)則(續(xù))構(gòu)造性兩難推理規(guī)則:(A→B)∧(C→D)∧(A∨C)(B∨D)破壞性兩難推理規(guī)則:(A→B)∧(C→D)∧(?B∨?D)(?A∨?C)22推理規(guī)則(續(xù))合取引入規(guī)則:(A)∧(B)(A∧B)AB————

A∧B23拒取式有個(gè)強(qiáng)盜,搶了一個(gè)老太婆的東西。老太婆大聲叫喊:“抓強(qiáng)盜!抓強(qiáng)盜!”有個(gè)過(guò)路人拼命追趕,把強(qiáng)盜抓住了??墒菑?qiáng)盜反咬一口,扭住這個(gè)過(guò)路人說(shuō)對(duì)方是強(qiáng)盜。當(dāng)時(shí)天快黑了,也不知道強(qiáng)盜到底是哪個(gè),于是他們來(lái)到官府,請(qǐng)官府?dāng)喽?。符融見了后笑著說(shuō):“這很好辦,可以讓他們兩人一起賽跑,先跑出鳳陽(yáng)門的就不是盜賊?!币粫?huì)兒他們回到符融身邊,符融嚴(yán)肅地對(duì)那個(gè)后出鳳陽(yáng)門的人說(shuō):

“盜賊如果跑得快,就不會(huì)被人家抓住?,F(xiàn)在被人家抓住了,可見盜賊是跑得慢的那個(gè)?,F(xiàn)在你跑不過(guò)人家,被人家抓住了,可見你是真正的盜賊,你為什么還要誣陷人家呢?”(A→?B)∧B

?A24李登輝推動(dòng)“臺(tái)灣正名”運(yùn)動(dòng),首先拿“中華民國(guó)”祭旗還有更隱蔽的目的,即為大陸對(duì)臺(tái)政策出難題:我李登輝說(shuō)中華民國(guó)并不存在,你大陸如果來(lái)批我,那么你是不是承認(rèn)中華民國(guó)還存在?如果你不批我,嘿嘿,正中我“正名”、“臺(tái)獨(dú)”、“建國(guó)”三步曲的下懷。構(gòu)造性二難的特殊形式:(A→B)∧(?A→B)

B25證明所謂證明,就是一些公式的序列,其中每一個(gè)公式或是已知的前提,或是由前面的公式運(yùn)用推理規(guī)則得出的公式,最后一個(gè)公式是結(jié)論前提:A1,A2,A3,,Ak

結(jié)論:B

證明:(1)A1P(前提引入)

(2)

A2T××××(推理規(guī)則)

(3)A3××××

(s)Ak××××26證明(舉例)

前提:p∨q,

?p

結(jié)論:q

證明:(1)p∨q

前提引入(2)?p前提引入(3)q(1)(2)析取三段論27證明(舉例、續(xù))

前提:(p∧q)

→r,

?s∨p,q

結(jié)論:s→r

證明:(1)?s∨p

前提引入(2)s→p(1)置換

(3)(p∧q)

→r

前提引入

(4)q→(p→r)(3)置換(5)q

前提引入(6)p→r(4)(5)假言推理(7)s→r(2)(6)假言三段論28證明(舉例、續(xù))證明:(p∧q)

→rq→(p→r)(p∧q)

→r

?(p∧q)∨r(蘊(yùn)涵等值式)

(?p∨?q)∨r(德●摩根律)

?q∨(?p∨r)

(交換律、結(jié)合律)

q→(?p∨r)

(蘊(yùn)涵等值式)

q→(p→r)

(蘊(yùn)涵等值式)29間接證法——附加前提(CP規(guī)則)附加前提的證明法:

(A1∧A2∧...∧Ak)→(A→B)等值變換為(A1∧A2∧...∧Ak∧A)→B由A∧BC證得AB→

C稱為CP規(guī)則30間接證法——附加前提例:前提:p→(q→r),┐s∨p,q

結(jié)論:s→r31附加前提舉例證明:1.┐s∨p前提引入

2.

s附加前提引入

3.

p

(1)(2)析取三段論

4.

p→(q→r)前提引入

5.

q→r

(3)(4)假言推理

6.

q前提引入

7.

r

(5)(6)假言推理32間接證法——反證法定義:設(shè)A1,A2,...,Ak是k個(gè)命題公式,若A1∧A2∧...∧Ak是可滿足式,則稱A1,A2,...,Ak是相容的,否則稱A1,A2,...,Ak是不相容的.因?yàn)?A1∧A2∧...∧Ak)→B┐(A1∧A2∧...∧Ak∧┐B)因而若A1,A2,...,Ak,┐B不相容,則說(shuō)明B為A1,A2,...,Ak的邏輯結(jié)論.33反證法舉例例:前提:p→(┐(r∧s)→┐q),p,┐s

結(jié)論:┐q證明:1.p→(┐(r∧s)→┐q)前提引入

2.p前提引入

3.┐(r∧s)→┐q

(1)(2)假言推理

4.┐┐q結(jié)論的否定引入

5.r∧s

(3)(4)拒取式

6.s

(5)化簡(jiǎn)

7.┐s

溫馨提示

  • 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)論