《離散數(shù)學》（7） 謂詞邏輯

第2章  謂詞邏輯

 

       一、教學要求

 

       1. 理解謂詞、量詞、個體詞、個體域、原子公式、謂詞公式和變元等概念。會將不太復雜的命題符號化。

     2. 掌握在有限個體域下求公式的真值和某些公式在給定解釋下真值的方法，判別公式類型(永真式、永假式和可滿足式)的方法。

    3. 掌握謂詞演算的等值式和重言蘊含式 (六種情況：(1)命題公式的推廣；(2)量詞否定式的等值式；(3)量詞轄域擴張和收縮的等值式；(4)量詞與聯(lián)結詞Ú，Ù，®的等值式；(5)量詞與聯(lián)結詞的重言蘊含式；(6)兩個量詞公式間的等值式與重言蘊含式)。會進行謂詞公式的等值演算。

      4. 了解前束范式的概念，會求公式的前束范式。

     5. 了解謂詞邏輯推理的規(guī)則：全量詞消去規(guī)則(US規(guī)則)；全量詞附加規(guī)則(UG規(guī)則)；存在量詞消去規(guī)則(ES規(guī)則)；存在量詞附加規(guī)則(EG規(guī)則)

 

       本章重點：謂詞與量詞，公式與解釋，前束范式，謂詞邏輯推理證明。

 

       二、學習輔導

 

       在命題邏輯中，我們把原子命題作為基本研究單位，對原子命題不再進行分解，只有復合命題才可以分解，揭示了一些有效的推理過程. 但是進一步研究發(fā)現(xiàn)，僅有命題邏輯是無法把一些常見的推理形式包括進去. 例如 “凡人要死，張三是人，張三要死”顯然是正確推理. 用命題邏輯解釋三段式. 設      P：人要死；Q張三是人；R：張三要死。要反映這種內在聯(lián)系，就要對命題邏輯進行分析，分析出其中的個體詞、謂詞和量詞，再研究它們之間的邏輯關系，總結出正確的推理形式和規(guī)則，這就是謂詞邏輯的研究內容。

 

       1. 謂詞與量詞

      學習這一部分要反復理解謂詞和量詞引入的意義，概念的含義。

      在謂詞邏輯中，原子命題分解成個體詞和謂詞。個體詞是可以獨立存在的客體，它可以是具體事物或抽象的概念，如小張，房子，南京，大米，思想，實數(shù)2等等。謂詞是用來刻劃個體詞的性質或事物之間的關系的詞。

   例如    (1)    ln5是無理數(shù)；

             (2)    高可比李木相高4cm；

             (3) 鄭州位于北京和廣州之間。

