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

第2章  謂詞邏輯

 

       一、教學(xué)要求

 

       1. 理解謂詞、量詞、個(gè)體詞、個(gè)體域、原子公式、謂詞公式和變元等概念。會(huì)將不太復(fù)雜的命題符號(hào)化。

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

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

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

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

 

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

 

       二、學(xué)習(xí)輔導(dǎo)

 

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

 

       1. 謂詞與量詞

      學(xué)習(xí)這一部分要反復(fù)理解謂詞和量詞引入的意義，概念的含義。

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

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

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

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

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

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

       個(gè)體常項(xiàng)a和個(gè)體變項(xiàng)都具有性質(zhì)F，記作F(a)或F(x);個(gè)體常項(xiàng)a,與b或個(gè)體變項(xiàng)x與y具有關(guān)系L,記作L(a,b)或L(x,y)。一般地，用F(a)表示a是無理數(shù)，其中a表示ln5，F表示的是“…是無理數(shù)”。當(dāng)F的含義不變時(shí)，則F(x)表示x是無理數(shù)，x是個(gè)體變項(xiàng)，F謂詞常項(xiàng)，F(x)不是命題，而是命題變項(xiàng)，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。

       注意，單獨(dú)的個(gè)體詞和謂詞不能構(gòu)成命題，將個(gè)體詞和謂詞分開不是命題。

       例2.1 將下列命題符號(hào)化：

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

       (2) 2既是偶數(shù)又是素?cái)?shù)；

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

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

                  P(x)：:x是學(xué)生。

                      a：丘華

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

             (2) 設(shè)個(gè)體域?yàn)檎麛?shù)集合N_＋。

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

                  Q(x)：x是素?cái)?shù)

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

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

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

                        a：張華

                        b：黎明

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

 

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

 

       例2.2 將下列命題符號(hào)化

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

              (2) 所有的人都呼吸；

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

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

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

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

             (2) 設(shè)個(gè)體域?yàn)槿说募稀?/DIV>