資源描述：
《一階邏輯等值演算與推理課件(離散數(shù)學(xué))精講.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第五章 一階邏輯等值演算與推理1本章主要內(nèi)容5.1一階邏輯等值式與置換規(guī)則5.2一階邏輯前束范式5.3一階邏輯的推理理論25.1一階邏輯等值式與置換規(guī)則等值式的概念基本等值式等值演算與置換規(guī)則3所有的學(xué)生都上課了，這是錯(cuò)的。令F(x):x是學(xué)生,G(x):x上課了。這句話相當(dāng)于“有些學(xué)生沒(méi)有上課”。4一、等值式的概念定義：若A?B為永真式，則稱A與B是等值的，記作A?B，并稱A?B為等值式。其中A、B是一階邏輯中任意的兩個(gè)合式公式。5二、基本等值式命題邏輯中16組基本等值式的代換實(shí)例例：?xF(x)??yG(y)???xF(x)??yG(y)?(?xF(x)??yG(y))???xF(x)
2、???yG(y)即命題邏輯中的基本等值式在謂詞邏輯中均適用。6二、基本等值式有限個(gè)體域中，消去量詞等值式設(shè)個(gè)體域?yàn)镈={a1,a2,…,an}?xA(x)?A(a1)?A(a2)?…?A(an)?xA(x)?A(a1)?A(a2)?…?A(an)7二、基本等值式量詞否定等值式“并不是所有的人都是黃皮膚?！边@句話相當(dāng)于“有的人不是黃皮膚?！?二、基本等值式量詞轄域收縮與擴(kuò)張等值式設(shè)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(A(x)?B)??xA(x)?B?x(B?A(x))?B??xA(x)
3、9二、基本等值式關(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)10二、基本等值式量詞分配等值式?x(A(x)?B(x))??xA(x)??xB(x)?x(A(x)?B(x))??xA(x)??xB(x)注意：?對(duì)?無(wú)分配律，?對(duì)?無(wú)分配律11三、等值演算與置換規(guī)則置換規(guī)則：設(shè)?(A)是含有公式A的公式，用公式B置換?(A)中所有的A后得到新的公式?(B)，若A?B,則?(B)??(A)等值演算的基礎(chǔ)：（1）一階邏輯的基本等值式；（2）置換規(guī)則、換名規(guī)則、代替規(guī)則。12例題
4、例1：下面的命題都有兩種不同的符號(hào)化形式，寫(xiě)出其中的一種，然后通過(guò)等值演算得到另一種。(1)沒(méi)有不犯錯(cuò)誤的人(2)不是所有的人都愛(ài)看電影13(1)沒(méi)有不犯錯(cuò)誤的人令F(x)：x是人，G(x)：x犯錯(cuò)誤例題14(2)不是所有的人都愛(ài)看電影令F(x)：x是人，G(x)：愛(ài)看電影例題15例2：設(shè)個(gè)體域D={a,b,c}，在D中消去下列公式中的量詞。兩次使用“消去等值式”例題16量詞轄域收縮與擴(kuò)張等值式解法二：小結(jié)：采用不同的演算過(guò)程同樣可以達(dá)到消去量詞的目的，但是如何演算才更簡(jiǎn)單呢？結(jié)論是將量詞轄域盡可能的縮小，然后再消量詞。例題17方法2：例題18(3)當(dāng)個(gè)體域D={a,b}提問(wèn)：如果先消去全
5、稱量詞，后消去存在量詞，結(jié)果會(huì)怎樣？例題19該題量詞的轄域已經(jīng)不能再縮小了，所以演算過(guò)程無(wú)法再簡(jiǎn)化，演算結(jié)果也不易化的更簡(jiǎn)單。兩種消去順序得到的結(jié)果相同。例題20例3給定解釋I如下:(a)個(gè)體域D={2，3}(b)(c)(d)謂詞如下頁(yè)所示例題21在I下求下列各式的真值。例題22計(jì)算過(guò)程見(jiàn)教材例題23例4：證明下面的謂詞公式是永真式。證明謂詞公式是永真式不能像命題公式那樣使用真值表。常用的方法是等值演算。例題24經(jīng)過(guò)等值演算可知該公式是永真式。例題25例題26兔子比烏龜跑得快。令：F(x):x是兔子G(y):y是烏龜L(x,y):x比y跑得快命題符號(hào)化為：另外一種等值的符號(hào)化形式為：275
6、.2前束范式定義：設(shè)A為一個(gè)一階邏輯公式,若A具有如下形式Q1x1Q2x2…QkxkB,則稱A為前束范式,其中Qi(1?i?k)為?或?，B為不含量詞的公式。例：?x?y(F(x)?(G(y)?H(x,y)))?x?(F(x)?G(x))??x(F(x)?G(x))不是前束范式。B前束范式B285.2前束范式(1)??x(M(x)?F(x))解：??x(M(x)?F(x))??x(?M(x)??F(x))（量詞否定等值式）??x(M(x)??F(x))兩步結(jié)果都是原公式的前束范式。例1：求下列公式的前束范式295.2前束范式(2)?xF(x)???xG(x)解：?xF(x)???xG(x)
7、??xF(x)??x?G(x)（量詞否定等值式）??x(F(x)??G(x))（量詞分配等值式）另有一種形式如下：305.2前束范式?xF(x)???xG(x)??xF(x)??x?G(x)??xF(x)??y?G(y)(換名規(guī)則)??x(F(x)??y?G(y))(量詞轄域擴(kuò)張)??x?y(F(x)??G(y))(量詞轄域擴(kuò)張)315.2前束范式(3)?xF(x)???xG(x)解?xF(x)???xG(x)??xF(
