離散數(shù)學(xué)第四章 謂詞演算的推理理論-假設(shè)推理系統(tǒng)

《離散數(shù)學(xué)第四章 謂詞演算的推理理論-假設(shè)推理系統(tǒng)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第四章謂詞演算的推理理論4.1謂詞演算的永真推理系統(tǒng)4.2謂詞演算的假設(shè)推理系統(tǒng)4.2.1假設(shè)推理系統(tǒng)的組成及證明方法4.2.2推理過(guò)程的推導(dǎo)過(guò)程4.3謂詞演算的歸結(jié)推理系統(tǒng)一、假設(shè)推理系統(tǒng)的組成(附加前提證明法)如果Γ，△A├△B，則Γ├△(A?B)，也可表示為：如果△A1，△A2，…，△An，△A├△B，則△A1，△A2，…，△An├△(A?B)。依次類(lèi)推可得定理：├△(A1?(A2?(…?(An?(A?B)))…)(2)存在推理定理如果有△A1，…，△An，△?xP(x)，△P(e)├△Q，其中Q中不含有自由的e，且在推理過(guò)程中不對(duì)假設(shè)中的自由變?cè)皖~外假設(shè)中的自由變?cè)獙?shí)施全規(guī)則和存在規(guī)

2、則，則有：△A1，△A2，…，△An，△?xP(x)├△Q去“存在量詞”二、假設(shè)推理過(guò)程的證明方法(1)把待證公式的前件作為假設(shè)一一列出，假設(shè)中的全稱(chēng)量詞?可用全稱(chēng)量詞消去規(guī)則消去，存在量詞可引入額外假設(shè)刪除，并在式子后注明它為額外假設(shè)。二、假設(shè)推理過(guò)程的證明方法(2)按永真的證明方法進(jìn)行證明，但此時(shí)不能對(duì)假設(shè)實(shí)施代入。(3)待證公式的后件中若有全稱(chēng)量詞，可用全0規(guī)則引入，存在量詞可由公理21引入。全稱(chēng)量詞消去規(guī)則規(guī)則成立的條件：（1）t是任意個(gè)體變項(xiàng)或常項(xiàng)。例考察?x?yF（x，y）全稱(chēng)量詞消去能不能得到下式:?yF（y，y）?存在量詞消去規(guī)則規(guī)則成立的條件：（1）c是使A（c）為真的特定的

3、個(gè)體常元。（2）?xA（x）是閉式。例考察?yF（x，y）存在量詞消去能不能得到下式:F（x，c）?全稱(chēng)量詞引入規(guī)則規(guī)則成立的條件：（1）A（t）在任何解釋I及I中對(duì)t的任何賦值下均為真。（2）x不在A（t）中約束出現(xiàn)。存在量詞引入規(guī)則規(guī)則成立的條件：（1）c是特定的個(gè)體常元。（2）x不在A（c）中出現(xiàn)。第四章謂詞演算的推理理論4.1謂詞演算的永真推理系統(tǒng)4.2謂詞演算的假設(shè)推理系統(tǒng)4.2.1假設(shè)推理系統(tǒng)的組成及證明方法4.2.2推理過(guò)程的推導(dǎo)過(guò)程4.3謂詞演算的歸結(jié)推理系統(tǒng)例求證蘇格拉底三段論凡人要死，蘇格拉底是人，所以蘇格拉底要死。解：P(e):e是人D(e):e要死a:蘇格拉底(1)?x

4、(P(x)?D(x))假設(shè)(2)P(a)假設(shè)(3)P(a)?D(a)全稱(chēng)量詞消去規(guī)則(4)D(a)(2)(3)分離由存在推理定理得：?x(P(x)?Q(x))，P(a)├Q(a)由假設(shè)推理定理得：?x(P(x)?D(x))?(P(a)?D(a))例下面推理是否正確？設(shè)前提為?x?yF（x，y），（1）?x?yF（x，y）前提引入（2）?yF（y，y）全稱(chēng)量詞消去解推理并不正確。如果給定解釋I：個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)（x，y）：x＞y。則?x?yF（x，y）意為“對(duì)于每個(gè)實(shí)數(shù)x，均存在著比之更小的實(shí)數(shù)y”，這是一個(gè)真命題。而?yF（y，y）意為“存在著比自己小的實(shí)數(shù)”，是假命題。之所以出現(xiàn)這樣的錯(cuò)

5、誤,是因?yàn)?yF（x，y）中有1個(gè)自由變?cè)獂,而?yF（y，y）中無(wú)自由變?cè)?。例下面推理是否正確？設(shè)前提為?x?yF（x，y），（1）?x?yF（x，y）前提引入（2）?yF（t，y）全稱(chēng)量詞消去（3）F（t，c）存在量詞消去（4）?xF（x，c）全稱(chēng)量詞引入（5）?y?xF（x，y）存在量詞引入解：推理并不正確。如果給定解釋I：個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)(x,y)：x＞y。則?x?yF（x，y）為真，而?y?xF（x，y）意為“存在著最小實(shí)數(shù)”，是假命題，故知推理不正確。之所以出現(xiàn)這樣的錯(cuò)誤，是在第（3）步中，?yF（t，y）非閉式（含有自由變?cè)猼)。例1(p44)求證：?x(P(x)?Q(x))

6、?(?xP(x)??xQ(x))解：(1)?x(P(x)?Q(x))假設(shè)(2)?xP(x)假設(shè)(3)P(e)?Q(e)額外假設(shè)(4)P(e)全稱(chēng)量詞消去規(guī)則(5)Q(e)(3)(4)分離(6)Q(e)??xQ(x)公理21+全稱(chēng)量詞消去規(guī)則(7)?xQ(x)(6)(5)分離由存在推理定理得：?x(P(x)?Q(x))，?xP(x)├?xQ(x)由假設(shè)推理定理得：?x(P(x)?Q(x))?(?xP(x)??xQ(x))例2(p44)已知知識(shí)：(1)有些病人喜歡所有的醫(yī)生；(2)所有的病人均不喜歡庸醫(yī)；試證明結(jié)論：所有的醫(yī)生均不是庸醫(yī)。例2(p44)證明：先把知識(shí)翻譯為符號(hào)公式,令P(e)表示“

7、e為病人”；D(e)表示“e為醫(yī)生”；Q(e)表示“e為庸醫(yī)”；L(e1，e2)表示“e1喜歡e2”；則已知知識(shí)翻譯為：(1)?x(P(x)??y(D(y)?L(x，y)))(2)?x(P(x)??y(Q(y)??L(x，y)))結(jié)論翻譯為：?x(D(x)??Q(x))(1)?x(P(x)??y(D(y)?L(x，y)))假設(shè)(2)?x(P(x)??y(Q(y)??L(x，y)))假設(shè)(3)P(a