第五部分一階邏輯等值演算與推理

目錄

基本等值式

例1 將下面命題用兩種形式符號化, 并證明兩者等值:

例2 將公式化成等值的不含既有約束出現、又有自由出現

例3 設個體域D={a,b,c}, 消去下述公式中的量詞:

例4 求下列公式的前束范式

推理的形式結構

定義5.3 自然推理系統

構造推理證明的實例?

例5?在自然推理系統?中構造下面推理的證明, 取個體域R:

?例6?在自然推理系統?中，構造推理的證明

基本要求?

定義 5.1 設 A , B 是兩個謂詞公式 , 如果 A ? B 是永真式 , 則稱 A 與 B 等值 , 記作 A ? B , 并稱 A ? B 是 等值式

基本等值式

第一組 命題邏輯中 16 組基本等值式的代換實例

例如

??? xF ( x ) ?? xF ( x ),

? xF ( x ) →? yG ( y ) ? ?? xF ( x ) ∨? yG ( y ) 等

第二組

(1) 消去量詞等值式

設 D ={ a 1 , a 2 , … , a n }

① ? xA ( x ) ? A ( a 1 ) ∧ A ( a 2 ) ∧ … ∧ A ( a n )

② ? xA ( x ) ? A ( a 1 ) ∨ A ( a 2 ) ∨ … ∨ A ( a n )

(2) 量詞否定等值式

① ?? xA ( x ) ? ? x ? A ( x )

② ?? xA ( x ) ? ? x ? A ( x )

(3) 量詞轄域收縮與擴張等值式 .

A ( x ) 是含 x 自由出現的公式， B 中不含 x 的自由出現

關于全稱量詞的：

① ? x ( A ( x ) ∨ B ) ? ? xA ( x ) ∨ B

② ? x ( A ( x ) ∧ B ) ? ? xA ( x ) ∧ B

③ ? x ( A ( x ) → B ) ? ? xA ( x ) → B

④ ? x ( B → A ( x )) ? B →? xA ( x )

關于存在量詞的：

① ? x ( A ( x ) ∨ B ) ? ? xA ( x ) ∨ B

② ? x ( A ( x ) ∧ B ) ? ? xA ( x ) ∧ B

③ ? x ( A ( x ) → B ) ? ? xA ( x ) → B

④ ? x ( B → A ( x )) ? B →? xA ( x )

(4) 量詞分配等值式

① ? x ( A ( x ) ∧ B ( x )) ? ? xA ( x ) ∧? xB ( x )

② ? x ( A ( x ) ∨ B ( x )) ? ? xA ( x ) ∨? xB ( x )

注意： ? 對 ∨ ， ? 對 ∧ 無分配律

1. 置換規則

設 Φ ( A ) 是含 A 的公式 , 那么 , 若 A ? B , 則 Φ ( A ) ? Φ ( B ).

2. 換名規則

設 A 為一公式，將 A 中某量詞轄域中個體變項的所有約束 出現及相應的指導變元換成該量詞轄域中未曾出現過的個 體變項符號，其余部分不變，設所得公式為 A ′ ，則 A ′? A .

3. 代替規則

設 A 為一公式，將 A 中某個個體變項的所有自由出現用 A 中 未曾出現過的個體變項符號代替，其余部分不變，設所得 公式為 A ′ ，則 A ′? A

例1 將下面命題用兩種形式符號化, 并證明兩者等值:

(1) 沒有不犯錯誤的人

解令 F ( x ) ： x 是人， G ( x ) ： x 犯錯誤 .

?? 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)) ????????置換規則

? ? x ( F ( x ) → G ( x)) ????????置換

(2) 不是所有的人都愛看電影

解令 F ( x ) ： x 是人， G ( x ) ：愛看電影 .

?? 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)) ????????置換規則

? ? x ( F ( x ) ∧? G (x)) ????????置換規則

例2 將公式化成等值的不含既有約束出現、又有自由出現

的個體變項 : ? x ( F ( x , y , z ) →? yG ( x , y , z ))

解 ? x ( F ( x,y,z ) →? yG ( x,y,z ))

? ? x ( F ( x,y,z ) →? tG ( x,t,z)) ????????換名規則

? ? x ? t ( F ( x,y,z ) → G ( x,t,z)) ????????轄域擴張等值式

或者

? x ( F ( x,y,z ) →? yG ( x,y,z ))

? ? x ( F ( x,u,z ) →? yG ( x,y,z)) ????????代替規則

? ? x ? y ( F ( x,u,z ) → G ( x,y,z)) ????????轄域擴張等值式

這兩個例子很好的解釋了換名規則和代替規則

例3 設個體域D={a,b,c}, 消去下述公式中的量詞:

(1) ? x ? y ( F ( x ) → G ( y ))

