第5章 一階邏輯等值演算與推理.ppt

《第5章 一階邏輯等值演算與推理.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第5章一階邏輯等值演算與推理離散數(shù)學(xué)本章說明本章的主要內(nèi)容一階邏輯等值式與基本等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式一階邏輯推理理論本章與其他各章的關(guān)系本章先行基礎(chǔ)是前四章本章是集合論各章的先行基礎(chǔ)本章主要內(nèi)容5.1一階邏輯等值式與置換規(guī)則5.2一階邏輯前束范式5.3一階邏輯的推理理論5.1一階邏輯等值式與置換規(guī)則在一階邏輯中，有些命題可以有不同的符號化形式。例如：沒有不犯錯(cuò)誤的人令M(x):x是人。F(x):x犯錯(cuò)誤。則將上述命題的符號化有以下兩種正確形式：(1)┐?x(M(x)∧┐F(x))(2)?x(M(x)→F(x))我們稱(1)和(2)是

2、等值的。說明等值式的定義定義5.1設(shè)A，B是一階邏輯中任意兩個(gè)公式，若A?B是永真式，則稱A與B是等值的。記做A?B，稱A?B是等值式。例如：判斷公式A與B是否等值，等價(jià)于判斷公式A?B是否為永真式。謂詞邏輯中關(guān)于聯(lián)結(jié)詞的等值式與命題邏輯中相關(guān)等值式類似。說明一階邏輯中的一些基本而重要等值式代換實(shí)例消去量詞等值式量詞否定等值式量詞轄域收縮與擴(kuò)張等值式量詞分配等值式代換實(shí)例由于命題邏輯中的重言式的代換實(shí)例都是一階邏輯中的永真式，因而第二章的16組等值式模式給出的代換實(shí)例都是一階邏輯的等值式的模式。例如：(1)?xF(x)?┐┐?xF(x)（雙重否定律）

3、(2)F(x)→G(y)?┐F(x)∨G(y)（蘊(yùn)涵等值式）(3)?x(F(x)→G(y))→?zH(z)?┐?x(F(x)→G(y))∨?zH(z)（蘊(yùn)涵等值式）消去量詞等值式設(shè)個(gè)體域?yàn)橛邢藜疍={a1,a2,…,an},則有（1）?xA(x)?A(a1)∧A(a2)∧…∧A(an)（2）?xA(x)?A(a1)∨A(a2)∨…∨A(an)（5.1）量詞否定等值式設(shè)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，則（1）┐?xA(x)??x┐A(x)（2）┐?xA(x)??x┐A(x)說明“并不是所有的x都有性質(zhì)A”與“存在x沒有性質(zhì)A”是一回事?！辈淮?/p>

4、在有性質(zhì)A的x”與”所有x都沒有性質(zhì)A”是一回事。（5.2）量詞否定等值式(舉例)????N?n(n>N→

5、an-a

6、N→

7、an-a

8、N→

9、an-a

10、N→

11、an-a

12、N→

13、an-a

14、N∨

15、an-a

16、N∧?

17、an-a

18、N∧

19、an-a

20、??)量詞轄域收縮與擴(kuò)張等值式設(shè)

21、A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B中不含x的出現(xiàn)，則（1）?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)（2）?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)（5.3）（5.4）量詞轄域收縮與擴(kuò)張(?、續(xù))?x(A(x)→B)??xA(x)→B證明:?x(A(x)→B)??x(?A(x)∨B)??x?A(x)∨B???xA(x)∨B?

22、?xA(x)→B?x(B→A(x))?B→?xA(x)證明:?x(B→A(x))??x(?B∨A(x))??B∨?xA(x)??B∨?xA(x)?B→?xA(x)量詞轄域收縮與擴(kuò)張(?、續(xù))?x(A(x)→B)??xA(x)→B證明:?x(A(x)→B)??x(?A(x)∨B)??x?A(x)∨B???xA(x)∨B??xA(x)→B?x(B→A(x))?B→?xA(x)證明:?x(B→A(x))??x(?B∨A(x))??B∨?xA(x)??B∨?xA(x)?B→?xA(x)量詞分配等值式設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，則（1

23、）?x(A(x)∧B(x))??xA(x)∧?xB(x)（2）?x(A(x)∨B(x))??xA(x)∨?xB(x)（5.5）例如，“聯(lián)歡會上所有人既唱歌又跳舞”和“聯(lián)歡會上所有人唱歌且所有人跳舞”，這兩個(gè)語句意義相同。故有(1)式。由(1)式推導(dǎo)(2)式?x(A(x)∧B(x))??xA(x)∧?xB(x)?x(┐A(x)∧┐B(x))??x┐A(x)∧?x┐B(x)┐?x(A(x)∨B(x))?┐(?xA(x)∨?xB(x))?x(A(x)∨B(x))??xA(x)∨?xB(x)量詞分配等值式①?x(A(x)?B(x))??xA(x)??xB(x)

24、②?x(A(x)?B(x))??xA(x)??xB(x)注意:?對?無分配律,?對?無分配律量