離散數(shù)學(xué)第二章謂詞邏輯ppt課件

1、n命題邏輯的局限性：命題邏輯的局限性：n 在命題邏輯中，命題是命題演算的根本單位，在命題邏輯中，命題是命題演算的根本單位，不不n再對(duì)原子命題進(jìn)展分解，因此無(wú)法研討命題的內(nèi)部再對(duì)原子命題進(jìn)展分解，因此無(wú)法研討命題的內(nèi)部結(jié)結(jié)n構(gòu)、成分及命題之間的內(nèi)在聯(lián)絡(luò)，甚至無(wú)法處置一構(gòu)、成分及命題之間的內(nèi)在聯(lián)絡(luò)，甚至無(wú)法處置一些些n簡(jiǎn)單而又常見(jiàn)的推理過(guò)程。簡(jiǎn)單而又常見(jiàn)的推理過(guò)程。 第二章第二章 謂謂 詞詞 邏邏 輯輯 例如，以下推理：例如，以下推理： 一切的人都是要死的。一切的人都是要死的。 蘇格拉底是人。蘇格拉底是人。 蘇格拉底是要死的。蘇格拉底是要死的。 眾所周知，這是真命題。但在命題邏輯中眾所周知，這是真

2、命題。但在命題邏輯中,假設(shè)假設(shè)用用P，Q，R表示以上三個(gè)命題，那么上述推理過(guò)程表示以上三個(gè)命題，那么上述推理過(guò)程為：為：PQR。借助命題演算的推理實(shí)際不能證明其。借助命題演算的推理實(shí)際不能證明其為重言式。為重言式。 第二章第二章 謂謂 詞詞 邏邏 輯輯緣由：命題邏輯不能將命題之間的內(nèi)在聯(lián)絡(luò)和數(shù)量緣由：命題邏輯不能將命題之間的內(nèi)在聯(lián)絡(luò)和數(shù)量關(guān)系反映出來(lái)。關(guān)系反映出來(lái)。處理方法：將命題進(jìn)展分解。處理方法：將命題進(jìn)展分解。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示2.2 命題函數(shù)與量詞命題函數(shù)與量詞2.3 謂詞公式與翻譯謂詞公式與翻譯2.4 變?cè)募s束變?cè)募s束2

3、.5 謂詞演算的等價(jià)式與蘊(yùn)含式謂詞演算的等價(jià)式與蘊(yùn)含式2.6 前束范式前束范式2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示 在謂詞邏輯中，可將原子命題劃分為個(gè)在謂詞邏輯中，可將原子命題劃分為個(gè)體和謂體和謂詞兩部分。詞兩部分。個(gè)體：可以獨(dú)立存在的詳細(xì)事物的或籠統(tǒng)的個(gè)體：可以獨(dú)立存在的詳細(xì)事物的或籠統(tǒng)的概念。概念。例如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、例如，電子計(jì)算機(jī)、李明、玫瑰花、黑板、實(shí)數(shù)、實(shí)數(shù)、 中國(guó)、思想、唯物主義等，客體也可稱中國(guó)、思想、唯物主義等，客體也可稱之為之為 主語(yǔ)。主語(yǔ)。謂詞：用來(lái)刻劃個(gè)體的性質(zhì)或個(gè)體

4、之間的相謂詞：用來(lái)刻劃個(gè)體的性質(zhì)或個(gè)體之間的相互關(guān)系互關(guān)系 的詞。的詞。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示例如在下面命題中：例如在下面命題中： 1張明是個(gè)勞動(dòng)模范。張明是個(gè)勞動(dòng)模范。 2李華是個(gè)勞動(dòng)模范。李華是個(gè)勞動(dòng)模范。 刻劃個(gè)體的性質(zhì)刻劃個(gè)體的性質(zhì) 3王紅是個(gè)大學(xué)生。王紅是個(gè)大學(xué)生。 4小李比小趙高小李比小趙高2cm。 5點(diǎn)點(diǎn)a在在b與與c之間。之間。 刻劃個(gè)體之間的相互關(guān)系刻劃個(gè)體之間的相互關(guān)系 6阿杜與阿寺同歲。阿杜與阿寺同歲?！笆莻€(gè)勞動(dòng)模范、是個(gè)勞動(dòng)模范、“是個(gè)大學(xué)生、是個(gè)大學(xué)生、“比比高高2cm、 “在在與與之間之間 “與與同歲都是謂詞。

5、同歲都是謂詞。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示n刻劃一個(gè)個(gè)體性質(zhì)的詞稱之為一元謂詞，刻劃刻劃一個(gè)個(gè)體性質(zhì)的詞稱之為一元謂詞，刻劃n個(gè)個(gè)體之間關(guān)系的詞稱之為個(gè)個(gè)體之間關(guān)系的詞稱之為n元謂詞。元謂詞。n普通我們用大寫英文字母表示謂詞，用小寫英普通我們用大寫英文字母表示謂詞，用小寫英文字母表示個(gè)體稱號(hào)。文字母表示個(gè)體稱號(hào)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示例如，將上述謂詞分別記作大寫字母例如，將上述謂詞分別記作大寫字母F、G、H、 R、S，那么上述命題可表示為：，那么上述命題可表示為： (1) F(a) a：張

6、明：張明 (2) F(b) b：李華：李華 (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)為三元謂詞。為三元謂詞。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示留意留意:(1)單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母后填單獨(dú)一個(gè)謂詞并不是命題，在謂詞字母后填 上個(gè)體所得到的式子稱之為謂詞方式。上個(gè)體所得到的式子稱之為謂詞方式。(2)在謂詞方式中，假設(shè)個(gè)體

7、確定，那么在謂詞方式中，假設(shè)個(gè)體確定，那么A(a1，a2，.，an)就變成了命題。就變成了命題。 (3)在多元謂詞表達(dá)式中，個(gè)體字母出現(xiàn)的先后在多元謂詞表達(dá)式中，個(gè)體字母出現(xiàn)的先后 次序與事先商定有關(guān)，普通不可以隨意交換次序與事先商定有關(guān)，普通不可以隨意交換 位置。位置。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示小結(jié)：本節(jié)將原子命題進(jìn)展分解，分為個(gè)體小結(jié)：本節(jié)將原子命題進(jìn)展分解，分為個(gè)體和謂詞兩部分。進(jìn)而引見(jiàn)了個(gè)體和謂詞、一和謂詞兩部分。進(jìn)而引見(jiàn)了個(gè)體和謂詞、一元謂詞和元謂詞和n元謂詞的概念。重點(diǎn)掌握一元謂元謂詞的概念。重點(diǎn)掌握一元謂詞和詞和n元謂詞的概念。

