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

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

2、太大，無法研究命題的內(nèi)部關(guān)系；2、無法描述同一個(gè)體的多個(gè)性質(zhì)；、無法描述同一個(gè)體的多個(gè)性質(zhì)；3、無法描述具有共同屬性（、無法描述具有共同屬性（性質(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、通過量化，引入量詞，可以把一部分非命題轉(zhuǎn)化為命題。、通過量化，引入量詞，可以把一部分非命題轉(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è)體詞（主語或賓語等主語或賓語等）所研究對(duì)象中可以獨(dú)立存在的所研究對(duì)象中可以獨(dú)立存在的具體（如：張三）具體（如：張三）或或抽象（如：抽象（如：3，x）的客體）的客體。分類：分類： 個(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； 無限個(gè)體域，如無限個(gè)體域，如 N, Z, R, 全總個(gè)體域（全總個(gè)體域（默認(rèn)默認(rèn)）由宇宙間一切事物組成。由宇宙間一切事物組成。6概念概念2：謂詞謂詞謂詞謂詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞分類分類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分類分類2：n（n 1）元謂詞（含）元謂詞（含n個(gè)個(gè)命題變元命題變元的謂詞）的謂詞） 一元謂詞一元謂詞(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ù) 簡單命題函數(shù)簡單命題函數(shù)由一個(gè)由一個(gè)謂詞謂詞和若干個(gè)個(gè)體和若干個(gè)個(gè)體變元變

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

9、數(shù)真值函數(shù)的區(qū)別；的區(qū)別；4、復(fù)合命題函數(shù)的真值由組成它的、復(fù)合命題函數(shù)的真值由組成它的簡單命題函數(shù)簡單命題函數(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）( 和和 的由來？的由來？) 全稱量詞全稱量詞 : 表示所有的表示所有的. 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) 是無理數(shù)那么是無理數(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是無理數(shù)，是無理數(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)可見：命題符號(hào)化在謂詞邏輯中不是唯一的。可見：命題符號(hào)化在謂詞邏輯中不是唯一的。13實(shí)例實(shí)例4例例4 在一階邏輯中將下面命題符號(hào)化在一階邏輯中將下面命題符號(hào)化 (1) 沒有不呼吸的人沒有不呼吸的人 (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例例 若論域是不超過若論域是不超過4的正整數(shù)的正整數(shù),P(x)是語句是語句”x210”, ( x)P(x) 的真值是什么的真值是什么? P(1) P(2) P(3) P(4) 15謂詞謂詞公式的語法公式的語法定義（謂詞公式的組成符號(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)，則稱個(gè)項(xiàng)，則稱R(t1, t2, , tn)是是L 的的原子公式原子公式. 其中：其中：L是謂詞邏輯的形式語言。是謂詞邏輯的形式語言。 如，如，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)串才是合式公式.謂詞合式公式簡稱謂詞合式公式簡稱謂詞公式謂詞公式 如如, F(x), F(x)G(x,y), x(F(x)G(x) x y(F(x)

17、G(y) L(x,y)等都是合式公式等都是合式公式思考：謂詞公式的子公式如何定義？思考：謂詞公式的子公式如何定義？合式公式合式公式18轄域和變元（轄域和變元（1/2）定義定義 在公式在公式 xA 和和 xA 中，稱中，稱x為為指導(dǎo)變元指導(dǎo)變元，A為相應(yīng)為相應(yīng)量詞的量詞的轄域轄域. 在在 x和和 x的的轄域轄域中，中，x的所有出現(xiàn)都稱為的所有出現(xiàn)都稱為約束出約束出現(xiàn)（約束變元）現(xiàn)（約束變元），A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)（自由變元）自由出現(xiàn)（自由變元）的的. 例如例如， x(F(x,y)G(x,z)， x為指導(dǎo)變元，為指導(dǎo)變元，(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)變元是指導(dǎo)變元, 轄域?yàn)檩犛驗(yàn)?F(x,y,z)y(G(x,y) H(x,y,z). y中的中的y是指導(dǎo)變元是指導(dǎo)變元, 轄轄域?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轄域和變元（轄域和變元（2/2） 注意：

19、根據(jù)約束變元的概念，注意：根據(jù)約束變元的概念，P(x1,x2,xn)是是n元謂詞，它元謂詞，它有有n個(gè)相互獨(dú)立的個(gè)相互獨(dú)立的自由變元自由變元。若對(duì)其中的。若對(duì)其中的k個(gè)變元進(jìn)行約束個(gè)變元進(jìn)行約束則成為則成為nk元謂詞。元謂詞。思考：局部變量和全局變量？思考：局部變量和全局變量？20換名換名原因：原因：在謂詞公式中，同一變元形式既是約束變元又是自由變在謂詞公式中，同一變元形式既是約束變元又是自由變元，這在概念上易引起混亂，因此需要對(duì)約束變元進(jìn)行換名。元，這在概念上易引起混亂，因此需要對(duì)約束變元進(jìn)行換名。使得一個(gè)變元在一個(gè)公式中只呈現(xiàn)一種形式，即呈自由出現(xiàn)使得一個(gè)變元在一個(gè)公式中只呈現(xiàn)一種形式，即

20、呈自由出現(xiàn)或呈約束出現(xiàn)?；虺始s束出現(xiàn)?？尚行裕嚎尚行裕阂粋€(gè)公式的變元，在無歧義的前提下，所使用的名稱一個(gè)公式的變元，在無歧義的前提下，所使用的名稱符號(hào)是無關(guān)緊要的。符號(hào)是無關(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約束變元換名（約束變元換名（1/2）對(duì)謂詞公式對(duì)謂詞公式A中的約束變元，遵照一定的規(guī)則更改中的約束變元，遵照一定的規(guī)則更改名稱符號(hào)，稱為名稱符號(hào)，稱為約束變元換名約束變元換名。 其規(guī)則為：其規(guī)則為：將將量詞中的指導(dǎo)變元量詞中的指導(dǎo)變元，以及，以及該量詞轄域中所出該量詞轄域中所出現(xiàn)的該變元現(xiàn)的該變元，全部換成，全部換成新的變元符號(hào)新的變元符號(hào)，保持公式，保持公式的其余部分不變。的其余部分不變。換名時(shí)換名時(shí)新變元新變元一定要更改為作用域中一定要更改為作用域中沒有出現(xiàn)沒有出現(xiàn)的變元名稱的變元名稱，最好是公式中沒有出現(xiàn)過的符號(hào)。，最好是公式中沒有出現(xiàn)過的符號(hào)。

22、22約束變元換名（約束變元換名（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自由變元代入（自由變元代入（1/2） 對(duì)于公式中的自由變元，也允許更改，這種更改叫對(duì)于公式中的自由變元，也允許更改，這種更改叫做做代入代入。 自由變元的代入，要遵循自由變元的代入，要遵循自由變元代入規(guī)則自由變元代入規(guī)則：對(duì)于謂詞公式中的自由變元，可以作代入，代對(duì)于謂詞公式中的自由變元，可以

23、作代入，代入是需對(duì)入是需對(duì)公式中公式中出現(xiàn)該自由變元的出現(xiàn)該自由變元的每一處每一處進(jìn)行。進(jìn)行。用以代入的用以代入的新變元新變元與原公式中與原公式中所有變元所有變元的名稱的名稱不能相同。不能相同。24自由變元代入（自由變元代入（2/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)，則稱中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為為封閉的公式封閉的公式，簡稱，簡稱閉式閉式.思考思考1：與閉式對(duì)應(yīng)的：與閉式對(duì)應(yīng)的開式開式？例如，例如， x y(F(x) G(y)H(x,y) 為閉式，為閉式，而而 x(F(x) G(x,y) 不是閉式不是閉式 思考思考2：閉式是命題函數(shù)還是命題？開式呢？：閉式是命題函數(shù)還是命題？開式呢？26賦值與謂詞公式的類型賦值與謂詞公式的類型l 在謂詞公式中，常包含在謂詞公式中，常包含謂詞變元謂詞變元和和客體變元客體變元，當(dāng)，當(dāng)客體變元客體變元由由確定的客體確定的客體取代，取代，謂詞變元謂詞變元用用確定的謂詞確定的謂

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

26、邏輯，判斷公式是否是可滿足的邏輯，判斷公式是否是可滿足的(永真式永真式, 矛盾式矛盾式)是不可判是不可判定的。定的。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稱為稱為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,全稱特定化規(guī)則全稱特定化規(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、依賴依賴于自由變量于自由變量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） 全稱一般化規(guī)則全稱一般化規(guī)則( (UG) )：A(x)yA(y)這個(gè)規(guī)則是說，如果個(gè)體域中任意一個(gè)個(gè)體都具這個(gè)規(guī)則是說，如果個(gè)體域中任意一個(gè)個(gè)體都具有性質(zhì)有性質(zhì)A，則個(gè)體域中的全體個(gè)體都具有性質(zhì)，則個(gè)體域中的全體個(gè)體都具有性質(zhì)A。這里要求這里要求x必須為

30、自由變量，并且必須為自由變量，并且y不出現(xiàn)在不出現(xiàn)在A(x)中中。 思考：思考：A(c)yA(y)？ 存在一般化規(guī)則存在一般化規(guī)則( (EG) )：A(c)yA(y)， A(x)yA(y)這個(gè)規(guī)則是說，如果個(gè)體域中某一元素這個(gè)規(guī)則是說，如果個(gè)體域中某一元素c具有性具有性質(zhì)質(zhì)A，則個(gè)體域中存在著具有性質(zhì)，則個(gè)體域中存在著具有性質(zhì)A的元素。的元素。這里要求這里要求y不在不在A(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)原題可改寫

32、成：原題可改寫成：( 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ī)則為了在推導(dǎo)過程中消去量詞，可以引用規(guī)則USUS和規(guī)則和規(guī)則ESES來消來消去量詞。去量詞。2 2） 當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則當(dāng)所要求的結(jié)論可能被定量時(shí)，此時(shí)可引用規(guī)則UGUG和規(guī)則和規(guī)則EGEG將其量詞加入。將其量詞加入。3 3） 在推導(dǎo)過程中，對(duì)消去量詞的公式或公式中沒含量詞的子公在推導(dǎo)過程中，對(duì)消去量詞的公式或公式中沒含量詞的子公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式，完全可以引用命題演算中的基本等價(jià)公式和基本蘊(yùn)涵公式。式。4 4）在推導(dǎo)過程中，對(duì)含有量詞的公式可以引用謂詞中的基本等）在推導(dǎo)過程中，對(duì)含有量詞的公式可以引用謂詞中的基本等價(jià)公式和基本蘊(yùn)涵公式。價(jià)公式和基本蘊(yùn)涵公式。5 5）在推導(dǎo)過程中，如既要使用規(guī)則）在推導(dǎo)過程中，如既要使用規(guī)則USUS又要使用規(guī)則又要使用規(guī)則ESES消去公式消去公式中的量詞中的量詞( (要先使用規(guī)則要先使用規(guī)則ESES，再使用規(guī)則，再使用規(guī)則USUS) )。然后再使用命。然后再使用命題演算中的推理