資源描述：
《離散數學(一階邏輯等值演算與推理)》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、1第五章一階邏輯等值演算與推理一階邏輯等值式與基本的等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式自然推理系統(tǒng)NL及其推理規(guī)則25.1一階邏輯等值式與置換規(guī)則定義5.1設A,B是兩個謂詞公式,如果A?B是永真式,則稱A與B等值,記作A?B,并稱A?B是等值式.由定義顯然可以看出：公式A，B等值的充要條件是：對A，B的任意解釋I，A，B在I下的真值相同。因為對任意公式A，B，在解釋I下，A，B就是兩個命題，所以命題邏輯中給出的基本等價式，在謂詞邏輯中仍然成立。3基本等值式第一組命題邏輯中16組基本等值式的代換實例例如，???xF(
2、x)??xF(x),?xF(x)??yG(y)???xF(x)??yG(y)等判斷下列公式的類型：（1）?xP(x)→(?x?yQ(x,y)→?xP(x))（2）?xP(x)→(?xP(x)∨?yG(y))（3）?(P(x,y)→Q(x,y))∧Q(x,y)永真式永真式矛盾式4基本等值式第二組(1)消去量詞等值式設D={a1,a2,…,an}①?xA(x)?A(a1)?A(a2)?…?A(an)②?xA(x)?A(a1)?A(a2)?…?A(an)設個體域A={a,b},公式(?x)P(x)?(?x)S(x)在A上消去量詞后
3、應為:例P(a)?P(b)?(S(a)?S(b))5基本等值式(2)量詞否定等值式①??xA(x)??x?A(x)②??xA(x)??x?A(x)例設論域為人，P(x):x來上課，?P(x):x沒來上課?xP(x):所有人都來上課??xP(x):不是所有人都來上課?x?P(x):有人沒來上課?xP(x):有人來上課??xP(x):沒有人來上課?x?P(x):所有人都沒來上課6①??xA(x)??x?A(x)的證明對于任意給定的解釋I，若I使??xA(x)為真，則I使?xA(x)為假。則必有某一個x0?D，A(x0)是假命題，
4、于是?A(x0)是真命題，即?x?A(x)在I下是真命題，故I使?x?A(x)為真。若I使??xA(x)為假，則I使?xA(x)為真。即對任意的x?D，有A(x)是真命題。也就是對任意的x?D，?A(x)是假命題，于是?x?A(x)是假命題，故I使?x?A(x)為假。7實例例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(?
5、F(x)?G(x))置換??x(F(x)?G(x))置換8實例(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))置換9量詞否定等值式（續(xù)）設個體域中的客體變元為a1,a2,…,an，則10基本等值式(3)量詞轄域收縮與擴張等值式.A(x)是含x自由出現的公式，B中不含x的自由出現關于全稱量詞的：①?x(A(x)?
6、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)11①?x(A(x)?B)??xA(x)?B的證明設I是A(x)和B的一個解釋。若?x(A(x)?B)在I下取1值，則在I下，對任意x?D，A(x)?B都是真命題。若B是真命題，則?xA(x)?B是真命題；若B是假命題，則必然是對每個x?D，A(x)都是真命題，故?xA(x)取1值。所以?xA(x)?B在I下取1值。若?x(A(x)?B)在I下取0值，則必有一個x0?D，使A(x0)?
7、B在I下取0值。故A(x0)為假命題，并且B為假命題。所以?xA(x)取0值。從而?xA(x)?B在I下取0值。12基本等值式關于存在量詞的：①?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)13①?x(A(x)?B)??xA(x)?B的證明設I是A(x)和B的一個解釋。若?x(A(x)?B)在I下取1值，則在I下，存在x0?D，A(x0)?B是真命題。若B是真命題，則?xA(x)?B是真命題；若B是假命題，則必然有
8、A(x0)是真命題，故?xA(x)取1值。所以?xA(x)?B在I下取1值。若?x(A(x)?B)在I下取0值，則在I下對任意的x?D，使A(x)?B在I下取0值。故A(x)和B都為假命題，所以?xA(x)?B在I下取0值。14基本等值式(4)量詞分配等值式①?x(A(x)?B(x))??
