謂詞邏輯 離散數(shù)學(xué)

1、1第二章第二章 謂詞邏輯謂詞邏輯第一章第一章 命題邏輯回顧：命題邏輯回顧：2為什么引入謂詞邏輯？為什么引入謂詞邏輯？命題邏輯的特點(diǎn)：命題邏輯的特點(diǎn)：1、其研究的基本單位是原子命題；、其研究的基本單位是原子命題；2、不再對(duì)原子命題進(jìn)行分解；、不再對(duì)原子命題進(jìn)行分解；3、原子命題之間通過(guò)聯(lián)結(jié)詞組合成為復(fù)合命題，并由原子命題、原子命題之間通過(guò)聯(lián)結(jié)詞組合成為復(fù)合命題，并由原子命題的真值和聯(lián)結(jié)詞共同決定復(fù)合命題的真值；的真值和聯(lián)結(jié)詞共同決定復(fù)合命題的真值；4、原子命題本身之間并無(wú)實(shí)質(zhì)聯(lián)系。、原子命題本身之間并無(wú)實(shí)質(zhì)聯(lián)系。命題邏輯的局限性：命題邏輯的局限性：1、顆粒度太大，無(wú)法研究命題的內(nèi)部關(guān)系；、顆粒度

2、太大，無(wú)法研究命題的內(nèi)部關(guān)系；2、無(wú)法描述同一個(gè)體的多個(gè)性質(zhì)；、無(wú)法描述同一個(gè)體的多個(gè)性質(zhì)；3、無(wú)法描述具有共同屬性（、無(wú)法描述具有共同屬性（性質(zhì)和關(guān)系性質(zhì)和關(guān)系）的命題之間的聯(lián)系；）的命題之間的聯(lián)系；4、不能揭示某些有效的推論。、不能揭示某些有效的推論。因此，需要對(duì)命題邏輯進(jìn)行推廣，導(dǎo)致謂詞邏輯被引入。因此，需要對(duì)命題邏輯進(jìn)行推廣，導(dǎo)致謂詞邏輯被引入。3為什么引入謂詞邏輯（實(shí)例）？為什么引入謂詞邏輯（實(shí)例）？實(shí)例實(shí)例1（蘇格拉底三段論）：（蘇格拉底三段論）：所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。 P：所有的人都是要死；

3、：所有的人都是要死； Q：蘇格拉底是人；：蘇格拉底是人； R：蘇格拉底要死。：蘇格拉底要死。三段論表示為三段論表示為(P Q)R，但該公式，但該公式在命題邏輯里在命題邏輯里不是重言式。不是重言式。實(shí)例實(shí)例2： P：所有自然數(shù)有大于它的素?cái)?shù)；：所有自然數(shù)有大于它的素?cái)?shù)； Q：100是自然數(shù)；是自然數(shù)； R： 100有大于它的素?cái)?shù)。有大于它的素?cái)?shù)。從謂詞邏輯的角度：從謂詞邏輯的角度：實(shí)例中實(shí)例中P和和Q有聯(lián)系；有聯(lián)系；Q和和R有聯(lián)系；有聯(lián)系；P和和R也有聯(lián)系。在學(xué)習(xí)謂詞邏輯之后，將看到實(shí)例中的有效推論。也有聯(lián)系。在學(xué)習(xí)謂詞邏輯之后，將看到實(shí)例中的有效推論。4什么是謂詞邏輯？什么是謂詞邏輯？1、回顧

4、：什么是命題？、回顧：什么是命題？2、由表及里由表及里看命題：命題由其看命題：命題由其基本成分基本成分（主、謂、賓等）（主、謂、賓等）構(gòu)成。構(gòu)成。3、判斷：、判斷：x=5 是否命題？是否命題？4、通過(guò)量化，引入量詞，可以把一部分非命題轉(zhuǎn)化為命題。、通過(guò)量化，引入量詞，可以把一部分非命題轉(zhuǎn)化為命題。因此，謂詞邏輯研究的基本部件包括：因此，謂詞邏輯研究的基本部件包括：個(gè)體個(gè)體（及其（及其論論域域）、）、謂詞謂詞、量詞量詞等。等。謂詞邏輯與命題邏輯之間的關(guān)系：謂詞邏輯與命題邏輯之間的關(guān)系：l 繼承繼承（聯(lián)結(jié)詞、等價(jià)公式、蘊(yùn)含公式、推理規(guī)則（聯(lián)結(jié)詞、等價(jià)公式、蘊(yùn)含公式、推理規(guī)則）；）；l 發(fā)展發(fā)展（量

