離散數(shù)學(xué)第10章-謂詞邏輯

1、1,為什么要研究謂詞邏輯？① 為了刻畫命題內(nèi)部的邏輯結(jié)構(gòu)。命題邏輯中主要研究命題和命題演算，原子命題是命題演算的基本單位。命題邏輯不再對(duì)原子命題進(jìn)行分解兩個(gè)原子命題之間，常常有一些共同特征。例如：張三是個(gè)大學(xué)生，李四是個(gè)大學(xué)生。但命題邏輯卻無(wú)法研究命題內(nèi)部的邏輯結(jié)構(gòu)及命題之間的內(nèi)在聯(lián)系。,第10章 謂詞邏輯,2,② 命題邏輯在推理方面存在局限性，有些簡(jiǎn)單的論斷也不能用命題邏輯進(jìn)行推證。例如無(wú)法判斷著名的“蘇格拉底三段論”的正

2、確性。蘇格拉底三段論：令 P:所有的人都是要死的，Q:蘇格拉底是人，R:所以蘇格拉底是要死的。在命題邏輯中，只能用 （P ∧ Q） ?R 表示上述命題，但它不是重言式。所以，這個(gè)簡(jiǎn)單而著名的論斷就無(wú)法用命題邏輯予以推證。,3,原因是：P,Q,R這樣的表示太粗略，沒(méi)有把它們之間的內(nèi)在聯(lián)系反映出來(lái)。辦法：要反映這種內(nèi)在聯(lián)系，就要對(duì)原子命題作進(jìn)一步的分析，分析出其中的客體、謂詞、量詞等，研究它們之間的形式結(jié)構(gòu)及邏輯關(guān)系，總結(jié)

3、出正確的推理形式和規(guī)則。這就是謂詞邏輯所研究的內(nèi)容。謂詞邏輯也叫一階邏輯。,4,基本知識(shí)點(diǎn)：1、個(gè)體詞2、謂詞3、量詞4、基于謂詞邏輯的命題符號(hào)化,10.1 謂詞、個(gè)體和量詞,5,基本概念：1、個(gè)體詞：可以獨(dú)立存在的具體的或抽象的客體 個(gè)體常元：具體的或特定，一般用a,b,c,…表示 個(gè)體變?cè)撼橄蟮幕蚍褐傅?，一般用x,y,z,…表示 個(gè)體域：個(gè)體變?cè)娜≈捣秶?全

4、總個(gè)體域:由宇宙間一切事物組成的.,,10.1 謂詞、個(gè)體和量詞,6,2、謂詞 用來(lái)描述個(gè)體詞性質(zhì)或個(gè)體詞之間相互關(guān)系的詞。例: (1)3是有理數(shù)。 (2)x是無(wú)理數(shù)。 (3)小李與小王同歲。 (4)x與y有關(guān)系L。其中“…是有理數(shù)”、“…是無(wú)理數(shù)”、“…與…同歲”、 “…與…有關(guān)系L”均為謂詞。,7,將上述謂詞分別記作大寫字母F、G、H、L，則上述可表示為： (

5、1)F(3) (2)G(x) (3)H(a,b) a:小李。b:小王。 (4)L(x,y),8,謂詞分類：謂詞常元：表示具體性質(zhì)或關(guān)系的謂詞 如上例中F、G、H等命題謂詞變?cè)罕硎境橄蠡蚍褐感再|(zhì)或關(guān)系的謂詞 如上例中L命題,,9,由一個(gè)謂詞和若干個(gè)個(gè)體變?cè)M成的表達(dá)式稱為簡(jiǎn)單命題函數(shù)；由n元謂詞P和n個(gè)個(gè)體變?cè)獂1 , x2 , …,

6、xn 組成的命題函數(shù)，表示為 P(x1 , x2 , …, xn) 。由一個(gè)或若干個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)詞組成的的命題形式稱為復(fù)合命題函數(shù)。 注意： 不帶任何個(gè)體變?cè)闹^詞稱為0元謂詞。命題邏輯中的命題可看成是0元謂詞。,10,3、量詞 用來(lái)表示個(gè)體常元或變?cè)g數(shù)量關(guān)系的詞。 量詞分為3種：全稱量詞：“一切”、“所有”、“凡”、“每一個(gè)”、“任意”等，符號(hào)記作?。如：?x

