離散一階邏輯等值演算和推理

1、5.1 一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則 5.2 一階邏輯的前束范式一階邏輯的前束范式 第五章一階邏輯等值演算和推理第五章一階邏輯等值演算和推理5.3 一階邏輯的推理理論一階邏輯的推理理論 A = xF(x) xF(x) 5.1一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則variable renaming 5.1一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則5.1一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則5.2一階邏輯的前束范式一階邏輯的前束范式第五章一階邏輯等值演算和推理第五章一階邏輯等值演算和推理5.3一階邏輯的推理理論一階邏輯的推理理論作業(yè)：作業(yè)：習(xí)題五習(xí)題五

2、 2（1），（），（3） 12（1），（），（2）預(yù)習(xí)：預(yù)習(xí)：5.3 一階邏輯的推理理論一階邏輯的推理理論Thank you !5.1一階邏輯等值式與置換規(guī)則一階邏輯等值式與置換規(guī)則5.2一階邏輯的前束范式一階邏輯的前束范式第五章一階邏輯等值演算和推理第五章一階邏輯等值演算和推理5.3一階邏輯的推理理論一階邏輯的推理理論在一階邏輯中在一階邏輯中, 推理推理 = A1, A2, , Ak | B的的形式結(jié)構(gòu)形式結(jié)構(gòu)是條件式是條件式A1 A2 Ak B.若該條件式是永真式若該條件式是永真式, 則稱該推理則稱該推理是是有效的有效的: |=B; 否則稱為否則稱為無(wú)效的無(wú)效的: | B.判斷一階邏輯永真

3、式比判斷命題邏輯重言式困難判斷一階邏輯永真式比判斷命題邏輯重言式困難得多得多. 下面采用在形式系統(tǒng)中構(gòu)造證明的方法下面采用在形式系統(tǒng)中構(gòu)造證明的方法.valid, invalid注意：本節(jié)內(nèi)容不使用教材例題的方法注意：本節(jié)內(nèi)容不使用教材例題的方法推理定律推理定律(永真蘊(yùn)涵式永真蘊(yùn)涵式)有下面這些有下面這些. A B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A B, B A, x A(x)A(y) x A(x)A(c) - 規(guī)則規(guī)則1. 全稱量詞消去規(guī)則（全稱量詞消去規(guī)則（UI規(guī)則）規(guī)則） A(y)xA(x) + 規(guī)則規(guī)則2.全稱量詞引入規(guī)則（全稱量詞引入規(guī)則（UG規(guī)則）規(guī)則） A(c)xA(x) + 規(guī)則規(guī)則 x A( x)A( c) - 規(guī)則規(guī)則new例例 證明蘇格拉底三段論證明蘇格拉底三段論: 人都是要死的人都是要死的. 蘇格拉底蘇格拉底是人是人. 所以所以, 蘇格拉底是要死的蘇格拉底是要死的.解解 設(shè)設(shè) H(x) 為為 x 是人是人; H(x) 為為 x 是要死的是要死的; a 為蘇格為蘇格拉底拉底, 則推理為則推理為前提前提: x(H(x) M(x), H(a).結(jié)論結(jié)論: M(a).形式結(jié)構(gòu)為形式結(jié)構(gòu)為 x(H(x) M(x) H(a) M(a).在命題邏輯中無(wú)法證明在命題邏輯中無(wú)法證明證明證明: x(H(x) M(x) 前提引入前提引入 H(a