離散數(shù)學(xué)命題邏輯知識(shí)點(diǎn)總結(jié)

1、 數(shù)理邏輯部分第1章 命題邏輯1.1 命題符號(hào)化及聯(lián)結(jié)詞 命題: 判斷結(jié)果惟一的陳述句 命題的真值: 判斷的結(jié)果 真值的取值: 真與假真命題: 真值為真的命題假命題: 真值為假的命題注意: 感嘆句、祈使句、疑問(wèn)句都不是命題，陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題。 簡(jiǎn)單命題(原子命題)：簡(jiǎn)單陳述句構(gòu)成的命題 復(fù)合命題：由簡(jiǎn)單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題 簡(jiǎn)單命題符號(hào)化用小寫英文字母 p, q, r, ,pi,qi,ri (i1）表示簡(jiǎn)單命題 用“1”表示真，用“0”表示假例如，令 p： 是有理數(shù)，則 p 的真值為 0 q：2 + 5 = 7，則 q 的真值為 1 聯(lián)結(jié)詞與復(fù)合

2、命題1.否定式與否定聯(lián)結(jié)詞“Ø” 定義 設(shè)p為命題，復(fù)合命題 “非p”（或 “p的否定”）稱 為p的否定式，記作Øp. 符號(hào)Ø稱作否定聯(lián)結(jié)詞，并規(guī)定Øp 為真當(dāng)且僅當(dāng)p為假.2.合取式與合取聯(lián)結(jié)詞“” 定義 設(shè)p,q為二命題,復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作pq. 稱作合取聯(lián)結(jié)詞，并規(guī)定 pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真 注意：描述合取式的靈活性與多樣性 分清簡(jiǎn)單命題與復(fù)合命題 例 將下列命題符號(hào)化. (1) 王曉既用功又聰明. (2) 王曉不僅聰明，而且用功. (3) 王曉雖然聰明，但不用功. (4) 張輝與王麗都是三好生.

3、(5) 張輝與王麗是同學(xué).解 令 p：王曉用功，q：王曉聰明，則 (1) pq (2) pq (3) pØq. 令 r : 張輝是三好學(xué)生，s :王麗是三好學(xué)生 (4) rs. (5) 令 t : 張輝與王麗是同學(xué)，t 是簡(jiǎn)單命題 .說(shuō)明: (1)(4)說(shuō)明描述合取式的靈活性與多樣性. (5) 中“與”聯(lián)結(jié)的是兩個(gè)名詞，整個(gè)句子是一個(gè)簡(jiǎn)單命題. 3.析取式與析取聯(lián)結(jié)詞“” 定義 設(shè) p,q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq. 稱作析取聯(lián)結(jié)詞，并規(guī)定pq為假當(dāng)且僅當(dāng)p與q同時(shí)為假.例 將下列命題符號(hào)化 (1) 2或4是素?cái)?shù). (2) 2或3是素?cái)?shù). (3) 4或6

4、是素?cái)?shù). (4) 小元元只能拿一個(gè)蘋果或一個(gè)梨. (5) 王曉紅生于1975年或1976年. 解 令 p:2是素?cái)?shù), q:3是素?cái)?shù), r:4是素?cái)?shù), s:6是素?cái)?shù), 則 (1), (2), (3) 均為相容或. 分別符號(hào)化為: pr , pq, rs, 它們的真值分別為 1, 1, 0. 而 (4), (5) 為排斥或. 令 t :小元元拿一個(gè)蘋果，u:小元元拿一個(gè)梨， 則 (4) 符號(hào)化為 (tØu) (Øtu). 令v :王曉紅生于1975年,w:王曉紅生于1976年,則 (5) 既可符號(hào)化為 (vØw)(Øvw), 又可符號(hào)化為 vw , 為什么?

