1、計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-1謂詞的概念與表示謂詞的概念與表示2-2 命題函數(shù)與量詞命題函數(shù)與量詞2-3謂詞公式與翻譯謂詞公式與翻譯2-4變?cè)募s束變?cè)募s束2-5謂詞演算的等價(jià)式與蘊(yùn)含式謂詞演算的等價(jià)式與蘊(yùn)含式2-7前束范式前束范式2-7謂詞演算的推理理論謂詞演算的推理理論計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(n命題邏輯的局限性命題邏輯的局限性： 在命題邏輯中，命題是命題演算的基本在命題邏輯中，命題是命題演算的基本單位，不再對(duì)原子命題進(jìn)行分解，因而無法單位，不再對(duì)原子命題進(jìn)行分解，因而無法研究命題的內(nèi)部結(jié)構(gòu)、成分及命題之間的內(nèi)研究命題的內(nèi)部結(jié)構(gòu)、成分及命題之間的內(nèi)在聯(lián)系，甚至無法

2、處理一些簡(jiǎn)單而又常見的在聯(lián)系，甚至無法處理一些簡(jiǎn)單而又常見的推理過程。推理過程。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院n例如，下列推理：例如，下列推理： 所有的人都是要死的。所有的人都是要死的。 蘇格拉底是人。蘇格拉底是人。 蘇格拉底是要死的。蘇格拉底是要死的。 眾所周知眾所周知,這是真命題。但在命題邏輯中這是真命題。但在命題邏輯中,如如果用果用P,Q,R表示以上三個(gè)命題，則上述推理過表示以上三個(gè)命題，則上述推理過程為：（程為：（PQ）R。借助命題演算的推理理。借助命題演算的推理理論不能論不能證明其為重言式證明其為重言式。謂詞的概念與表示謂詞的概念與表示(計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(原

3、因：原因：命題邏輯不能將命題之間的內(nèi)在聯(lián)系命題邏輯不能將命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系反映出來。和數(shù)量關(guān)系反映出來。解決辦法：解決辦法：將命題進(jìn)行分解。將命題進(jìn)行分解。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(2-1謂詞的概念與表示謂詞的概念與表示(2-1.1 客體客體和和謂詞謂詞 在謂詞邏輯中，可將在謂詞邏輯中，可將原子命題原子命題劃分為劃分為客體客體和和謂詞謂詞兩部分。兩部分。客體客體：可以獨(dú)立存在的具體事物的或抽象的概：可以獨(dú)立存在的具體事物的或抽象的概念。念。例例如，電子計(jì)算機(jī)、李明、玫瑰花、黑如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、實(shí)數(shù)、中國(guó)、思想、唯物主義等，客體也板、實(shí)數(shù)、

4、中國(guó)、思想、唯物主義等，客體也可稱之為可稱之為主語主語。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(謂詞：謂詞：用來刻劃客體的性質(zhì)或客體之間的相互關(guān)系的詞。用來刻劃客體的性質(zhì)或客體之間的相互關(guān)系的詞。例如在下面命題中：例如在下面命題中： （1）張明是個(gè)勞動(dòng)模范。）張明是個(gè)勞動(dòng)模范。 （2）李華是個(gè)勞動(dòng)模范。）李華是個(gè)勞動(dòng)模范。 刻劃客體的性質(zhì)刻劃客體的性質(zhì) （3）王紅王紅是個(gè)大學(xué)生。是個(gè)大學(xué)生。 （4）小李比小趙高小李比小趙高2cm。 （5）點(diǎn)）點(diǎn)a在在b與與c之間。之間。 刻劃客體之間的相互關(guān)系刻劃客體之間的相互關(guān)系 （6）阿杜與阿寺同歲。阿杜與阿寺同歲。 “是個(gè)勞動(dòng)模范是個(gè)勞動(dòng)模

5、范”、“是個(gè)大學(xué)生是個(gè)大學(xué)生”、“比比高高2cm”、 “在在與與之間之間”都是都是謂詞。謂詞。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(n刻劃刻劃一個(gè)客體性質(zhì)一個(gè)客體性質(zhì)的詞稱之為的詞稱之為一元謂詞一元謂詞,刻劃刻劃n個(gè)客體個(gè)客體之間關(guān)系之間關(guān)系的詞稱之為的詞稱之為n元謂詞元謂詞.n一般我們用大寫英文字母表示一般我們用大寫英文字母表示謂詞，謂詞，用小寫英文字母用小寫英文字母表示客體名稱，例如，表示客體名稱，例如，將上述謂詞分別記作大寫字母將上述謂詞分別記作大寫字母F、G、H、R，S則上述命題可表示為：則上述命題可表示為： (1) F(a) a：張明張明 (2) F(b) b：李華李

6、華 (3) G(c) c：王紅王紅 (4) H(s,t) s：小李小李 t：小趙：小趙 (5) R(a,b,c) (6) S(a,b) a:阿杜。阿杜。b:阿寺。阿寺。其中其中(1)、(2)、 (3)為一元謂詞，為一元謂詞， (4) 、 (6)為二元謂詞，為二元謂詞， (5)為三元謂詞。為三元謂詞。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(n注注:n(1)單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母后填上客體所得到的式子稱之為謂詞填式。后填上客體所得到的式子稱之為謂詞填式。n(2)在謂詞填式中，若客體確定，則在謂詞填式中，若客體確定，則A(a1，a2.an)

7、就變成了命題就變成了命題 n(3)在多元謂詞表達(dá)式中，客體字母出現(xiàn)的在多元謂詞表達(dá)式中，客體字母出現(xiàn)的先后次序與事先約定有關(guān)先后次序與事先約定有關(guān),一般不可以隨意交一般不可以隨意交換位置換位置(如如,上例中上例中H(s,t) 與與H(t, s)代表兩個(gè)不代表兩個(gè)不同的命題同的命題) 。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(n設(shè)謂詞設(shè)謂詞H表示表示“是勞動(dòng)模范是勞動(dòng)模范”, a表示客體名稱表示客體名稱張張明明, b表示客體名稱表示客體名稱李華李華,c表示客體名稱這只老虎，表示客體名稱這只老虎，那么那么H(a)、H(b)、H(c)表示三個(gè)不同的命題表示三個(gè)不同的命題,但但它們有一個(gè)

8、共同的形式它們有一個(gè)共同的形式,即即H(x).一般地，一般地，H(x)表表示客體示客體x具有性質(zhì)具有性質(zhì)H。這里。這里x表示抽象的或泛指的表示抽象的或泛指的客體，稱為客體，稱為客體變?cè)腕w變?cè)Ｓ眯懹⑽淖帜福Ｓ眯懹⑽淖帜竫, y, z, 表示。相應(yīng)地，表示具體或特定的客體的表示。相應(yīng)地，表示具體或特定的客體的詞稱為詞稱為客體常項(xiàng)客體常項(xiàng)，常用小寫英文字母，常用小寫英文字母a,b,c, 表表示。示。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院謂詞的概念與表示謂詞的概念與表示(同理，客體變?cè)恚腕w變?cè)獂，y具有關(guān)系具有關(guān)系L，記作，記作L(x,y);客體變?cè)腕w變?cè)獂, y, z具有關(guān)系具有關(guān)系A(chǔ)，記作，記作

9、A(x,y,z).nH(x)、L(x,y) 、A(x,y,z)本身并不是一個(gè)命題本身并不是一個(gè)命題.只只有用特定的客體取代客體變?cè)杏锰囟ǖ目腕w取代客體變?cè)獂,y,z后，它們才成為后，它們才成為命題。命題。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2 命題函數(shù)與量詞2-2.1 命題函數(shù)命題函數(shù)一般來說，當(dāng)謂詞一般來說，當(dāng)謂詞P給定，給定， x1,x2,xn是客體變?cè)强腕w變?cè)?，P(x1,x2,xn) 不是一個(gè)命題，因?yàn)樗恼嬷禑o法確定，不是一個(gè)命題，因?yàn)樗恼嬷禑o法確定，要想使它成為命題，要用要想使它成為命題，要用n個(gè)客體常項(xiàng)代替?zhèn)€客體常項(xiàng)代替n個(gè)客體變個(gè)客體變?cè)Ｔ?P(x1,x2,xn) 就是就是命題函

