一階邏輯等值式與置換規(guī)則ppt課件

1、1第五章第五章 一階邏輯等值演算與推理一階邏輯等值演算與推理5.1 5.1 一階邏輯等值式與置換規(guī)那一階邏輯等值式與置換規(guī)那么么2 定義定義5.15.1等值式等值式 設(shè)設(shè)A A，B B是一階邏輯中恣意兩是一階邏輯中恣意兩個公式，假設(shè)個公式，假設(shè)A AB B是永真式，那么稱是永真式，那么稱A A和和B B是等值的，是等值的，記作記作A AB B，稱，稱A AB B是等值式。是等值式。 下面給出一階邏輯中的一些根本而重要的等值式： 由于命題邏輯的重言式的代換實例都是一階邏輯的永真式，所以命題邏輯中24個等值式方式p.24給出的代換實例都是一階邏輯的等值式方式。例如：xFxxFx xyFx，yGx，

2、y xyFx，yGx，y 等都是AA的代換實例。3 下面引見一些一階邏輯固有的等值式，這些等值式都與量詞有關(guān)。 1、消去量詞等值式 設(shè)個體域為有限集D=a1，a2，an，那么有 1xAx Aa1Aa2Aan 2xAx Aa1Aa2Aan 2、量詞否認等值式 對于恣意的公式Ax： 1xAxxAx 2xAxxAx 4 3、量詞轄域收縮與擴張等值式 設(shè)Ax是恣意的含自在出現(xiàn)個體變項x的公式，B是不含x的公式，那么 1xAxBxAxB xAxBxAxB xAxBxAxB xB Ax BxAx 2xAxB xAxB xAxB xAxB xAxB xAxB xBAx BxAx5 4、量詞分配等值式 對于恣

3、意的公式Ax和Bx： 1xAxBxxAxx Bx 2xAxBx xAxx Bx 闡明：量詞分配等值式中，只需闡明：量詞分配等值式中，只需對對的分配和的分配和對對的分配的等值式。而的分配的等值式。而對對和和對對無分配律。無分配律。65、同種量詞順序置換等值式 對于恣意的公式Ax，y (1)xyAx，y yxAx，y (2)xyAx，y yxAx，y7一階邏輯的等值演算一階邏輯的等值演算一階邏輯的等值演算中三條重要的規(guī)那么：一階邏輯的等值演算中三條重要的規(guī)那么： 1 1、置換規(guī)那么、置換規(guī)那么 設(shè)設(shè)(A)(A)是含公式是含公式A A的公式，的公式，(B)(B)是用公是用公式式B B置換了置換了(A

4、)(A)中一切的中一切的A A后得到的公式，假后得到的公式，假設(shè)設(shè)A AB B，那么，那么(A) (A) (B)(B)。8例例 設(shè)個體域為設(shè)個體域為D=aD=a，b b，cc，將下面公式的量詞消去。，將下面公式的量詞消去。1 1x xF Fx xGGx x2 2x xF Fx xyGyGy y3 3x xyFyFx x，y y解：解：1 1x xF Fx xGGx x F Fa aGGa a F Fb bGGb b F Fc cGGc c 2 2x xF Fx xyGyGy y xFxFx xyGyGy y F Fa aFFb bFFc c G Ga aGGb bGGc c93 3x xyFy

5、Fx x，y y x xF Fx x，a aFFx x，b bFFx x，c c F Fa a，a aFFa a，b bFFa a，c c F Fb b，a aFFb b，b bFFb b，c c F Fc c，a aFFc c，b bFFc c，c c10例例 給定解釋給定解釋I I如下：如下：a a個體域個體域D=2D=2，33； b bD D中特定元素中特定元素a=2a=2c cD D上特定函數(shù)上特定函數(shù)f fx x為：為：f f2 2=3=3，f f3 3=2=2d dD D上特定謂詞上特定謂詞 G Gx x，y y為：為：G G2 2，2 2= G= G2 2，3 3= G= G3

6、3，2 2=1=1， G G3 3，3 3=0=0。 L Lx x，y y為：為：L L2 2，2 2= L= L3 3，3 3=1=1， L L2 2，3 3= L= L3 3，2 2=0=0。 F Fx x為：為：F F2 2=0=0，F(xiàn) F3 3=1=1。 在在I I下求以下各式的真值。下求以下各式的真值。1 1x x F Fx x G Gx x，a a2 2x x F Ff fx x G Gx x，f fx x3 3x x y Ly Lx x，y y4 4y y x Lx Lx x，y y11解：解：1 1x xF Fx xGGx x，a aF F2 2GG2 2，a aF F3 3G