5、 4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“®” 定義 設(shè) p,q為二命題，復(fù)合命題 “如果p,則q” 稱作p與q的蘊(yùn)涵式，記作p®q，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件. ®稱作蘊(yùn)涵聯(lián)結(jié)詞，并規(guī)定，p®q為假當(dāng)且僅當(dāng) p 為真 q 為假.p®q 的邏輯關(guān)系：q 為 p 的必要條件 “如果 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ò)誤：不分充分與必要條件 5.等價(jià)式與等價(jià)聯(lián)結(jié)詞“«” 定義

6、設(shè)p，q為二命題，復(fù)合命題 “p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作p«q. «稱作等價(jià)聯(lián)結(jié)詞.并規(guī)定p«q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假.說(shuō)明: (1) p«q 的邏輯關(guān)系:p與q互為充分必要條件 (2) p«q為真當(dāng)且僅當(dāng)p與q同真或同假聯(lián)結(jié)詞優(yōu)先級(jí):( ),Ø, Ù, Ú, ®, « 同級(jí)按從左到右的順序進(jìn)行以上給出了5個(gè)聯(lián)結(jié)詞：Ø, Ù, Ú, ®, «，組成一個(gè)聯(lián)結(jié)詞集合Ø, Ù, Ú, ®

7、, «， 聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋?#216;, Ù, Ú, ®, « 如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無(wú)括號(hào)時(shí)，則按從左到右的順序運(yùn)算; 若遇有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算. 注意: 本書中使用的 括號(hào)全為園括號(hào). n 命題常項(xiàng) n 命題變項(xiàng) 1.2 命題公式及分類 § 命題變項(xiàng)與合式公式§ 命題常項(xiàng)：簡(jiǎn)單命題 § 命題變項(xiàng)：真值不確定的陳述句 § 定義 合式公式 (命題公式, 公式) 遞歸定義如下：§ (1) 單個(gè)命題常項(xiàng)或變項(xiàng) p,q,r,pi ,qi ,ri ,0,1§ 是合式公式

8、67; (2) 若A是合式公式，則 (ØA)也是合式公式§ (3) 若A, B是合式公式，則(AÙB), (AÚB), (A®B), (A«B)也是合式公式§ (4) 只有有限次地應(yīng)用(1)(3)形成的符號(hào)串才是合式公式§ 說(shuō)明: 元語(yǔ)言與對(duì)象語(yǔ)言, 外層括號(hào)可以省去 合式公式的層次定義 (1) 若公式A是單個(gè)的命題變項(xiàng), 則稱A為0層公式.(2) 稱A是n+1(n0)層公式是指下面情況之一： (a) A=ØB, B是n層公式； (b) A=BÙC, 其中B,C分別為i層和j層公式，且 n=ma

9、x(i, j)； (c) A=BÚC, 其中B,C的層次及n同(b)； (d) A=B®C, 其中B,C的層次及n同(b)； (e) A=B«C, 其中B,C的層次及n同(b). 例如 公式 p 0層 Øp 1層 Øp®q 2層 Ø(p®q)«r 3層 (ØpÙq) ®r)«(ØrÚs) 4層§ 公式的賦值§ 定義 給公式A中的命題變項(xiàng) p1, p2, , pn指定§ 一組真值稱為對(duì)A的一個(gè)賦值或解釋 §

10、成真賦值: 使公式為真的賦值 § 成假賦值: 使公式為假的賦值 § 說(shuō)明： § 賦值a=a1a2an之間不加標(biāo)點(diǎn)符號(hào)，ai=0或1.§ A中僅出現(xiàn) p1, p2, , pn，給A賦值a1a2an是§ 指 p1=a1, p2=a2, , pn=an § A中僅出現(xiàn) p, q, r, , 給A賦值a1a2a3是指§ p=a1,q=a2 , r=a3 § 含n個(gè)變項(xiàng)的公式有2n個(gè)賦值.§ 真值表真值表: 公式A在所有賦值下的取值情況列成的表 例 給出公式的真值表 A= (q®p) Ùq

