資源描述：
《離散數(shù)學(xué)(一階邏輯等值演算與推理)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、1第五章一階邏輯等值演算與推理一階邏輯等值式與基本的等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式自然推理系統(tǒng)NL及其推理規(guī)則25.1一階邏輯等值式與置換規(guī)則定義5.1設(shè)A,B是兩個(gè)謂詞公式,如果A?B是永真式,則稱A與B等值,記作A?B,并稱A?B是等值式.由定義顯然可以看出：公式A，B等值的充要條件是：對(duì)A，B的任意解釋I，A，B在I下的真值相同。因?yàn)閷?duì)任意公式A，B，在解釋I下，A，B就是兩個(gè)命題，所以命題邏輯中給出的基本等價(jià)式，在謂詞邏輯中仍然成立。3基本等值式第一組命題邏輯中16組基本等值式的代換實(shí)例例如，???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)消去量詞等值式設(shè)D={a1,a2,…,an}①?xA(x)?A(a1)?A(a2)?…?A(an)②?xA(x)?A(a1)?A(a2)?…?A(an)設(shè)個(gè)體域A={a,b},公式(?x)P(x)?(?x)S(x)在A上消去量詞后
3、應(yīng)為:例P(a)?P(b)?(S(a)?S(b))5基本等值式(2)量詞否定等值式①??xA(x)??x?A(x)②??xA(x)??x?A(x)例設(shè)論域?yàn)槿?，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)的證明對(duì)于任意給定的解釋I，若I使??xA(x)為真，則I使?xA(x)為假。則必有某一個(gè)x0?D，A(x0)是假命題，
4、于是?A(x0)是真命題，即?x?A(x)在I下是真命題，故I使?x?A(x)為真。若I使??xA(x)為假，則I使?xA(x)為真。即對(duì)任意的x?D，有A(x)是真命題。也就是對(duì)任意的x?D，?A(x)是假命題，于是?x?A(x)是假命題，故I使?x?A(x)為假。7實(shí)例例1將下面命題用兩種形式符號(hào)化,并證明兩者等值:(1)沒有不犯錯(cuò)誤的人解令F(x)：x是人，G(x)：x犯錯(cuò)誤.??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實(shí)例(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ù)）設(shè)個(gè)體域中的客體變?cè)獮閍1,a2,…,an，則10基本等值式(3)量詞轄域收縮與擴(kuò)張等值式.A(x)是含x自由出現(xiàn)的公式，B中不含x的自由出現(xiàn)關(guān)于全稱量詞的：①?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的證明設(shè)I是A(x)和B的一個(gè)解釋。若?x(A(x)?B)在I下取1值，則在I下，對(duì)任意x?D，A(x)?B都是真命題。若B是真命題，則?xA(x)?B是真命題；若B是假命題，則必然是對(duì)每個(gè)x?D，A(x)都是真命題，故?xA(x)取1值。所以?xA(x)?B在I下取1值。若?x(A(x)?B)在I下取0值，則必有一個(gè)x0?D，使A(x0)?
7、B在I下取0值。故A(x0)為假命題，并且B為假命題。所以?xA(x)取0值。從而?xA(x)?B在I下取0值。12基本等值式關(guān)于存在量詞的：①?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的證明設(shè)I是A(x)和B的一個(gè)解釋。若?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下對(duì)任意的x?D，使A(x)?B在I下取0值。故A(x)和B都為假命題，所以?xA(x)?B在I下取0值。14基本等值式(4)量詞分配等值式①?x(A(x)?B(x))??