7、G3 3，a aF F2 2GG2 2，2 2F F3 3GG3 3，2 201011111 0 02 2x xF Ff fx xGGx x，f fx xF Ff f2 2GG2 2，f f2 2 F Ff f3 3GG3 3，f f3 3F F3 3GG2 2，3 3F F2 2GG3 3，2 211110101 1 1123 3x x y Ly Lx x，y yx xL Lx x，2 2LLx x，3 3L L2 2，2 2LL2 2，3 3 L L3 3，2 2LL3 3，3 310100101 1 14 4y y x Lx Lx x，y y y yL L2 2，y yLL3 3，y y

8、L L2 2，2 2LL3 3，2 2 L L2 2，3 3LL3 3，3 310100101 0 0留意：留意：x xyLyLx x，y yy yx Lx Lx x，y y，闡明量詞的次序不能隨意顛，闡明量詞的次序不能隨意顛倒。倒。 13例例 證明以下各等值式。證明以下各等值式。1 1x x M Mx xFFx x x x M Mx xFFx x2 2x x F Fx xGGx x x x F Fx xGGx x3 3x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y4 4x x y y F Fx xGGy yLLx x，y y

9、 x x y y F Fx xGGy yLLx x，y y14證明：證明： 1 1x xM Mx xFFx xx xM Mx xFFx x x xM Mx xFFx x x x M Mx xFFx x x xMMx xFFx x x xM Mx xFFx x 2 2x xF Fx xGGx xx xF Fx xGGx x x xF Fx xGGx x x x F Fx xGGx x x x FFx xGGx x x xF Fx xGGx x 153 3x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y 證明：證明： x x y y

10、 F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y x x y y F Fx xGGy yHHx x，y y4 4x x y y F Fx xGGy yLLx x，y y x x y y F Fx xGGy yLLx x，y y 證明與證明與3 3類似，略類似，略 16一階邏輯的等值演算一階邏輯的等值演算一階邏輯的等值演算中三條重要的規(guī)那么：一階邏輯的等值演算中三條重要的規(guī)那么： 1 1、置換規(guī)那么、置換規(guī)那么 設(shè)設(shè)(A)(A)是

11、含公式是含公式A A的公式，的公式，(B)(B)是用公是用公式式B B置換了置換了(A)(A)中一切的中一切的A A后得到的公式，假后得到的公式，假設(shè)設(shè)A AB B，那么，那么(A) (A) (B)(B)。 2 2、換名規(guī)那么、換名規(guī)那么 設(shè)設(shè)A A為一公式，將為一公式，將A A中某量詞轄域中某約束中某量詞轄域中某約束變項的一切出現(xiàn)及相應(yīng)的指點變元，改成該量變項的一切出現(xiàn)及相應(yīng)的指點變元，改成該量詞轄域中未曾出現(xiàn)過的某個體變項符號，公式詞轄域中未曾出現(xiàn)過的某個體變項符號，公式中其他部分不變，設(shè)所得公式為中其他部分不變，設(shè)所得公式為A A，那么，那么A AA A。17解：解： xFx，y，zyG

12、x，y，z sFs，y，zyGx，y，z換名規(guī)那么換名規(guī)那么 sFs，y，ztGx，t，z換名規(guī)那么換名規(guī)那么 例例 將下面公式化成與之等值的公式，使其沒有既是將下面公式化成與之等值的公式，使其沒有既是約束出現(xiàn)的又是自在出現(xiàn)的個體變項。約束出現(xiàn)的又是自在出現(xiàn)的個體變項。 xFxFx x，y y，z zyGyGx x，y y，z z18一階邏輯的等值演算中三條重要的規(guī)那么： 1、置換規(guī)那么 設(shè)(A)是含公式A的公式，(B)是用公式B置換了(A)中一切的A后得到的公式，假設(shè)AB，那么(A) (B)。 2、換名規(guī)那么 設(shè)A為一公式，將A中某量詞轄域中某約束變項的一切出現(xiàn)及相應(yīng)的指點變元，改成該量詞轄

13、域中未曾出現(xiàn)過的某個體變項符號，公式中其他部分不變，設(shè)所得公式為A，那么AA。 3、替代規(guī)那么 設(shè)A為一公式，將A中某個自在出現(xiàn)的個體變項的一切出現(xiàn)用A中未曾出現(xiàn)過的個體變項符號替代，公式中其他部分不變，設(shè)所得公式為A，那么AA。19解：解： 1xFx，y，zyGx，y，z sFs，y，zyGx，y，z換名規(guī)那么換名規(guī)那么 sFs，y，ztGx，t，z換名規(guī)那么換名規(guī)那么 xFx，y，zyGx，y，z xFx，s，zyGx，y，z替代規(guī)那么替代規(guī)那么 xFx，s，zyGt，y，z替代規(guī)那么替代規(guī)那么 例例 將下面公式化成與之等值的公式，使其沒有既是將下面公式化成與之等值的公式，使其沒有既是約束