8、元謂詞的概念。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.1 謂詞的概念與表示謂詞的概念與表示2.2.1 命題函數(shù)命題函數(shù)2.2.2 量詞量詞 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞2.2.1 命題函數(shù)命題函數(shù)例如：設(shè)謂詞例如：設(shè)謂詞H表示表示“是勞動(dòng)模范，是勞動(dòng)模范， a表表示個(gè)體示個(gè)體張明，張明，b表示個(gè)體李華，表示個(gè)體李華，c表示個(gè)體這只老虎，表示個(gè)體這只老虎，那么那么H(a) 、 H(b)、H(c)表示三個(gè)不同的命題，表示三個(gè)不同的命題，但它們但它們有一個(gè)共同的方式，即有一個(gè)共同的方式，即H(x)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與

9、量詞命題函數(shù)與量詞 普通地，普通地， H(x)表示個(gè)體表示個(gè)體x具有性質(zhì)具有性質(zhì)H。這里。這里x表示抽表示抽象的或泛指的個(gè)體，稱為個(gè)體變?cè)?，常用小寫英文字母象的或泛指的個(gè)體，稱為個(gè)體變?cè)?，常用小寫英文字母x,y,z, 表示。相應(yīng)地，表示詳細(xì)或特定的個(gè)體的詞稱表示。相應(yīng)地，表示詳細(xì)或特定的個(gè)體的詞稱為個(gè)體常元，常用小寫英文字母為個(gè)體常元，常用小寫英文字母a,b,c, 表示。表示。 同理，個(gè)體變?cè)?，個(gè)體變?cè)獂,y具有關(guān)系具有關(guān)系L，記作，記作L(x,y)；個(gè)體；個(gè)體變?cè)冊(cè)獂,y,z具有關(guān)系具有關(guān)系A(chǔ)，記作，記作A(x,y,z)。 H(x)、L(x,y) 、A(x,y,z)本身并不是一個(gè)命題。

10、只需本身并不是一個(gè)命題。只需用特定的個(gè)體取代個(gè)體變?cè)锰囟ǖ膫€(gè)體取代個(gè)體變?cè)獂,y,z后，它們才成為命題。后，它們才成為命題。我們稱我們稱H(x)、L(x,y) 、A(x,y,z)為命題函數(shù)。為命題函數(shù)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞定義定義:由一個(gè)謂詞由一個(gè)謂詞H和和n個(gè)個(gè)體變?cè)M成的表達(dá)式個(gè)個(gè)體變?cè)M成的表達(dá)式 H(x1,x2 , , xn)稱為稱為n元簡(jiǎn)單命題函數(shù)。元簡(jiǎn)單命題函數(shù)。 由定義可知，由定義可知，n元謂詞就是有元謂詞就是有n個(gè)個(gè)體變?cè)獋€(gè)個(gè)體變?cè)拿}函數(shù)。當(dāng)?shù)拿}函數(shù)。當(dāng)n=0時(shí)，稱為時(shí)，稱為0元謂詞。因此，元謂詞。因此，普通情況下，

11、命題函數(shù)不是命題；特殊情況普通情況下，命題函數(shù)不是命題；特殊情況0元元謂詞就變成一個(gè)命題。謂詞就變成一個(gè)命題。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞復(fù)合命題函數(shù)：由一個(gè)或幾個(gè)簡(jiǎn)單命題函數(shù)以及邏復(fù)合命題函數(shù)：由一個(gè)或幾個(gè)簡(jiǎn)單命題函數(shù)以及邏輯結(jié)合詞組合而成的表達(dá)式。輯結(jié)合詞組合而成的表達(dá)式。例例1：假設(shè)：假設(shè)x的學(xué)習(xí)好，那么的學(xué)習(xí)好，那么x的任務(wù)好。的任務(wù)好。 設(shè)設(shè)S(x):x學(xué)習(xí)好；學(xué)習(xí)好；W(x):x任務(wù)好任務(wù)好 那么有那么有S(x) W(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞例例2：將以下命題用：將以下命題用0元謂詞

12、符號(hào)化。元謂詞符號(hào)化。(1) 2是素?cái)?shù)且是偶數(shù)。是素?cái)?shù)且是偶數(shù)。(2) 假設(shè)假設(shè)2大于大于3，那么，那么2大于大于4。(3) 假設(shè)張明比李民高，李民比趙亮高，那么張明比假設(shè)張明比李民高，李民比趙亮高，那么張明比趙亮高。趙亮高。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞解：解：(1) 設(shè)設(shè)F(x): x是素?cái)?shù)是素?cái)?shù). G(x): x是偶數(shù)是偶數(shù). 那么命題符號(hào)化為：那么命題符號(hào)化為： F(2)G(2) (2) 設(shè)設(shè)L(x,y) ：x大于大于y. 那么命題符號(hào)化為：那么命題符號(hào)化為： L(2,3) L(2,4) (3) 設(shè)設(shè) H(x,y): x比比y高高. a:張明

13、張明 b:李民李民 c：趙亮：趙亮 那么命題符號(hào)化為：那么命題符號(hào)化為： H(a,b)H(b ,c)H(a,c) 留意：命題函數(shù)中，個(gè)體變?cè)谀男┓秶鷥?nèi)取特定留意：命題函數(shù)中，個(gè)體變?cè)谀男┓秶鷥?nèi)取特定 的值，對(duì)命題的真值極有影響。的值，對(duì)命題的真值極有影響。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞例如：例如：H(x,y)H(y ,z)H(x,z) 假設(shè)假設(shè)H(x,y)解釋為解釋為: x大于大于y，當(dāng)，當(dāng)x,y,z都在實(shí)數(shù)中取都在實(shí)數(shù)中取值時(shí)，那么這個(gè)式子表示值時(shí)，那么這個(gè)式子表示“假設(shè)假設(shè)x大于大于y 且且y 大大于于z，那么，那么x大于大于z 。這是一個(gè)永

