階邏輯等值演算與推理

《階邏輯等值演算與推理》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第五章一階邏輯等值演算與推理本章的主要內(nèi)容一階邏輯等值式與基本的等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式一階邏輯推理理論本章與其他各章的關(guān)系本章的先行基礎(chǔ)是前四章本章是集合論各章的先行基礎(chǔ)5.1一階邏輯等值式與置換規(guī)則一、等值式與基本的等值式1．等值式（定義5.1）A?B當(dāng)且僅當(dāng)A?B為永真式（A與B為任意的一階邏輯公式）注意：與定義2.1的區(qū)別與聯(lián)系2．基本的等值式第一組：命題邏輯中16組基本等值式代換實(shí)例例如，?xF(x)??yG(y)???xF(x)??yG(y)p?q??p?q的代換實(shí)例第二組：本章新給出（1）消去量詞等值式D={a1,a2,…,an}①?xA(x)?A(

2、a1)?A(a2)?…?A(an)②?xA(x)?A(a1)?A(a2)?…?A(an)（2）量詞否定等值式①??xA(x)??x?A(x)②??xA(x)??x?A(x)例:設(shè)個(gè)體域D={a,b,c},消去下列各公式的量詞:（1）?x(F(x)?G(x))（2）?x(F(x)??yG(y))（3）?x?yF(x,y)解：（1）?x(F(x)?G(x))?(F(a)?G(a))?(F(b)?G(b))?(F(c)?G(c))（2）?x(F(x)??yG(y))??xF(x)??yG(y)?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))解：（3）?x?y(F(x,

3、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))注意：也可以先消存在量詞，得到的結(jié)果是等值的。練習(xí)：在有限個(gè)體域內(nèi)消去下列公式的量詞：（1）個(gè)體域：D={1,2,3}?x?y(F(x)?G(y))（2）個(gè)體域：D={a,b}?x?y(F(x,y)?G(y,x))（3）量詞轄域收縮與擴(kuò)張等值式.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(

4、A(x)?B)??xA(x)?B④?x(B?A(x))?B??xA(x)關(guān)于全稱(chēng)量詞的：①?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)注意：?對(duì)?無(wú)分配律，?對(duì)?無(wú)分配律例：證明：（1）?x(A(x)?B(x))與?xA(x)??xB(x)不等值（2）?x(A(x)?B(x))與?xA(x)??xB(x)不等值。證明：（1）取解釋I為:個(gè)體

5、域?yàn)樽匀粩?shù)集合N,A(x)解釋為：x是奇數(shù)；B(x)解釋為：x是偶數(shù)；則?x(A(x)?B(x))為真命題，而?xA(x)??xB(x)為假命題。（2）取解釋I為:個(gè)體域?yàn)樽匀粩?shù)集合N,A(x)解釋為:x是奇數(shù);B(x)解釋為：x是偶數(shù)；則?x(A(x)?B(x))為假命題,而?xA(x)??xB(x)為真命題。二、置換規(guī)則、換名及代替規(guī)則1．置換規(guī)則（同命題邏輯）2．換名規(guī)則設(shè)A為一公式，將A中某量詞轄域中約束變項(xiàng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)?，改成該量詞轄域中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)符號(hào)，公式中其余部分不變，設(shè)所得公式為A’，則A’?A.3.代替規(guī)則設(shè)A為一公式，將A中某個(gè)自由出現(xiàn)的

6、個(gè)體變項(xiàng)的所有出現(xiàn)用A中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)符號(hào)代替，A中其余部分不變，設(shè)所得公式為A’，則A’?A.例：將下列公式化成與其等值的公式，使其不含既是約束出現(xiàn)又是自由出現(xiàn)的個(gè)體變項(xiàng)：（1）?xF(x,y,z)??yG(x,y,z)（2）?x(F(x,y)??yG(x,y,z))例將下面命題用兩種形式符號(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))（2）令F(x)：x是人，G(x)：愛(ài)看電影.??x(F(x)?G(x))??x(F(x)??G(x))例：證明下列等值式

7、：（1）??x(M(x)?F(x))??x(M(x)??F(x))（2）??x(M(x)?F(x))??x(M(x)??F(x))（3）??x?y(F(x)?G(y)?H(x,y))??x?y(F(x)?G(y)??H(x,y))（4）??x?y(F(x)?G(y)?L(x,y))??x?y(F(x)?G(y)??L(x,y))5.2一階邏輯前束范式一、前束范式與命題公式的前束范式1．前束范式：定義5.2設(shè)A為一個(gè)一階邏輯公式，若A具有形式Q1x1Q2x2…QkxkB