10、數(shù)命題函數(shù)。比如比如L(x,y)表示表示“x小于小于y”，那么，那么L(2,3)表示了一表示了一個(gè)真命題個(gè)真命題“2小于小于3”。而。而 L(5,1)表示了一個(gè)假命題表示了一個(gè)假命題“5小于小于1”計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.1 命題函數(shù)定義定義2-2.1：簡(jiǎn)單命題函數(shù)簡(jiǎn)單命題函數(shù)(simple propositional function)：由一個(gè)謂詞，一些客體變?cè)M成的表達(dá)式稱為由一個(gè)謂詞，一些客體變?cè)M成的表達(dá)式稱為簡(jiǎn)單命題函數(shù)簡(jiǎn)單命題函數(shù)。比如：比如：A(x)，B(x,y)，L(x,y,z)簡(jiǎn)單命題函數(shù)不是命題，只有當(dāng)變?cè)?jiǎn)單命題函數(shù)不是命題，只有當(dāng)變?cè)獂,y,z等等取特定的客體才確定

11、了一個(gè)命題。取特定的客體才確定了一個(gè)命題。對(duì)于對(duì)于n元謂詞，當(dāng)元謂詞，當(dāng)n=0時(shí)，稱為時(shí)，稱為0元謂詞元謂詞，它，它本身就是一個(gè)命題，故命題是本身就是一個(gè)命題，故命題是n元謂詞的一個(gè)特元謂詞的一個(gè)特殊情況。殊情況。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.1 命題函數(shù)比如：比如：L(x,y)表示表示“x小于小于y”是二元謂詞，是二元謂詞，L(x,3)表示表示“x小于小于3”是一元謂詞，是一元謂詞，L(2,3)表示表示“2小于小于3”是是0元謂詞。元謂詞。因此可以將命題看成因此可以將命題看成n元謂詞的一個(gè)特殊情元謂詞的一個(gè)特殊情況。況。 0元謂詞都是命題，命題邏輯中的簡(jiǎn)單命題元謂詞都是命題，命題邏輯中的簡(jiǎn)單命