14、真式。這是一個(gè)永真式。 假設(shè)假設(shè)H(x,y)解釋為解釋為: “x是是y的兒子，的兒子， 當(dāng)當(dāng)x,y,z都都指人時(shí)，那么這個(gè)式子表示指人時(shí)，那么這個(gè)式子表示“假設(shè)假設(shè)x為為y的兒子的兒子 且且y 是是z的兒子，那么的兒子，那么x是是z的兒子的兒子 。這是一。這是一個(gè)永假式。個(gè)永假式。 假設(shè)假設(shè)H(x,y)解釋為解釋為: “x距距y10米，當(dāng)米，當(dāng)x,y,z為平為平面上的點(diǎn)，那么這個(gè)式子表示面上的點(diǎn)，那么這個(gè)式子表示“假設(shè)假設(shè)x距距y10米米且且y距距z10米，那么米，那么x距距z10米米 。這個(gè)命題的真。這個(gè)命題的真值將由值將由x,y,z的詳細(xì)位置而定，它能夠是的詳細(xì)位置而定，它能夠是1，也，也

15、能夠是能夠是0。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞n在命題函數(shù)中，個(gè)體變?cè)娜≈捣秶Q為在命題函數(shù)中，個(gè)體變?cè)娜≈捣秶Q為個(gè)體域，又稱之為論域。個(gè)體域可以是有個(gè)體域，又稱之為論域。個(gè)體域可以是有限事物的集合，也可以是無(wú)限事物的集合。限事物的集合，也可以是無(wú)限事物的集合。n全總個(gè)體域：宇宙間一切事物組成的個(gè)體全總個(gè)體域：宇宙間一切事物組成的個(gè)體域稱為全總個(gè)體域。域稱為全總個(gè)體域。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞2.2.2 量詞量詞量詞：全稱量詞量詞：全稱量詞()和存在量詞和存在量詞()1.全稱量詞全稱量詞 對(duì)日常

16、言語(yǔ)中的對(duì)日常言語(yǔ)中的“一切、一切、“一切、一切、“凡是凡是 、“每一個(gè)、每一個(gè)、“恣意等詞，用符號(hào)恣意等詞，用符號(hào)“ 表示，表示， 表表示對(duì)個(gè)體域里的一切個(gè)體，示對(duì)個(gè)體域里的一切個(gè)體， F()表示個(gè)體域表示個(gè)體域里的一切個(gè)體具有性質(zhì)里的一切個(gè)體具有性質(zhì)F。 符號(hào)符號(hào)“稱為全稱量詞。稱為全稱量詞。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞例例3：在謂詞邏輯中將以下命題符號(hào)化。：在謂詞邏輯中將以下命題符號(hào)化。1凡是人都呼吸。凡是人都呼吸。 2每個(gè)學(xué)生都要參與考試。每個(gè)學(xué)生都要參與考試。3任何整數(shù)或是正的或是負(fù)的。任何整數(shù)或是正的或是負(fù)的。 第二章第二章 謂謂 詞詞

17、 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞解解: (1) 當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)：當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令令F(x): x呼吸。那么呼吸。那么1符號(hào)化為符號(hào)化為 xF(x). 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令令M(x): x是人。那么是人。那么1符號(hào)化為符號(hào)化為 x(M(x) F(x). 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞(2) 當(dāng)個(gè)體域?yàn)槿w學(xué)生的集合時(shí)：當(dāng)個(gè)體域?yàn)槿w學(xué)生的集合時(shí)： 令令P(x): x要參與考試。那么要參與考試。那么2符號(hào)化為符號(hào)化為 xP(x). 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令令S(x)

18、: x是學(xué)生。那么是學(xué)生。那么2符號(hào)化為符號(hào)化為 x(S(x) P(x). 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞(3) 當(dāng)個(gè)體域?yàn)槿w整數(shù)的集合時(shí)：當(dāng)個(gè)體域?yàn)槿w整數(shù)的集合時(shí)： 令令P(x): x是正的。是正的。N(x): x是負(fù)的。那么是負(fù)的。那么3符符號(hào)化為號(hào)化為 x(P(x)N(x) . 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令令I(lǐng)(x): x是整數(shù)。那么是整數(shù)。那么3符號(hào)化為符號(hào)化為 x(I(x)(P(x)N(x). 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞2.存在量詞存在量詞 對(duì)日常言語(yǔ)中的對(duì)日常言語(yǔ)中的

19、“有一個(gè)、有一個(gè)、“有的、有的、“存在著、存在著、“至少有一個(gè)、至少有一個(gè)、 “存在一些等詞，用符號(hào)存在一些等詞，用符號(hào)“ 表表示，示，表示存在個(gè)體域里的個(gè)體，表示存在個(gè)體域里的個(gè)體， F()表示表示存在個(gè)體域里的個(gè)體具有性質(zhì)存在個(gè)體域里的個(gè)體具有性質(zhì)F。 符號(hào)符號(hào)“稱為存在量詞。稱為存在量詞。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞例例4：在謂詞邏輯中將以下命題符號(hào)化：在謂詞邏輯中將以下命題符號(hào)化.1一些數(shù)是有理數(shù)。一些數(shù)是有理數(shù)。 2有些人活百歲以上。有些人活百歲以上。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞解解: (1)

20、令令Q(x): x是有理數(shù)。那么是有理數(shù)。那么1符號(hào)化為符號(hào)化為 Q(x)。 2當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)：當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令令G(x): x活百歲以上。那么活百歲以上。那么2符號(hào)化為符號(hào)化為 xG(x)。 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)：當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令令M(x): x是人。那么是人。那么2符號(hào)化為符號(hào)化為 x(M(x) G(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞有時(shí)需求同時(shí)運(yùn)用多個(gè)量詞。有時(shí)需求同時(shí)運(yùn)用多個(gè)量詞。例例5：命題：命題“對(duì)恣意的對(duì)恣意的x,存在存在y, 使得使得x+y=5, 取個(gè)體域?yàn)閷?shí)數(shù)集合，那么該命題符號(hào)化為取個(gè)體域?yàn)閷?shí)數(shù)集合，

