離散數(shù)學(xué)第一部分?jǐn)?shù)理邏輯2

1、12.3 一階邏輯等值式與前束范式等值式基本等值式 量詞否定等值式 量詞轄域收縮與擴(kuò)張等值式 量詞分配等值式前束范式 2等值式與基本等值式 基本等值式:命題邏輯中16組基本等值式的代換實(shí)例如，xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 消去量詞等值式 設(shè)D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an)定義 若AB為邏輯有效式，則稱A與B是等值的，記作 AB，并稱AB為等值式. 3基本等值式(續(xù))量詞轄域收縮與擴(kuò)張等值式 設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn)關(guān)于全稱量詞的： x(

2、A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x) 關(guān)于存在量詞的: x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)4基本的等值式(續(xù))量詞否定等值式設(shè)A(x)是含x自由出現(xiàn)的公式 xA(x) x A(x) xA(x)x A(x)量詞分配等值式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x)注意：對(duì)無(wú)分配律，對(duì)無(wú)分配律, 即 x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x)5例例 將下面命題

3、用兩種形式符號(hào)化 (1) 沒(méi)有不犯錯(cuò)誤的人 (2) 不是所有的人都愛(ài)看電影解 (1) 令F(x)：x是人，G(x)：x犯錯(cuò)誤. x(F(x)G(x) x (F(x)G(x) x(F(x)G(x) (2) 令F(x)：x是人，G(x)：愛(ài)看電影. x(F(x)G(x) x(F(x)G(x) x(F(x)G(x)6前束范式 例如，xy(F(x)(G(y)H(x,y) x(F(x)G(x)是前束范式, 而 x(F(x)y(G(y)H(x,y) x(F(x)G(x)不是前束范式.定義 設(shè)A為一個(gè)一階邏輯公式, 若A具有如下形式Q1x1Q2x2QkxkB, 則稱A為前束范式, 其中Qi (1ik)為或，

4、B為不含量詞的公式.7換名規(guī)則換名規(guī)則: 將量詞轄域中出現(xiàn)的某個(gè)約束出現(xiàn)的個(gè)體變項(xiàng)及對(duì)應(yīng)的指導(dǎo)變項(xiàng)，改成其他轄域中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，公式中其余部分不變，則所得公式與原來(lái)的公式等值.8公式的前束范式例 求下列公式的前束范式 (1) x(M(x)F(x)解 定理（前束范式存在定理）一階邏輯中的任何公式都存在與之等值的前束范式求前束范式: 使用重要等值式、置換規(guī)則、換名規(guī)則進(jìn)行等值演算. x(M(x)F(x) 量詞否定等值式 x(M(x)F(x) 兩步結(jié)果都是前束范式，說(shuō)明前束范式不惟一.9例(續(xù)) (2) xF(x)xG(x)解xF(x)xG(x) （量詞否定等值式）x(F(x)G(x)

5、（量詞分配等值式）或者 xF(x)xG(x) xF(x)yG(y) ( 換名規(guī)則 ) xy(F(x)G(y) ( 量詞轄域擴(kuò)張 )10例(續(xù)) (3) xF(x)xG(x) 解 xF(x)xG(x) x(F(x)G(x) (4) xF(x)y(G(x,y)H(y)解 zF(z)y(G(x,y)H(y) zy(F(z)(G(x,y)H(y)或 xF(x) yG(y) x(F(x)yG(y) xy(F(x)G(y) 11例(續(xù))(5) x(F(x,y)y(G(x,y)H(x,z)解 x(F(x,y)u(G(x,u)H(x,z) xu(F(x,y)G(x,u)H(x,z)注意：與不能顛倒蘇格拉底三段論的正確性“凡是人都要死的. 蘇格拉底是人. 所以蘇格拉底是要死的.”12設(shè)F(x)：x是人，G(x)：x是要死的，a：蘇格拉底. x(F(x)G(x)F(a)G(a)設(shè)前件為真