數(shù)理邏輯總結(jié)

1、1 1總結(jié)總結(jié)第第一一章章 命題邏輯命題邏輯(1)(1)命題；命題；(2)(2)命題聯(lián)結(jié)詞：否定命題聯(lián)結(jié)詞：否定( )( )，合取，合取( )( )，析取，析取( )( )，異或，異或( )( )，蘊(yùn)含，蘊(yùn)含( )( )，等值，等值( )( )； (3)(3)原子命題和復(fù)合命題；原子命題和復(fù)合命題； (4)(4)命題符號(hào)化命題符號(hào)化。 1. 1. 命題命題 (1)(1)命題常元，命題變?cè)?，命題公式命題常元，命題變?cè)}公式( (或稱(chēng)公式或稱(chēng)公式) )； (2)(2)命題公式命題公式F(PF(P1 1,P,P2 2, ,P,Pn n) )的真值指派，公式的真值表；的真值指派，公式的真值表； (

2、3)(3)命題公式的分類(lèi)：重言式命題公式的分類(lèi)：重言式( (或永真式或永真式) )、矛盾式、矛盾式( (或永假或永假式式) )和可滿足公式；和可滿足公式； 2. 2. 命題公式命題公式 2 2總結(jié)總結(jié)第第一一章章 命題邏輯命題邏輯3. 3. 命題公式間的關(guān)系命題公式間的關(guān)系 (1)(1)命題公式間的等價(jià)關(guān)系命題公式間的等價(jià)關(guān)系( )( )(2)(2)命題公式間的蘊(yùn)含關(guān)系命題公式間的蘊(yùn)含關(guān)系( ) ( ) (3)(3)基本的等價(jià)式；基本的等價(jià)式； (4)(4)基本的蘊(yùn)含式基本的蘊(yùn)含式；(5)(5)判斷公式類(lèi)型的方法判斷公式類(lèi)型的方法( (真值表、等價(jià)公式變換、主范式真值表、等價(jià)公式變換、主范式)

3、 )； (6)(6)判定兩公式是否具有等價(jià)和蘊(yùn)含關(guān)系的方法判定兩公式是否具有等價(jià)和蘊(yùn)含關(guān)系的方法。ABAB3 3總結(jié)總結(jié)第第一一章章 命題邏輯命題邏輯(1)(1)推理的概念：推理的概念：(2)(2)推理規(guī)則：四個(gè)規(guī)則推理規(guī)則：四個(gè)規(guī)則；4. 4. 命題邏輯的推理理論命題邏輯的推理理論 12nHHHC4 4練習(xí)練習(xí)9-1 1. 判斷下列語(yǔ)句哪些是命題，若是命題，則指出其真值。判斷下列語(yǔ)句哪些是命題，若是命題，則指出其真值。 （1） 只有小孩才愛(ài)哭。只有小孩才愛(ài)哭。 （2） X+6=Y （3） 銀是白的。銀是白的。 （4） 起來(lái)吧，我的朋友。起來(lái)吧，我的朋友。( 是是 假假 ) ( 不是不是 )(

4、 是是 真真 ) ( 不是不是 ) 2 將下列命題符號(hào)化將下列命題符號(hào)化 （1 1）我看見(jiàn)的既不是小張也不是老李。）我看見(jiàn)的既不是小張也不是老李。 解解 令令P：我看見(jiàn)的是小張；：我看見(jiàn)的是小張；Q：我看見(jiàn)的是老李。：我看見(jiàn)的是老李。 則該命題可表示為則該命題可表示為PQ （2）如果晚上做完了作業(yè)并且沒(méi)有其它的事，他就會(huì)如果晚上做完了作業(yè)并且沒(méi)有其它的事，他就會(huì)看電視或聽(tīng)音樂(lè)?？措娨暬蚵?tīng)音樂(lè)。 解解 令令 P：他晚上做完了作業(yè)；：他晚上做完了作業(yè)；Q：他晚上有其它的事；：他晚上有其它的事； R：他看電視；：他看電視； S：他聽(tīng)音樂(lè)。：他聽(tīng)音樂(lè)。 則該命題可表示為則該命題可表示為（PQ）（RS）

