離散數(shù)學(xué)一階邏輯等值演算.pptx

《離散數(shù)學(xué)一階邏輯等值演算.pptx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、1主要內(nèi)容一階邏輯等值式與基本的等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式自然推理系統(tǒng)NL及其推理規(guī)則第五章一階邏輯等值演算與推理25.1一階邏輯等值式與置換規(guī)則定義5.1設(shè)A,B是兩個謂詞公式,如果A?B是永真式,則稱A與B等值,記作A?B,并稱A?B是等值式利用永真式判斷，與命題公式的等值相同：真值表、演算基本等值式:1.第一組命題邏輯中16組基本等值式的代換實例例如，???xF(x)??xF(x),?xF(x)??yG(y)???xF(x)??yG(y)等基本等值式第二組2.消去量詞等值式（個體域為有窮集合）設(shè)D={a1

2、,a2,…,an}由前述的量詞的定義及所表示的邏輯意義能夠得出①?xA(x)?A(a1)?A(a2)?…?A(an)邏輯意義：對任何x具有性質(zhì)A，相當(dāng)于對每一個x都具有性質(zhì)A②?xA(x)?A(a1)?A(a2)?…?A(an)邏輯意義：對一些x具有性質(zhì)A，只要存在有x具有性質(zhì)A即可（析取的意義）3例：設(shè)個體域D={a,b,c}消去下列公式中的量詞1、?x（F(x)→G(x))2、?xF(x)∨?xG(x)3、?x?yF(x,y)45例給定解釋I如下：(a)個體域D＝{2，3}(b)D中特定元素a=2。(c)D上特定函數(shù)f(x

3、)為：f(2)=3，f(3)＝2．(d)D上的特定謂詞G(x，y)為：G(2，2)＝G(2，3)＝G(3，2)=1，G(3，3)＝0．L(x，y)為：L(2，2)＝L(3，3)＝1，L(2，3)=L(3，2)=0．F(x)為：F(2)＝0，F(xiàn)(3)＝1．在I下求下列各式的真值．(1)?x(F(x)∧G(x，a))(2)?x(F(f(x))∧G(x，f(x)))(3)?x?yL(x，y)?y?xL(x，y)上面兩例說明量詞的次序不能隨意顛倒（交換量詞的次序，其真值可能改變）63.量詞否定等值式設(shè)A(x)是任意的含自由出現(xiàn)個體變項

4、x的公式，則(1)┑?xA(x)??x┑A(chǔ)(x)(2)┑?xA(x)??x┑A(chǔ)(x)(1)式直觀解釋是：“并不是所有的x都有性質(zhì)A”與“存在x沒有性質(zhì)A”是一回事(邏輯意義相同)(2)式，“不存在有性質(zhì)A的x”“所有x都沒有性質(zhì)A”是一回事(邏輯意義相同)該式可理解為是德摩根律在無限項下的推廣如：在自然數(shù)集中“任何自然數(shù)均為偶數(shù)是不對的”┑?xA(x)與“有不是偶數(shù)的自然數(shù)”?x┑A(chǔ)(x)邏輯意義是相同的74.量詞轄域收縮與擴張等值式A(x)是含x自由出現(xiàn)的公式，B中不含x的自由出現(xiàn)(1)關(guān)于全稱量詞的：?x(A(x)∨B)?

5、?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)關(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)注：其中的B中不含變元x，可以是B（y）形式的量詞的轄域可以擴充（或收縮）到與個體變項無關(guān)的部分量詞的轄域不可以擴充（或收縮）到相同的自由個體變項的部分5．量詞分配等值式設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個體變項x的公式，則

6、(1)?x(A(x)∧B(x))??xA(x)∧?xB(x)全稱量詞對合取可分配(2)?x(A(x)∨B(x))??xA(x)∨?xB(x)存在量詞對析取可分配注：這兩個等值式很重要，因為全稱量詞對析取（?對?）不可分配，存在量詞對合取（?對?）不可分配例：設(shè)：A(x):x是奇數(shù)B(x):x是偶數(shù)個體域D為整數(shù)那么?x(A(x)∨B(x))是為真的但?xA(x)∨?xB(x)是為假的它們是不等值的另外?x(A(x)∧B(x))是為假的，而?xA(x)∧?xB(x)是為真的，所以它們也不等值。注：前面提出：多個量詞出現(xiàn)時，它們的

7、順序不能隨意調(diào)換但有?x?yA(x，y)??y?xA(x，y)?x?yA(x，y)??y?xA(x，y)二、等值演算規(guī)則1、置換規(guī)則（等值代換）設(shè)Φ(A)是含公式A的公式，若A?B，則Φ(A)?Φ(B)．一階邏輯中的置換規(guī)則與命題邏輯中的置換規(guī)則形式上完全相同，只是在這里A，B是一階邏輯公式．對于公式中出現(xiàn)有雙重身份的變元（即自由又約束)的處理：2、換名規(guī)則（約束變元的換名）－目的是使每個變元性質(zhì)唯一設(shè)A為一公式，將A中某量詞轄域中某約束變項的所有出現(xiàn)及相應(yīng)的指導(dǎo)變元，改成該量詞轄域中未曾出現(xiàn)過的某個體變項符號，公式中其余部分

8、不變，設(shè)所得公式為A’，則A’?A例：?xA(x)∨B(x)由于公式中的x即是自由的又是約束的，可利用此規(guī)則進行換名為：?tA(t)∨B(x)??xA(x)∨B(x)后可利用量詞的擴充得到：?tA(t)∨B(x)??t(A(t)∨B(x))例：?xF(x，y，z)→?yG(x