5、詞、新公式、新規(guī)則（量詞、新公式、新規(guī)則） 。52.1、2.2 謂詞的概念與表示謂詞的概念與表示 概念概念1：個(gè)體詞：個(gè)體詞個(gè)體詞（個(gè)體詞（主語(yǔ)或賓語(yǔ)等主語(yǔ)或賓語(yǔ)等）所研究對(duì)象中可以獨(dú)立存在的所研究對(duì)象中可以獨(dú)立存在的具體（如：張三）具體（如：張三）或或抽象（如：抽象（如：3，x）的客體）的客體。分類(lèi)：分類(lèi)： 個(gè)體常項(xiàng)個(gè)體常項(xiàng)：具體的事物，用：具體的事物，用a, b, c表示；表示； 個(gè)體變項(xiàng)個(gè)體變項(xiàng)：抽象的事物，用：抽象的事物，用x, y, z表示。表示。討論對(duì)象：討論對(duì)象： 個(gè)體域個(gè)體域(論域論域)個(gè)體變項(xiàng)的取值范圍。個(gè)體變項(xiàng)的取值范圍。 有限個(gè)體域，如有限個(gè)體域，如 a, b, c, 1

6、, 2； 無(wú)限個(gè)體域，如無(wú)限個(gè)體域，如 N, Z, R, 全總個(gè)體域（全總個(gè)體域（默認(rèn)默認(rèn)）由宇宙間一切事物組成。由宇宙間一切事物組成。6概念概念2：謂詞謂詞謂詞謂詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞分類(lèi)分類(lèi)1： 謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞，如，如, F(a)：a是人是人 謂詞變項(xiàng)：表示抽象或泛指的性質(zhì)或關(guān)系的謂詞，謂詞變項(xiàng)：表示抽象或泛指的性質(zhì)或關(guān)系的謂詞，如如, G(x)：x具有性質(zhì)具有性質(zhì)G分類(lèi)分類(lèi)2：n（n 1）元謂詞（含）元謂詞（含n個(gè)個(gè)命題變?cè)}變?cè)闹^詞）的謂詞） 一元謂詞一元謂詞(n=1)表示性質(zhì)；表示性

7、質(zhì)； 多元謂詞多元謂詞(n 2)表示事物之間的關(guān)系；表示事物之間的關(guān)系； 如如, L(x,y)：x與與 y 有關(guān)系有關(guān)系 L，L(x,y)：x y，注意：注意：1、 0元謂詞元謂詞不含個(gè)體變項(xiàng)的謂詞不含個(gè)體變項(xiàng)的謂詞, 即命題常項(xiàng)，因此，可將即命題常項(xiàng)，因此，可將命題看成特殊的謂詞命題看成特殊的謂詞；2、個(gè)體的順序不能任意調(diào)換，否則可能影響其真值；、個(gè)體的順序不能任意調(diào)換，否則可能影響其真值；3、個(gè)體域的選取決定謂詞是否成為命題及其真值情況。、個(gè)體域的選取決定謂詞是否成為命題及其真值情況。7概念概念3：命題函數(shù)命題函數(shù) 簡(jiǎn)單命題函數(shù)簡(jiǎn)單命題函數(shù)由一個(gè)由一個(gè)謂詞謂詞和若干個(gè)個(gè)體和若干個(gè)個(gè)體變?cè)?/p>

8、元組成的命題組成的命題形式稱(chēng)為簡(jiǎn)單命題函數(shù)，表示為形式稱(chēng)為簡(jiǎn)單命題函數(shù)，表示為P(x1,x2,xn)。復(fù)合命題函數(shù)復(fù)合命題函數(shù)由一個(gè)或若干個(gè)由一個(gè)或若干個(gè)簡(jiǎn)單命題函數(shù)簡(jiǎn)單命題函數(shù)以及以及邏輯聯(lián)結(jié)邏輯聯(lián)結(jié)詞詞組成的命題形式稱(chēng)為復(fù)合命題函數(shù)。組成的命題形式稱(chēng)為復(fù)合命題函數(shù)。注意：注意：1、當(dāng)所有的、當(dāng)所有的個(gè)體變?cè)獋€(gè)體變?cè)锰囟ǖ挠锰囟ǖ膫€(gè)體常元個(gè)體常元替換替換之后，命題函數(shù)之后，命題函數(shù)成為一個(gè)命題（可見(jiàn)：成為一個(gè)命題（可見(jiàn)：命題函數(shù)不是一個(gè)命題命題函數(shù)不是一個(gè)命題）；）；2、命題函數(shù)是一類(lèi)函數(shù)，有、命題函數(shù)是一類(lèi)函數(shù)，有定義域定義域、值域值域；3、命題函數(shù)與、命題函數(shù)與一般函數(shù)一般函數(shù)、真值函

