《離散數(shù)學(xué)課件》命題邏輯1

1、1/60,離散數(shù)學(xué),——研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型的數(shù)學(xué)分支的統(tǒng)稱(chēng),古代數(shù)學(xué)——整數(shù)、整數(shù)的比近代數(shù)學(xué)——連續(xù)的數(shù)量概念（實(shí)數(shù)），處理連續(xù)數(shù)量關(guān)系的數(shù)學(xué)（微積分）,Discrete,離散問(wèn)題舉例,世界地圖問(wèn)題,2,一筆畫(huà)問(wèn)題,船夫問(wèn)題,幻方問(wèn)題,韓信點(diǎn)兵,郵差送信,3/60,主要內(nèi)容,數(shù)理邏輯(1-5),集 合 論 (6-8),圖 論(9-10),代 數(shù)(11-12),,,,沒(méi)有預(yù)修課程。學(xué)習(xí)數(shù)理邏

2、輯時(shí)會(huì)涉及一點(diǎn)中學(xué)階段學(xué)習(xí)的集合知識(shí)。,4/60,對(duì)計(jì)算機(jī)專(zhuān)業(yè)系統(tǒng)知識(shí)的輻射作用,《計(jì)算機(jī)光盤(pán)軟件與應(yīng)用》 188-189, 2013,5/60,數(shù)理邏輯——數(shù)學(xué)化的邏輯學(xué),德國(guó)G.W. Leibniz (1626-1716)把數(shù)學(xué)引入形式邏輯，明確提出用數(shù)學(xué)方法研究推理。英國(guó)G. Boole (1815-1864)等創(chuàng)立了邏輯代數(shù)，1847年Boole實(shí)現(xiàn)了命題演算。德國(guó)G. Frege (1848-1925)在1879年建立了第

3、一個(gè)謂詞演算系統(tǒng)。英國(guó)B. Russell (1872-1970)等從邏輯學(xué)的基本法則建立了自然數(shù)理論、實(shí)數(shù)理論及解析幾何學(xué)等。英國(guó)Alan M. Turing (1912-1954)在1936年提出一種抽象計(jì)算模型（數(shù)學(xué)邏輯機(jī)），引入圖靈機(jī)——一種理想的計(jì)算機(jī),6/60,數(shù)理邏輯的學(xué)習(xí),“我現(xiàn)在年紀(jì)大了，搞了這么多年的軟件，錯(cuò)誤不知犯了多少，現(xiàn)在覺(jué)悟了。我想，假如我早年在數(shù)理邏輯上好好下點(diǎn)工夫的話，我就不會(huì)犯這么多的錯(cuò)誤。不少東西

4、邏輯學(xué)家早就說(shuō)過(guò)了，可是我不知道。要是我能年輕二十歲的話，我就去學(xué)邏輯?！?—— Edsger. W. Dijkstra 1972年Turing獎(jiǎng)獲得者 (1930-2002),帶權(quán)圖的最短通路算法,7/60,數(shù)理邏輯,第一章 命題演算基礎(chǔ)第二章 命題演算的推理理論第三章 謂詞演算基礎(chǔ)第四章* 謂詞演算的推

5、理理論第五章* 遞歸函數(shù)論,8/60,(一) 命題定義,凡是可以判斷真假的陳述句稱(chēng)為命題。,,1.1.1 命題,9/60,例：下列句子都是命題嗎？,雪是白的。 雪是黑的。 好大的雪??！ 8大于12。 1+101=110。,?,?,?,?,?,兩個(gè)要素：,1、陳述句；,2、可以判斷真假。,凡是可以判斷真假的陳述句稱(chēng)為命

6、題。,10/60,例：下列句子都是命題嗎？,21世紀(jì)末，人類(lèi)將住在月球。 大于2的偶數(shù)可表示成兩個(gè)素?cái)?shù)之和。X<0 。 如果x大于3，則x2大于9。 我正在說(shuō)謊 。,?,?,?,?,?,悖論,11/60,命題的真假問(wèn)題,在數(shù)理邏輯的學(xué)習(xí)中，不能去糾纏各種具體命題的真假問(wèn)題，而是將命題當(dāng)成數(shù)學(xué)概念來(lái)處理，看成一個(gè)抽象的形式化的概念

