5(等值式和前束范式以及推理理論).ppt

1、一、等值式,定義 1 若AB為邏輯有效式，則稱A與B是等值的， 記作 AB，并稱AB為等值式.,定義 2 若謂詞公式A和B對任意一個解釋都取相同的真值，則稱A與B是等值的，記作 AB，并稱AB為等值式.,5.1 一階邏輯等值式與置換規(guī)則,二、基本等值式,第一組 命題邏輯中16組基本等值式的代換實例 由代換實例可知,命題邏輯中的等值式可以得到一類謂詞邏輯中的等值式.例如 xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 第二組 1、 消去量詞等值式 設(shè)D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an

2、),2、量詞否定等值式 設(shè)A(x)是含x自由出現(xiàn)的公式， (1) xA(x)x A(x) (2) xA(x) x A(x),證: (1)對于任意的解釋，設(shè)其個體域為。,若 xA(x)在解釋下為真，由否定律可知， xA(x)為假，根據(jù)全稱量詞的定義，存在x0 D,使A(x)為假，從而A(x)為真，所以解釋也使xA(x)為真。,三、量詞否定等值式,4個公式的敘述,若 xA(x)在解釋下為假，由否定律可知， xA(x)為真，根據(jù)全稱量詞的定義，對任意xD,使A(x)為真，亦即對任意xD， A(x)為假，所以解釋也使x A(x)為假。,(2)可類似于(1)證明之，也可以利用(1)的結(jié)果證明。（練習題）

