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

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

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

3、出正確的推理形式和規(guī)則。這就是謂詞邏輯所研究的內(nèi)容。謂詞邏輯也叫一階邏輯。,4,基本知識點(diǎn)：1、個體詞2、謂詞3、量詞4、基于謂詞邏輯的命題符號化,10.1 謂詞、個體和量詞,5,基本概念：1、個體詞：可以獨(dú)立存在的具體的或抽象的客體 個體常元：具體的或特定，一般用a,b,c,…表示 個體變元：抽象的或泛指的，一般用x,y,z,…表示 個體域：個體變元的取值范圍： 全

4、總個體域:由宇宙間一切事物組成的.,,10.1 謂詞、個體和量詞,6,2、謂詞 用來描述個體詞性質(zhì)或個體詞之間相互關(guān)系的詞。例: (1)3是有理數(shù)。 (2)x是無理數(shù)。 (3)小李與小王同歲。 (4)x與y有關(guān)系L。其中“…是有理數(shù)”、“…是無理數(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等命題謂詞變元：表示抽象或泛指性質(zhì)或關(guān)系的謂詞 如上例中L命題,,9,由一個謂詞和若干個個體變元組成的表達(dá)式稱為簡單命題函數(shù)；由n元謂詞P和n個個體變元x1 , x2 , …,

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

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

8、是左撇子。① 當(dāng)個體域為人類集合時： 令F(x): x呼吸。G(x): x是左撇子。則（1）?xF(x) (2) ?xG(x)② 當(dāng)個體域為全總個體域時： 令F(x): x呼吸。G(x): x是左撇子。M(x): x是人。則（1）?x(M(x) ?F(x)) (2) ?x(M(x)∧ G(x)),4、基于謂詞邏輯的命題符號化,12,例：在謂詞邏輯中將下列命題符號化。（1）所有的

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

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

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

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

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

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

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

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

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

18、下列各公式中的量詞轄域及自由變元和約束變元。,（1）?x P(x) → ? y R(x, y) ；,（2） ? x （ P(x) ∧ Q(x)） ；,（3） ? x P(x) ∧ Q(x),24,三、換名規(guī)則和代入規(guī)則,（ 1）約束變元換名時，該變元在量詞及其轄域中的所有出現(xiàn)均須同時更改，公式的其余部分不變；,1. 換名規(guī)則,（2）換名時，一定要更改為該量詞轄域中沒有出現(xiàn)過的符號，最好是公式中未出現(xiàn)過的符號。,一個公式的約束變元

19、的符號無關(guān)緊要，因此可以換名，但需遵守一定規(guī)則,例　對公式 ?x （ P(x)∧ Q(x, y)） → R(x, y)中x 換名,25,2. 代入規(guī)則：,（1）對于謂詞公式中的自由變元, 可以代入，代入時須對該自由變元的所有自由出現(xiàn)同時進(jìn)行代入；,一個公式的自由變元的符號也允許更改，這種更改稱為帶入，需遵守一定規(guī)則,例　對公式 （?y （ P(x, y)∧ ?z Q(x, z)）） ∨ ?x R(x, y)中的自由變元x 帶入