7、，把命題定義成非真必假的陳述句．,12/60,帶聯(lián)結(jié)詞的命題,今晚我看書(shū)。 今晚我玩網(wǎng)絡(luò)游戲。 今晚我不看書(shū)。 今晚我不玩網(wǎng)絡(luò)游戲。 今晚我不看書(shū)， 我玩網(wǎng)絡(luò)游戲。 今晚我看書(shū)，或者我玩網(wǎng)絡(luò)游戲。,否定,并且,或者,13/60,(二) 命題的分類(lèi),原子命題——不可剖開(kāi)或分解為更簡(jiǎn)單命題的命題，也稱(chēng)為簡(jiǎn)單命題。復(fù)合命題——由原子命題利用聯(lián)結(jié)詞構(gòu)成的命題,約定用大寫(xiě)字母表示,14/60,復(fù)合命題例子,（1）雪不是白

8、的（并非雪是白的）（2）今晚我看書(shū)或者去看電影。（3）如果天氣好，那么我去接你。（4）偶數(shù)a是質(zhì)數(shù)，當(dāng)且僅當(dāng)a=2（a是常數(shù)）。（5） 2是偶數(shù)且3也是偶數(shù)。 （6）你去了學(xué)校，我去了工廠。,15/60,(三) 命題變?cè)?當(dāng)P表示任意命題時(shí)，稱(chēng)P為命題變?cè)?,16/60,1.1.2 聯(lián)結(jié)詞,否定詞 ﹁ 合取詞 ∧ 析取詞

9、 ∨ 蘊(yùn)含詞 ? 等價(jià)詞 ?,17/60,否定詞 ﹁P,讀作“非P” ， 是指命題： “P的否定”。,P ?PT FF T,,,真值表,,例 P：雪是黑色的。 ﹁P：并非雪是黑色的。,18/60,否定聯(lián)結(jié)詞使用的原則,將真命題變成假命題，將假命題變成真命題。但這并不是簡(jiǎn)單的隨意加個(gè)

10、不字就能完成的。,例 P: 這些都是學(xué)生。 ﹃P(guān)：這些不都是學(xué)生 ≠ 這些都不是學(xué)生,,19/60,合取詞 P∧Q,讀作“ P合取Q”，是指命題： “P并且Q”。,,例1 P: 今天刮風(fēng)。 Q： 今天下雨。 P∧Q：今天刮風(fēng)，下雨。,真值表,例2 P: 1+1=2。 Q： 雪是白色的。 P∧Q： 1+1=2 且雪是白色的。

11、,,例 將下列命題符號(hào)化. (1) 王曉既用功又聰明. (2) 王曉不僅聰明，而且用功. (3) 王曉雖然聰明，但不用功. (4) 張輝與王麗都是三好生. (5) 張輝與王麗是同學(xué). 解 令 p：王曉用功，q：王曉聰明，則 (1) p∧q (2) p∧q (3) p∧?q.,20,例 (續(xù)),令 r : 張輝是三好學(xué)生，s :王麗是三好學(xué)生

12、 (4) r∧s. (5) 令 t : 張輝與王麗是同學(xué)，t 是簡(jiǎn)單命題 .,21,說(shuō)明: (1)~(4)說(shuō)明描述合取式的靈活性與多樣性. (5) 中“與”聯(lián)結(jié)的是句子的主語(yǔ)成分，因而(5)中句子是簡(jiǎn)單命題.,22/60,析取詞 P∨Q,讀作“P析取Q” ，是指命題： “P或者Q”。,P Q P ?QT T TT F TF T

13、 TF F F,,,,例 P: 他會(huì)英語(yǔ)。 Q：他會(huì)法語(yǔ)。 P∨Q ：他會(huì)英語(yǔ)或者法語(yǔ)。,23/60,可兼的“或”——不可兼的“或”,P Q P∨QT T TT F TF T TF F F,,他會(huì)英語(yǔ)或法語(yǔ)。,,24/60,蘊(yùn)含詞

14、P→Q,讀作“P蘊(yùn)含Q” ，是指命題： “如果P，則Q”,,例 P：1+1＝3。 Q：雪是黑的。 P→Q: 只要1+1=3，雪就是黑的。,P Q P ?QT T TT F FF T TF F T,,,25/60,注1. 前件為假時(shí)，蘊(yùn)含式命題為真,如果蘊(yùn)含前件P是假命題，那么不管Q是什么命題，命題 P