21、那么該命題符號(hào)化為 x y H(x,y). 其中其中H(x,y): x+y=5. 這是個(gè)真命題這是個(gè)真命題. 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞3. 運(yùn)用量詞時(shí)應(yīng)留意的問(wèn)題運(yùn)用量詞時(shí)應(yīng)留意的問(wèn)題1在不同的個(gè)體域，同一命題的符號(hào)化方式可在不同的個(gè)體域，同一命題的符號(hào)化方式可 能一樣也能夠不同。能一樣也能夠不同。2在不同的個(gè)體域，同一命題的真值能夠一樣在不同的個(gè)體域，同一命題的真值能夠一樣 也能夠不同。也能夠不同。(如，如，Rx表示表示x為大學(xué)生。如為大學(xué)生。如 果個(gè)體域?yàn)榇髮W(xué)里的某個(gè)班級(jí)的學(xué)生，那么果個(gè)體域?yàn)榇髮W(xué)里的某個(gè)班級(jí)的學(xué)生，那么 x Rx為真；假設(shè)個(gè)

22、體域?yàn)橹袑W(xué)里的某個(gè)班級(jí)為真；假設(shè)個(gè)體域?yàn)橹袑W(xué)里的某個(gè)班級(jí) 的學(xué)生，那么的學(xué)生，那么 x Rx為假。為假。) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞3商定以后如不指定個(gè)體域，默以為全總商定以后如不指定個(gè)體域，默以為全總 個(gè)體域。對(duì)每個(gè)個(gè)體變?cè)淖兓秶鷤€(gè)體域。對(duì)每個(gè)個(gè)體變?cè)淖兓秶?用用 特性謂詞加以限制。特性謂詞加以限制。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞特性謂詞：限定個(gè)體變?cè)兓秶闹^詞。特性謂詞：限定個(gè)體變?cè)兓秶闹^詞。普通而言，對(duì)全稱量詞，特性謂詞常作蘊(yùn)含普通而言，對(duì)全稱量詞，特性謂詞常作蘊(yùn)含的前件，如的前

23、件，如x(M(x) F(x)；對(duì)存在量詞，；對(duì)存在量詞，特性謂詞常作合取項(xiàng)，如特性謂詞常作合取項(xiàng)，如x(M(x) G(x)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞(4)普通來(lái)說(shuō)，當(dāng)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，普通來(lái)說(shuō)，當(dāng)多個(gè)量詞同時(shí)出現(xiàn)時(shí)， 它們的順序不能隨意互換。它們的順序不能隨意互換。 例如：在實(shí)數(shù)域上用例如：在實(shí)數(shù)域上用H(x,y)表示表示x+y=5，那么命題，那么命題“對(duì)于恣意的對(duì)于恣意的x，都，都存在存在y使得使得x+y=5可符號(hào)化為：可符號(hào)化為： x yH(x,y)，其真值為，其真值為1。假設(shè)互換。假設(shè)互換量詞順序后為：量詞順序后為： y xH(x,y)

24、 , 其真值其真值為為0。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞(5) 當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí)，如當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí)，如D=a1, a2 , an，對(duì)恣意謂詞，對(duì)恣意謂詞A(x)，有，有 xA(x)A(a1)A(a2)A(an ) xA(x)A(a1)A(a2)A(an ) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞例例6：在謂詞邏輯中將以下命題符號(hào)化。：在謂詞邏輯中將以下命題符號(hào)化。1一切的人都長(zhǎng)頭發(fā)。一切的人都長(zhǎng)頭發(fā)。2有的人吸煙。有的人吸煙。3沒(méi)有人登上過(guò)木星。沒(méi)有人登上過(guò)木星。4清華大學(xué)的學(xué)生未必都是高素質(zhì)的。清華大學(xué)的