9、數(shù)真值函數(shù)的區(qū)別；的區(qū)別；4、復(fù)合命題函數(shù)的真值由組成它的、復(fù)合命題函數(shù)的真值由組成它的簡(jiǎn)單命題函數(shù)簡(jiǎn)單命題函數(shù)以及以及邏輯聯(lián)邏輯聯(lián)結(jié)詞決定。結(jié)詞決定。8概念概念4：量詞量詞(1/2)量詞量詞表示個(gè)體常量與個(gè)體變量之間數(shù)量關(guān)系的詞表示個(gè)體常量與個(gè)體變量之間數(shù)量關(guān)系的詞, 起到把個(gè)起到把個(gè)體變量變成常量的作用（如：體變量變成常量的作用（如：x=5）( 和和 的由來(lái)？的由來(lái)？) 全稱(chēng)量詞全稱(chēng)量詞 : 表示所有的表示所有的. x : 對(duì)個(gè)體域中所有的對(duì)個(gè)體域中所有的x； 如如, xF(x)表示個(gè)體域中所有的表示個(gè)體域中所有的x具有性質(zhì)具有性質(zhì)F ； x yG(x,y)表示個(gè)體域中所有的表示個(gè)體域中所

10、有的x和和y有關(guān)系有關(guān)系G ； 存在量詞存在量詞 : 表示存在表示存在, 有一個(gè)有一個(gè). x : 個(gè)體域中有一個(gè)個(gè)體域中有一個(gè)x ； 如如, xF(x)表示個(gè)體域中有一個(gè)表示個(gè)體域中有一個(gè)x具有性質(zhì)具有性質(zhì)F ； x yG(x,y)表示個(gè)體域中存在表示個(gè)體域中存在x和和y有關(guān)系有關(guān)系G ； x yG(x,y)表示對(duì)個(gè)體域中每一個(gè)表示對(duì)個(gè)體域中每一個(gè)x都存在一個(gè)都存在一個(gè)y使得使得 x和和y有關(guān)系有關(guān)系G ； x yG(x,y)表示個(gè)體域中存在一個(gè)表示個(gè)體域中存在一個(gè)x使得對(duì)每一個(gè)使得對(duì)每一個(gè)y, x和和y有關(guān)系有關(guān)系G ；9概念概念4：量詞量詞(2/2)( x)P(x) 對(duì)于每一個(gè)對(duì)于每一個(gè)x