15、→Q在邏輯中都被認(rèn)為是真命題。,,例,如果1=2，那太陽(yáng)從西邊升起。只有太陽(yáng)從西邊升起，才能1=2。只要太陽(yáng)從西邊升起，張三考試就能夠及格。,26/60,注2.蘊(yùn)含式前件、后件可以毫不相關(guān),在日常語(yǔ)言中“如果……則……”所聯(lián)結(jié)的句子之間表現(xiàn)的是一種因果關(guān)系，但在數(shù)理邏輯中，盡管說(shuō)前件蘊(yùn)涵后件，但兩個(gè)命題可以是毫不相關(guān)的。 例 P：2×3＝5 Q：雪是黑色的 P→Q：如果2&#

16、215;3＝5，則雪是黑色的,,27/60,靈活敘述蘊(yùn)含詞的例子,設(shè) R：天下雨， H：我回家， 試表示下列命題： 只要天下雨，我就回家。 只有天下雨，我才回家。 除非天下雨，否則我不回家。 僅當(dāng)天下雨，我才回家。,R→H,H→R,H→R,H→R,或﹃R→﹃H,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),p?q 的邏輯關(guān)系：q 為 p 的必要條件“如果 p，則 q ” 的不同表述法很多： 若 p，就 q 只

17、要 p，就 q p 僅當(dāng) q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否則非 p，當(dāng) p 為假時(shí)，p?q 為真常出現(xiàn)的錯(cuò)誤：不分充分與必要條件,28,29/60,等價(jià)詞 P?Q,讀作“P等價(jià)于Q”, 是指命題： “P當(dāng)且僅當(dāng)Q”,P Q P ?QT T TT F FF T

18、 FF F T,,,,例 P: 2+3＝5 Q: e是無(wú)理數(shù) P?Q ：2+3＝5的充要條件是 e是無(wú)理數(shù),,本講小結(jié),1、命題是客觀上能判明真假的陳述句。當(dāng)命題為真時(shí)，稱(chēng)命題的真值為“真”；否則，說(shuō)命題的真值為“假”。命題一般用大寫(xiě)英文字母表示。表示命題的符號(hào)叫命題標(biāo)識(shí)符。當(dāng)命題標(biāo)識(shí)符表示不確定命題時(shí)稱(chēng)為命題變?cè)?2、簡(jiǎn)單命題由聯(lián)結(jié)詞?、?、?、?、?連接可以表示復(fù)

19、合命題?P，P?Q，P?Q，P?Q，P?Q，這些復(fù)合命題的真值由真值表定義。 3、析取聯(lián)結(jié)詞?指的是“可兼或”，而漢語(yǔ)中的“或”，既可以用于“可兼或”，也可用于“排斥或”。 4、復(fù)合命題P?Q表示的邏輯關(guān)系是：Ｑ是Ｐ的必要條件,Ｐ是Ｑ的充分條件。在數(shù)學(xué)中，“如Ｐ，則Ｑ”往往要求前件為真,后者為真的推理關(guān)系。但在數(shù)理邏輯中規(guī)定當(dāng)前件為假，不論后件為真為假，均有Ｐ→Ｑ為真。,聯(lián)結(jié)詞與復(fù)合命題(續(xù)),p?q 的邏輯關(guān)系：q 為 p

20、 的必要條件“如果 p，則 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 僅當(dāng) q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否則非 p，當(dāng) p 為假時(shí)，p?q 為真常出現(xiàn)的錯(cuò)誤：不分充分與必要條件,31,第二講 命題公式與分類(lèi)（1.1.3-1.2.1）,命題變項(xiàng)與合式公式公式的賦值真值表命題的分類(lèi) 重言式 矛盾式

21、 可滿(mǎn)足式,32,33/60,1.1.3 合式公式,命題常項(xiàng)：簡(jiǎn)單命題命題變項(xiàng)：真值不確定的陳述句合式公式為如下定義的式子，簡(jiǎn)稱(chēng)為公式：?jiǎn)蝹€(gè)命題常項(xiàng)或變項(xiàng)均是公式； 如果P為公式，則?P為公式； 如果P，Q為公式，則 P?Q, P?Q, P?Q, P?Q 為公式；當(dāng)且僅當(dāng)經(jīng)過(guò)有限次使用①、②、③所組成的符號(hào)串才是公式，否則不為公式 。,34/60,n 元公式,——有n個(gè)不同的命