解

? x ? y ( F ( x ) → G ( y ))

? ( ? y ( F ( a ) → G ( y ))) ∧ ( ? y ( F ( b ) → G ( y ))) ∧ ( ? y ( F ( c ) → G ( y )))

? (( F ( a ) → G ( a )) ∨ ( F ( a ) → G ( b )) ∨ ( F ( a ) → G ( c ))) ∧ (( F ( b ) → G ( a )) ∨ ( F ( b ) → G ( b )) ∨ ( F ( b ) → G ( c ))) ∧ (( F ( c ) → G ( a )) ∨ ( F ( c ) → G ( b )) ∨ ( F ( c ) → G ( c )))

解法二

? x ? y ( F ( x ) → G ( y ))

? ? x ( F ( x ) →? yG ( y )) 轄域縮小等值式

? ? x ( F ( x ) → G ( a ) ∨ G ( b ) ∨ G ( c ))

? ( F ( a ) → G ( a ) ∨ G ( b ) ∨ G ( c )) ∧ ( F ( b ) → G ( a ) ∨ G ( b ) ∨ G ( c )) ∧ ( F ( c ) → G ( a ) ∨ G ( b ) ∨ G ( c ))

(2) ? x ? yF ( x,y )

? x ? yF ( 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 ( c,a ) ∧ F ( c , b ) ∧ F ( c , c ))

定義 5.2 設 A 為一個一階邏輯公式，若 A 具有如下形式 Q 1 x 1 Q 2 x 2 … Q k x k B 則稱 A 為 前束范式 ，其中 Q i (1 ≤ i ≤ k ) 為 ? 或 ? ， B 為不含量詞 的公式 .

例如

? x ? ( F ( x ) ∧ G ( x ))

? x ? y ( F ( x ) → ( G ( y ) ∧ H ( x , y ))) 是前束范式

而 ?? x ( F ( x ) ∧ G ( x ))

? x ( F ( x ) →? y ( G ( y ) ∧ H ( x , y ))) 不是前束范式，

定理 5.1 （前束范式存在定理）

一階邏輯中的任何公式都存在與之等值的前束范式

例4 求下列公式的前束范式

(1) ?? x ( M ( x ) ∧ F ( x ))

解 ?? x ( M ( x ) ∧ F ( x ))

? ? x ( ? M ( x ) ∨? F ( x )) （量詞否定等值式）

? ? x ( M ( x ) →? F ( x ))

后兩步結果都是前束范式，說明公式的前束范式不唯一

(2) ? xF ( x ) ∧?? xG ( x )

解 ? xF ( x ) ∧?? xG ( x )

? ? xF ( x ) ∧? x ? G ( x ) 量詞否定等值式

? ? x ( F ( x ) ∧? G ( x )) 量詞分配等值式

或

? xF ( x ) ∧?? xG ( x )

? ? xF ( x ) ∧? x ? G ( x ) 量詞否定等值式

? ? xF ( x ) ∧? y ? G ( y ) 換名規則

? ? x ? y ( F ( x ) ∧? G ( y )) 轄域收縮擴張規則

(3) ? xF ( x ) →? y ( G ( x , y ) ∧? H ( y ))

解 ? xF ( x ) →? y ( G ( x , y ) ∧? H ( y ))

? ? zF ( z ) →? y ( G ( x , y ) ∧? H ( y )) 換名規則

? ? z ? y ( F ( z ) → ( G ( x , y ) ∧? H ( y ))) 轄域收縮擴張規則

或

? ? xF ( x ) →? y ( G ( z , y ) ∧? H ( y )) 代替規則

? ? x ? y ( F ( x ) → ( G ( z , y ) ∧? H ( y )))

推理的形式結構

1. A 1 ∧ A 2 ∧…∧ A k → B

若次式是永真式 , 則稱推理正確 , 記作 A 1 ∧ A 2 ∧…∧ A k ? B

2. 前提 : A 1 , A 2 , … , A k

結論 : B

推理定理 : 永真式的蘊涵式

第一組 命題邏輯推理定理的代換實例

如 , ? xF ( x ) ∧? yG ( y ) ? ? xF ( x )

第二組 基本等值式生成的推理定理

如 , ? xF ( x ) ???? xF ( x ), ??? xF ( x ) ?? xF ( x )

?? xF ( x ) ?? x ? F ( x ), ? x ? F ( x ) ? ?? xF ( x )

第三組 其他常用推理定律

(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 )

1. 全稱量詞消去規則 ( ? -)

? xA ( x)或? xA ( x )

———? ? ———

∴ A ( y)? ? ??∴ A (c )

其中 x , y 是個體變項符號 , c 是個體常項符號 , 且在 A 中 x 不在 ? y 和 ? y 的轄域內自由出現