11、,P(x)=T有一個(gè)有一個(gè)x,P(x)=F( x)P(x) 有一個(gè)有一個(gè)x,P(x)=T對(duì)于每一個(gè)對(duì)于每一個(gè)x,P(x)=F注意：注意：1、有限個(gè)體域的量詞含義；、有限個(gè)體域的量詞含義；2、量詞的、量詞的順序順序不能隨意調(diào)換；不能隨意調(diào)換；3、 和和 的變換關(guān)系。的變換關(guān)系。10實(shí)例實(shí)例1例例1 分別用命題邏輯和謂詞邏輯將命題符號(hào)化分別用命題邏輯和謂詞邏輯將命題符號(hào)化 (1) 墨西哥位于南美洲墨西哥位于南美洲 (2) 是無(wú)理數(shù)那么是無(wú)理數(shù)那么 是有理數(shù)是有理數(shù) (3) 如果如果23，則，則33，q：3y，G(x, y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x) G(

12、y)L(x,y) (2) 令令F(x)：x是無(wú)理數(shù)，是無(wú)理數(shù)，G(y)：y是有理數(shù)，是有理數(shù)，L(x,y)：xy x(F(x)y(G(y) L(x,y)或者或者 x y(F(x) G(y) L(x,y)可見(jiàn)：命題符號(hào)化在謂詞邏輯中不是唯一的。可見(jiàn)：命題符號(hào)化在謂詞邏輯中不是唯一的。13實(shí)例實(shí)例4例例4 在一階邏輯中將下面命題符號(hào)化在一階邏輯中將下面命題符號(hào)化 (1) 沒(méi)有不呼吸的人沒(méi)有不呼吸的人 (2) 不是所有的人都喜歡吃糖不是所有的人都喜歡吃糖解解 (1) F(x): x是人是人, G(x): x呼吸呼吸x(F(x)G(x) x(F(x)G(x)(2) F(x): x是人是人, G(x):

13、 x喜歡吃糖喜歡吃糖 x(F(x)G(x)x(F(x)G(x)14實(shí)例實(shí)例5例例 若論域是不超過(guò)若論域是不超過(guò)4的正整數(shù)的正整數(shù),P(x)是語(yǔ)句是語(yǔ)句”x210”, ( x)P(x) 的真值是什么的真值是什么? P(1) P(2) P(3) P(4) 15謂詞謂詞公式的語(yǔ)法公式的語(yǔ)法定義（謂詞公式的組成符號(hào)：字母表）定義（謂詞公式的組成符號(hào)：字母表） 字母表字母表包括下述符號(hào)：包括下述符號(hào)： (1) 個(gè)體常項(xiàng)符號(hào)：個(gè)體常項(xiàng)符號(hào)：a, b, c, , ai, bi, ci, , i 1 (2) 函數(shù)符號(hào)：函數(shù)符號(hào)：f, g, h, , fi, gi, hi, , i 1 (3) 謂詞符號(hào)：謂詞符

14、號(hào)：F, G, H, , Fi, Gi, Hi, , i 1 (4) 個(gè)體變項(xiàng)符號(hào)：個(gè)體變項(xiàng)符號(hào)：x, y, z, , xi, yi, zi, , i 1 (5) 量詞符號(hào)：量詞符號(hào)： , (6) 聯(lián)結(jié)詞符號(hào)：聯(lián)結(jié)詞符號(hào)： , , , , (7) 括號(hào)與逗號(hào)：括號(hào)與逗號(hào)：(, ), ，16項(xiàng)與原子公式項(xiàng)與原子公式定義（項(xiàng)）定義（項(xiàng)） 項(xiàng)項(xiàng)的定義如下：的定義如下：(1) 個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2) 若若 (x1, x2, , xn)是任意的是任意的n元函數(shù)，元函數(shù)，t1, t2, , tn是任意的是任意的 n個(gè)項(xiàng)，則個(gè)項(xiàng)，則 (t1, t2, , tn) 是項(xiàng)是項(xiàng).(3

15、) 所有的項(xiàng)都是有限次使用所有的項(xiàng)都是有限次使用(1),(2)得到的。得到的。 如如, a, x, x+y, f(x), g(x,y)等都是項(xiàng)。等都是項(xiàng)。 定義（原子公式）定義（原子公式） 設(shè)設(shè)R(x1, x2, , xn)是是L 的任意的任意n元謂詞，元謂詞，t1, t2, , tn 是是L 的任意的任意n個(gè)項(xiàng)，則稱(chēng)個(gè)項(xiàng)，則稱(chēng)R(t1, t2, , tn)是是L 的的原子公式原子公式. 其中：其中：L是謂詞邏輯的形式語(yǔ)言。是謂詞邏輯的形式語(yǔ)言。 如，如，F(xiàn)(x, y), F(f(x1, x2), g(x3, x4)等均為原子公式等均為原子公式17定義（合式公式）定義（合式公式） 謂詞合式公式

16、謂詞合式公式定義如下：定義如下： (1) 原子公式是合式公式原子公式是合式公式. (2) 若若A是合式公式，則是合式公式，則 ( A)也是合式公式也是合式公式 (3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是也是 合式公式合式公式 (4) 若若A是合式公式，則是合式公式，則 xA, xA也是合式公式也是合式公式 (5) 只有有限次地應(yīng)用只有有限次地應(yīng)用(1)(4)形成的符號(hào)串才是合式公式形成的符號(hào)串才是合式公式.謂詞合式公式簡(jiǎn)稱(chēng)謂詞合式公式簡(jiǎn)稱(chēng)謂詞公式謂詞公式 如如, F(x), F(x)G(x,y), x(F(x)G(x) x y(F(x)

17、G(y) L(x,y)等都是合式公式等都是合式公式思考：謂詞公式的子公式如何定義？思考：謂詞公式的子公式如何定義？合式公式合式公式18轄域和變?cè)ㄝ犛蚝妥冊(cè)?/2）定義定義 在公式在公式 xA 和和 xA 中，稱(chēng)中，稱(chēng)x為為指導(dǎo)變?cè)笇?dǎo)變?cè)?，A為相應(yīng)為相應(yīng)量詞的量詞的轄域轄域. 在在 x和和 x的的轄域轄域中，中，x的所有出現(xiàn)都稱(chēng)為的所有出現(xiàn)都稱(chēng)為約束出約束出現(xiàn)（約束變?cè)┈F(xiàn)（約束變?cè)珹中不是約束出現(xiàn)的其他變項(xiàng)均稱(chēng)為是中不是約束出現(xiàn)的其他變項(xiàng)均稱(chēng)為是自由出現(xiàn)（自由變?cè)┳杂沙霈F(xiàn)（自由變?cè)┑牡? 例如例如， x(F(x,y)G(x,z)， x為指導(dǎo)變?cè)?，為指?dǎo)變?cè)?F(x,y)G(x,

18、z)為為 x 的的轄域轄域，x的兩次出現(xiàn)均為約束出現(xiàn)，的兩次出現(xiàn)均為約束出現(xiàn)，y與與 z 均為自由出現(xiàn)。均為自由出現(xiàn)。又如又如, x(F(x,y,z)y(G(x,y) H(x,y,z), x中的中的x是指導(dǎo)變?cè)侵笇?dǎo)變?cè)? 轄域?yàn)檩犛驗(yàn)?F(x,y,z)y(G(x,y) H(x,y,z). y中的中的y是指導(dǎo)變?cè)侵笇?dǎo)變?cè)? 轄轄域?yàn)橛驗(yàn)?G(x,y) H(x,y,z). x的的3次出現(xiàn)都是約束出現(xiàn)次出現(xiàn)都是約束出現(xiàn), y的第一次出的第一次出現(xiàn)是自由出現(xiàn)現(xiàn)是自由出現(xiàn), 后后2次是約束出現(xiàn)次是約束出現(xiàn), z的的2次出現(xiàn)都是自由出現(xiàn)。次出現(xiàn)都是自由出現(xiàn)。19轄域和變?cè)ㄝ犛蚝妥冊(cè)?/2） 注意：