11、74;p 的真值表例 B = Ø (ØpÚq) Ùq 的真值表例 C= (pÚq) ®Ør 的真值表命題的分類 重言式 矛盾式 可滿足式定義 設(shè)A為一個(gè)命題公式 (1) 若A無(wú)成假賦值，則稱A為重言式(也稱永真式) (2) 若A無(wú)成真賦值，則稱A為矛盾式(也稱永假式) (3) 若A不是矛盾式，則稱A為可滿足式 注意：重言式是可滿足式，但反之不真. 上例中A為重言式，B為矛盾式，C為可滿足式 A= (q®p)Ùq®p，B =Ø(ØpÚq)Ùq，C= (p&#

12、218;q)®Ør1.3 等值演算 n 等值式定義 若等價(jià)式A«B是重言式，則稱A與B等值，記作AÛB，并稱AÛB是等值式說(shuō)明：定義中，A,B,Û均為元語(yǔ)言符號(hào), A或B中可能有啞元出現(xiàn).例如，在 (p®q) Û (ØpÚq)Ú (ØrÙr)中，r為左邊公式的啞元. 用真值表可驗(yàn)證兩個(gè)公式是否等值請(qǐng)驗(yàn)證：p®(q®r) Û (pÙq) ®r p®(q®r) (p®q) ®r n

13、 基本等值式雙重否定律 : ØØAÛA 等冪律： AÚAÛA, AÙAÛA 交換律: AÚBÛBÚA, AÙBÛBÙA 結(jié)合律: (AÚB)ÚCÛAÚ(BÚC) (AÙB)ÙCÛAÙ(BÙC)分配律: AÚ(BÙC)Û(AÚB)Ù(AÚC) AÙ(BÚC)Û (AÙB)