3、,設(shè)A(x)是含x自由出現(xiàn)的公式， (1) xA(x)x A(x) (2) xA(x) x A(x),令D是全班所有同學組成的集合, A(x): x今天來上課,則 “并非每位同學今天都來上課”邏輯等價于 “有同學今天沒有來上課”, “并非有同學今天來上課”邏輯等價于 “每位同學今天都沒有來上課”。,量詞否定等值式之舉例說明：,設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn) 關(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),關(guān)于存在量詞的: x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(

4、x)B)xA(x)B x(BA(x)BxA(x),3、 量詞轄域收縮與擴張等值式.,4、量詞分配等值式,x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 注意：對無分配律，對無分配律,證:取具體謂詞公式F(x)和G(x) 分別代入A(x)和B(x) 使得x(A(x)B(x) xA(x)xB(x)不是邏輯有效式即可.,5、量詞交換等值式,xy A(x,y) y x A(x,y); x y A(x,y) y x A(x,y) .,例 將下面命題用兩種形式符號化 (1) 沒有不犯錯誤的人 (2) 不是所有的人都愛看電影,解 (1) 令F(x)：x是人，G(x)：x犯

5、錯誤. x(F(x)G(x) x(F(x)G(x) 請給出演算過程，并說明理由.,(2) 令F(x)：x是人，G(x)：x愛看電影. x(F(x)G(x) x(F(x)G(x) 給出演算過程，并說明理由.,七、前束范式,例如，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為一個謂詞公式, 若A具有如下形式 Q1x1Q2x2QkxkB, 則稱A為前束范式, 其中Qi (1ik) 為或，B為不含量詞的公式.,公式的前束范式,定理（前束范式存在定理）： 謂詞邏輯中的任何公式都存在與之

6、等值的前束范式。,注意: （1）公式的前束范式不惟一. （2）求公式的前束范式的方法: 利用重要等值式、置換規(guī)則、換名規(guī)則、代替規(guī)則進行等值演算.,換名規(guī)則與代替規(guī)則,換名規(guī)則: 將量詞轄域中出現(xiàn)的某個約束出現(xiàn)的 個體變項及對應(yīng)的指導變項，改成另一個轄域中未 曾出現(xiàn)過的個體變項符號，公式中其余部分不變， 則所得公式與原來的公式等值. 代替規(guī)則: 對某自由出現(xiàn)的個體變項用與原公式 中所有個體變項符號不同的符號去代替，則所得公 式與原來的公式等值.,換名規(guī)則與代替規(guī)則例子,分別用換名規(guī)則和代替規(guī)則對下列公式改名: x(F(x)G(x) H(x,y) 解: (1)用換名規(guī)則: 由于x既是約束變項,又

7、是自由變項,故將約束變項x改為z,得 z(F(z)G(z) H(x,y) (2)用代替規(guī)則: 將公式中的自由變項x用z代替,得 x(F(x)G(x) H(z,y),公式的前束范式(續(xù)),例 求下列公式的前束范式 (1) x(M(x)F(x) 解 x(M(x)F(x) x(M(x)F(x) （量詞否定等值式） x(M(x)F(x) 兩步結(jié)果都是前束范式，說明前束范式不惟一.,例(續(xù)),(2) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) （量詞否定等值式） x(F(x)G(x) （量詞分配等值式） 另有一種形式 xF(x)xG(x) xF(x)xG(x) xF(x)yG(

8、y) ( 換名規(guī)則 ) xy(F(x)G(y) ( 量詞轄域擴張 ) 兩種形式是等值的,例(續(xù)),(3) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) x(F(x)G(x) （為什么？） 或 xy(F(x)G(y) （為什么？） (4) xF(x)y(G(x,y)H(y) 解 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) （換名規(guī)則） zy(F(z)(G(x,y)H(y) （為什么？）,例(續(xù)),或 xF(x)y(G(z,y)H(y) （代替規(guī)則） xy(F(x)(G(z,y)H(y) (5) x(F(x,y)y(G(x,y)H(x,z) 解

9、用換名規(guī)則, 也可用代替規(guī)則, 這里用代替規(guī)則 x(F(x,y)y(G(x,y)H(x,z) x(F(x,u)y(G(x,y)H(x,z) xy(F(x,u)G(x,y)H(x,z) 注意：x與y不能顛倒,5.3 一階邏輯的推論理論,一、推理的形式結(jié)構(gòu) 二、判斷推理是否正確的方法 三、重要的推理定律 四、推理規(guī)則 五、構(gòu)造證明 六、附加前提證明法,一、推理的形式結(jié)構(gòu),推理的形式結(jié)構(gòu)有兩種： 第一種 A1A2AkB (*) 第二種 前提：A1，A2，Ak 結(jié)論： B 其中 A1,A2,Ak,B為謂詞邏輯公式. 若(*)為永真式, 則稱推理正確, 否則稱推理不正確. 判斷方法: (1)真值表法;(

10、2)等值演算法;(3)主析取范式法(4)構(gòu)造證明法. 前3種方法采用第一種形式結(jié)構(gòu), 構(gòu)造證明法采用第二種形式結(jié)構(gòu).,重要的推理定律,第一組 命題邏輯推理定律代換實例 如 xF(x)yG(y)xF(x)為化簡律代換實例. 第二組 由基本等值式生成 如 由 xA(x)xA(x) 生成 xA(x)xA(x), xA(x)xA(x), 第三組 xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x),永真蘊涵式,推理規(guī)則,(1)前提引入規(guī)則 (2)結(jié)論引入規(guī)則 (3)置換規(guī)則 (4)假言推理規(guī)則 (5)附加規(guī)則 (6)化簡規(guī)則 (7)拒取式規(guī)則 (8)假言三段論規(guī)則 (9)

11、析取三段論規(guī)則 (10)構(gòu)造性二難推理規(guī)則 (11)合取引入規(guī)則,復習,推理規(guī)則(續(xù)),(12) 全稱量詞消去規(guī)則（簡記為UI規(guī)則或UI） 兩式成立的條件是： 在第一式中，取代x的y應(yīng)為任意的不在A(x)中 約束出現(xiàn)的個體變項. 在第二式中，c為任意個體常項. 用y或c去取代A(x)中的自由出現(xiàn)的x時，一定要在x自由出現(xiàn)的一切地方進行取代.,推理規(guī)則(續(xù)),(13) 全稱量詞引入規(guī)則（簡記為UG規(guī)則或UG） 該式成立的條件是： 無論A(y)中自由出現(xiàn)的個體變項y取何值，A(y) 應(yīng)該均為真. 取代自由出現(xiàn)的y的x，也不能在A(y)中約束出 現(xiàn).,推理規(guī)則(續(xù)),(14) 存在量詞引入規(guī)則（簡記

12、為EG規(guī)則或EG） 該式成立的條件是： c是使A為真的特定個體常項. 取代c的x不能在A(c)中出現(xiàn)過.,推理規(guī)則(續(xù)),(15) 存在量詞消去規(guī)則（簡記為EI規(guī)則或EI） 該式成立的條件是： c是使A為真的特定的個體常項.c不能在A(x)、前提或前面的推導公式中出現(xiàn)過。 c不在A(x)中出現(xiàn). 若A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn)的個體變項，此規(guī)則不能使用.,例1 證明蘇格拉底三段論: “人都是要死的, 蘇格拉 底是人，所以蘇格拉底是要死的.”,令 F(x): x是人, G(x): x是要死的, a: 蘇格拉底 前提：x(F(x)G(x)，F(xiàn)(a) 結(jié)論：G(a),證明： F(a)

13、 前提引入 x(F(x)G(x) 前提引入 F(a)G(a) UI G(a) 假言推理 注意：使用UI時，用a取代x .,構(gòu)造推理證明(續(xù)),例2 烏鴉都不是白色的. 北京鴨是白色的. 因此， 北京鴨不是烏鴉.,令 F(x): x是烏鴉, G(x): x是北京鴨, H(x): x是白色的,前提：x(F(x)H(x)， x(G(x)H(x) 結(jié)論：x(G(x)F(x),例2(續(xù)),證明： x(F(x)H(x) 前提引入 F(y)H(y) UI x(G(x)H(x) 前提引入 G(y)H(y) UI H(y)G(y) 置換 F(y)G(y) 假言三段論 G(y)F(y) 置換 x(G(x)F(x)

14、 UG,構(gòu)造推理證明(續(xù)),例3 構(gòu)造下述推理證明 前提：x(F(x)G(x)，xF(x) 結(jié)論：xG(x) 證明： xF(x) 前提引入 x(F(x)G(x) 前提引入 F(c) EI F(c)G(c) UI G(c) 假言推理 xG(x) EG 注意：必須先消存在量詞,構(gòu)造推理證明(續(xù)),例4 構(gòu)造下述推理證明 前提：xF(x)xG(x) 結(jié)論：x(F(x)G(x) 證明： xF(x)xG(x) 前提引入 xy(F(x)G(y) 置換 x(F(x)G(z) UI F(z)G(z) UI x(F(x)G(x) UG 說明: 不能對xF(x)xG(x)消量詞, 因為它不是前束范式. 對此題不能

15、用附加前提證明法.,構(gòu)造推理證明(續(xù)),例5 構(gòu)造下述推理證明 前提：x(F(x)G(x) 結(jié)論：xF(x)xG(x) 證明： xF(x) 附加前提引入 F(y) UI x(F(x)G(x) 前提引入 F(y)G(y) UI G(y) 假言推理 xG(x) UG,stop,基本等值式 （命題定律）,(1)雙重否定律 : AA,(5)分配律: A(BC)(AB)(AC) A(BC) (AB)(AC),(4)結(jié)合律: (AB)CA(BC) (AB)CA(BC),(3)交換律: ABBA, ABBA,(2)等冪律： AAA, AAA,基本等值式(續(xù)),(7)德摩根律 : (AB)AB (AB)AB

16、(8)吸收律: A(AB)A, A(AB)A (9)零律: A11, A00 (10)同一律: A0A, A1A (11)排中律: AA1 (12)矛盾律: AA0,基本等值式(續(xù)),(12)蘊涵等值式: ABAB (13)等價等值式: AB(AB)(BA) (14)假言易位: ABBA (15)等價否定等值式: ABAB (16)歸謬論: (AB)(AB) A,4個公式的含義:,(1) xA(x):,(4) x A(x):,并不是所有的個體x都具有性質(zhì)A;,(2) x A(x):,存在一個不具有性質(zhì)A的個體;,(3) xA(x):,不存在具有性質(zhì)A的個體;,所有的個體都不具有性質(zhì)A.,三、推

17、理定律重言蘊涵式,重要的推理定律 A (AB) 附加式 (AB) A 化簡式 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段論 (AB)(BC) (AC) 假言三段論 (AB)(BC) (AC) 等價三段論 (AB)(CD)(AC) (BD) 構(gòu)造性二難規(guī)則,三、推理定律 (續(xù)),(AB)(AB)(AA) B 構(gòu)造性二難（特殊形式） (AB)(CD)( BD) (AC) 破壞性二難,說明： A, B, C為元語言符號 若某推理符合某條推理定律，則它自然是正確的 AB產(chǎn)生兩條推理定律: A B, B A,四、推理規(guī)則,四、推理規(guī)則(續(xù)),例如,若D=R,F(x, y)

18、:xy , 則x yF(x,y) 是真命題.,設(shè)A(x)=yF(x,y) ,x在A(x)中自由出現(xiàn)是滿足的,但y在A(x)中是約束出現(xiàn)的.若取y代替x,得 x yF(x,y) yF(y,y) 結(jié)論為”存在y,yy”,這是假命題. 出錯的條件是違備了條件(2).,有的教科書上的表述方式:,1. US(Universal quantifier Specification)規(guī)則: 全稱量詞消去規(guī)則 (1)xA(x) (2)A(c) (其中c為個體域中任意個體),2.UG(Universal quantifier Generalization)規(guī)則: 全稱量詞產(chǎn)生規(guī)則 (1)A(c) (其中為個體域中

19、任意個體) (2)xA(x),3.ES(Existential quantifier Specification)規(guī)則: 存在量詞消去規(guī)則 (1)xA(x) (2)A(c) (其中c為個體域中某個體) 注意:由xA(x)推出A(c), 要確保c與其他自由變元無關(guān).,4.EG (Existential quantifier Generalization)規(guī)則: 存在量詞產(chǎn)生規(guī)則 (1)A(c) (其中c為個體域中某個體) (2)xA(x),例:用構(gòu)造法證明以下推理: 前提:x(F(x) G(x), xF(x) 結(jié)論:xG(x). 證明: (1)xF(x) P (2)F(c) ES(1) (3)x(F(x) G(x) P (4)F(c) G(c) US(3) (5)G(c) T(2)(4)I (6)xG(x) EG(5),注意:不能把(1)(2)與(3)(4)的順序顛倒; 在(2)中,F(c)中的c是某個體; 在(4)中,F(c) G(c)中的c本來是任意個體現(xiàn)取為(2)中出現(xiàn)的c, 這是可以的. 但反過來就不行. 避免這種錯誤的最好方法是象上面的證明過程一樣, 先消去存在量詞,