19、根據(jù)約束變?cè)母拍睿⒁猓焊鶕?jù)約束變?cè)母拍?，P(x1,x2,xn)是是n元謂詞，它元謂詞，它有有n個(gè)相互獨(dú)立的個(gè)相互獨(dú)立的自由變?cè)杂勺冊(cè)?。若?duì)其中的。若對(duì)其中的k個(gè)變?cè)M(jìn)行約束個(gè)變?cè)M(jìn)行約束則成為則成為nk元謂詞。元謂詞。思考：局部變量和全局變量？思考：局部變量和全局變量？20換名換名原因：原因：在謂詞公式中，同一變?cè)问郊仁羌s束變?cè)质亲杂勺冊(cè)谥^詞公式中，同一變?cè)问郊仁羌s束變?cè)质亲杂勺冊(cè)?，這在概念上易引起混亂，因此需要對(duì)約束變?cè)M(jìn)行換名。元，這在概念上易引起混亂，因此需要對(duì)約束變?cè)M(jìn)行換名。使得一個(gè)變?cè)谝粋€(gè)公式中只呈現(xiàn)一種形式，即呈自由出現(xiàn)使得一個(gè)變?cè)谝粋€(gè)公式中只呈現(xiàn)一種形式，即

20、呈自由出現(xiàn)或呈約束出現(xiàn)?；虺始s束出現(xiàn)?？尚行裕嚎尚行裕阂粋€(gè)公式的變?cè)?，在無(wú)歧義的前提下，所使用的名稱(chēng)一個(gè)公式的變?cè)?，在無(wú)歧義的前提下，所使用的名稱(chēng)符號(hào)是無(wú)關(guān)緊要的。符號(hào)是無(wú)關(guān)緊要的。例如：例如：設(shè)：設(shè)：A(x)：x是不小于是不小于0，那么，那么( x)A(x)表示一切表示一切x都使得都使得x不小于不小于0；( y)A(y)表示一切表示一切y都使得都使得y不小于不小于0；( z)A(z)表示一切表示一切z都使得都使得z不小于不小于0。這三個(gè)命題在實(shí)數(shù)域中都表示假命題這三個(gè)命題在實(shí)數(shù)域中都表示假命題“一切實(shí)數(shù)均不小于一切實(shí)數(shù)均不小于0”。同理，同理，( x)A(x)、( y)A(y)與與( z)A