22、題變?cè)墓健?,例,35/60,優(yōu)先級(jí)約定,聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋?, ?, ?, ?, ?; 如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無(wú)括號(hào)時(shí)，則按從左到右的順序運(yùn)算; 若遇有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算,36/60,命題符號(hào)化,分析出簡(jiǎn)單命題，符號(hào)化用聯(lián)結(jié)詞聯(lián)結(jié)簡(jiǎn)單命題,例 將下列自然語(yǔ)言符號(hào)化:（1）如果天不下雨并且不刮風(fēng)，我就去書(shū)店。（2）小王邊走邊唱。（3）除非a能被2整除，否則a不能被4整除。（4）此時(shí)，小綱要么在學(xué)習(xí)，要

23、么在玩游戲。（5）如果天不下雨，我們?nèi)ゴ蚧@球，除非班上有會(huì)。,解 （1）如果天不下雨并且不刮風(fēng)，我就去書(shū)店。 設(shè)p：今天天下雨，q：今天天刮風(fēng)，r：我去書(shū)店。則原命題符號(hào)化為： (2)小王邊走邊唱。 設(shè)p：小王走路，q：小王唱歌。則原命題符號(hào)化為： p∧q (3)除非a能被2整除，否則a不能被4整除。

24、 設(shè)p：a能被2整除，q：a能被4整除。則原命題符號(hào)化為：,或,(4)此時(shí)，小綱要么在學(xué)習(xí)，要么在玩游戲。 設(shè)p：小剛在學(xué)習(xí)，q：小剛在玩游戲。則原命題符號(hào)化為：(5)如果天不下雨，我們?nèi)ゴ蚧@球，除非班上有會(huì)。 設(shè)p：今天天下雨，q：我們?nèi)ゴ蚧@球，r：今天班上有會(huì)。則原命題符號(hào)化為：,或,命題符號(hào)化,例2. 將下列命題符號(hào)化：（1）李明是計(jì)算機(jī)系的學(xué)生，他住在312室或313室。（2）張三和李四是朋

25、友。（3）雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)了車(chē)站。（4）只有一個(gè)角是直角的三角形才是直角三角形。（5）老王或小李中有一個(gè)去上海出差。,命題符號(hào)化,解：（1）首先用字母表示簡(jiǎn)單命題。P：李明是計(jì)算機(jī)系的學(xué)生。Q：李明住在312室。R：李明住在313室。該命題符號(hào)化為：P?（(¬Q ∧ R) ∨ (Q ∧¬R)）（2）張三和李四是朋友。是一個(gè)簡(jiǎn)單句該命題符號(hào)化為：P,（1）李明是計(jì)算機(jī)系的學(xué)生，他住在

26、312室或313室。,命題符號(hào)化,（3）雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)了車(chē)站。P：交通堵塞。Q：老王準(zhǔn)時(shí)到達(dá)了車(chē)站。該命題符號(hào)化為：P?Q（4）只有一個(gè)角是直角的三角形才是直角三角形。P：三角形的一個(gè)角是直角。Q：三角形是直角三角形。該命題符號(hào)化為：?P? ?Q 或 Q ?P,命題符號(hào)化,首先用字母表示簡(jiǎn)單命題。P：老王去上海出差。Q：小李去上海出差。該命題符號(hào)化為：（P??Q）?（?P?Q）或者（P ? Q）

27、? ? （P?Q）,（5）老王或小李中有一個(gè)去上海出差。,43/60,1.2 真假性及真值表,定義：設(shè)n元公式?中所有的不同的命題變?cè)獮?P1, P2, …,Pn,問(wèn)題：n元公式?有多少個(gè)完全解釋?zhuān)?1.2.1 解釋?zhuān)ㄙx值）,如果對(duì)每個(gè)命題變?cè)o予一個(gè)確定的值，則稱(chēng)對(duì)公式?給了一個(gè)完全解釋?zhuān)蝗绻麅H對(duì)部分變?cè)o予確定的值，則稱(chēng)對(duì)公式?給了一個(gè)部分解釋。,44/60,例 考察公式

28、?=(P?Q)? R,45/60,成真解釋與成假解釋,定義：對(duì)于任何公式?，,凡使得?取值真的解釋?zhuān)Q(chēng)為?的成真解釋。凡使得?取值假的解釋?zhuān)Q(chēng)為?的成假解釋。,,真值表 （補(bǔ)充）,46,真值表: 公式A在所有賦值下的取值情況列成的表。 例 給出公式的真值表 A= (q?p) ?q?p 的真值表,47,例 B = ? (?p?q) ?q 的真值表,,48,例 C= (p?q) ??r 的真值表,公式的類(lèi)型,定義