5、5 5“如果嫦娥是虛構(gòu)的，而如果圣誕老人也是虛構(gòu)的，那如果嫦娥是虛構(gòu)的，而如果圣誕老人也是虛構(gòu)的，那么許多孩子受騙了。么許多孩子受騙了。”解：解：令令P：嫦娥是虛構(gòu)的；：嫦娥是虛構(gòu)的；Q：圣誕老人是虛構(gòu)的；：圣誕老人是虛構(gòu)的；R：許多孩子受騙了。：許多孩子受騙了。則一上語(yǔ)句可表示為：則一上語(yǔ)句可表示為： 或或RQP)()(RQP3判斷下面一段論述是否為真：判斷下面一段論述是否為真：“ 是是 無(wú)理數(shù)，并且，如果無(wú)理數(shù)，并且，如果3是無(wú)理數(shù)，則是無(wú)理數(shù)，則 也是無(wú)理數(shù)，也是無(wú)理數(shù)，另外，只有另外，只有6能被能被2整除時(shí)，整除時(shí)，6才能被才能被4整除整除”2解：解：令令P： 是無(wú)理數(shù)；是無(wú)理數(shù)； S

6、：6能被能被2整除整除 Q：3是無(wú)理數(shù)：是無(wú)理數(shù)： H：6能被能被4整除整除 R： 是無(wú)理數(shù)是無(wú)理數(shù)語(yǔ)句符號(hào)化為：語(yǔ)句符號(hào)化為： 1 0 1 0 1命題的真值為真。命題的真值為真。)()(SHRQP26 64. 證明下列命題公式的等值關(guān)系證明下列命題公式的等值關(guān)系（1） （P Q） （PQ） （PQ）（2）（）（P （Q R） （P Q）（P R）解解 (1) （P Q） （PQ）（ P Q） E12 （PQ）（PQ） E10，E6 （P Q） （PQ） （PQ）（2）（P Q）（P R） （ P Q）（ PR） E11 （ P P）（ QR） E1，E2 P（ QR） E7 P （Q R）

7、（P P （Q Q R R） （P P Q Q）（P P R R）7 75、求出下式的主析取范式、求出下式的主析取范式1） （PQ） （RP）2）（）（PQ）（R P）解：解：1） （PQ） （RP）= （ P Q） （ R P）=（PQ） （ R P）=（PQR） （PQ）=（PQR） （PQ R） （PQ R）2）（）（PQ）（R P）=（ P Q）（R P）= （ P Q） （R P）=（PQ） （R P）=（P R） （PQ R）=（P Q R） （PQ R）=M0M2= m1,m3,m4,m5,m6,m7=( PQ R) ( P Q R) (PQR) (PQ R) (P QR) (P

8、 Q R)8 86. 用主范式方法證明下列命題公式的等值關(guān)系用主范式方法證明下列命題公式的等值關(guān)系（1 1）( ( A A B)B)(A(A B)B)(A(A B)B) (B(BA)A)解：解： 左左( ( A A B)B)(A(A B)B)( A A B)B) (A(A B)B) (A (AB)B) (A(A B)B) m m1010,m,m1111 右右(A(A B)B) (B(BA)A) (A (A B)B) ( ( B B A)A) M M0000,M,M0101 m m1010,m,m11 11 問(wèn)題得證。問(wèn)題得證。9 99/22(2) A(2) A ( ( A A (A(A B)B

9、)( ( A AB)B)(A(AB)B)解：解： 左左A A ( ( A A (A(A B)B) A A (B(BB)B) ( ( A A (B(BB)B) (A(A B)B) (A(A B)B) (A(AB)B) ( ( A A B)B) ( ( A AB)B) (A(A B)B) ( ( A AB)B) ( ( A A B)B) (A(AB)B) (A(A B)B) m m0000,m,m01 01 ,m,m1010,m,m1111右右( ( A AB)B)(A(AB)B)( ( A AB)B)( ( A AB)B) ( ( A AB)B) (A(A B) B) ( ( A A (B(BB

10、)B)B B (A(AA)A) (A(A B)B) ( ( A A B)B) ( ( A AB)B) (A(AB)B) ( ( A AB)B) (A(A B)B) ( ( A AB)B) ( ( A A B)B) (A(AB)B) (A(A B)B) m m0000,m,m01 01 ,m,m1010,m,m1111 問(wèn)題得證。問(wèn)題得證。101010/227.7.符號(hào)化下列命題并推證其結(jié)論的有效性。符號(hào)化下列命題并推證其結(jié)論的有效性。、明天是晴天，或者是下雨；如果是晴天，、明天是晴天，或者是下雨；如果是晴天，我就去看電影；如果我去看電影，我就不看我就去看電影；如果我去看電影，我就不看書(shū)。結(jié)論：

11、如果我在看書(shū)，則天在下雨。書(shū)。結(jié)論：如果我在看書(shū)，則天在下雨。解：首先符號(hào)化，并令解：首先符號(hào)化，并令：明天是晴天。：明天是晴天。：明天下雨。：明天下雨。：明天我去看電影。：明天我去看電影。：明天我看書(shū)。于是問(wèn)題可描述成：明天我看書(shū)。于是問(wèn)題可描述成：111111/22P P Q,PQ,PR,RR,RS SS SQ Q1.S P1.S P規(guī)則規(guī)則( (附加前提附加前提) )2.R2.RS PS P規(guī)則規(guī)則3.3. R TR T規(guī)則及和規(guī)則及和4.P4.PR PR P規(guī)則規(guī)則5.5. P TP T規(guī)則及規(guī)則及3 3和和4 46. P6. P Q PQ P規(guī)則規(guī)則7.Q T7.Q T規(guī)則及規(guī)則及5

12、 5和和6 68. S8. SQ CPQ CP規(guī)則及和規(guī)則及和121212/22. .如果今天我沒(méi)課，則我就去機(jī)房上機(jī)或去如果今天我沒(méi)課，則我就去機(jī)房上機(jī)或去圖書(shū)館查資料；若機(jī)房沒(méi)有空機(jī)器，那麼圖書(shū)館查資料；若機(jī)房沒(méi)有空機(jī)器，那麼我沒(méi)法上機(jī)；今天我沒(méi)課，機(jī)房也沒(méi)空機(jī)我沒(méi)法上機(jī)；今天我沒(méi)課，機(jī)房也沒(méi)空機(jī)器所以今天我去圖書(shū)館查資料。器所以今天我去圖書(shū)館查資料。解；首先定義下列符號(hào)：解；首先定義下列符號(hào)：今天我沒(méi)課。：今天我沒(méi)課。：我去機(jī)房上機(jī)。：我去機(jī)房上機(jī)。：我去圖書(shū)館查資料。：我去圖書(shū)館查資料。：機(jī)房沒(méi)有空機(jī)器。：機(jī)房沒(méi)有空機(jī)器。于是問(wèn)題可描述為：于是問(wèn)題可描述為：131313/22P P(Q

13、(Q R),SR),SQ,PQ,P S S R R1.1.P P S S 規(guī)則規(guī)則2. P T2. P T規(guī)則和規(guī)則和1 13. S3. S T T規(guī)則和規(guī)則和1 14. S4. SQ Q 規(guī)則規(guī)則5. 5. Q TQ T規(guī)則規(guī)則3 3和和4 46. P6. P(Q(Q R) R) 規(guī)則規(guī)則7. Q7. Q R TR T規(guī)則規(guī)則2 2和和6 68. R T8. R T規(guī)則規(guī)則5 5和和7 7141414/22 前面我們?cè)?jīng)介紹過(guò)等價(jià)變換和邏輯聯(lián)結(jié)詞最小功能前面我們?cè)?jīng)介紹過(guò)等價(jià)變換和邏輯聯(lián)結(jié)詞最小功能完備集的概念，當(dāng)一個(gè)實(shí)際問(wèn)題用命題邏輯表達(dá)出來(lái)完備集的概念，當(dāng)一個(gè)實(shí)際問(wèn)題用命題邏輯表達(dá)出來(lái)后

14、我們可以利用等價(jià)變換使之僅含邏輯聯(lián)結(jié)詞后我們可以利用等價(jià)變換使之僅含邏輯聯(lián)結(jié)詞 、 、 ，然后可以選用邏輯部件組成其邏輯電路。，然后可以選用邏輯部件組成其邏輯電路。 邏輯聯(lián)結(jié)詞和邏輯部件的對(duì)應(yīng)關(guān)系如下：邏輯聯(lián)結(jié)詞和邏輯部件的對(duì)應(yīng)關(guān)系如下： ： ： 151515/22 8、給定命題公式、給定命題公式: P (Q R) S給出對(duì)應(yīng)的邏輯電路給出對(duì)應(yīng)的邏輯電路 解：解： P (Q R) S ( P (Q R) S P Q R S./*黑板畫(huà)黑板畫(huà)*/16169.設(shè)計(jì)一盞燈的開(kāi)關(guān)電路時(shí)，要求三個(gè)開(kāi)關(guān)設(shè)計(jì)一盞燈的開(kāi)關(guān)電路時(shí)，要求三個(gè)開(kāi)關(guān)A，B，C的控制：的控制：當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AC同時(shí)關(guān)閉或者同時(shí)關(guān)閉或

15、者BC同時(shí)關(guān)閉時(shí)燈亮。用同時(shí)關(guān)閉時(shí)燈亮。用F表示燈表示燈亮，亮，p,q,r分別表示開(kāi)關(guān)分別表示開(kāi)關(guān)A，B，C關(guān)閉，求關(guān)閉，求F=F(p,q,r)的邏輯的邏輯表達(dá)式以及表達(dá)式以及F的主范式。的主范式。解：解：F=F(p,q,r)=(p r) (q r)F的主析取范式為：的主析取范式為：F=(p (q q) r) (p p) q r) =(p q r) (p q r) (p q r) ( p q r) =(p q r) (p q r) ( p q r) =m111 m101 m011 = m3,5,7= M0,1,2,4,5171710.某電路中有某電路中有1只燈泡和只燈泡和3個(gè)開(kāi)關(guān)個(gè)開(kāi)關(guān)A，B，

16、C。已知當(dāng)且僅當(dāng)。已知當(dāng)且僅當(dāng)在下述在下述4種情況之一燈亮。種情況之一燈亮。（1）C的搬鍵向上，的搬鍵向上，A和和B的搬鍵向下。的搬鍵向下。（2）A的搬鍵向上，的搬鍵向上，B和和C的搬鍵向下。的搬鍵向下。（3）B和和C的搬鍵都向上，的搬鍵都向上，A的搬鍵向下。的搬鍵向下。（4）A和和B的搬鍵都向上，的搬鍵都向上，C的搬鍵向下。的搬鍵向下。求燈亮的邏輯表達(dá)式以及主范式。求燈亮的邏輯表達(dá)式以及主范式。解：另解：另F表示燈亮，表示燈亮，p,q,r分別表示分別表示A,B,C的搬鍵向上，則的搬鍵向上，則F=F(p,q,r) =( p qr)(p q r)( pqr) (pq r) =m001 m100

17、m011 m110 = m1,3,4,6 = M0,2,5,7 =(pqr)(p qr)( pq r)( p q r) 181818/2211、一家航空公司為了保證安全，用計(jì)算機(jī)復(fù)核、一家航空公司為了保證安全，用計(jì)算機(jī)復(fù)核飛行計(jì)劃。每臺(tái)計(jì)算機(jī)能給出飛行計(jì)劃正確或飛行計(jì)劃。每臺(tái)計(jì)算機(jī)能給出飛行計(jì)劃正確或者有誤的回答。由于計(jì)算機(jī)也有可能發(fā)生故障，者有誤的回答。由于計(jì)算機(jī)也有可能發(fā)生故障，因此采用因此采用3臺(tái)計(jì)算機(jī)同時(shí)復(fù)核。由所給答案，根臺(tái)計(jì)算機(jī)同時(shí)復(fù)核。由所給答案，根據(jù)據(jù)“少數(shù)服從多數(shù)少數(shù)服從多數(shù)”的原則作出判斷。試將結(jié)的原則作出判斷。試將結(jié)果用公式表示，并加以簡(jiǎn)化，畫(huà)出電路圖。果用公式表示，并加

18、以簡(jiǎn)化，畫(huà)出電路圖。 解：設(shè)解：設(shè)C1，C2，C3分別表示分別表示3臺(tái)計(jì)算機(jī)的答案，臺(tái)計(jì)算機(jī)的答案，S表示判斷結(jié)果，根據(jù)題意可有下面的真值表：表示判斷結(jié)果，根據(jù)題意可有下面的真值表：191919/22 C1 C2 C3 S 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1202020/22 并且并且S=( C1 C2 C3) (C1 C2 C3) (C1 C2 C3) (C1 C2 C3) = (C1 C2) ( C1 C2 C3) (C1 C2 C3).212111.在一次研討會(huì)上，在一次研討會(huì)上，3名與會(huì)者根據(jù)王

19、教授的口音分別進(jìn)行名與會(huì)者根據(jù)王教授的口音分別進(jìn)行下述判斷：下述判斷：甲說(shuō)：甲說(shuō)：“王教授不是蘇州人，是上海人王教授不是蘇州人，是上海人”乙說(shuō)：乙說(shuō)：“王教授不是上海人，是蘇州人王教授不是上海人，是蘇州人”丙說(shuō)：丙說(shuō)：“王教授不是杭州人，也不是上海人王教授不是杭州人，也不是上海人”王教授聽(tīng)后笑道：王教授聽(tīng)后笑道：“你們你們3人中有人中有1人全說(shuō)對(duì)了，有一人全說(shuō)人全說(shuō)對(duì)了，有一人全說(shuō)錯(cuò)了，有錯(cuò)了，有1人對(duì)錯(cuò)各半人對(duì)錯(cuò)各半”。請(qǐng)問(wèn)王教授是哪里人？請(qǐng)問(wèn)王教授是哪里人？222222/2212、有一邏輯學(xué)家誤入某部落，被拘于牢獄，酋長(zhǎng)意欲、有一邏輯學(xué)家誤入某部落，被拘于牢獄，酋長(zhǎng)意欲放行，他對(duì)邏輯學(xué)家說(shuō)

20、：放行，他對(duì)邏輯學(xué)家說(shuō)：“今有兩扇門(mén)，一為自由，今有兩扇門(mén)，一為自由，一為死亡，你可任意開(kāi)啟一門(mén)。為協(xié)助你逃脫，加派一為死亡，你可任意開(kāi)啟一門(mén)。為協(xié)助你逃脫，加派兩名戰(zhàn)士負(fù)責(zé)回答你所提出的問(wèn)題，唯可慮者，此兩兩名戰(zhàn)士負(fù)責(zé)回答你所提出的問(wèn)題，唯可慮者，此兩名戰(zhàn)士一名天性誠(chéng)實(shí)，一名說(shuō)謊成性，今后生死由你名戰(zhàn)士一名天性誠(chéng)實(shí)，一名說(shuō)謊成性，今后生死由你自己選擇自己選擇”。邏輯學(xué)家沉思片刻，即向一戰(zhàn)士發(fā)問(wèn)，。邏輯學(xué)家沉思片刻，即向一戰(zhàn)士發(fā)問(wèn)，然后開(kāi)門(mén)從容離去，邏輯學(xué)家該如何發(fā)問(wèn)？然后開(kāi)門(mén)從容離去，邏輯學(xué)家該如何發(fā)問(wèn)？ 解：邏輯學(xué)家手指一門(mén)問(wèn)身邊的戰(zhàn)士說(shuō)：解：邏輯學(xué)家手指一門(mén)問(wèn)身邊的戰(zhàn)士說(shuō)：“這扇門(mén)是這扇

21、門(mén)是死亡門(mén)，他（指另一名戰(zhàn)士）將說(shuō)是對(duì)嗎？死亡門(mén)，他（指另一名戰(zhàn)士）將說(shuō)是對(duì)嗎？” 當(dāng)被問(wèn)戰(zhàn)士回答當(dāng)被問(wèn)戰(zhàn)士回答“對(duì)對(duì)”，則邏輯學(xué)家開(kāi)啟所指的門(mén)離，則邏輯學(xué)家開(kāi)啟所指的門(mén)離去。當(dāng)被問(wèn)戰(zhàn)士回答去。當(dāng)被問(wèn)戰(zhàn)士回答“否否”，他開(kāi)啟另一扇門(mén)離去。，他開(kāi)啟另一扇門(mén)離去。232323/22 設(shè)設(shè)P：被問(wèn)戰(zhàn)士是誠(chéng)實(shí)人：被問(wèn)戰(zhàn)士是誠(chéng)實(shí)人 Q：被問(wèn)戰(zhàn)士回答對(duì)：被問(wèn)戰(zhàn)士回答對(duì) R：另一名戰(zhàn)士的回答為：另一名戰(zhàn)士的回答為“是是” S：這扇門(mén)是死亡門(mén)：這扇門(mén)是死亡門(mén) 真值表如下：真值表如下： P Q R S 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0242424/221313、A A、B B、C

22、C、D 4D 4個(gè)人中要派兩個(gè)人出差，個(gè)人中要派兩個(gè)人出差，按下述按下述3 3個(gè)條件有幾種派法？如何派？并編個(gè)條件有幾種派法？如何派？并編程驗(yàn)證給出的結(jié)論。程驗(yàn)證給出的結(jié)論。(1)(1)若若A A去，則去，則C C和和D D中要去一人；中要去一人；(2)B(2)B和和C C不能都去；不能都去；(3)C(3)C去則去則D D要留下要留下252525/22解：本題的意思是求同時(shí)滿足上面解：本題的意思是求同時(shí)滿足上面3 3個(gè)條件的派法。個(gè)條件的派法。由組合數(shù)學(xué)知由組合數(shù)學(xué)知C C4 42 2=(4=(4* *3)/2=63)/2=6種種這這6 6種派法是：種派法是：P1P1：AB AB ；P2P2：

23、AC AC ；P3P3：ADAD P4 P4：BC BC ；P5P5：BD BD ；P6P6：CDCD但是由于但是由于P1P1不滿足條件不滿足條件(1), P6(1), P6不滿足條件不滿足條件(3),P4(3),P4不滿足條件不滿足條件(2)(2)所以均被排除。剩下所以均被排除。剩下3 3種派法是種派法是P2P2：ACAC；P3P3：ADAD和和 P5P5：BDBD262614.符號(hào)化下列命題，并用推理方法證明誰(shuí)是做案者：符號(hào)化下列命題，并用推理方法證明誰(shuí)是做案者：（1）A或或B盜竊了金項(xiàng)鏈盜竊了金項(xiàng)鏈（2）若）若A作案，則作案時(shí)間不在營(yíng)業(yè)時(shí)間作案，則作案時(shí)間不在營(yíng)業(yè)時(shí)間（3）若）若B提供的

24、證據(jù)正確，則貨柜不上鎖提供的證據(jù)正確，則貨柜不上鎖（4）若）若B提供的證據(jù)不正確，則作案時(shí)間在營(yíng)業(yè)時(shí)間提供的證據(jù)不正確，則作案時(shí)間在營(yíng)業(yè)時(shí)間（5）貨柜上鎖）貨柜上鎖另另 P：A盜竊了金項(xiàng)鏈盜竊了金項(xiàng)鏈 Q：B盜竊的金項(xiàng)鏈盜竊的金項(xiàng)鏈 R：作案時(shí)間在營(yíng)業(yè)時(shí)間：作案時(shí)間在營(yíng)業(yè)時(shí)間 S：B提供的證據(jù)正確提供的證據(jù)正確 G：貨柜上鎖：貨柜上鎖2727總結(jié)總結(jié)第二章第二章 謂詞邏輯謂詞邏輯(1)(1)個(gè)體詞、謂詞和量詞：個(gè)體詞、謂詞和量詞：(2)(2)個(gè)體常元、個(gè)體變?cè)⒓s束變?cè)?、自由變?cè)獋€(gè)體常元、個(gè)體變?cè)⒓s束變?cè)?、自由變?cè)?3)(3)命題函數(shù)，個(gè)體域，全總個(gè)體域。命題函數(shù)，個(gè)體域，全總個(gè)體域。1.