14、Ú(AÙC)德·摩根律: Ø(AÚB)ÛØAÙØB Ø(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Û0n 等

15、值演算: 由已知的等值式推演出新的等值式的過(guò)程 置換規(guī)則：若AÛB, 則F(B)ÛF(A) 等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞 (2) 基本的等值式 (3) 置換規(guī)則 應(yīng)用舉例證明兩個(gè)公式等值例1 證明 p®(q®r) Û (pÙq)®r 證 p®(q®r) ÛØpÚ(ØqÚr) （蘊(yùn)涵等值式，置換規(guī)則） Û(ØpÚØq)Úr （結(jié)合律，置換規(guī)則） ÛØ(p

16、17;q)Úr （德×摩根律，置換規(guī)則） Û(pÙq) ®r （蘊(yùn)涵等值式，置換規(guī)則）說(shuō)明:也可以從右邊開(kāi)始演算（請(qǐng)做一遍） 因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出 應(yīng)用舉例證明兩個(gè)公式不等值例2 證明: p®(q®r) (p®q) ®r 用等值演算不能直接證明兩個(gè)公式不等值,證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真,另一個(gè)成假. 方法一 真值表法（自己證） 方法二 觀察賦值法. 容易看出000, 010等是左邊的的成真賦值，是右邊的成假賦值. 方法三 用等值演算先

17、化簡(jiǎn)兩個(gè)公式，再觀察.應(yīng)用舉例判斷公式類型例3 用等值演算法判斷下列公式的類型 (1) qÙØ(p®q) 解 qÙØ(p®q) Û qÙØ(ØpÚq) （蘊(yùn)涵等值式） Û qÙ(pÙØq) （德×摩根律） Û pÙ(qÙØq) （交換律，結(jié)合律） Û pÙ0 （矛盾律） Û 0 （零律） 由最后一步可知，該式為矛盾式. (2) (p®q)«(

18、16;q®Øp) 解 (p®q)«(Øq®Øp) Û (ØpÚq)«(qÚØp) （蘊(yùn)涵等值式） Û (ØpÚq)«(ØpÚq) （交換律） Û 1由最后一步可知，該式為重言式.問(wèn)：最后一步為什么等值于1？ (3) (pÙq)Ú(pÙØq)Ùr) 解 (pÙq)Ú(pÙØq)Ùr) Û (

19、pÙ(qÚØq)Ùr （分配律） Û pÙ1Ùr （排中律） Û pÙr （同一律） 這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當(dāng)且僅當(dāng)AÛ0 A為重言式當(dāng)且僅當(dāng)AÛ1說(shuō)明：演算步驟不惟一,應(yīng)盡量使演算短些 1.5 對(duì)偶與范式對(duì)偶式與對(duì)偶原理 定義 在僅含有聯(lián)結(jié)詞Ø, ,的命題公式A中，將換成, 換成，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對(duì)偶式，記為A*. 從定義不難看出，(A*

20、)* 還原成A 定理 設(shè)A和A*互為對(duì)偶式，p1,p2,pn是出現(xiàn)在A和A*中的全部命題變項(xiàng)，將A和A*寫成n元函數(shù)形式，則 (1) Ø A(p1,p2,pn) Û A* (Ø p1, Ø p2, Ø pn) (2) A(Ø p1, Ø p2, Ø pn) Û Ø A* (p1,p2,pn) 定理（對(duì)偶原理）設(shè)A，B為兩個(gè)命題公式，若A Û B，則A* Û B*.析取范式與合取范式 文字:命題變項(xiàng)及其否定的總稱 簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式 如 p, Øq,

21、pÚØq, pÚqÚr, 簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合取式 如 p, Øq, pÙØq, pÙqÙr, 析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式 A1ÚA2Ú¼ÚAr, 其中A1,A2,¼,Ar是簡(jiǎn)單合取式 合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式 A1ÙA2Ù¼ÙAr , 其中A1,A2,¼,Ar是簡(jiǎn)單析取式范式:析取范式與合取范式的總稱  公式A的析取范式: 與A等值的析取范式 公式A的合取

22、范式: 與A等值的合取范式說(shuō)明： 單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式 pÙØqÙr, ØpÚqÚØr既是析取范式，又是合取范式(為什么?) 命題公式的范式定理 任何命題公式都存在著與之等值的析取范式與合取范式. 求公式A的范式的步驟： (1) 消去A中的®, «（若存在） (2) 否定聯(lián)結(jié)詞Ø的內(nèi)移或消去 (3) 使用分配律 Ù對(duì)Ú分配（析取范式） Ú對(duì)Ù分配（合取范式） 公式的范式存在，但不惟一 求公式的范式舉例例 求下列公式的析取范式與合取范式 (

23、1) A=(p®Øq)ÚØr 解 (p®Øq)ÚØr Û (ØpÚØq)ÚØr （消去®） Û ØpÚØqÚØr （結(jié)合律） 這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式） (2) B=(p®Øq)®r 解 (p®Øq)®r Û (ØpÚ

24、6;q)®r （消去第一個(gè)®） Û Ø(ØpÚØq)Úr （消去第二個(gè)®） Û (pÙq)Úr （否定號(hào)內(nèi)移德×摩根律） 這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成） 繼續(xù)： (pÙq)Úr Û (pÚr)Ù(qÚr) （Ú對(duì)Ù分配律） 這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成） 極小項(xiàng)與極大項(xiàng)定義 在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式(簡(jiǎn)單析取式)中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出

25、現(xiàn)一次，而且第i（1£i£n）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）.說(shuō)明：n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng) 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值 用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示. 用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示, mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱. mi與Mi的關(guān)系: Ømi Û Mi , ØMi Û mi 主析取范式與主合取范式 主析取范式: 由極小項(xiàng)構(gòu)成的析取范式 主合取范式: 由極大項(xiàng)構(gòu)成的合取范式 例如，n=3, 命