14、出現(xiàn)的又是自在出現(xiàn)的個體變項。約束出現(xiàn)的又是自在出現(xiàn)的個體變項。 1 1xFxFx x，y y，z zyGyGx x，y y，z z 2 2x xF Fx x，y yyGyGx x，y y，z z202 2x xF Fx x，y yyGyGx x，y y，z z x xF Fx x，t tyGyGx x，y y，z z替代規(guī)那么替代規(guī)那么 x xF Fx x，y yyGyGx x，y y，z z x xF Fx x，y ytGtGx x，t t，z z換名規(guī)那么換名規(guī)那么21第五章第五章 一階邏輯等值演算與推理一階邏輯等值演算與推理5.2 5.2 一階邏輯前束范式一階邏輯前束范式22 定義定義

15、5.25.2前束范式前束范式 設(shè)設(shè)A A為一個一階邏為一個一階邏輯公式，假設(shè)輯公式，假設(shè)A A具有如下方式具有如下方式Q1x1Q2x2QkxkBQ1x1Q2x2QkxkB，那么稱那么稱A A為前束范式為前束范式,Qi,Qi1ik1ik為為或或，B B為不含量詞的公式。為不含量詞的公式。例如：x yFxGyHx，yx y zFxGyHzLx，y，z 等公式都是前束范式。x Fxx GxxFxyGyHx，y 等公式都不是前束范式。 留意：前束范式中不存在既是自在出現(xiàn)的，又是約束出現(xiàn)的個體變項。23定理5.1前束范式存在定理 一階邏輯中的任何公式都存在與之等值的前束范式。 闡明： 1定理闡明任何公式

16、的前束范式都是存在的，但并不獨一。 2可利用上節(jié)的等值式和三條變換規(guī)那么來求公式的前束范式。24例5.6 求下面公式的前束范式。 1x Fxx Gx 2x Fxx Gx 3x Fxx Gx 4x Fxx Gx 5x Fx，yy Gx，y 6x Fx，yy Gyx Hx，y，z25 1 1x Fx Fx xx Gx Gx x方法一：方法一： x Fx Fx xxGxGx x等值置換等值置換 x xF Fx xGGx x方法二：方法二： x Fx Fx xy Gy Gy y換名規(guī)那換名規(guī)那么么 x Fx Fx xy Gy Gy y x xF Fx xy Gy Gy y x x y yF Fx x

17、G Gy y262 2xFxFx xxGxGx x xFxFx xxGxGx x x xF Fx xGGx x 錯誤！錯誤！ 由于由于對對沒有分配律！沒有分配律！ 正確解法如下：正確解法如下： xFxFx xxGxGx x xFxFx xxGxGx x xFxFx x yGyGy y x xy yF Fx x G Gy y273 3xFxFx xxGxGx x方法一：方法一： yFyFy yxGxGx x y(Fy(Fy yxGxGx x) ) y yx(Fx(Fy yGGx x) )方法二：方法二： xFxFx xxGxGx x xFxFx xxGxGx x x xFFx xGGx x方法三

18、：方法三： x xy(Fy(Fx xGGy y) )284 4x Fx Fx xx Gx Gx x方法一：方法一： x Fx Fx xy Gy Gy y x (Fx (Fx xy Gy Gy y) ) x xy (Fy (Fx xGGy y) )方法二：方法二： y yx(Fx(Fy yGGx x) )方法三：方法三： x Fx Fx x x Gx Gx x xFxFx x x Gx Gx x xFxFx x y Gy Gy y x xy(Fy(Fx x G Gy y) ) x xy (Fy (Fx xGGy y) )295 5x Fx Fx x，y yy Gy Gx x，y y方法一：方法一： t Ft Ft t，y ys Gs Gx x，s s換名規(guī)那么換名規(guī)那么 t ts s F Ft t，y yGGx x，s s方法二：方法二： x Fx Fx x，y yy Gy Gx x，y y x Fx Fx x，t ty Gy Gs s，y y 替代規(guī)那么替代規(guī)那么 x xy yF Fx x，t tGGs s，y y306 6x Fx Fx x，y yy Gy Gy yx Hx Hx x，y y，z z方法一：方法一： sFsFs s，y yt Gt Gt txHxHx x，y y，z z s st tF Fs s，y yGGt txHxHx x，y y，