12、題都可以用都可以用0元謂詞表示。元謂詞表示。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.1 命題函數(shù)定義定義2-2.2：復(fù)合命題函數(shù)（復(fù)合命題函數(shù)（compound propositional function）：）：由一個(gè)或由一個(gè)或n個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式。詞組合而成的表達(dá)式。命題邏輯中的聯(lián)結(jié)詞在謂詞邏輯中含義完命題邏輯中的聯(lián)結(jié)詞在謂詞邏輯中含義完全相同。全相同。舉例說明：舉例說明：P56例，例例，例計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.1 命題函數(shù)定義定義2-2.3：謂詞填式謂詞填式單獨(dú)一個(gè)謂詞不是完整的命題，把謂詞字單獨(dú)一個(gè)謂詞不是完整的命題，把謂詞字母以客體填后所

13、得的式子稱為謂詞填式。母以客體填后所得的式子稱為謂詞填式。例如：例如：P(x)表示表示x3，則，則P(1)、 P(2)、 P(5)分別表示分別表示1大于大于3，2大于大于3，5大于大于3，P(1)、 P(2)、 P(5)即是謂詞填式。即是謂詞填式。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.1 命題函數(shù)定義定義2-2.4：謂詞表達(dá)式謂詞表達(dá)式簡(jiǎn)單命題函數(shù)與邏輯聯(lián)結(jié)詞組合而成。簡(jiǎn)單命題函數(shù)與邏輯聯(lián)結(jié)詞組合而成。示例分析示例分析 P59 (1) a),b),c)a)設(shè)設(shè)W(x):x是工人，是工人，z:小張，則原命題表示為：小張，則原命題表示為： W(z) b)設(shè)設(shè)S(x):x是田徑運(yùn)動(dòng)員，是田徑運(yùn)動(dòng)員， B(x)