25、 1. 基本概念基本概念 (1)(1)原子公式，謂詞公式：原子公式，謂詞公式：(2)(2)謂詞公式的解釋謂詞公式的解釋?zhuān)?3)(3)謂詞公式的分類(lèi)：永真公式，永假公式，可滿足公式。謂詞公式的分類(lèi)：永真公式，永假公式，可滿足公式。 2. 2. 謂詞公式謂詞公式 2828總結(jié)總結(jié)第第二二章章 謂詞邏輯謂詞邏輯3. 3. 謂詞公式間的關(guān)系謂詞公式間的關(guān)系 (1)(1)謂詞公式間的等價(jià)關(guān)系謂詞公式間的等價(jià)關(guān)系( )( )(2)(2)謂詞公式間的蘊(yùn)含關(guān)系謂詞公式間的蘊(yùn)含關(guān)系( ) ( ) (3)(3)基本的等價(jià)式；基本的等價(jià)式； (4)(4)基本的蘊(yùn)含式基本的蘊(yùn)含式；(5)(5)判定兩公式是否具有等價(jià)和

26、蘊(yùn)含關(guān)系的方法判定兩公式是否具有等價(jià)和蘊(yùn)含關(guān)系的方法 。ABAB4. 4. 謂詞邏輯的推理理論謂詞邏輯的推理理論 (1)(1)含有量詞的推理規(guī)則：全稱(chēng)特指規(guī)則含有量詞的推理規(guī)則：全稱(chēng)特指規(guī)則(US)(US)、存在特指規(guī)則、存在特指規(guī)則(ES)(ES)； (2) P(2) P，T T，CPCP，F(xiàn) F。全稱(chēng)推廣規(guī)則全稱(chēng)推廣規(guī)則(UG)(UG)、存在推廣規(guī)則、存在推廣規(guī)則(EG)(EG)。2929 習(xí)習(xí) 題題1 1 將下列命題符號(hào)化將下列命題符號(hào)化. . （1 1）在上海高校學(xué)習(xí)的學(xué)生，未必都是上海籍的學(xué)生。）在上海高校學(xué)習(xí)的學(xué)生，未必都是上海籍的學(xué)生。 解解 令令 H(x)：x是在上海高校學(xué)習(xí)的

