資源描述：
《離散數(shù)學(xué)第二章命題演算的推理理論-假設(shè)推理系統(tǒng).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第二章命題演算的推理理論2.1命題演算的公理系統(tǒng)2.2命題演算的假設(shè)推理系統(tǒng)2.2.1假設(shè)推理系統(tǒng)的組成2.2.2假設(shè)推理系統(tǒng)的推理過程2.3命題演算的歸結(jié)推理法2．2命題演算的假設(shè)推理系統(tǒng)假設(shè)推理系統(tǒng)：由于它的推理形式類似于日常生活中的推理形式，也稱為自然推理系統(tǒng)。2.2.1假設(shè)推理系統(tǒng)的組成一、擴(kuò)充的推理規(guī)則二、假設(shè)推理過程三、推理定理四、假設(shè)推理證明定理的方法一、擴(kuò)充的推理規(guī)則分離規(guī)則的推廣A1，A2，…，An├A(2)肯定前提律A1，A2，A3，…，An├Ai分離規(guī)則的推廣設(shè)有如下的推理規(guī)則R：若A1，A2，…，An，可以推出A，即R：A1
2、，A2，…，An├A，則稱A是由A1，A2，…，An實(shí)施規(guī)則R而得。設(shè)Γ=A1，A2，…，An，則上述規(guī)則R可以記為Γ├A其中Γ為形式前提，A為形式結(jié)論。肯定前提律A1，A2，A3，…，An├Ai(i=1，2，…，n)，即前提中的任何命題均可作為結(jié)論。二、假設(shè)推理過程定義:如果能夠作出一系列合式公式序列A1，A2,A3,…，An，它們(諸Ai)滿足下列性質(zhì)：(1)或?yàn)楣碇唬?2)或?yàn)楣?1,?2,…,?k之一，每個(gè)?i稱為假設(shè)；(3)或由前面的若干個(gè)Ag、Ah利用分離規(guī)則而得；(4)An=B。稱這個(gè)公式序列A1，A2,…，An為由公式?1，?
3、2，…，?k證明B的證明過程.?1，?2，…，?k├B三、推理定理(附加前提證明法)如果Γ，A├B，則Γ├A?B要證Γ├(A?B)，即要證Γ，A├B附加前提證明法如果A1，A2，…，An-1，An，A├B，則A1，A2，…，An-1，An├A?B進(jìn)而，有下面定理：A1，A2…，An-1├An?(A?B)A1，A2，…，An-2├An-1?(An?(A?B))依次類推可得定理：├A1?(A2?(…?(An?(A?B))…))(2)歸謬法如果Γ，?A├B且Γ，?A├?B，則Γ├A。此定理稱為反證律。這里B是一個(gè)公式。其它公理、規(guī)則同前節(jié)。四、假設(shè)推理證
4、明定理的方法(1)把待證公式的前件一一列出，作為假設(shè)(或把待證公式的后件的否定作為假設(shè))，并在式子后注明為假設(shè)。(2)按上述介紹的推理方法進(jìn)行推理，但此時(shí)不能對(duì)假設(shè)實(shí)施代入規(guī)則（因?yàn)榧僭O(shè)不是永真公式）。(3)當(dāng)推導(dǎo)出待證公式的后件時(shí)(或推導(dǎo)出矛盾時(shí))就說證明了該定理。第二章命題演算的推理理論2.1命題演算的公理系統(tǒng)2.2命題演算的假設(shè)推理系統(tǒng)2.2.1假設(shè)推理系統(tǒng)的組成2.2.2假設(shè)推理系統(tǒng)的推理過程2.3命題演算的歸結(jié)推理法例1：求證(P?(Q?R))?((P?Q)?R)證明:(1)P?(Q?R)假設(shè)(2)P?Q假設(shè)(3)(P?Q)?P公理8(4
5、)(P?Q)?Q公理9(5)P(3)(2)分離(6)Q(4)(2)分離(7)Q?R(1)(5)分離(8)R(6)(7)分離由假設(shè)推理過程的定義知：P?(Q?R)，P?Q├R由推理定理得：(P?(Q?R))?((P?Q)?R)(6)R在(5)中用R代入P有錯(cuò)嗎?不能對(duì)(5)實(shí)施代入規(guī)則!!!例2(p21)求證：(?P?P)?P證明：(1)?P?P假設(shè)(2)?P假設(shè)，結(jié)論的否定(3)P(1)(2)分離顯然，(2)與(3)表明推出矛盾(?P?P),?P├?P(?P?P),?P├P由反證法得：(?P?P)├P由推理定理得：(?P?P)?P例((S??Q)?
6、(P?Q)?S)??P解:(1)S→?Q假設(shè)(2)P→Q假設(shè)(3)S假設(shè)(4)P假設(shè),結(jié)論的否定(5)?Q(1)(3)分離(6)Q(1)(3)分離顯然，(5)與(6)表明推出矛盾:S??Q,P?Q,S,P├?QS??Q,P?Q,S,P├Q由反證法推理定理得：((S??Q)?(P?Q)?S)??P例(P?(Q?R))?((P?Q)?(P?R)))解:(1)P假設(shè)(2)P→Q假設(shè)(3)P→(Q→R)假設(shè)(4)Q(1)(2)分離(5)Q→R(1)(3)分離(7)R(4)(5)分離即證得P→(Q→R),P→Q,P┣R亦即證得命題：(P?(Q?R))?((P
7、?Q)?(P?R))例((P?Q)?R)?(P?(Q?R))解:(1)P∧Q→R假設(shè)(2)P假設(shè)(3)Q假設(shè)(4)P→(Q→(P∧Q))公理10(5)Q→(P∧Q)(2)(4)分離(6)P∧Q(3)(5)分離(7)R(1)(6)分離即證得(P∧Q)→R,P,Q┣R亦即證得((P?Q)?R)?(P?(Q?R))例((P?Q)?((P?R)?(Q?S)))?(S?R)解:(1)(P∧Q)∧((P?R)∧(Q?S))假設(shè)(2)P∧Q→P公理8(3)P∧Q→Q公理9(4)(P∧Q)∧((P?R)∧(Q?S))→(P∧Q)代入(2)(5)(P∧Q)∧((P?
8、R)∧(Q?S))→(P?R)∧(Q?S)代入(3)(6)P∧Q(1)(4)分離(7)(P?R)∧(Q?S)(1)(5)分