25、學(xué)生未必都是高素質(zhì)的。解：令解：令M(x): x是人。特性謂詞是人。特性謂詞1 令令F(x): x長(zhǎng)頭發(fā)。那么符號(hào)化為：長(zhǎng)頭發(fā)。那么符號(hào)化為： x(M(x) F(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞2 令令S(x): x吸煙。那么符號(hào)化為：吸煙。那么符號(hào)化為： x(M(x)S(x)3 令令D(x): x登上過(guò)木星。那么符號(hào)化為：登上過(guò)木星。那么符號(hào)化為： x(M(x)D(x)4令令Q(x):x是清華大學(xué)的學(xué)生。是清華大學(xué)的學(xué)生。H(x):x是高是高 素質(zhì)的。那么符號(hào)化為：素質(zhì)的。那么符號(hào)化為： x(Q(x) H(x) 第二章第二章 謂謂 詞詞 邏邏 輯

26、輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞小結(jié)小結(jié):本節(jié)引見(jiàn)了本節(jié)引見(jiàn)了n元謂詞、命題函數(shù)、全元謂詞、命題函數(shù)、全稱量詞和存在量詞等概念。重點(diǎn)掌握全稱量詞和存在量詞等概念。重點(diǎn)掌握全稱量詞和存在量詞及量化命題的符號(hào)化。稱量詞和存在量詞及量化命題的符號(hào)化。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.2 命題函數(shù)與量詞命題函數(shù)與量詞2.3謂詞公式與翻譯謂詞公式與翻譯n元謂詞元謂詞A(x1，x2.xn) 稱為謂詞演算的原子稱為謂詞演算的原子公式。公式。定義：謂詞演算的合式公式，可由下述各條定義：謂詞演算的合式公式，可由下述各條組成組成:1原子公式是合式公式。原子公式是合式公式。2假設(shè)假設(shè)A 是合式公式，那

27、么是合式公式，那么( A)也是合式也是合式公式。公式。3假設(shè)假設(shè)A，B是合式公式，那么是合式公式，那么(A B)，(A B)，(A B)，(A B)也是合式公式。也是合式公式。4假設(shè)假設(shè)A是合式公式，是合式公式，x是是A中出現(xiàn)的任何中出現(xiàn)的任何變?cè)冊(cè)?那么那么(x)A , (x)A，也是合式公式。，也是合式公式。5只需有限次運(yùn)用只需有限次運(yùn)用(1)(4)得到的公式是合得到的公式是合式公式。式公式。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.3 謂詞公式與翻譯謂詞公式與翻譯例例1：在謂詞邏輯中將以下命題符號(hào)化：在謂詞邏輯中將以下命題符號(hào)化.1凡正數(shù)都大于零。凡正數(shù)都大于零。2存在小于存在小于2的

28、素?cái)?shù)。的素?cái)?shù)。3沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù)。沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù)。4并不是一切參與考試的人都能獲得好成果。并不是一切參與考試的人都能獲得好成果。解：解：1令令F(x): x是正數(shù)。是正數(shù)。M(x):x大于零。大于零。 那么符號(hào)化為：那么符號(hào)化為： x(F(x)M(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.3 謂詞公式與翻譯謂詞公式與翻譯2令令E(x): x小于小于2。S(x):x是素?cái)?shù)。那么符號(hào)化是素?cái)?shù)。那么符號(hào)化為：為： x(E(x)S(x)真值為真值為0 3令令D(x): x是有理數(shù)。是有理數(shù)。F(x):x能表示成分?jǐn)?shù)。能表示成分?jǐn)?shù)。 那么符號(hào)化為：那么符號(hào)化為： x(D(x)

29、F(x) 或或 x(D(x) F(x)真值為真值為 4令令M(x)：x是人。是人。Q(x):x參與考試。參與考試。 H(x):x獲得好成果。那么符號(hào)化為：獲得好成果。那么符號(hào)化為： x(M(x)Q(x)H(x) 或或 x(M(x)Q(x) H(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.3 謂詞公式與翻譯謂詞公式與翻譯例例2：在謂詞邏輯中將以下命題符號(hào)化：在謂詞邏輯中將以下命題符號(hào)化. 1一切運(yùn)發(fā)動(dòng)都?xì)J佩某些教練一切運(yùn)發(fā)動(dòng)都?xì)J佩某些教練.2有些運(yùn)發(fā)動(dòng)不欽佩教練有些運(yùn)發(fā)動(dòng)不欽佩教練.設(shè)：設(shè)：L(x):x是運(yùn)發(fā)動(dòng)是運(yùn)發(fā)動(dòng) J(y):y是教練是教練 A(x,y):x欽佩欽佩y(1) (x)(L(x

30、) y)(J(y)A(x,y)(2)x)(L(x) (y)(J(y)A(x,y) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.3 謂詞公式與翻譯謂詞公式與翻譯小結(jié)：本節(jié)引見(jiàn)了謂詞合式公式的概念，重點(diǎn)小結(jié)：本節(jié)引見(jiàn)了謂詞合式公式的概念，重點(diǎn)掌握謂詞公式的翻譯。掌握謂詞公式的翻譯。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.3 謂詞公式與翻譯謂詞公式與翻譯2.4.1變?cè)募s束變?cè)募s束定義定義:在謂詞公式中，形如在謂詞公式中，形如( x)P(x)和和( x)P(x)的部的部 分，稱為謂詞公式的分，稱為謂詞公式的x約束部分。約束部分。 ( x)P(x)或或( x)P(x)中的中的x叫做量詞的指點(diǎn)變?cè)凶隽?/p>

31、詞的指點(diǎn)變?cè)?或作用變?cè)?，或作用變?cè)?，P(x)稱為相應(yīng)量詞的作用域或轄域。稱為相應(yīng)量詞的作用域或轄域。 在在 x和和 x的轄域中，的轄域中，x的一切出現(xiàn)都稱為約束出的一切出現(xiàn)都稱為約束出 現(xiàn)，相應(yīng)的現(xiàn)，相應(yīng)的x稱為約束變?cè)Q為約束變?cè)? P(x)中除約束變?cè)谐s束變?cè)?以外出現(xiàn)的變?cè)Q為是自在變?cè)Ｒ酝獬霈F(xiàn)的變?cè)Q為是自在變?cè)?第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束例例1： 1、 x( H(x,y)y(W(y) L(x,y,z) 2、 x( H(x)W(y) y( F(x) L(x,y,z) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束闡明闡明

32、:(1)n元謂詞公式元謂詞公式A(x1，x2.xn) 中有中有n個(gè)自在變?cè)賯€(gè)自在變?cè)?，假設(shè)對(duì)其中的設(shè)對(duì)其中的k(kn)個(gè)進(jìn)展約束，那么構(gòu)成了個(gè)進(jìn)展約束，那么構(gòu)成了n-k元元謂詞；假設(shè)一個(gè)公式中沒(méi)有自在變?cè)霈F(xiàn)，那么謂詞；假設(shè)一個(gè)公式中沒(méi)有自在變?cè)霈F(xiàn)，那么該公式就變成了一個(gè)命題。該公式就變成了一個(gè)命題。(2)一個(gè)公式的約束變?cè)\(yùn)用的稱號(hào)符號(hào)是無(wú)關(guān)緊一個(gè)公式的約束變?cè)\(yùn)用的稱號(hào)符號(hào)是無(wú)關(guān)緊要的，如要的，如(x)M(x)與與(y)M(y)意義一樣。意義一樣。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束2.4.2 約束變?cè)膿Q名與自在變?cè)拇爰s束變?cè)膿Q名與自在變?cè)?/p>

33、代入 一個(gè)變?cè)谕粋€(gè)公式中既是自在出現(xiàn)又是約束出現(xiàn)，一個(gè)變?cè)谕粋€(gè)公式中既是自在出現(xiàn)又是約束出現(xiàn)，這樣在了解上容易發(fā)生混淆。為了防止這種混亂，可對(duì)約這樣在了解上容易發(fā)生混淆。為了防止這種混亂，可對(duì)約束變?cè)M(jìn)展換名。束變?cè)M(jìn)展換名。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束換名規(guī)那么換名規(guī)那么: (對(duì)約束變?cè)詫?duì)約束變?cè)詫?duì)約束變?cè)M(jìn)展換名，使得一個(gè)變?cè)谝粋€(gè)公式對(duì)約束變?cè)M(jìn)展換名，使得一個(gè)變?cè)谝粋€(gè)公式中中只呈一種方式出現(xiàn)只呈一種方式出現(xiàn)(1)約束變?cè)梢該Q名，其更改的變?cè)Q號(hào)范圍是約束變?cè)梢該Q名，其更改的變?cè)Q號(hào)范圍是量詞中的指點(diǎn)變?cè)约霸摿吭~作用域中所出現(xiàn)