29、設(shè)A為一個(gè)命題公式 (1) 若A無(wú)成假賦值，則稱(chēng)A為重言式(也稱(chēng)永真式) (2) 若A無(wú)成真賦值，則稱(chēng)A為矛盾式(也稱(chēng)永假式) (3) 若A不是矛盾式，則稱(chēng)A為可滿(mǎn)足式注意：重言式是可滿(mǎn)足式，但反之不真.上例中A為重言式，B為矛盾式，C為可滿(mǎn)足式 A= (q?p)?q?p，B =?(?p?q)?q，C= (p?q)??r,49,上節(jié)課內(nèi)容 命題公式與分類(lèi),命題變項(xiàng)與合式公式公式的賦值真值表命題的分類(lèi)

30、 重言式 矛盾式 可滿(mǎn)足式,50,第三講 等值演算和聯(lián)結(jié)詞完備集1.2.2-1.2.3,等值式、基本等值式等值演算復(fù)合聯(lián)結(jié)詞 排斥或 與非式 或非式聯(lián)結(jié)詞全功能集,51,52/60,1.2.2 等價(jià)公式（等值式）,定義 給定兩個(gè)公式?和?，設(shè)P1，P2，……，Pn為?和?的所有命題變?cè)?那么?和?有2n個(gè)解釋。 如果對(duì)每個(gè)解釋?zhuān)?和?永取相同的真

31、假值， 則稱(chēng)?和?是邏輯等價(jià)(值)的，記為?=?。,與? ??是什么關(guān)系?,定義 若等價(jià)式A?B是重言式，則稱(chēng)A與B等值，記作A?B，并稱(chēng)A?B是等值式,53/60,例 問(wèn)： P ? ?P = ?P?,從真值表，可以看出： P ? ?P = ?P,考察真值表如下,基本等值式,雙重否定律 : ??A?A結(jié)合律: (A?B)?C?A?(B?C)

32、 (A?B)?C?A?(B?C)分配律: A?(B?C)?(A?B)?(A?C) A?(B?C)? (A?B)?(A?C)交換律: A?B?B?A, A?B?B?A等冪律： A?A?A, A?A?A,54,德·摩根律 : ?(A?B)??A??B

33、?(A?B)??A??B吸收律: A?(A?B)?A, A?(A?B)?A零 律: A?1?1, A?0?0 同一律: A?0?A, A?1?A排中律: A??A?1矛盾律: A??A?0,55,蘊(yùn)涵等值式: A?B??A?B等價(jià)等值式: A?B?(A?B)?(B?A)假言易位:

34、 A?B??B??A等價(jià)否定等值式: A?B??A??B歸謬論: (A?B)?(A??B) ??A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ),56,57/60,原命題=逆否命題，逆命題=否命題,設(shè)原命題為蘊(yùn)含式： P?Q，則逆命題為： Q ?P， 否命題為： ?P ? ?Q， 逆否命題為： ?

35、Q ? ?P，于是,P?Q= ?Q ? ?PQ ?P= ?P ? ?Q,真值表法等值演算法,58/60,QQ心情謎語(yǔ),,？,并非如果只有考試通過(guò)就能心情好那么我心情好。,我心情不好。,59/60,QQ心情謎語(yǔ),,？,并非如果只有考試通過(guò)才能心情好那么我心情不好。,我心情好，并且考試通過(guò)。,60/60,例 判斷下列公式的類(lèi)型 Q∨?((?P∨Q) ∧P),解: Q∨?((?P∨Q) ∧P)

36、 =Q∨(?(?P∨Q) ) ∨? P =Q∨(P ∧ ? Q) ) ∨? P = (Q ∨P ) ∧ (Q ∨ ? Q) ∨?P = (Q ∨P ) ∧ 1 ∨?P （排中律） = (Q ∨P ) ∨?P （同一律） = Q ∨1 = 1 永真式,61/60,例 判斷下列

37、公式的類(lèi)型 (P∨?P) ?((Q∧?Q) ∧R),解: (P∨?P) ?((Q∧?Q) ∧R) = 1 ?(0∧R) = 1 ? 0 = 0 所以，它是永假的。,62,續(xù)例,例 ((p?q)?(p??q))?r解 (p?q)?(p??q))?r ? (p?(q??q))?r （分配律） ? p?1?r

