第五章一階邏輯等值演算及推理

1、“凡人都呼吸”。第五章 一階邏輯等值演算與推理 可以符號化為兩種形式：x (F(x) G(x)和x (F(x) G(x)它們都是正確的，所以同命題邏輯中一樣，它們是等值的。定義定義5.1 設(shè)A，B是一階邏輯中任意兩個公式，若A B是永真式，則稱A與B是等值等值的。記做AB，稱A B是等值式等值式。 即：x (F(x) G(x) x (F(x) G(x)5.1 一階邏輯等值式與置換規(guī)則 一、幾組基本等值式 第一組 代換實例 由于命題邏輯中的重言式的代換實例都是一階邏輯中的永真式，因而第二章的16組等值式給出的代換實例都是一階邏輯的等值式的模式。例如： xy(F(x,y) G(x,y)xF(x)

2、xF(x) xy(F(x,y)G(x,y) xy(F(x,y)G(x,y)第二組 消去量詞等值式 (2)xA(x) A(a1)A(a2)A(an) 設(shè)個體域為有限域D=a1,a2,an，則有(1)xA(x) A(a1)A(a2)A(an)第三組 量詞否定等值式 設(shè)A(x)是任意的含有自由出現(xiàn)個體變項x的公式，則 1)xA(x) xA(x)2)xA(x) xA(x) 第四組 量詞轄域收縮與擴張等值式 設(shè)A(x)是任意的含自由出現(xiàn)個體變項x的公式，B中不含x的出現(xiàn)，則 x(BA(x) B xA(x) 1) x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)B2

3、) x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x) B xA(x) 第五組 量詞分配等值式 設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個體變項x的公式，則(1) x(A(x)B(x)）xA(x)xB(x)(2) x(A(x)B(x)）xA(x) xB(x) 二、基本規(guī)則 一階邏輯中的置換規(guī)則與命題邏輯中的置換規(guī)則形式上完全相同，只是在這里A，B是一階邏輯公式。 1置換規(guī)則 設(shè)(A)是含公式A的公式，(B)是用公式B取代(A)中所有的A之后的公式，若AB，則(A) (B).2換名規(guī)則 設(shè)A為一公式，將A中某量詞轄域中某約束變項的所有出現(xiàn)及相應(yīng)

4、的指導(dǎo)變元改成該量詞轄域中未曾出現(xiàn)過的某個體變項符號，公式的其余部分不變，設(shè)所得公式為A，則AA. 3代替規(guī)則 設(shè)A為一公式，將A中某個自由出現(xiàn)的個體變項的所有出現(xiàn)用A中未曾出現(xiàn)過的個體變項符號代替，A中其余部分不變，設(shè)所得公式為A，則AA. 三、等值演算 例例5.1 將下面公式化成與之等值的公式，使其沒有既是約束出現(xiàn)又是自由出現(xiàn)的個體變項。(1) xF(x,y,z)yG(x,y,z)解解： xF(x,y,z)yG(x,y,z) tF(t,y,z) yG(x,y,z) (換名規(guī)則) tF(t,y,z) wG(x,w,z) (換名規(guī)則) 或 xF(x,y,z)yG(x,y,z) xF(x,t,z

5、) yG(x,y,z) (代替規(guī)則) xF(x,t,z) yG(w,y,z) (代替規(guī)則)(2) x(F(x,y) yG(x,y,z) x(F(x,t) yG(x,y,z) (代替規(guī)則) 或：x(F(x,y)yG(x,y,z) x(F(x,y)tG(x,t,z) (換名規(guī)則) 例例5.2 證明1)x(A(x)B(x) xA(x)xB(x)2)x(A(x)B(x) xA(x)xB(x)其中A(x)，B(x)為含x自由出現(xiàn)的公式。 證證 (1)只要證明在某個解釋下兩邊的式子不等值。 取解釋I：個體域為自然數(shù)集合N；取F(x)：x是奇數(shù)，代替A(x)；取G(x)：x是偶數(shù)，代替B(x). 則x(F(

6、x)G(x)為真命題，而xF(x)xG(x)為假命題。兩邊不等值。在同樣的解釋I下，下， x(A(x)B(x) 為假命題， xA(x)xB(x)為真命題，兩邊不等值。全稱量詞對無分配律存在量詞對無分配律例例5.3 設(shè)個體域為Da,b,c，將下面各公式的量詞消去：1) x(F(x)G(x) 2) x(F(x)yG(y) xF(x)yG(y) (F(a)F(b)F(c)(G(a)G(b)G(c) (F(a)G(a)(F(b)G(b)(F(c)G(c) 3) xyF(x,y) x(F(x,a)F(x,b)F(x,c) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c) (F

7、(c,a)F(c,b)F(c,c) 例5.4 給定解釋I如下：(a) 個體域D=3,4。(b) (x)為 (3)=4， (4)=3。(c) (x,y)為 (3,3)= (4,4)=0， (3,4)= (4,3)=1。 fffFFFFF試求下列公式在I下的真值： (1) xyF(x,y) (F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10) 1(2) xyF(x,y)(F(3,3)F(3,4)(F(4,3)F(4,4)(01)(10)0(3) xy(F(x,y)F(f(x),f(y) (F(3,3)F(f(3),f(3) (F(4,3)F(f(4),f(3) (F(3,4)F(

8、f(3),f(4)(F(4,4)F(f(4),f(4) (00)(11)(11)(00) 1例5.5 證明下列等值式 1）x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) （德.摩根律） x(F(x)G(x) （量詞否定等值式） x(F(x)G(x) （蘊涵等值式）2） x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) （蘊涵等值式） x(F(x)G(x) （量詞否定等值式） x(F(x)G(x) （德.摩根律）3） x(F(x)y(F(y)H(x,y)L(x,y) xy(F(x)F(y)H(x,y)L(x,y) x y(F(x)F(y)H(x,y)L(x,y)

9、 （蘊涵等值式） x(F(x) y(F(y)H(x,y)L(x,y)xy(F(x)(F(y)H(x,y)L(x,y) （轄域擴張等值式）xy(F(x)（(F(y)H(x,y)）L(x,y) （蘊涵等值式） x y(F(x)F(y)H(x,y)L(x,y) （德.摩根律）5.2 一階邏輯的前束范式 定義定義5.2 設(shè)A為一個一階邏輯公式，若A具有如下形式Q1x1Q2x2QkxkB 則稱A為前束范式前束范式，其中Qi(1ik)為 或，B為不含量詞的公式。例如，xy(F(x)G(y)H(x，y) xyz(F(x)G(y)H(z)L(x，y，z)都是前束范式 而：x(F(x)y(G(y)H(x，y)

10、x(F(x)y(G(y)H(x，y) 都不是前束范式 定理定理5.1 (前束范式存在定理)一階邏輯中的任何公式都存在與之等值的前束范式。 例例5.6 求下面公式的前束范式： (1) xF(x)xG(x)解：解： xF(x)yG(y) xF(x)yG(y) x(F(x)yG(y) xy(F(x)G(y) x(F(x)G(x) 或者 xF(x)xG(x) xF(x)xG(x) 由此可知，前束范式是不唯一的。 (2) xF(x)xG(x) xF(x) xG(x) xF(x) yG(y) (換名規(guī)則) x(F(x) yG(y) xy(F(x) G(x)？ x(F(x)G(y) 說明：1、一個公式的前束

11、范式的各指導(dǎo)變元應(yīng)是各個不同的。2、原公式中自由出現(xiàn)的個體變項在前束范式中還應(yīng)是自由出現(xiàn)的。例5.7 求下列公式的前束范式 （1） xF(x) yG(x,y) （2） xF(x,y) xG(x,y) （3） x1(F(x1,x2) x2G(x2) x2H(x1,x2) 5.3 一階邏輯推理理論 推理的形式結(jié)構(gòu)依然采用蘊含式的的形式：A1A2Ak BA1A2Ak B若該式為永真式，則稱推理正確，稱B是前提A1A2Ak的有效結(jié)論。記為：同樣也可以寫成如下形式：前提： A1，A2，Ak結(jié)論： B在一階邏輯中，稱永真式的蘊涵式為推理定律。推理定律的主要來源有：第一組 命題邏輯推理定律的代換實例。例如：

12、xF(x)yG(y) xF(x)xF(x)xF(x)yG(y)第二組 由基本等值式生成的推理定律。 xF(x)xF(x) xF(x) xF(x) xF(x)xF(x) xF(x) xF(x) 和每個等值式可生成兩個推理定律 第三組 關(guān)于量詞分配的推理定律。(1) xA(x)xB(x) x(A(x) B(x)）(2) x(A(x) B(x)） xA(x) xB(x)(3) x(A(x) B(x) ) xA(x)xB(x)(4) x(A(x) B(x) ) xA(x) xB(x)(5) x(A(x) B(x) ) xA(x) xB(x)在命題邏輯中判斷推理的方法很多，可以通過等值演算，真值表，構(gòu)造

13、證明法。但在一階邏輯中很困難，主要是通過構(gòu)造證明法。為了構(gòu)造推理系統(tǒng)，給出四條推理規(guī)則：1全稱量詞消去規(guī)則(簡記為UI規(guī)則或UI)()(yAxxA或)()(cAxxA兩式成立的條件是：1）在第一式中，取代x的y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個體變項。2）在第二式中，c為任意個體常項。3）用y或c去取代A(x)中自由出現(xiàn)的x時，一定要在x自由出現(xiàn)的一切地方進(jìn)行取代。2全稱量詞引入規(guī)則(簡記為UG規(guī)則或UG)()(xxAyA該式成立的條件是：1）無論A(y)中自由出現(xiàn)的個體變項y取何值，A(y)應(yīng)該均為真。2）取代自由出現(xiàn)的y的x也不能在A(y)中約束出現(xiàn)。 3存在量詞引入規(guī)則(簡稱EG規(guī)則或

14、EG)()(xxAcA該式成立的條件是：1）c是特定的個體常項。2）取代c的x不能在A(c)中出現(xiàn)過。 該式成立的條件是： 4存在量詞消去規(guī)則(簡記為EI規(guī)則或EI) )()(cAxxA（1）c是使A為真的特定的個體常項。（2）c不在A(x)中出現(xiàn)。（3）若A(x)中除自由出現(xiàn)的x外，還有其它自由出現(xiàn)的個體變項，此規(guī)則不能使用。 只能對前束范式使用UI，UG，EI，EG規(guī)則。例例5.8 設(shè)個體域為實數(shù)集合，F(xiàn)(x,y):xy。G(X):X是偶數(shù)，指出下面使用規(guī)則的錯誤。),(),(yyyFyxyFxUI規(guī)則),(),(xxxFxyxxFUG規(guī)則),()5 ,(xxxFxxxFEG規(guī)則)3()(

15、GxxGEI規(guī)則定義定義5.3 一階邏輯自然推理系統(tǒng)自然推理系統(tǒng)F定義如下：1、 字母表。同一階語言L的字母表2、合式公式。同L合式公式的定義3 、推理規(guī)則： （1） 前提引入規(guī)則。 （2） 結(jié)論引入規(guī)則。 （3） 置換規(guī)則。 （4） 假言推理規(guī)則。 （5） 附加規(guī)則。 （6） 化簡規(guī)則。 （7） 拒取式規(guī)則。 （8） 假言三段論規(guī)則。 （9） 析取三段論規(guī)則。 （10）構(gòu)造性二難推理規(guī)則。 （11）合取引入規(guī)則。 （12）UI規(guī)則。 （13）UG規(guī)則。 （14）EI規(guī)則。 （15）EG規(guī)則。 例例5.9 設(shè)個體域為實數(shù)集合，設(shè)個體域為實數(shù)集合，F(xiàn)(x,y)為為xy. 指出在推指出在推理系統(tǒng)理

16、系統(tǒng)F中，以中，以 x yF(x，y)(真命題真命題)為前提，推出為前提，推出 xF(x,c)(假命題假命題)的下述推理證明中的錯誤。的下述推理證明中的錯誤。 x yF(x,y) 前提引入前提引入 yF(z,y) UI規(guī)則規(guī)則 F(z,c) EI規(guī)則規(guī)則 xF(x,c) UG規(guī)則規(guī)則 Z也是自由出現(xiàn)，同時有多個自由出現(xiàn)不能用EI規(guī)則。錯！錯！例例5.10 在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：任何自然數(shù)都是整數(shù)；存在著自然數(shù)。所以存在著整數(shù)。個體域為實數(shù)集合R。 解解 先將原子命題符號化。設(shè) F(x):x為自然數(shù)，G(x):x為整數(shù)。 前提： x(F(x)G(x), xF(x)結(jié)論： xG(

17、x)證明： xF(x) 前提引入 F(c) EI規(guī)則 x(F(x)G(x) 前提引入 F(c)G(c) UI規(guī)則 G(c) 假言推理 xG(x)EG規(guī)則 x(F(x)G(x) 前提引入 F(c)G(c) UI規(guī)則 xF(x) 前提引入 F(c) E1規(guī)則如果證明如下：在中取c=2,則F(2)G(2)為真（前件假）,于是中F(2)為假，這樣從前件真推出了假的中間結(jié)果。注意：在證明序列中先引進(jìn)帶存在量詞的前提。前提： x(F(x)(G(a)R(x), xF(x)結(jié)論： x(F(x)R(x) 證明： x(F(x)R(x) EG xF(x) 前提引入 F(c) EI x(F(x)(G(a)R(x) 前提引入 F(c)(G(a)R(c) UI G(a)R(c) 假言推理 R(c) 化簡 F(c)R(c) 合取所有的人或者是吃素的或者是吃葷的，吃素的常吃豆制品，因而不吃豆制品的人是吃葷的。（個體域為人的集合）。 個體域為人類集合，所以不用引入特性謂詞， 令F(x)：x是吃素的，G(x)：x是吃葷的，H(x)：x吃豆制品。 前提： x(F(x)G(x)， x(F(x)H(x) 結(jié)論： x(H(x)G(x) x(F(x)G(x) 前提引入 F(y)G(y) UI F(y)G(y) 置換證明： x(H(x)G(x) UG F(y)H(y) 置換 H(y)F(y) 置換 H(y)G(y) 假言三段論