2. 全稱量詞引入規則 ( ? +)

????A( x )

————

∴? xA ( x )

其中 x 是個體變項符號 , 且不在前提的任何公式中自由出現

3. 存在量詞消去規則 ( ? -)

?A( x ) → B

—————

∴? xA ( x ) → B

其中 x 是個體變項符號 , 且不在前提的任何公式和 B 中自由 出現

4. 存在量詞引入消去規則 ( ? +)

A(y)??????????或??????B→A(y)

————? ? ? ? ?—————

∴? xA (x)?????????∴B →? xA ( x )

A(c)??????????或??????B→A(c)

————? ? ? ? ?—————

∴? xA (x)?????????∴B →? xA ( x )

其中 x , y 是個體變項符號 , c 是個體常項符號 , 且在 A 中 y 和 c 不在 ? x 和 ? x 的轄域內自由出現 .

定義5.3 自然推理系統

推理規則 :

(1) 前提引入規則

(2) 結論引入規則

(3) 置換規則

(4) 假言推理規則

(5) 附加規則

(6) 化簡規則

(7) 拒取式規則

(8) 假言三段論規則

(9) 析取三段論規則

(10) 構造性二難推理規則

(11) 合取引入規則

(12) ? - 規則

(13) ? + 規則

(14) ? - 規則

(15) ? + 規則

構造推理證明的實例?

例5?在自然推理系統?中構造下面推理的證明, 取個體域R:

不存在能表示成分數的無理數 . 有理數都能表示成分數 .

所以 , 有理數都不是無理數 .

解

設 F ( x ): x 是無理數 , G ( x ): x 是有理數 , H ( x ): x 能表示成分數 .

前提 : ?? x ( F ( x ) ∧ H ( x )), ? x ( G ( x ) → H ( x ))

結論 : ? x ( G ( x ) →? F ( x ))

證明 :

① ?? x ( F ( x ) ∧ H ( x)) ????????前提引入

② ? x ( ? F ( x ) ∨? H (x)) ????????①置換規則

③ ? x ( F ( x ) →? H (x)) ????????②置換規則

④ F ( x ) →? H ( x) ????????③ ?-

⑤ ? x ( G ( x ) → H ( x)) ????????前提引入

⑥ G ( x ) → H ( x) ????????⑤ ? -

⑦ H ( x ) →? F (x) ????????④置換規則

⑧ G ( x ) →? F ( x) ????????⑥⑦假言三段論

⑨ ? x ( G ( x ) →? F ( x)) ????????⑧ ? +

要特別注意使用 ? - 、 ? + 、 ? - 、 ? + 規則的條件

例6?在自然推理系統?中，構造推理的證明

人都喜歡吃蔬菜．但不是所有的人都喜歡吃魚．所以, 存在喜歡吃蔬菜而不喜歡吃魚的人

解

令 F ( x ): x 為人， G ( x ): x 喜歡吃蔬菜， H ( x ): x 喜歡吃魚

前提： ? x ( F ( x ) → G ( x )), ?? x ( F ( x ) → H ( x ))

結論： ? x ( F ( x ) ∧ G ( x ) ∧? H ( x ))

證明：用歸謬法

(1) ?? x ( F ( x ) ∧ G ( x ) ∧? H ( x)) ????????結論否定引入

(2) ? x ? ( F ( x ) ∧ G ( x ) ∧? H ( x)) ????????(1)置換規則

(3) ? ( F ( y ) ∧ G ( y ) ∧? H ( y)) ????????(2)??

(4) G ( y ) → ? F ( y ) ∨ H ( y) ????????(3)置換規則

(5) ? x ( F ( x ) → G ( x)) ????????前提引入

(6) F ( y ) → G ( y) ????????(5)??

(7) F ( y ) → ? F ( y ) ∨ H ( y) ????????(4)(6)假言三段論

(8) F ( y ) → H ( y) ????????(7)置換規則

(9) ? y ( F ( y ) → H ( y)) ????????(8)? +

(10) ? x ( F ( x ) → H ( x)) ????????(9)置換規則

(11) ?? x ( F ( x ) → H ( x)) ????????前提引入

(12) 0 ????????(10)(11)合取

注意：

如果不明白什么是置換規則可以去看第二部分命題邏輯等值演算，簡單來說置換規則就是基本等值式

基本要求?

深刻理解并牢記一階邏輯中的重要等值式 , 并能準確而熟 練地應用它們

熟練正確地使用置換規則、換名規則、代替規則

熟練地求出給定公式的前束范式

深刻理解自然推理系統 N L 的定義，牢記 N L 中的各條推理 規則，特別是注意使用 ?? 、 ? + 、 ? + 、 ?? 4 條推理規則的 條件

能正確地給出有效推理的證明