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

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

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

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

3、個體常元。（2）?xA（x）是閉式。例考察?yF（x，y）存在量詞消去能不能得到下式:F（x，c）?全稱量詞引入規(guī)則規(guī)則成立的條件：（1）A（t）在任何解釋I及I中對t的任何賦值下均為真。（2）x不在A（t）中約束出現(xiàn)。存在量詞引入規(guī)則規(guī)則成立的條件：（1）c是特定的個體常元。（2）x不在A（c）中出現(xiàn)。第四章謂詞演算的推理理論4.1謂詞演算的永真推理系統(tǒng)4.2謂詞演算的假設(shè)推理系統(tǒng)4.2.1假設(shè)推理系統(tǒng)的組成及證明方法4.2.2推理過程的推導(dǎo)過程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)全稱量詞消去規(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）全稱量詞消去解推理并不正確。如果給定解釋I：個體域為實數(shù)集，F(xiàn)（x，y）：x＞y。則?x?yF（x，y）意為“對于每個實數(shù)x，均存在著比之更小的實數(shù)y”，這是一個真命題。而?yF（y，y）意為“存在著比自己小的實數(shù)”，是假命題。之所以出現(xiàn)這樣的錯

5、誤,是因為?yF（x，y）中有1個自由變元x,而?yF（y，y）中無自由變元。例下面推理是否正確？設(shè)前提為?x?yF（x，y），（1）?x?yF（x，y）前提引入（2）?yF（t，y）全稱量詞消去（3）F（t，c）存在量詞消去（4）?xF（x，c）全稱量詞引入（5）?y?xF（x，y）存在量詞引入解：推理并不正確。如果給定解釋I：個體域為實數(shù)集，F(xiàn)(x,y)：x＞y。則?x?yF（x，y）為真，而?y?xF（x，y）意為“存在著最小實數(shù)”，是假命題，故知推理不正確。之所以出現(xiàn)這樣的錯誤，是在第（3）步中，?yF（t，y）非閉式（含有自由變元t)。例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)全稱量詞消去規(guī)則(5)Q(e)(3)(4)分離(6)Q(e)??xQ(x)公理21+全稱量詞消去規(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)已知知識：(1)有些病人喜歡所有的醫(yī)生；(2)所有的病人均不喜歡庸醫(yī)；試證明結(jié)論：所有的醫(yī)生均不是庸醫(yī)。例2(p44)證明：先把知識翻譯為符號公式,令P(e)表示“

7、e為病人”；D(e)表示“e為醫(yī)生”；Q(e)表示“e為庸醫(yī)”；L(e1，e2)表示“e1喜歡e2”；則已知知識翻譯為：(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