27、學(xué)生是在上海高校學(xué)習(xí)的學(xué)生 S(y)：y是上海籍的學(xué)生是上海籍的學(xué)生 或者或者)()(xSxHx)()(xSxHx（2 2）沒(méi)有一位女同志既是國(guó)家選手又是家庭婦女。）沒(méi)有一位女同志既是國(guó)家選手又是家庭婦女。 解解 令令W(x):x是一位女同志；是一位女同志； C(x):x是國(guó)家選手；是國(guó)家選手； H(x):x是家庭婦女是家庭婦女 x(W(x(W(x)C(x)H(x) 3030（3 3）對(duì)于每一個(gè)實(shí)數(shù)對(duì)于每一個(gè)實(shí)數(shù)x x，存在一個(gè)更大的實(shí)數(shù)，存在一個(gè)更大的實(shí)數(shù)y y。 解解 令令R(x)：x是實(shí)數(shù)；是實(shí)數(shù)； G(x,y):x比比y大。大。 x(R(x) y y( (R(y)GR(y)G(y,x)

28、 （4 4）某些汽車(chē)比所有的火車(chē)都慢，但至少有一列火車(chē)比每）某些汽車(chē)比所有的火車(chē)都慢，但至少有一列火車(chē)比每輛汽車(chē)快。輛汽車(chē)快。 解解 令令C(x)：x是汽車(chē)；是汽車(chē)；H(x)：x是火車(chē)；是火車(chē)； S(x,y): x比比y慢。慢。 ),()()(yxSyHyxCx),()()(zySyCyzHz3131 2將下一命題符號(hào)化。分析到個(gè)體詞、謂詞和量詞，將下一命題符號(hào)化。分析到個(gè)體詞、謂詞和量詞，使用全總個(gè)體域。使用全總個(gè)體域?！坝行┐髮W(xué)生不欽佩任何運(yùn)動(dòng)員有些大學(xué)生不欽佩任何運(yùn)動(dòng)員”解：解： 令令P(x): x 是大學(xué)生是大學(xué)生Q(y): y 是運(yùn)動(dòng)員是運(yùn)動(dòng)員 H(x, y): x 欽佩欽佩 y(

29、( )( ( )( , )x P xy Q yH x y命題符號(hào)化為32323.將下列各公式翻譯成自然語(yǔ)言，個(gè)體域?yàn)檎麛?shù)集將下列各公式翻譯成自然語(yǔ)言，個(gè)體域?yàn)檎麛?shù)集I，并判，并判斷各命題的真值。斷各命題的真值。(1)(2)(3)(zyxZyx) 1(yxyx)(ZyxZyx解解: (1)對(duì)任意整數(shù)對(duì)任意整數(shù) 任意整數(shù)任意整數(shù) ，存在整數(shù)，存在整數(shù) ，使得使得 。（真命題）。（真命題）(2)對(duì)任意整數(shù)對(duì)任意整數(shù) ，存在整數(shù)，存在整數(shù) ，使得，使得 （假命題）（假命題）(3)存在整數(shù)存在整數(shù) ，使得對(duì)于任意整數(shù)，使得對(duì)于任意整數(shù) 和任意整數(shù)和任意整數(shù) ，有有 （假命題）（假命題）ZZyxxy1 y

30、xZyxxyxyZ33334試判斷下列公式是否永真公式試判斷下列公式是否永真公式)()()()(xxQxxPxQxPx(1) 解：解：原式原式)()()()(xxQxxPxQxPx)()()()(xxQxxPxQxPx)()()()(xxQxxPxQxPx)()()()(xxPxxQxQxPx)()()()(xxPxQxQxPx)()()(xxPxQxPx)()()(xxPxxQxPx)()()(xxQxxPxxP( )TxQ xT因此，（因此，（1）式是永真公式。）式是永真公式。 3434（2）)()()()(yQxxPyQxPx 解：原式解：原式)()()()(yQxxPyQxxP)()(

31、)()(yQxxPyQxxP)()()()(yQxPxyQxxP)()()()()()(yQxPxyQyQxPxxxP)()()(yQxPxxxP此公式不是永真公式此公式不是永真公式設(shè)設(shè)Q(y) F，個(gè)體域，個(gè)體域E = a,b,P(a)=T,P(b)=F，則，則 但但因此因此不是永真公式。不是永真公式。( ( )( )x P xQ yT( )( )xP xQ yF)()()()(yQxxPyQxPx35355 5 用等價(jià)公式變換法證明下一等值式用等價(jià)公式變換法證明下一等值式)()()()()()(x,yHyGxFyxx,yHyGxFyx證明證明( ( )( )() )x y F xG yH

32、x,y y( ( )()()( )xF xG yH x,y ( )( )()() )x yF xG yH x,y ( ( )( )()()x y F xG yH x,y (1)3636(2)( ( )( )( )( )x A xB xxA xxB x 證明證明( ( )( )x A xB x( )( )xA xxB x ( )( )xA xxB x ( )( )xA xxB x ( )( )xA xB x 37376 6 證明下一蘊(yùn)含式證明下一蘊(yùn)含式證法一：證法一：此題等價(jià)于證明( )( )( ( )( )1()xP xxQ xx P xQ x (PQ)RP(QR)根據(jù)此題又等價(jià)于證明( )(

33、 )()( ( )( )1xP xxQ xx P xQ x )()()()(xQxPxxxQxxP3838( )( )()( ( )( )xP xxQ xx P xQ x ( )( )( ( ) ) )(xP xx Q xP xQ x ( )( )( )( )() )(xP xxQ xP xQ x ( )( )( )xP xxQ xP x ( )( )( )xP xx Q xxP x 139396 6 證明下一蘊(yùn)含式證明下一蘊(yùn)含式)()()()(xQxPxxxQxxP證法二：證法二：為真假設(shè))()(xxQxxP為真為真，且則)()(xxQxxP因此，必存在個(gè)體因此，必存在個(gè)體c，使，使P(c)

34、 為真，為真， Q(c) 為真。為真。為真，于是)()(cQcP為真故)()(xQxPx4040 7. 7. 用構(gòu)造推理過(guò)程的方法證明用構(gòu)造推理過(guò)程的方法證明)()()()()1(aQxxPaQxPx證明證明(1)( ( )( )x P xQ aP(2)( ( ( )( )(1)xP xQ aT ，(3)( )( )(2)xP xQ aT ，(4)( )( )(3)xP xQ aT ，(5)( )( )(4)xP xQ aT，(6)( )( )(5)xP xQ aT，4141(2)( )( ( )( ),( )( )( ( )( )( )xF xy G yH yxM xyG yx F xM xyH y證明證明(1)( )( ( )( )xF xy G yH yP(6)( ( )( )(1),(5)y G yH yT，(4)( )( )(3)xF xxM xT，(3)( ( )M( )x F xxP（附加前提）(2)( )( )xM xyG yP(7)( )(4)xM xT，(5)( )(4)xF xT，(9)( );(8)G cES(8)( )(2),(7)yG yT，(10)( )( );(6)G cH cUS(11)( )