7、表示個(gè)體域內(nèi)所有的x。存在量詞：“有一個(gè)”、“有的”、“存在”、“至少有一個(gè)”等，符號(hào)記作?。如:?y表示個(gè)體域內(nèi)有個(gè)體y。而用?xF(x), ?yG(y)等分別表示在個(gè)體域里存在個(gè)體具有性質(zhì)F和存在個(gè)體具有性質(zhì)G。存在唯一量詞：“存在唯一的”、“恰有一個(gè)”等，符號(hào)記作?!。如令命題 P（x）：x是x+1=0的整數(shù)解. 則 ?! x P（x）。,,11,例：在謂詞邏輯中將下列命題符號(hào)化。（1）凡是人都呼吸。（2）有的人

8、是左撇子。① 當(dāng)個(gè)體域?yàn)槿祟惣蠒r(shí)： 令F(x): x呼吸。G(x): x是左撇子。則（1）?xF(x) (2) ?xG(x)② 當(dāng)個(gè)體域?yàn)槿倐€(gè)體域時(shí)： 令F(x): x呼吸。G(x): x是左撇子。M(x): x是人。則（1）?x(M(x) ?F(x)) (2) ?x(M(x)∧ G(x)),4、基于謂詞邏輯的命題符號(hào)化,12,例：在謂詞邏輯中將下列命題符號(hào)化。（1）所有的

9、人都長(zhǎng)頭發(fā)。（2）有的人吸煙。解：令　M(x): x是人。（1） 令F(x): x長(zhǎng)頭發(fā)。則符號(hào)化為：　　　?x(M(x) ?F(x)),（2） 令S(x): x吸煙。則符號(hào)化為：　　　 ?x(M(x)∧S(x)),13,例：在謂詞邏輯中將下列命題符號(hào)化。（3）沒(méi)有人登上過(guò)木星。（4）清華大學(xué)的學(xué)生未必都是高素質(zhì)的。解：令　M(x): x是人。,（3） 令D(x): x登上過(guò)木星。則符號(hào)化為：　　　 ?

10、?x(M(x)∧D(x))（4）令Q(x):x是清華大學(xué)的學(xué)生。H(x):x是高素質(zhì)的。則符號(hào)化為： 　 ? ?x(Q(x) ?H(x)),14,例：在謂詞邏輯中將下列命題符號(hào)化 。（1）兔子比烏龜跑得快。（2）有的兔子比所有的烏龜跑得快。解：令　H(x): x是兔子。W(y):y是烏龜。 K(x,y):x比y跑得快。 則符號(hào)化為：（1）?x ?y(H(x)∧ W(y)

11、?K(x,y)),（2） ?x (H(x)∧ ?y(W(y) ?K(x,y))),15,例：在謂詞邏輯中將下列命題符號(hào)化 。（1）每列火車都比有些汽車跑得快。（2）某些汽車比所有火車慢。解：（1）令　H(x): x是火車。W(y):y是汽車。 K(x,y):x比y跑得快。 則符號(hào)化為： 　　?x (H(x) ? ? y(W(y) ∧ K(x,y))),（2）令　H(x): x是火車。W(x):x是

12、汽車。 K(x,y):x比y跑得慢。 則符號(hào)化為： 　　 ? x(W(x) ∧ ? y(H(y) ? K(x,y))),16,說(shuō)明：（1）分析命題中表示性質(zhì)和關(guān)系的謂詞，要分別符號(hào)化為一元和n(n ≥ 2)元謂詞。（2）根據(jù)命題的實(shí)際意義選用? 或 ? 。（3）一般來(lái)說(shuō)，當(dāng)多個(gè)量詞同時(shí)出現(xiàn)時(shí)，它們的順序不能隨意調(diào)換。如： 在實(shí)數(shù)域上用L(x,y)表示x+y=10命題為：對(duì)于任意的x,都存在