34、的量詞中的指點(diǎn)變?cè)约霸摿吭~作用域中所出現(xiàn)的該變?cè)?，公式的其他部分不變。該變?cè)?，公式的其他部分不變?2)換名時(shí)一定要更改為作用域中沒(méi)有出現(xiàn)的變?cè)獡Q名時(shí)一定要更改為作用域中沒(méi)有出現(xiàn)的變?cè)Q號(hào)。稱號(hào)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束例例1: x( P(x)R(x,y) L(x,y)換名為換名為t( P(t)R(t,y) L(x,y) 2：x( H(x,y)y(W(y) L(x,y,z)換名為換名為x( H(x,y)s(W(s) L(x,s,z) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束代入規(guī)那么對(duì)自在變?cè)源胍?guī)那么對(duì)自在變?cè)詫?duì)公式

35、中自在變?cè)母姆Q為代入對(duì)公式中自在變?cè)母姆Q為代入(1)對(duì)于謂詞公式中的自在變?cè)梢宰鞔?，代入時(shí)對(duì)于謂詞公式中的自在變?cè)梢宰鞔?，代入時(shí)需求對(duì)公式中出現(xiàn)該自在變?cè)拿恳惶庍M(jìn)展；需求對(duì)公式中出現(xiàn)該自在變?cè)拿恳惶庍M(jìn)展；(2)用以代入的變?cè)c原公式中一切變?cè)姆Q號(hào)不能用以代入的變?cè)c原公式中一切變?cè)姆Q號(hào)不能一樣。一樣。例：例：x( P(x)R(x,y) L(x,y) 對(duì)自在變?cè)獙?duì)自在變?cè)獃用用z來(lái)代入，得來(lái)代入，得x( P(x)R(x,z)L(x,z) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束小結(jié)：本節(jié)引見(jiàn)了約束變?cè)⒆栽谧冊(cè)男〗Y(jié)：本節(jié)引見(jiàn)了約束變?cè)?、自在變?cè)?/p>

36、 概念，重點(diǎn)掌握約束變?cè)膿Q名與自在變?cè)拍?，重點(diǎn)掌握約束變?cè)膿Q名與自在變?cè)拇搿５拇搿?第二章第二章 謂謂 詞詞 邏邏 輯輯2.4 變?cè)募s束變?cè)募s束2.5.1謂詞公式的等價(jià)和永真的概念謂詞公式的等價(jià)和永真的概念定義：一個(gè)解釋定義：一個(gè)解釋I由下面由下面4部分組成：部分組成：1.非空個(gè)體域非空個(gè)體域DI；2.DI中部分特定元素中部分特定元素a、b， .；3.DI上的特定一些函數(shù)上的特定一些函數(shù)f、g， .；4. DI上特定謂詞上特定謂詞P、Q， .。見(jiàn)書見(jiàn)書P40例例2.4.1。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式定義：給定恣

37、意的謂詞公式定義：給定恣意的謂詞公式A，其個(gè)體域?yàn)椋鋫€(gè)體域?yàn)镋，1對(duì)于對(duì)于A的一切解釋，公式的一切解釋，公式A都為真，那么稱都為真，那么稱A在在E上是永真的上是永真的(或有效的或有效的)。2假設(shè)對(duì)于假設(shè)對(duì)于A的一切解釋，公式的一切解釋，公式A都為假，那么都為假，那么稱稱A在在E上是永假的上是永假的(或不可滿足的或不可滿足的)。3假設(shè)至少存在著一種解釋使得公式假設(shè)至少存在著一種解釋使得公式A為真，那為真，那么稱么稱A在在E上是可滿足的。上是可滿足的。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式定義：給定任何兩個(gè)謂詞公式定義：給定任何兩個(gè)謂詞公式

38、A、B，設(shè)它們，設(shè)它們有共同的個(gè)體域有共同的個(gè)體域E，假設(shè)對(duì)，假設(shè)對(duì)A和和B的任一組的任一組變?cè)M(jìn)展解釋，所得命題的真值一樣，那變?cè)M(jìn)展解釋，所得命題的真值一樣，那么稱謂詞公式么稱謂詞公式A和和B在在E上等價(jià)，并記為上等價(jià)，并記為A B。定義：給定任何兩個(gè)謂詞公式定義：給定任何兩個(gè)謂詞公式A、B，當(dāng)且僅，當(dāng)且僅當(dāng)當(dāng)A B是永真式時(shí)，稱是永真式時(shí)，稱“A蘊(yùn)涵蘊(yùn)涵B，記作，記作A B。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式2.5.2 謂詞演算的等價(jià)式和蘊(yùn)涵式謂詞演算的等價(jià)式和蘊(yùn)涵式1、命題公式的推行、命題公式的推行在命題公式中成立的等價(jià)公式，