14、:x是球類運(yùn)動(dòng)員，是球類運(yùn)動(dòng)員，h:他，則原命題表示為：他，則原命題表示為： S(h) B(h)c)設(shè)設(shè)C(x):x是聰明的，是聰明的，B(x):x是美麗的，是美麗的，a:小莉，則原小莉，則原命題表示為：命題表示為： C(a) B(a)計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院注意：注意：命題函數(shù)不是一個(gè)命題，只有客體變命題函數(shù)不是一個(gè)命題，只有客體變?cè)√囟腕w時(shí)，才能成為一個(gè)命題。但是客元取特定客體時(shí)，才能成為一個(gè)命題。但是客體變?cè)谀男┓秶√囟ǖ闹担瑢?duì)命題函數(shù)以體變?cè)谀男┓秶√囟ǖ闹担瑢?duì)命題函數(shù)以下兩方面有極大影響：下兩方面有極大影響：(1) 命題函數(shù)是否能成為一個(gè)命題；命題函數(shù)是否能成為一個(gè)命題；(2

15、) 命題的真值是真還是假。命題的真值是真還是假。2-2.1 命題函數(shù)計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.1 命題函數(shù)個(gè)體域個(gè)體域(universe of discourse)：在命題函數(shù)中，命題變?cè)恼撌龇秶Q為在命題函數(shù)中，命題變?cè)恼撌龇秶Q為個(gè)個(gè)體域體域。全總個(gè)體域：全總個(gè)體域：個(gè)體域可以是有限的，也可以是無限的，把個(gè)體域可以是有限的，也可以是無限的，把各種個(gè)體域綜合在一起，作為論述范圍的域，各種個(gè)體域綜合在一起，作為論述范圍的域，稱為稱為全總個(gè)體域全總個(gè)體域。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.2 量詞例題：例題：符號(hào)化以下命題符號(hào)化以下命題(1)所有人都要死去。所有人都要死去。(2)有的人的年齡超過

16、百歲。有的人的年齡超過百歲。以上給出的命題，除了有個(gè)體詞和謂詞以外，以上給出的命題，除了有個(gè)體詞和謂詞以外，還有表示數(shù)量的詞，稱表示數(shù)量的詞為量詞。量還有表示數(shù)量的詞，稱表示數(shù)量的詞為量詞。量詞有兩種：詞有兩種：全稱量詞全稱量詞(universal quantifier)存在量詞存在量詞(existential quantifier)計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.2 量詞定義定義2-2.5全稱量詞全稱量詞(universal quantifier)用符號(hào)用符號(hào)“ ”表示，表示，“ x”表示對(duì)個(gè)體域里的所表示對(duì)個(gè)體域里的所有個(gè)體。有個(gè)體。( x)P(x)表示對(duì)個(gè)體域里的所有個(gè)體都有表示對(duì)個(gè)體域里的

17、所有個(gè)體都有屬性屬性P。表達(dá)。表達(dá)“對(duì)所有的對(duì)所有的”，“每一個(gè)每一個(gè)”，“對(duì)任一對(duì)任一個(gè)個(gè)”，“凡凡”，“一切一切”等詞。等詞。定義定義2-2-7存在量詞存在量詞(existential quantifier)用符號(hào)用符號(hào)“ ”表示。表示。 x表示存在個(gè)體域里的個(gè)體。表示存在個(gè)體域里的個(gè)體。( x)P(x)表示存在個(gè)體域里的個(gè)體具有性質(zhì)表示存在個(gè)體域里的個(gè)體具有性質(zhì)P。符號(hào)符號(hào)“ ”稱為存在量詞，用以表達(dá)稱為存在量詞，用以表達(dá)“某個(gè)某個(gè)”，“存在一些存在一些”，“至少有一個(gè)至少有一個(gè)”，“對(duì)于一些對(duì)于一些”等等詞。詞。 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.2 量詞現(xiàn)在對(duì)以上兩個(gè)命題進(jìn)行符號(hào)化，在進(jìn)行