這時三個簡單命題，其中l(wèi)n5，高可，李木相，鄭州，北京，廣州等都是個體詞，而“是無理數(shù)”，“……比……高4cm”，“……位于……和……之間”等都是謂詞。

       個體詞分個體常項(用a,b,c,d,…表示)和個體變項(用x,y,z,…表示)；謂詞分謂詞常項(表示具體性質和關系的詞)和謂詞變項(表示抽象的或泛指的謂詞)，用F,G,P,…表示。

       個體常項a和個體變項都具有性質F，記作F(a)或F(x);個體常項a,與b或個體變項x與y具有關系L,記作L(a,b)或L(x,y)。一般地，用F(a)表示a是無理數(shù)，其中a表示ln5，F表示的是“…是無理數(shù)”。當F的含義不變時，則F(x)表示x是無理數(shù)，x是個體變項，F謂詞常項，F(x)不是命題，而是命題變項，F(a)是命題。用M(x,y,z)表示“z=x×y”，M(x,y,z)不是命題。a表示3，b表示5，c表示15，M(a,b,c)表示“15＝3×5”。M(a,b,c)是命題，真值為1，若c=12，那么M(a,b,c)是命題，真值為0。

       注意，單獨的個體詞和謂詞不能構成命題，將個體詞和謂詞分開不是命題。

       例2.1 將下列命題符號化：

       (1) 丘華和李兵都是學生；

       (2) 2既是偶數(shù)又是素數(shù)；

       (3) 如果張華比黎明高，黎明比王宏高，則張華比王宏高。

        解 (1) 設個體域是人的集合。

                  P(x)：:x是學生。

                      a：丘華

                      b：黎兵     該命題符號化為P(a)ÙP(b)

             (2) 設個體域為正整數(shù)集合N_＋。

                   F(x)：x是偶數(shù)，

                  Q(x)：x是素數(shù)

                       a：2       該命題符號化為F(a)ÙQ(a)

              (3)    設個體域是人的集合。

                 G(x,y)：x比y高。

                        a：張華

                        b：黎明

                        c：王宏     該命題符號化為G(a,b)ÙG(b,c)®G(a,c)    

 

       量詞是在命題中表示數(shù)量的詞，量詞有兩類：全稱量詞"，表示“所有的”或“每一個”；存在量詞$，表示“存在某個”或“至少有一個”。

 

       例2.2 將下列命題符號化

              (1)    每個母親都愛自己的孩子；

              (2) 所有的人都呼吸；

              (3) 有某些實數(shù)是有理數(shù)。

       解  (1) 設個體域是所有母親的集合。

                 M(x)：x表示愛自己的孩子；

                  該命題符號化為"xM(x)。

             (2) 設個體域為人的集合。

                  H(x)：x表示要呼吸。 該命題符號化為"xH(x) 或設個體域為生物集合，

                  M(x)：x是人。

                  H(x)：x表示要呼吸。       該命題符號化為"x(M(x)®H(x))

             (3) 設個體域為數(shù)的集合。

                  R(x)：x表示實數(shù)

                  Q(x)：x表示有理數(shù)。       該命題符號化$x(R(x)ÙQ(x))。

       在謂詞邏輯，使用量詞應注意以下幾點：      

       (1)    在不同個體域中，命題符號化的形式可能不同，命題的真值也可能會改變。

       (2)    在考慮命題符號化時，如果對個體域未作說明，一律使用全個體域。   

       (3)    多個量詞出現(xiàn)時，不能隨意顛倒它們的順序，否則可能會改變命題的涵義。

 

       學習這一部分內容要側重于能將謂詞邏輯公式表達式中，量詞消除寫成與之等值的公式，然后將解釋中的數(shù)值代入，求出真值，并著重理解在謂詞和量詞的作用下變元的自由性、約束性和更名規(guī)則、代入規(guī)則等。

       我們將命題常數(shù)0，1，一個命題和命題變元以及一個命題函數(shù)P(x₁,x₂,…,x_n)，統(tǒng)稱原子公式，由原子公式、聯(lián)結詞和量詞可構成謂詞公式(嚴格定義見教材)。命題的符號化結果都是謂詞公式，例如"x(F(x)®G(x))，$x(F(x)ÙG(x))，"x"y(F(x)ÙF(y)ÙL(x,y)®H(x,y))等都是謂詞公式，當然$x(F(x)ÙG(x,y)),"x(F(x)®G(x,y))等也是謂詞公式。

       在謂詞公式"xA和$xA中，x是指導變元，A是相應量詞的轄域。在"x和$x的轄域A中，x的所有出現(xiàn)都是約束出現(xiàn)，即x是約束變元，不是約束出現(xiàn)的變元，就是自由變元。也就是說，量詞后面的式子是轄域。量詞只對轄域內的同一變元有效。

       換名規(guī)則，就是把公式中量詞的指導變元及其該量詞的轄域中的該變元換成該公式中沒有出現(xiàn)的個體變元，公式的其余部分不變。

      代入規(guī)則，就是把公式中的某一自由變元，用該公式中沒有出現(xiàn)的個體變元符號替代，且要把該公式中所有的該自由變元都換成新引入的該符號。   

       謂詞公式只是一個符號串，沒有什么意義，但我們給這個符號串一個解釋，使它具有真值，就變成一個命題。所謂解釋就是使公式中的每一個變項都有個體域中的元素相對應。

       解釋有四部分組成：

       (1) 非空個體域D；

       (2) D中有一部分特定元素，用來解釋個體常項；

       (3) D上一些特定函數(shù)，用來解釋出現(xiàn)的函數(shù)變項；

       (4) D上一些特定謂詞，用來解釋謂詞變項。

 

      和命題邏輯一樣，在謂詞邏輯中，有的公式在任何解釋下都真，也有的公式在任何解釋下都假。以此，把公式分為三類：在任何解釋下公式A為真，或者公式A的真值表全為1，這就是永真式；在任何解釋下公式A為假，或者公式A的真值表全為0，這就是永假式；公式A不總是假，或者公式A的真值表至少有一個1，這就是可滿足式。由此可見，永真式也是可滿足式。

       一般地，判定一個公式是不是可滿足式，還沒有一定的算法。但是，可以證明，重言式的代換實例一定是永真式。而矛盾式的代換實例均為矛盾式。

 

           

       3. 前束范式

       一個謂詞公式的前束范式，仍然是謂詞公式，只是把謂詞公式的所有量詞均提到公式的開頭，而且它的轄域一直延伸到公式的末尾。      

       每個謂詞公式F都可以變換成與它等值的前束范式。其步驟如下：

       ① 消去聯(lián)結詞®，«，`Ú；

       ② 將聯(lián)結詞Ø向內深入，使之只作用于原子謂詞公式；

    ③ 利用換名或代入規(guī)則使所有約束變元的符號均不同，并且自由變元與約束變元的符號也不同；

       ④ 利用量詞轄域的擴張和收縮律，擴大量詞的轄域至整個公式；

       ⑤ 利用分配律將公式化為前束范式。

 

      重要的是弄清楚前束范式的定義，求前束范式主要是利用基本等值式、蘊含式和換名規(guī)則，把一個謂詞公式化為前束范式，雖然前束范式是謂詞公式的一種標準形式，但是一般一個謂詞公式的前束范式并不是唯一的。

 

       4.謂詞邏輯的推理理論

       謂詞演算的推理是命題演算推理的推廣和擴充，命題演算中的一些規(guī)則，如基本等值公式，重言蘊含式以及P，T，CP規(guī)則在謂詞演算中仍然使用。但是在謂詞演算推理中，某些前提和結論可能受到量詞的限制，為了使用這些推理，必須在推理過程中，有消去和附加量詞的規(guī)則，即US規(guī)則(全稱量詞消去規(guī)則)，UG規(guī)則(全稱量詞附加規(guī)則)，ES規(guī)則(存在量詞消去規(guī)則)，EG規(guī)則(存在量詞附加規(guī)則)等，以便使謂詞演算公式的推理過程可類似于命題演算的推理進行。