39、用謂詞公式去代換在命題公式中成立的等價(jià)公式，用謂詞公式去代換其中相應(yīng)的命題變?cè)?，得到的公式依然成立其中相?yīng)的命題變?cè)玫降墓揭廊怀闪⑷纾喝纾?x( P(x)Q(x) x( P(x) Q(x) P(x) Q(x) P(x) Q(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式2、量詞與、量詞與 之間的關(guān)系之間的關(guān)系 xP(x) x P(x) xP(x) x P(x)證明：對(duì)個(gè)體域證明：對(duì)個(gè)體域 a1，a2，an， xP(x) (P(a1)P(a2)P(an) P(a1) P(a2) P(an) x P(x) 第二章第二章 謂謂 詞詞 邏邏 輯

40、輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式3、量詞作用域的擴(kuò)張與收縮、量詞作用域的擴(kuò)張與收縮量詞作用域中假設(shè)有合取或析取項(xiàng)，且其中有一個(gè)量詞作用域中假設(shè)有合取或析取項(xiàng)，且其中有一個(gè)是命題，那么可將該命題移至量詞作用域之外。如：是命題，那么可將該命題移至量詞作用域之外。如： xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B xA(x)B 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式證明：當(dāng)個(gè)體域?yàn)樽C明：當(dāng)個(gè)體域?yàn)閍1，a2，an ， xA(x)P (P(a1)P(a2)P(an)P)

41、(P(a1)P)(P(a2) P)(P(an)P) x(A(x)P) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式n量詞作用域的擴(kuò)張和收縮量詞作用域的擴(kuò)張和收縮n( xA(x)B x) (A(x) Bn(x)A(x) B) (x) (A(x)Bn(B (x)A(x)x)(B A(x)n(B (x)A(x) x(B A(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式例例1：xA(x，y)P(y) x(A(x，y)P(y)例例2：xy(P(x)Q(y ) ( x P(x) yQ(y) 第二章第二章

42、謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式例例1：xA(x，y)P(y) x(A(x，y)P(y)例例2：xy(P(x)Q(y ) ( x P(x) yQ(y)證明：證明：xy(P(x)Q(y ) xy(P(x) Q(y ) x (P(x) y Q(y ) xP(x)yQ(y ) x P(x) y Q(y ) x P(x) yQ(y) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式4、量詞的分配、量詞的分配設(shè)設(shè)A(x)、B(x)是恣意的含自在出現(xiàn)個(gè)體變是恣意的含自在出現(xiàn)個(gè)體變?cè)獂的公式，那么的公式，那么(1)

43、x(A(x)B(x) x A(x) x B(x) (2) x(A(x)B(x) x A(x) x B(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式證明：對(duì)個(gè)體域證明：對(duì)個(gè)體域a1，a2，an x(A(x)B(x)(A(a1)B(a1) (A(an)B(an)(A(a1)A(a2)A(an)(B(a1)B(a2)B(an) xA(x)xB(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式(3) x(A(x)B(x) x A(x) x B(x)(4) x(A(x)B(x) x A(x) x B(

44、x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式留意：逆方向不成立。留意：逆方向不成立。如如4式，式，xA(x) x B(x)x(A(x)B(x)不成立。不成立。舉反例：設(shè)個(gè)體域是整數(shù)集合舉反例：設(shè)個(gè)體域是整數(shù)集合 A(x)：x為奇數(shù)為奇數(shù) ，B(x)：x為偶數(shù)，為偶數(shù)， 那么那么xA(x)xB(x)為真，但為真，但x(A(x)B(x)為假。為假。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式(5) x (A(x) B(x) xA(x) xB(x)(6) x A(x) xB(x) x (A(x)

45、B(x) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式5、多個(gè)量詞的運(yùn)用、多個(gè)量詞的運(yùn)用 (1) xyP(x，y ) y xP(x，y ) (二者二者同義同義) (2) xyP(x，y ) y xP(x，y ) xyP(x，y ) x yP(x，y ) (3) yxP(x，y) xyP(x，y) (4) xyPx，y xyP(x，y) yxPx，y yxP(x，y) (5) yxPx，y yxP(x，y) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式留意留意:上述蘊(yùn)涵式逆方向均不成立。上述蘊(yùn)涵式逆方

46、向均不成立。例：如例：如3中，設(shè)個(gè)體域?yàn)橛欣頂?shù)集合，中，設(shè)個(gè)體域?yàn)橛欣頂?shù)集合， P(x,y) ：x+y=0， 那么那么xy P(x,y)為真。為真。 但是，但是，y xP(x,y)為假。為假。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式小結(jié)：本節(jié)引見(jiàn)了謂詞演算的根本等價(jià)式和蘊(yùn)涵式。小結(jié)：本節(jié)引見(jiàn)了謂詞演算的根本等價(jià)式和蘊(yùn)涵式。重點(diǎn)掌握謂詞公式之間的等價(jià)演算。重點(diǎn)掌握謂詞公式之間的等價(jià)演算。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.5 謂詞演算的等價(jià)式與謂詞演算的等價(jià)式與蘊(yùn)涵式蘊(yùn)涵式定義定義:任何一個(gè)謂詞公式任何一個(gè)謂詞公式A，假設(shè)具有如下方式：

47、，假設(shè)具有如下方式： (x1) (x2) (xn)B， 其中其中能夠是量詞能夠是量詞 或量詞或量詞 ，xii=1， n 是個(gè)體變?cè)?，是個(gè)體變?cè)?，B是不含量詞的謂詞公式，那么是不含量詞的謂詞公式，那么稱稱 A是前束范式。是前束范式。闡明：前束范式的量詞均在全式的開(kāi)頭闡明：前束范式的量詞均在全式的開(kāi)頭,它們的作用它們的作用 域延伸到整個(gè)公式的末尾。域延伸到整個(gè)公式的末尾。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式 例例: x y(F(x)G(y) H(x,y) x y(F(x,y)G(y,z) x H(x,y,z) 定理：任何一個(gè)謂詞公式，均和一個(gè)前束范定理：任何一個(gè)謂詞公式，

48、均和一個(gè)前束范 式等價(jià)。式等價(jià)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式前束范式的求法：前束范式的求法：第一步：否認(rèn)深化。即利用量詞轉(zhuǎn)化公式，把否認(rèn)第一步：否認(rèn)深化。即利用量詞轉(zhuǎn)化公式，把否認(rèn)結(jié)合詞深化到命題變?cè)椭^詞填式的前面。結(jié)合詞深化到命題變?cè)椭^詞填式的前面。第二步：改名。即利用換名規(guī)那么、代入規(guī)那么改第二步：改名。即利用換名規(guī)那么、代入規(guī)那么改換一換一些變?cè)姆Q號(hào)，以便消除混亂。些變?cè)姆Q號(hào)，以便消除混亂。第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張第三步：量詞前移。即利用量詞轄域的收縮與擴(kuò)張把量詞移到前面。把量詞移到前面。這樣便可求出與公式等價(jià)的前束范式。這樣

49、便可求出與公式等價(jià)的前束范式。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式例例: :求以下公式的前束范式。求以下公式的前束范式。),(),()(),()(),()()6(),()()()(),()()5()()()()()4()()()()() 3()()()()()2()()()()() 1 (yxBxyAyyxByxyxAyxyxHxyGyyxFxxGxxFxxGxxFxxGxxFxxGxxFx 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式n解解:)()()()()()()()()()()() 1 (量詞分配量詞轉(zhuǎn)換律xGxFxxGxxFxxGxxFx)(

50、)()()()()()()()()()()()()()()()()()()()2(轄域擴(kuò)張轄域擴(kuò)張換名量詞轉(zhuǎn)換律yGxFyxyGyxFxyGyxFxxGxxFxxGxxFx 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式 )(,()(),()()()()(,()()(),()()()(,()()(),()()()(,()()()(),()()(,()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()(),()()()(),()()5(轄域擴(kuò)張轄域擴(kuò)張轄域擴(kuò)張換名代入ztHyGzxFtyxztHtyGzxFyxztHtyGzxFy

51、xztHtyGyzxFxzxHxyGyzxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFxyxHxyGyyxFx 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式n ),(),()(),()(),()(),(),()(),()(),()(),(),()(),()(),()()(),(),()(),()(),()()6(yxBxyAyyxByxyxAyxyxBxyAyyxByxyxAyxyxBxyAyyxByxyxAyxyxBxyAyyxByxyxAyx 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式 ),(),(),(),()()()()()(,

52、(),()(),()(),()(),(),()(),()(),()()6(zuBuzAvuByxAzvuyxzuBuzAzvuBvuyxAyxyxBxyAyyxByxyxAyx換名續(xù) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式闡明：闡明：1.等價(jià)演算的順序不同，使得前束范式不獨(dú)一。等價(jià)演算的順序不同，使得前束范式不獨(dú)一。2.一個(gè)謂詞公式的前束范式的各指點(diǎn)變?cè)獞?yīng)是各不一個(gè)謂詞公式的前束范式的各指點(diǎn)變?cè)獞?yīng)是各不一樣的，原來(lái)在謂詞公式中自在出現(xiàn)的個(gè)體變?cè)粯拥?，原?lái)在謂詞公式中自在出現(xiàn)的個(gè)體變?cè)谇笆妒街羞€應(yīng)是自在出現(xiàn)。在前束范式中還應(yīng)是自在出現(xiàn)。小結(jié)：本節(jié)引見(jiàn)了謂詞公式前束范式

53、的概念和求法。小結(jié)：本節(jié)引見(jiàn)了謂詞公式前束范式的概念和求法。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.6 前束范式前束范式2.7.1推理規(guī)那么推理規(guī)那么在謂詞演算中，推理的方式構(gòu)造仍為在謂詞演算中，推理的方式構(gòu)造仍為 H1 H2 H3 . HnC。假設(shè)假設(shè) H1 H2 H3 . HnC是永真式，那么稱是永真式，那么稱由前由前提提H1,H2,H3,Hn邏輯的推出結(jié)論邏輯的推出結(jié)論C，但在謂，但在謂詞詞邏輯中邏輯中, H1,H2,H3,.,Hn , C均為謂詞公式。均為謂詞公式。命題演算中的推理規(guī)那么，可在謂詞推理實(shí)命題演算中的推理規(guī)那么，可在謂詞推理實(shí)際中運(yùn)用。際中運(yùn)用。 第二章第二章 謂謂 詞

54、詞 邏邏 輯輯2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際與量詞有關(guān)的四條重要推理規(guī)那么：與量詞有關(guān)的四條重要推理規(guī)那么：1、全稱量詞消去規(guī)那么、全稱量詞消去規(guī)那么US規(guī)那么規(guī)那么2、全稱量詞產(chǎn)生規(guī)那么、全稱量詞產(chǎn)生規(guī)那么UG規(guī)那么規(guī)那么3、存在量詞消去規(guī)那么、存在量詞消去規(guī)那么ES規(guī)那么規(guī)那么4、存在量詞產(chǎn)生規(guī)那么、存在量詞產(chǎn)生規(guī)那么EG規(guī)那么規(guī)那么留意：只能對(duì)前束范式適用上述規(guī)那么。留意：只能對(duì)前束范式適用上述規(guī)那么。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際1. 全稱指定規(guī)那么全稱指定規(guī)那么 US ： x A(x) A(c) x A(x) A(y)

55、 運(yùn)用此規(guī)那么時(shí)要留意：運(yùn)用此規(guī)那么時(shí)要留意： 1x是是A(x)中的自在變?cè)?；中的自在變?cè)?2c是個(gè)體域中恣意個(gè)體常元；是個(gè)體域中恣意個(gè)體常元；3y為恣意不在為恣意不在A(x)中約束出現(xiàn)的個(gè)體變?cè)?。中約束出現(xiàn)的個(gè)體變?cè)?第二章第二章 謂謂 詞詞 邏邏 輯輯2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際例：設(shè)例：設(shè)F(x，y)：xy ， x、y的個(gè)體域?yàn)閷?shí)數(shù)的個(gè)體域?yàn)閷?shí)數(shù)集合集合 ，令，令A(yù)(x) y F(x，y)，那么那么x A(x) x y F(x，y) , 該式真值為該式真值為1。假設(shè)運(yùn)用假設(shè)運(yùn)用US得得y F(y，y) ，那么是錯(cuò)誤的，那么是錯(cuò)誤的，正確的做法是換成正確的做法是換成y

56、F(z，y) 第二章第二章 謂謂 詞詞 邏邏 輯輯2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際2.全稱推行規(guī)那么全稱推行規(guī)那么UG： A(y) x A(x) 運(yùn)用此規(guī)那么時(shí)留意運(yùn)用此規(guī)那么時(shí)留意: (1) y在在A(y)中自在出現(xiàn)，且中自在出現(xiàn)，且y取任何值時(shí)取任何值時(shí)A均均為真；為真； (2) 取代取代y的的x不在不在A(y)中約束出現(xiàn)。中約束出現(xiàn)。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際例：設(shè)例：設(shè)F(x，y)：xy ， x、y的個(gè)體域?yàn)閷?shí)數(shù)的個(gè)體域?yàn)閷?shí)數(shù)集合集合 ，令，令A(yù)(y) x F(x，y)，該式真值為，該式真值為1，假設(shè)運(yùn)用假設(shè)運(yùn)用UG規(guī)

57、那么取規(guī)那么取x替代替代y得得x x F(x，x) ，那么，那么是錯(cuò)誤的，正確的做法是換成是錯(cuò)誤的，正確的做法是換成z x F(x，z) 。 第二章第二章 謂謂 詞詞 邏邏 輯輯2.7 謂詞演算的推理實(shí)際謂詞演算的推理實(shí)際3.存在指定規(guī)那么存在指定規(guī)那么(ES): x A(x) A(c)留意：留意：c是個(gè)體域中的某些個(gè)體，是個(gè)體域中的某些個(gè)體，c并不具有恣意性。并不具有恣意性。運(yùn)用此規(guī)那么時(shí)應(yīng)留意：運(yùn)用此規(guī)那么時(shí)應(yīng)留意：1c是使是使A為真的特定的個(gè)體常元，且未在為真的特定的個(gè)體常元，且未在A(x)中中 出現(xiàn)過(guò)；出現(xiàn)過(guò)；2假設(shè)假設(shè)A(x)中有其他自在變?cè)霈F(xiàn)，且中有其他自在變?cè)霈F(xiàn)，且x是隨其是隨其 他自在變?cè)兓?，那么不能運(yùn)用此規(guī)那么。他自在變?cè)兓?/p>