21、(z)意義也是相同的。意義也是相同的。21約束變?cè)獡Q名（約束變?cè)獡Q名（1/2）對(duì)謂詞公式對(duì)謂詞公式A中的約束變?cè)?，遵照一定的?guī)則更改中的約束變?cè)?，遵照一定的?guī)則更改名稱(chēng)符號(hào)，稱(chēng)為名稱(chēng)符號(hào)，稱(chēng)為約束變?cè)獡Q名約束變?cè)獡Q名。 其規(guī)則為：其規(guī)則為：將將量詞中的指導(dǎo)變?cè)吭~中的指導(dǎo)變?cè)?，以及，以及該量詞轄域中所出該量詞轄域中所出現(xiàn)的該變?cè)F(xiàn)的該變?cè)?，全部換成，全部換成新的變?cè)?hào)新的變?cè)?hào)，保持公式，保持公式的其余部分不變。的其余部分不變。換名時(shí)換名時(shí)新變?cè)伦冊(cè)欢ㄒ臑樽饔糜蛑幸欢ㄒ臑樽饔糜蛑袥](méi)有出現(xiàn)沒(méi)有出現(xiàn)的變?cè)Q(chēng)的變?cè)Q(chēng)，最好是公式中沒(méi)有出現(xiàn)過(guò)的符號(hào)。，最好是公式中沒(méi)有出現(xiàn)過(guò)的符號(hào)。

22、22約束變?cè)獡Q名（約束變?cè)獡Q名（2/2）例例 對(duì)對(duì)( x)(P(x)R(x,y) Q(x,y)換名。換名。解：可換名為：解：可換名為：( z)(P(z)R(z,y) Q(x,y)。 但是不能換名為：但是不能換名為：( y)(P(y)R(y,y) Q(x,y)、( z)(P(z)R(x,y) Q(x,y)。23自由變?cè)耄ㄗ杂勺冊(cè)耄?/2） 對(duì)于公式中的自由變?cè)苍试S更改，這種更改叫對(duì)于公式中的自由變?cè)?，也允許更改，這種更改叫做做代入代入。 自由變?cè)拇?，要遵循自由變?cè)拇?，要遵循自由變?cè)胍?guī)則自由變?cè)胍?guī)則：對(duì)于謂詞公式中的自由變?cè)?，可以作代入，代?duì)于謂詞公式中的自由變?cè)?，可?/p>

23、作代入，代入是需對(duì)入是需對(duì)公式中公式中出現(xiàn)該自由變?cè)某霈F(xiàn)該自由變?cè)拿恳惶幟恳惶庍M(jìn)行。進(jìn)行。用以代入的用以代入的新變?cè)伦冊(cè)c原公式中與原公式中所有變?cè)凶冊(cè)拿Q(chēng)的名稱(chēng)不能相同。不能相同。24自由變?cè)耄ㄗ杂勺冊(cè)耄?/2）例例 對(duì)對(duì)( x)(P(y) R(x,y)代入。代入。解：對(duì)解：對(duì)y施行代入，經(jīng)代入后公式為：施行代入，經(jīng)代入后公式為：( x)(P(z) R(x,z) 但是但是( x)(P(x) R(x,y)、 ( x)(P(z) R(x,y)、 ( x)(P(x) R(x,z) 這三種代入都是與規(guī)則不符的。這三種代入都是與規(guī)則不符的。25封閉的公式封閉的公式定義（閉式）定義（

24、閉式） 若公式若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱(chēng)中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱(chēng)A為為封閉的公式封閉的公式，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)閉式閉式.思考思考1：與閉式對(duì)應(yīng)的：與閉式對(duì)應(yīng)的開(kāi)式開(kāi)式？例如，例如， x y(F(x) G(y)H(x,y) 為閉式，為閉式，而而 x(F(x) G(x,y) 不是閉式不是閉式 思考思考2：閉式是命題函數(shù)還是命題？開(kāi)式呢？：閉式是命題函數(shù)還是命題？開(kāi)式呢？26賦值與謂詞公式的類(lèi)型賦值與謂詞公式的類(lèi)型l 在謂詞公式中，常包含在謂詞公式中，常包含謂詞變?cè)^詞變?cè)秃涂腕w變?cè)腕w變?cè)?，?dāng)，當(dāng)客體變?cè)腕w變?cè)捎纱_定的客體確定的客體取代，取代，謂詞變?cè)^詞變?cè)糜么_定的謂詞確定的謂

25、詞所取代時(shí)，就所取代時(shí)，就稱(chēng)為對(duì)稱(chēng)為對(duì)謂詞公式的賦值謂詞公式的賦值。l 一個(gè)謂詞公式經(jīng)過(guò)賦值以后，就成為具有確定真值一個(gè)謂詞公式經(jīng)過(guò)賦值以后，就成為具有確定真值T 或或F 的命題，即成為的命題，即成為命題命題。 定義定義 若公式若公式A在任何解釋下均為真在任何解釋下均為真, 則稱(chēng)則稱(chēng)A為為永真式永真式(有效有效式式). 若若A在任何解釋下均為假在任何解釋下均為假, 則稱(chēng)則稱(chēng)A為為矛盾式矛盾式(永假式永假式). 若至少有一個(gè)解釋使若至少有一個(gè)解釋使A為真為真, 則稱(chēng)則稱(chēng)A為為可滿(mǎn)足式可滿(mǎn)足式.說(shuō)明：說(shuō)明：1936年年Church和和Turing分別獨(dú)立地證明了：對(duì)于謂詞分別獨(dú)立地證明了：對(duì)于謂詞