13、y使得x+y=10。 可符號(hào)化為： ?x?yL(x,y) 真值為1。 若調(diào)換順序后為： ?y?xL(x,y) 真值為0。,17,（4）有些命題的符號(hào)化形式不止一種。例 在謂詞邏輯中將下列命題符號(hào)化 。（1）沒(méi)有不能表示為分?jǐn)?shù)的有理數(shù)。解：（1）令　H(x): x是有理數(shù)。 W(x):x能表示成分?jǐn)?shù)。 則符號(hào)化為： 　　 ?x

14、 (H(x) ? W(x)) 或 ? ?x(H(x)∧ ? W(x)),18,蘇格拉底三段論： 凡是人都是 要死的。 蘇格拉底是人。 蘇格拉底是要死的。設(shè)：M(x):x是人。D(x):x是要死的。a:蘇格拉底。則符號(hào)化為： ?x(M(x)?D(x)) ∧M(a) ? D(a),19,練習(xí)題: 在謂詞邏

15、輯中將下列命題符號(hào)化 。（1）烏鴉都是黑色的。 令H(x): x是烏鴉。W(x): x是黑色的。 則符號(hào)化為： 　 ?x (H(x) ? W(x)) （2）有的人天天鍛煉身體。 令H(x): x是人。W(x): x天天鍛煉身體。 則符號(hào)化為： ?x(H(x)∧ W(x)),20,10.2 謂詞公式,一、謂詞公式,定義 （謂詞公式的遞歸定義） ( 1）命題常元、命題變?cè)?/p>

16、和簡(jiǎn)單命題函數(shù)都是謂詞公式。 （2）如果A是謂詞公式，則 ? A也是謂詞公式。 （3）如果A和B是謂詞公式，則（A∨B）、(A∧B）、 (A →B) 、(A? B) 也是謂詞公式。 （4）如果A是謂詞公式，x是A中的個(gè)體變?cè)?，則 ?xA 和 ?xA 也是謂詞公式。 （5）只有由使用上述四條規(guī)則有限次而得到的才是謂詞公式。,21,例1,?x (H(x) ? W(x)),(

17、? x（M（x）→ D（x））∧ M（a）) → D（a）,22,二、轄域、約束變?cè)妥杂勺冊(cè)?令Q（x）：x是有理數(shù)；F（x）：x可以表示為分?jǐn)?shù),這是一個(gè)真值確定的命題。,定義 在謂詞公式 ?xA(x) 和 ?xA(x) 中，x稱為量詞的指導(dǎo)變?cè)?，而公式A(x)稱為量詞的轄域。在?x 和? x 的轄域中，x的所有出現(xiàn)稱為約束出現(xiàn) ，且x稱為約束變?cè)?，而A(x)中不是約束出現(xiàn)的其它變?cè)Q為自由變?cè)?。,23,例 指出

18、下列各公式中的量詞轄域及自由變?cè)图s束變?cè)?（1）?x P(x) → ? y R(x, y) ；,（2） ? x （ P(x) ∧ Q(x)） ；,（3） ? x P(x) ∧ Q(x),24,三、換名規(guī)則和代入規(guī)則,（ 1）約束變?cè)獡Q名時(shí)，該變?cè)诹吭~及其轄域中的所有出現(xiàn)均須同時(shí)更改，公式的其余部分不變；,1. 換名規(guī)則,（2）換名時(shí)，一定要更改為該量詞轄域中沒(méi)有出現(xiàn)過(guò)的符號(hào)，最好是公式中未出現(xiàn)過(guò)的符號(hào)。,一個(gè)公式的約束變?cè)?/p>

19、的符號(hào)無(wú)關(guān)緊要，因此可以換名，但需遵守一定規(guī)則,例　對(duì)公式 ?x （ P(x)∧ Q(x, y)） → R(x, y)中x 換名,25,2. 代入規(guī)則：,（1）對(duì)于謂詞公式中的自由變?cè)? 可以代入，代入時(shí)須對(duì)該自由變?cè)乃凶杂沙霈F(xiàn)同時(shí)進(jìn)行代入；,一個(gè)公式的自由變?cè)姆?hào)也允許更改，這種更改稱為帶入，需遵守一定規(guī)則,例　對(duì)公式 （?y （ P(x, y)∧ ?z Q(x, z)）） ∨ ?x R(x, y)中的自由變?cè)獂 帶入