38、 （排中律） ? p?r （同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿(mǎn)足式.如101是它的成真賦值,000是它的成假賦值.,總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A?0 A為重言式當(dāng)且僅當(dāng)A?1說(shuō)明：演算步驟不惟一,應(yīng)盡量使演算短些,應(yīng)用舉例——證明兩個(gè)公式等值,例 證明 p?(q?r) ? (p?q)?r證

39、p?(q?r) ??p?(?q?r) （蘊(yùn)涵等值式） ?(?p??q)?r （結(jié)合律） ??(p?q)?r （德摩根律） ?(p?q) ?r （蘊(yùn)涵等值式）,63,說(shuō)明:也可以從右邊開(kāi)始演算（請(qǐng)做一遍） 熟練后，基本等值式也可以不寫(xiě)出,64/60,成真解釋和成假解釋的求解方法,（1）否定深入：即把否定詞一直深入至命題變?cè)?；?）部分解釋

40、：選定某個(gè)出現(xiàn)次數(shù)最多的變?cè)獙?duì)它作真或假的兩種解釋從而得公式；（3）化簡(jiǎn)；（4）依次類(lèi)推，直至產(chǎn)生公式的所有解釋。,前提是公式中沒(méi)有蘊(yùn)含詞、等價(jià)詞,65/60,例(p7) 試判定公式 ?(P?Q)?((?Q?P)??R) 的永真性和可滿(mǎn)足性。,解：對(duì)P=F進(jìn)行解釋并化簡(jiǎn)。 原式= ?(F?Q)?((?Q?F)??R) = ?F?(Q??R)

41、= Q ??R 當(dāng)Q=T 時(shí)， 原式 =T??R = ?R， 于是，當(dāng)R=T 時(shí)，原式=F； 當(dāng)R=F 時(shí)，原式=T。 因此,存在成真解釋 (P,Q,R)=(F,T,F); 存在成假解釋 (P,Q,R)=(F,T,T)。 故公式可滿(mǎn)足但非永真。,66,思考：證明兩個(gè)公式不等值,用等值演算不能直接證明

42、兩個(gè)公式不等值,證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真,另一個(gè)成假. 方法一 真值表法 方法二 觀察賦值法. 容易看出000, 010等是左邊的成真賦值，是右邊的成假賦值. 方法三 用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.,例 證明: p?(q?r) (p?q) ?r,67/48,1.2.3 聯(lián)結(jié)詞的完備集,定義 設(shè)S是聯(lián)結(jié)詞的集合，如果 對(duì)任何命題演算公式均可以

43、由S中的聯(lián)結(jié)詞表示出來(lái)的公式與之等價(jià)， 則稱(chēng)S是聯(lián)結(jié)詞的完備集。,由聯(lián)結(jié)詞的定義知，聯(lián)結(jié)詞集合 {?，?，?，?，?}是完備的。,68/48,定理1 聯(lián)結(jié)詞的集合{?，?，?}是完備的。,思路: 去蘊(yùn)含詞與等價(jià)詞 P?Q = ?P ∨ Q P?Q = (?P ∨Q) ∧(P ∨ ?Q),69/48,定理 聯(lián)結(jié)詞的集合{?， ∧}是完備

44、的。,思路: 在去蘊(yùn)含詞與等價(jià)詞的基礎(chǔ)上, P?Q =?P ∨ Q P?Q = (?P ∨Q) ∧(P ∨ ?Q) 去析取詞： P ∨ Q = ?(?P ∧ ?Q),70/48,定理 聯(lián)結(jié)詞的集合{?， ?}是完備的。,思路: 去等價(jià)詞、析取詞、合取詞： P?Q = ( P?Q) ∧ (P?Q

45、) P∨Q= ? P?Q P∧Q = ?(?P∨?Q)=?(P ? ?Q),71/48,定理 聯(lián)結(jié)詞的集合{↓}是完備的。,或非： P↓Q=?(P∨Q),思路： 對(duì)于完備集{?， ∨}，去否定詞與析取詞 ?P = P ↓ P P ∨ Q= ? (P ↓ Q),72/48,例 試證明聯(lián)結(jié)詞集合{∨}不完備。,證明： 對(duì)于任意公式P， ?

46、P也是公式 。 假設(shè){∨}是完備的。根據(jù)完備性的定義知， ?P = Q1 ∨ Q2 ∨ Q3 ∨ …… ∨ Qn 當(dāng)P，Q1, Q2, Q3, …… , Qn全取為假時(shí)，公式左邊=T，公式右邊=F。 顯然矛盾。 故聯(lián)結(jié)詞集合{