26、題變項(xiàng)為p, q, r時(shí)， (ØpÙØqÙr)Ú(ØpÙqÙr) Û m1Úm3 是主析取范式 (pÚqÚØr)Ù(ØpÚqÚØr) Û M1ÙM5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: 與A等值的主合取范式. 定理 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是惟一的. 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2)

27、 將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn) 單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析 ?。O大項(xiàng)的合?。枰猛宦桑?律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序. 求公式的主范式例 求公式 A=(p®Øq)®r的主析取范式與主合 取范式. (1) 求主析取范式 (p®Øq)®r Û (pÙq)Úr , （析取范式） (pÙq) Û (pÙq)Ù(ØrÚr) Û

28、; (pÙqÙØr)Ú(pÙqÙr) Û m6Úm7 , r Û(ØpÚp)Ù(ØqÚq)Ùr Û(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr) Û m1Úm3Úm5Úm7 , 代入并排序，得 (p®Øq)

29、®r Û m1Úm3Úm5Ú m6Úm7（主析取范式） (2) 求A的主合取范式 (p®Øq)®r Û (pÚr)Ù(qÚr) , （合取范式） pÚr Û pÚ(qÙØq)Úr Û (pÚqÚr)Ù(pÚØqÚr) Û M0ÙM2, qÚr Û (pÙØp)Úq

30、18;r Û (pÚqÚr)Ù(ØpÚqÚr) Û M0ÙM4 , 代入并排序，得 (p®Øq)®r Û M0ÙM2ÙM4 （主合取范式） 主范式的用途與真值表相同(1) 求公式的成真賦值和成假賦值 例如 (p®Øq)®r Û m1Úm3Úm5Ú m6Úm7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦

31、值. 類似地，由主合取范式也可立即求出成 假賦值和成真賦值. (2) 判斷公式的類型 設(shè)A含n個(gè)命題變項(xiàng)，則 A為重言式ÛA的主析取范式含2n個(gè)極小項(xiàng) ÛA的主合取范式為1.A為矛盾式Û A的主析取范式為0 Û A的主合取范式含2n個(gè)極大項(xiàng) A為非重言式的可滿足式 ÛA的主析取范式中至少含一個(gè)且不含全部極小項(xiàng) ÛA的主合取范式中至少含一個(gè)且不含全部極大項(xiàng) 例 某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí). 選派必須滿足以下條件： (1)若趙去，錢也去； (2)李、周兩人中至少有一人去； (3)錢、孫兩人中有一人去

32、且僅去一人； (4)孫、李兩人同去或同不去； (5)若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國(guó)？ 解此類問(wèn)題的步驟為： 將簡(jiǎn)單命題符號(hào)化 寫出各復(fù)合命題 寫出由中復(fù)合命題組成的合取式 求中所得公式的主析取范式 解 設(shè)p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. (1) (p®q) (2) (sÚu) (3) (qÙØr)Ú(ØqÙr) (4) (rÙs)Ú(ØrÙØs) (5) (u®(pÙq) (1) (5)構(gòu)成

33、的合取式為 A=(p®q)Ù(sÚu)Ù(qÙØr)Ú(ØqÙr)Ù (rÙs)Ú(ØrÙØs)Ù(u®(pÙq) A Û (ØpÙØqÙrÙsÙØu)Ú(pÙqÙØrÙØsÙu)結(jié)論：由可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙

34、、錢、周去（孫、李不去）. A的演算過(guò)程如下: A Û (ØpÚq)Ù(qÙØr)Ú(ØqÙr)Ù(sÚu)Ù(ØuÚ(pÙq)Ù (rÙs)Ú(ØrÙØs) （交換律)B1= (ØpÚq)Ù(qÙØr)Ú(ØqÙr) Û (ØpÙqÙØr)Ú(ØpÙØqÙr)Ú(qÙØr) （分配律）B2= (sÚu)Ù(ØuÚ(pÙq) Û (sÙØu