26、邏輯，判斷公式是否是可滿(mǎn)足的邏輯，判斷公式是否是可滿(mǎn)足的(永真式永真式, 矛盾式矛盾式)是不可判是不可判定的。定的。27代換實(shí)例代換實(shí)例定義（代換實(shí)例）定義（代換實(shí)例） 設(shè)設(shè)A0是含命題變項(xiàng)是含命題變項(xiàng) p1, p2, , pn的命題公的命題公式，式，A1, A2, , An是是n個(gè)謂詞公式，用個(gè)謂詞公式，用Ai (1 i n) 處處代替處處代替A0中的中的pi，所得公式，所得公式A稱(chēng)為稱(chēng)為A0的的代換實(shí)例代換實(shí)例.例如，例如， F(x)G(x), xF(x)yG(y)等都是等都是pq的代換實(shí)例的代換實(shí)例.代換定理：重言式代換定理：重言式的代換實(shí)例都是永真式，的代換實(shí)例都是永真式，矛盾式矛盾式

27、的代換實(shí)的代換實(shí)例都是矛盾式例都是矛盾式. 思考：代換與代入的區(qū)別？思考：代換與代入的區(qū)別？28實(shí)例實(shí)例例例 判斷下列公式中，哪些是永真式，哪些是矛盾式？判斷下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)( x yG(x,y)xF(x)重言式重言式 p(qp) 的代換實(shí)例，故為永真式的代換實(shí)例，故為永真式. (2) ( xF(x)yG(y)yG(y)矛盾式矛盾式 (pq) q 的代換實(shí)例，故為永假式的代換實(shí)例，故為永假式. (3) x(F(x)G(x)解釋解釋I1: 個(gè)體域個(gè)體域N, F(x):x5, G(x): x4, 公式為真公式為真 解釋解釋I2: 個(gè)體域個(gè)體域N, F(x

28、):x5, G(x):xx。請(qǐng)看下述推導(dǎo)：請(qǐng)看下述推導(dǎo)：(1).( x)( y)G(x,y)P(2).( y)G(y,y)US,全稱(chēng)特定化規(guī)則全稱(chēng)特定化規(guī)則(US)正確的推導(dǎo)為：正確的推導(dǎo)為：(1).( x)( y)G(x,y)P(2).( y)G(w,y)US,錯(cuò)誤的結(jié)論錯(cuò)誤的結(jié)論58存在特定化規(guī)則存在特定化規(guī)則(ES)例如例如， x( (x=y) )中，中，x、y的論域是實(shí)數(shù)集合。的論域是實(shí)數(shù)集合。若使用若使用ES規(guī)則，則得規(guī)則，則得c=y，即在實(shí)數(shù)集中有一實(shí)，即在實(shí)數(shù)集中有一實(shí)數(shù)數(shù)c，等于任意實(shí)數(shù)，等于任意實(shí)數(shù)y。結(jié)論顯然不成立，這是因?yàn)榻Y(jié)論顯然不成立，這是因?yàn)锳(x)：x=y中的中的x

29、依賴(lài)依賴(lài)于自由變量于自由變量y，此時(shí)不能使用，此時(shí)不能使用ES規(guī)則。規(guī)則。另外，要注意的是，另外，要注意的是，如果如果 xP(x)和和 xQ(x)都真都真，則對(duì)于某個(gè)則對(duì)于某個(gè)c和某個(gè)和某個(gè)d，可以斷定，可以斷定 P(c) Q(d)必真，必真，但不能斷定但不能斷定P(c) Q(c)為真為真。59謂詞演算的推理理論（續(xù)謂詞演算的推理理論（續(xù)2） 全稱(chēng)一般化規(guī)則全稱(chēng)一般化規(guī)則( (UG) )：A(x)yA(y)這個(gè)規(guī)則是說(shuō)，如果個(gè)體域中任意一個(gè)個(gè)體都具這個(gè)規(guī)則是說(shuō)，如果個(gè)體域中任意一個(gè)個(gè)體都具有性質(zhì)有性質(zhì)A，則個(gè)體域中的全體個(gè)體都具有性質(zhì)，則個(gè)體域中的全體個(gè)體都具有性質(zhì)A。這里要求這里要求x必須為

30、自由變量，并且必須為自由變量，并且y不出現(xiàn)在不出現(xiàn)在A(yíng)(x)中中。 思考：思考：A(c)yA(y)？ 存在一般化規(guī)則存在一般化規(guī)則( (EG) )：A(c)yA(y)， A(x)yA(y)這個(gè)規(guī)則是說(shuō)，如果個(gè)體域中某一元素這個(gè)規(guī)則是說(shuō)，如果個(gè)體域中某一元素c具有性具有性質(zhì)質(zhì)A，則個(gè)體域中存在著具有性質(zhì)，則個(gè)體域中存在著具有性質(zhì)A的元素。的元素。這里要求這里要求y不在不在A(yíng)(c)中出現(xiàn)。中出現(xiàn)。 60證明：證明：（1） x(P(x)Q(x) P規(guī)則規(guī)則（2）P(c)Q(c) (1)；US（3）P(c) P規(guī)則規(guī)則（4）Q(c) (2),(3) ； I例例 證明證明: x(P(x)Q(x) P(c

31、)Q(c)直接證法（例直接證法（例1）61歸謬法歸謬法試證：試證： 前提：前提： x(F(x) G(x), xG(x)；結(jié)論：；結(jié)論： xF(x) 證明：證明： xF(x) 結(jié)論否定引入結(jié)論否定引入 x F(x) 置換置換 xG(x) P規(guī)則規(guī)則 x G(x) 置換置換 x(F(x) G(x) P規(guī)則規(guī)則 F(c) US G(c) US F(c) G(c) US G(c) 析取三段論析取三段論 G(c) G(c) 合取引入合取引入 思考：直接證法如何證？思考：直接證法如何證？62間接證法間接證法2（CP規(guī)則）規(guī)則）證明：證明：( x)(F(x)G(x)( x)F(x)( x)G(x)原題可改寫(xiě)

32、成：原題可改寫(xiě)成：( x)(F(x)G(x)( x)F(x)( x)G(x) 證明：證明： ( x)F(x) CP(附加前提附加前提) ( x) F(x) T量詞否定等價(jià)式量詞否定等價(jià)式 F(c) ES ( x) (F(x)G(x) P F(c)G(c) US G(c) T析取三段論析取三段論 ( x)G(x) EG ( x)F(x)( x)G(x) CP63（1） x(F(x) G(x) 前提前提（2）F(c) G(c) （1），），ES（3）F(c) （2）（4） y(H(y) I(y) 前提前提（5）H(c) I(c) （4）（6）H(c) （5）（7）F(c) H(c) （3）,（6）

33、（8） x(F(x) H(x) （7），），EG。 例例 指出下面推理中的錯(cuò)誤。指出下面推理中的錯(cuò)誤。 前提：前提： x(F(x) G(x) ， y(H(y) I(y) ；結(jié)論：；結(jié)論： x(F(x) H(x) 。找錯(cuò)找錯(cuò)64謂詞邏輯推理總結(jié)（謂詞邏輯推理總結(jié)（1）1 1） 為了在推導(dǎo)過(guò)程中消去量詞，可以引用規(guī)則為了在推導(dǎo)過(guò)程中消去量詞，可以引用規(guī)則USUS和規(guī)則和規(guī)則ESES來(lái)消來(lái)消去量詞。去量詞。2 2） 當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則UGUG和規(guī)則和規(guī)則EGEG將其量詞加入。將其量詞加入。3 3） 在推導(dǎo)過(guò)程中，對(duì)消去量詞的公式或公式中沒(méi)含量詞的子公在推導(dǎo)過(guò)程中，對(duì)消去量詞的公式或公式中沒(méi)含量詞的子公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。式。4 4）在推導(dǎo)過(guò)程中，對(duì)含有量詞的公式可以引用謂詞中的基本等）在推導(dǎo)過(guò)程中，對(duì)含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。價(jià)公式和基本蘊(yùn)涵公式。5 5）在推導(dǎo)過(guò)程中，如既要使用規(guī)則）在推導(dǎo)過(guò)程中，如既要使用規(guī)則USUS又要使用規(guī)則又要使用規(guī)則ESES消去公式消去公式中的量詞中的量詞( (要先使用規(guī)則要先使用規(guī)則ESES，再使用規(guī)則，再使用規(guī)則USUS) )。然后再使用命。然后再使用命題演算中的推理