18、符號(hào)化現(xiàn)在對(duì)以上兩個(gè)命題進(jìn)行符號(hào)化，在進(jìn)行符號(hào)化之前必須確定個(gè)體域。之前必須確定個(gè)體域。第一種情況第一種情況個(gè)體域個(gè)體域D為人類集合。為人類集合。設(shè)：設(shè)：F(x) ： x是要死的。是要死的。G(x)： x活百歲以上。活百歲以上。則有則有( x) F(x) 和和 ( x) G(x)這兩個(gè)命題都是真命題這兩個(gè)命題都是真命題計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.2 量詞 第二種情況第二種情況個(gè)體域個(gè)體域D為全總個(gè)體域。為全總個(gè)體域。不能符號(hào)化為不能符號(hào)化為( x)F(x)和和( x)G(x)，因，因?yàn)闉?( x)F(x)表示宇宙間一切事物都要死的，表示宇宙間一切事物都要死的，這與原命題不符。這與原命題不符。(

19、 x)G(x)表示宇宙間一切事物中存在百歲表示宇宙間一切事物中存在百歲以上，這與原命題不符。以上，這與原命題不符。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.2 量詞因此必須引入一個(gè)新的謂詞，將人分離出來。因此必須引入一個(gè)新的謂詞，將人分離出來。在全總個(gè)體域的情況下，以上兩個(gè)命題敘述如下：在全總個(gè)體域的情況下，以上兩個(gè)命題敘述如下：(1) 對(duì)于所有個(gè)體而言，如果它是人，則它對(duì)于所有個(gè)體而言，如果它是人，則它要死去。要死去。(2) 存在著個(gè)體，它是人并且活過百歲以上。存在著個(gè)體，它是人并且活過百歲以上。于是，再符號(hào)化時(shí)必須引入一個(gè)新的謂詞于是，再符號(hào)化時(shí)必須引入一個(gè)新的謂詞 M(x)：x是人。是人。稱這個(gè)謂詞為

20、稱這個(gè)謂詞為特性謂詞特性謂詞。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院2-2.2 量詞定義：特性謂詞定義：特性謂詞在討論帶有量詞的命題函數(shù)時(shí)，必須確定其在討論帶有量詞的命題函數(shù)時(shí)，必須確定其個(gè)體域，為了方便，可使用全總個(gè)體域。限定個(gè)體域，為了方便，可使用全總個(gè)體域。限定客體變?cè)兓秶闹^詞，稱作特性謂詞。客體變?cè)兓秶闹^詞，稱作特性謂詞。利用特性謂詞，對(duì)以上兩個(gè)命題進(jìn)行符號(hào)化利用特性謂詞，對(duì)以上兩個(gè)命題進(jìn)行符號(hào)化(1) ( x)( M(x)F(x) )(2) ( x)( M(x)G(x) )計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院使用量詞時(shí)應(yīng)注意的問題：使用量詞時(shí)應(yīng)注意的問題：(1)在討論有量詞的命題函數(shù)時(shí)如果事先沒有給出在討

21、論有量詞的命題函數(shù)時(shí)如果事先沒有給出個(gè)體域，那么都應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域。個(gè)體域，那么都應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域。(2)對(duì)全稱量詞，特性謂詞常做蘊(yùn)含的前件。對(duì)存對(duì)全稱量詞，特性謂詞常做蘊(yùn)含的前件。對(duì)存在量詞，特性謂詞常做合取項(xiàng)。在量詞，特性謂詞常做合取項(xiàng)。2-2.2 量詞計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院舉例說明：舉例說明：例例1“有些人是要死的有些人是要死的”.解解1：采用全體人作為個(gè)體域采用全體人作為個(gè)體域. 設(shè)設(shè): G(x): x是要死的是要死的.原命題符號(hào)化成原命題符號(hào)化成: ( x)G(x)解解2：采用全總個(gè)體域采用全總個(gè)體域. 設(shè)設(shè): M(x): x是人是人; G(x):x是要死的是要死的.原命題符號(hào)化成原命題符號(hào)化成: ( x)(M(x) G(x)2-2.2 量詞計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院例例2 “凡人都是要死的凡人都是要死的”.解解1: 采用全體人作為個(gè)體