離散數(shù)學(xué)課件第1章

1、,前言研究人的思維形式和規(guī)律的科學(xué)稱為邏輯學(xué)，由于研究的對象和方法各有側(cè)重而又分為形式邏輯、辨證邏輯和數(shù)理邏輯。數(shù)理邏輯是應(yīng)用數(shù)學(xué)方法研究推理的科學(xué)。數(shù)理邏輯又叫符號邏輯，因為它的主要工具是符號體系。數(shù)理邏輯的核心是把邏輯推理符號化，即變成象數(shù)學(xué)演算一樣完全形式化了的邏輯演算。本章主要介紹命題演算(1.1---1.5)和謂詞演算(1.6---1.8)。,1.1　命題1.2　重言式1.3　范式1.4　聯(lián)結(jié)詞的擴(kuò)充與歸約1

2、.5　推理規(guī)則和證明方法1.6　謂詞和量詞1.7　謂詞演算的永真公式1.8　謂詞演算的推理規(guī)則,第1章 數(shù)理邏輯,1.1 命 題1.1.1 基本概念　　斷言是一陳述語句。 一個命題是一個或真或假而不能兩者都是的斷言。如果命題是真，我們說它的真值為真; 如果命題是假，我們說它的真值是假。,,注：所謂命題，是具有真假意義的陳述句，也就是能夠確定或分辨其真假的陳述句，且真與假必居其一。簡言之，命題是非真即假的陳述

3、句。命題是真就說其真值為真，命題是假就說其真值為假。,例 1.1 - 1 下述都是命題:　　(1) 今天下雪;　　(2) 3+3=6;　　(3) 2 是偶數(shù)而 3 是奇數(shù);　　(4) 陳涉起義那天，杭州下雨;　　(5) 較大的偶數(shù)都可表為兩個質(zhì)數(shù)之和。,,以上命題中，(1)的真值取決于今天的天氣; (2)和(3)是真; (4)已無法查明它的真值，但它是或真或假的， 故將它歸屬于命題; (5)目前尚未確定其真假，但它是有真

4、值的，應(yīng)歸屬于命題。,,注：某些命題可能無法查明其真值。如例1.1-1(4),(5).命題真假會因時因地而異。例如： a) 人一只手有五指 b) 現(xiàn)在是上午那些‘自稱謂’的陳述句可能產(chǎn)生自相矛盾的結(jié)論，故不在我們討論之列。例如：某人說: ‘我正在說謊’(見P.1.1-3)請注意: 數(shù)理邏輯的任務(wù)不在于研究某個具體命題的真假問題，而在于它可以賦予真或假的可能性，特別是研究各命題規(guī)定其真值后它們之間的聯(lián)系。,例

5、1.1 - 2 下述都不是命題:　　(1) x+y＞4。 　　(2) x=3?！　?3) 真好啊!　　(4) 你去哪里?　　(1)和(2)是斷言，但不是命題，因為它的真值取決于x和y的值。 (3)和(4)都不是斷言，所以不是命題。 下邊我們再看一個例子。,,例 1.1 - 3 一個人說:“我正在說謊”?！　∷窃谡f謊還是在說真話呢? 如果他講真話，那么他所說的是真，也就是他在說謊。 我們得出結(jié)論如果他講真話

6、，那么他是在說謊。 另一方面，如果他是說謊，那么他說的是假; 因為他承認(rèn)他是說謊，所以他實際上是在說真話，我們得出結(jié)論如果他是說謊，那么他是講真話。,,從以上分析，我們得出他必須既非說謊也不是講真話。 這樣，斷言“我正在說謊”事實上不能指定它的真假，所以不是命題。 這種斷言叫悖論。　　若一個命題已不能分解成更簡單的命題，則這個命題叫原子命題或本原命題。 例1.1 - 1中(1)、(2)、(4)、(5)都是本原命題，但(3)不是，因為它

7、可寫成“2 是偶數(shù)”和“3 是奇數(shù)”兩個命題?！　∶}和本原命題常用大寫字母P、Q、R…表示。 如用P表示“4 是質(zhì)數(shù)”，則記為 　　　P: 4 是質(zhì)數(shù),,1.1.2 命題聯(lián)結(jié)詞　　原子命題?？赏ㄟ^一些命題聯(lián)結(jié)詞構(gòu)成新命題，這種命題稱為復(fù)合命題。例如　　 P: 明天下雪　　 Q: 明天下雨是兩個命題，利用聯(lián)結(jié)詞“不”、“并且”、“或(者)”等可分別構(gòu)成新命題:　　 “明天不下雪”

8、;　　 “明天下雪并且明天下雨”;　　 “明天下雪或者明天下雨”等。,,即　　 “非P”;　　 “P并且Q”;　　 “P或Q”等。　　在代數(shù)式x+3 中，x、3 叫運算對象，+叫運算符，x+3 表示運算結(jié)果。 在命題演算中，也用同樣的術(shù)語。 命題聯(lián)結(jié)詞就是命題演算中的運算符，叫邏輯運算符或叫邏輯聯(lián)結(jié)詞。 常用的聯(lián)結(jié)詞有以下 5 個。,,1 否定詞 ¬,設(shè)P表示

9、命題，則‘P不真’ 是另一命題，記為 ¬ P，讀為 ‘非P’否定詞可用右表定義，此表稱為 ¬ P的真值表,這張表叫真值表。定義運算符的真值表， 可指明如何用運算對象的真值來決定一個應(yīng)用運算符的命題的真值。 真值表的左邊列出運算對象的真值的所有可能組合，結(jié)果命題的真值列在最右邊的一列。 為了便于閱讀，我們通常用符號T(true)或 1 代表真，符號F(false)或 0 代表假。 一般在公式中采用T和F，在真值表中采

10、用 1 和 0。 這樣，以上真值表可寫成表1.1-2所示的形式。,,表1.1-2,,例 1.1-4　　(1) P: 4 是質(zhì)數(shù)?！?　　　P: 4 不是質(zhì)數(shù)?；?4 是質(zhì)數(shù)，不是這樣?！　?2) Q: 這些都是男同學(xué)?！?　　　Q: 這些不都是男同學(xué)。(翻譯成“這些都不是男同學(xué)”是錯的。),2 合取詞 ∧,若 P,Q 表示命題，則 ‘P并且Q’ 也是命題，記為 P∧Q ,讀為 ‘P合取Q’.P∧Q 的真值表如右表所

11、示。由真值表可知 P∧Q 真,當(dāng)且僅當(dāng) P,Q 俱真.,表1.1-3,例 1.1-5 P: 王華的成績很好，Q: 王華的品德很好。 P∧Q: 王華的成績很好并且品德很好。,3 析取詞 ∨,若 P,Q 表示命題，則 ‘P或者Q’ 也是命題，記為 P∨Q,讀為 ‘P析取Q’.P∨Q 的真值表如右表所示。由真值表可知 P∨Q 真,當(dāng)且僅當(dāng)P,Q 至少有一個真,表1.1-4,,例 1.1-6　　(1) P: 今晚我寫字，Q:

12、今晚我看書?！　　∨Q: 今晚我寫字或看書。　　“或”字常見的含義有兩種: 一種是“可兼或”，如例1.1-6中的或，它不排除今晚既看書又寫字這種情況; 一種是“排斥或”，例如“人固有一死，或重于泰山，或輕于鴻毛”中的“或”，它表示非此即彼，不可兼得。 運算符∨表示可兼或，排斥或以后用另一符號表達(dá)。,,(2) P: 今年是閏年; Q: 今年她生孩子?！　∨Q: 今年是閏年或者今年她生孩子?！　∵壿嬤\算符可以把兩個無關(guān)的命題

13、聯(lián)結(jié)成一新命題，作如此規(guī)定是因為有關(guān)和無關(guān)的界線難以劃分，而如此規(guī)定不會妨礙應(yīng)用。,,4 蘊(yùn)涵詞 →,若 P,Q 表示命題，則 ‘P蘊(yùn)涵Q’ 也是命題，記為 P→Q,讀為 ‘P蘊(yùn)涵Q’. P→Q 的真值表如右表所示。由真值表可知P→Q為假,當(dāng)且僅當(dāng)P為真而Q為假.,表1.1-5,,例 1.1-7　　(1) P: 天不下雨，Q: 草木枯黃?！　→Q: 如果天不下雨，那么草木枯黃。　　(2) R: G是正方形，S: G的四

14、邊相等?！　→S: 如果G是正方形，那么G的四邊相等?！　?3) W: 桔子是紫色的，V: 大地是不平的?！　→V: 如果桔子是紫色的，那么大地是不平的。,,在日常生活中用蘊(yùn)含式來斷言前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系，如例1.1-7中的(1)和(2)，這樣的蘊(yùn)含式叫形式蘊(yùn)含。在命題演算中，一個蘊(yùn)含式的前提和結(jié)論并不需要有因果和實質(zhì)聯(lián)系，這樣的蘊(yùn)含式叫實質(zhì)蘊(yùn)含，如例1.1-7中的(3)， 桔子的顏色和大地的外形之間沒有因果和實質(zhì)關(guān)

15、系存在，但蘊(yùn)含式W→V是真，因為前提是假而結(jié)論是真。 采用實質(zhì)蘊(yùn)含作定義，是因為在討論邏輯和數(shù)學(xué)問題中，這不僅是正確的，而且應(yīng)用方便。,,蘊(yùn)含式P→Q可以用多種方式陳述: 　 “若P，則Q”; 　“P是Q的充分條件”; 　“Q是P的必要條件”; 　 “Q每當(dāng)P”; 　 “P僅當(dāng)Q”等。如例1.1-7(2)中的R→S可陳述為“G是正方形的必要條件是它的四邊相等”。　　給定命題P→Q

16、，我們把Q→P，　 P→　 Q，　 Q→　 P分別叫做命題P→Q的逆命題、反命題和逆反命題。,,關(guān)于 P→Q 真值表的說明,在日常生活中當(dāng)P=0時，P→Q 沒有實際意義。故人們只考慮 P=1 的情形。但在P→Q 真值表中規(guī)定：當(dāng) P=0 時，不管 Q 如何 P→Q 的真值都為1. 有沒有道理呢？例如，張三對李四說：‘我去圖書館一定幫你借那本書’。可以將這句話表為命題 P→Q(P表示:張三去圖書館,Q表示:張三借那本書)。后

17、來張三因有事未去圖書館，即 P=0，此時按規(guī)定 P→Q 為真。我們應(yīng)理解為張三講了真話，即他要是去圖書館我們相信他一定會為李四借書。這種理解也稱為‘善意推定’。,5 等值詞 ?,若 P,Q 表示命題，則 ‘P等值于Q’ 也是命題,記為 P?Q, 讀為 ‘P等值于Q’. P?Q 的真值表如右表所示. 由真值表可知 P?Q 為真,當(dāng)且僅當(dāng)P與Q有相同的真值.,表1.1-6,,從以上 5 個定義可看出，聯(lián)結(jié)詞之意義由其真值表唯一確定，而不

18、由命題的含義確定。　　使用以上 5 個聯(lián)結(jié)詞，可將一些語句翻譯成邏輯式。 翻譯時為了減少圓括號(一般不用其它括號)的使用，我們作以下約定:　　·運算符結(jié)合力的強(qiáng)弱順序為 　 、∧、∨、→、　 ，凡符合此順序的，括號均可省去。　　·相同的運算符，按從左至右次序計算時，括號可省去?！　?#183;最外層的圓括號可以省去。,例如: 　　　　　(　 ((P∧　 Q)∨R)→((R∨P)∨Q))可寫成　　　

19、　　　　 (P∧　 Q∨R)→R∨P∨Q但有時為了看起來清楚醒目，也可以保留某些原可省去的括號。,例 1.1-8　　(1) 設(shè)P表示“他有理論知識”，Q表示“他有實踐經(jīng)驗”，則“他既有理論知識又有實踐經(jīng)驗”可譯為: P∧Q。,,(2) 設(shè)P: 明天下雨，Q: 明天下雪，R: 我去學(xué)校，則　?、?“如果明天不是雨夾雪則我去學(xué)?！笨蓪懗伞?　　　　　　　　　(P∧Q)→R　　② “如果明天不下雨并且不下雪則我去學(xué)?！笨蓪懗?/p>

20、　 　　　　　　　　　P∧　 Q→R　?、?“如果明天下雨或下雪則我不去學(xué)校”可寫成　　　　　　　　　　P∨Q→　 R,④ “明天，我將雨雪無阻一定去學(xué)?！笨蓪懗伞　∧Q∧R∨　 P∧Q∧R∨P∧　 Q∧R∨　 P∧　 Q∧R　　⑤ “當(dāng)且僅當(dāng)明天不下雪并且不下雨時我才去學(xué)?！笨蓪懗伞?　　　　　　　　 P∧　 Q　 R,,(3) 用邏輯符表達(dá)“說小學(xué)生編不了程序，或說小學(xué)生用不了個人計算機(jī)，那是不對的”。　　設(shè)P

21、: 小學(xué)生會編程序，Q: 小學(xué)生會用個人計算機(jī)，則上句可譯為　 　　　　　　　　 (　 P∨　 Q),,(4) 用邏輯符表達(dá)“若不是他生病或出差了，我是不會同意他不參加學(xué)習(xí)的”?！　≡O(shè)P: 他生病了，Q: 他出差了，R: 我同意他不參加學(xué)習(xí)，則上句可譯為　　　　　　　 　 (P∨Q)　 　 R或　　　　　　　　　P∨Q　 R　　翻譯時要按邏輯關(guān)系翻譯，而不能憑字面翻。 例如，設(shè)P: 林芬做作業(yè)，Q: 林芳做作業(yè)，則“林芬

22、和林芳同在做作業(yè)”可譯為P∧Q，但“林芬和林芳是姐妹”就不能翻釋成兩個命題的合取，它是一個原子命題。,,1.1.3 命題變元和命題公式　　通常，如果P代表真值未指定的任意命題，我們就稱P為命題變元; 如果P代表一個真值已指定的命題，我們就稱P為命題常元。 但由于在命題演算中并不關(guān)心具體命題的涵義，只關(guān)心其真假值，因此，我們可以形式地定義它們?！　∫浴罢妗?、“假”為其變域的變元，稱為命題變元; T和F稱為命題常元。,,習(xí)慣上把含有

23、命題變元的斷言稱為命題公式。 但這樣描述過于表面，它沒能指出命題公式的結(jié)構(gòu)。 因為不是由命題變元、聯(lián)結(jié)詞和一些括號組成的字符串都能成為命題公式，因此在計算機(jī)科學(xué)中常用以下定義?！　蝹€命題變元和命題常元叫原子公式。 由以下形成規(guī)則生成的公式叫命題公式(簡稱公式):　?、?單個原子公式是命題公式。　?、?如果A和B是命題公式，則(　 A)、(A∧B)、(A∨B)、(A→B)、(A　 B)是命題公式?！　、?只有有限步地應(yīng)用規(guī)則①

24、和②生成的公式，才是命題公式。,,這種定義叫歸納定義，也叫遞歸定義。 由這種定義產(chǎn)生的公式叫合式公式。 如何構(gòu)成這種定義，以后將專門敘述?！　∶}公式的真假值一般是不確定的。 當(dāng)命題公式中所有的命題變元代以命題時，命題公式就變?yōu)槊}。 在不致產(chǎn)生混亂時，我們把命題公式也叫做命題。,,例 1.1-9　　(1) 說明(P→(P∨Q))是命題公式。　　解 (i) P是命題公式 根據(jù)規(guī)則①　　(ii

25、) Q是命題公式根據(jù)規(guī)則①　　(iii) (P∨Q)是命題公式根據(jù)(i)、(ii)和規(guī)則②　　(iv) (P→(P∨Q))是命題公式根據(jù)(i)、(iii)和規(guī)則②,,(2) 以下不是命題公式，因為它們不能由形成規(guī)則得出: 　　∧Q，(P→Q，P→∧Q，((PQ)∧R)　　為了減少圓括號的使用，以后手寫命題公式時，可按過去的約定省略。　　下面舉例說明命題公式真值表的構(gòu)成方法。,,例 1.1-10　　(

26、1) 　 ((P∨Q)∧P)的真值表如表1.1-7所示。,,表1.1-7,,(2) 兩個命題公式如果有相同的真值，則稱它們是邏輯等價命題。 證明P　 Q與P∧Q∨　 P∧　 Q是邏輯等價命題?！　∽C 列真值表，如表1.1-8所示。 　　因后兩列的真假值完全一致，所以它們是邏輯等價命題。,,表1.1-8,,習(xí) 題　　1. 設(shè)P是命題“天下雪”; Q是命題“我去鎮(zhèn)上”; R是命題“我有時間”?！　?1) 用邏輯

27、符號寫出以下命題:　?、?如果天不下雪和我有時間，那么我去鎮(zhèn)上?！　、?我去鎮(zhèn)上，僅當(dāng)我有時間?！　、?天不下雪?！　、?天正在下雪，我沒去鎮(zhèn)上。,,(2) 對下述命題用中文寫出語句。① Q　 (R∧　 P)② R∧Q③ (Q→R)∧(R→Q)④ 　 (R∨Q)2. 否定下列命題:(1) 上海處處清潔。(2) 每一個自然數(shù)都是偶數(shù)。,,3. 說出下述每一命題的逆命題和逆反命題:　　(1) 如果天下雨，我將不去

28、。　　(2) 僅當(dāng)你去我將逗留。　　(3) 如果n是大于 2 的正整數(shù)，則方程xn+yn=zn無正整數(shù)解(費爾馬最后定理)?！　?4) 如果我不獲得更多幫助，我不能完成這個任務(wù)。,,4. 給P和Q指派真值T，給R和S指派真值F，求出下列命題的真值:　　(1) P∨Q∧R　　(2) P∧Q∧R∨　 ((P∨Q)∧(R∨S))　　(3) (　 (P∧Q)∨　 R)∨(　 P∧Q∨　 R)∧S　　(4) 　 (P∧Q

29、)∨　 R∨((Q　 　 P)→R∨　 S)　　(5) (P　 R)∧(　 Q→S)　　(6) P∨(Q→R∧　 P)　 Q∨　 S,,5. 構(gòu)成下列公式的真值表:(1) Q∧(P→Q)→P(2) 　 (P∨Q∧R)　 (P∨Q)∧(P∨R)(3) (P∨Q→Q∧R)→P∧　 R(4) ((　 P→P∧　 Q)→R)∧Q∨　 R,,6. 證明下列公式的真值與它們的變元值無關(guān):(1) P∧(P→Q)→Q

30、(2) (P→Q)→(　 P∨Q)(3) (P→Q)∧(Q→R)→(P→R)(4) (P　 Q)　 (P∧Q∨　 P∧　 Q),,7. 用真值表證明如果P　 Q是真，那么P→Q和Q→P都是真。 反之，如果P→Q和Q→P 都是真，那么P　 Q是真?！　?. 對P和Q的所有值，證明P→Q與　 P∨Q有同樣真值以及(P→Q)　 (　 P∨Q)總是真的。,,9. 一個有兩個運算對象的邏輯運算符，如果交換運算對象的次序，產(chǎn)生一邏

31、輯等價命題，則該邏輯運算符稱為可交換的?！　?1) 確定下述邏輯運算符哪些是可交換的: ∧、∨→、　 。　　(2) 用真值表證明你的斷言?！　?0. 設(shè)*是具有兩個運算對象的邏輯運算符，如果(x*y)*z和x*(y*z)邏輯等價，那么運算符*是可結(jié)合的?！　?1) 確定邏輯運算符∧、∨、→、　 中哪些是可結(jié)合的?！　?2) 用真值表證明你的斷言。,,11. 指出以下各式哪些不是命題公式，如果是命題公式，請說明理由:　　(1)

32、 (((　 P)→(P∧Q))∨R)　　(2) (PQ∨R)　　(3) P∧∨R　　(4) ((Q∧(P→Q))→P) 　　*12. 一個形容詞如果不具有它所表示的性質(zhì)，則稱為“它謂的”(Heterological)，例如“單音節(jié)”(Monosyllabic)就是它謂的形容詞，而“多音節(jié)”(Polysyllabic)就不是它謂的形容詞，問“Heterological”是它謂的形容詞嗎? 為什么這是悖論?,,,1.2 重

33、 言 式1.2.1 基本概念　　對有n個命題變元的命題公式A(P1，P2，…，Pn)，命題變元的真值有2n種不同的組合。 每一種組合叫做一種指派，一共有2n種指派，這就是說真值表有 2n行。 對應(yīng)于每一指派，命題公式得到一確定的值，即命題公式成為具有真假值的命題，于是可能出現(xiàn)以下情況:,,(1) 對應(yīng)于所有指派，命題公式均取值真。 這種命題公式叫重言式，或叫永真式，例如P∨　 P。　　(2) 對應(yīng)于所有指派，命題公

34、式均取值假。這種命題公式叫矛盾式，或叫永假式，例如P∧　 P?！　?3) 不是永真式，也不是永假式，這種命題公式叫偶然式?！　∫粋€公式如果至少存在一個指派，使其值為真，則稱此公式為可滿足的; 一個公式如果至少存在一個指派，使其值為假，則稱此公式為非永真。,我們著重研究重言式，它最有用，因為它有以下特點:　　(1) 重言式的否定是矛盾式，矛盾式的否定是重言式，所以研究其一就可以了?！　?2) 重言式的合取、析取、蘊(yùn)含、等值等都是

35、重言式。 這樣，由簡單的重言式可推出復(fù)雜的重言式?！　?3) 重言式中有許多非常有用的恒等式和永真蘊(yùn)含式。,,1.2.2 恒等式　　設(shè)A: A(P1,P2,…,Pn)，B: B(P1,P2,…,Pn)是兩個命題公式，這里Pi(i=1,2,…,n)不一定在兩公式中同時出現(xiàn)?！　∪绻鸄　 B是重言式，則A與B對任何指派都有相同的真值。 記為A B，叫做邏輯恒等式，讀做“A恒等于B”。,,容易看出，A　 B不過是上節(jié)的“A和B邏輯

36、等價”的另一種描述方式而已。 所以，A　 B 也讀做“A等價于B”。 請注意符號　 與符號　 意義不同。 　 是邏輯聯(lián)結(jié)詞，而　 是表示A和B有邏輯等價這個關(guān)系的符號，它的作用相當(dāng)于代數(shù)中的“=”?！　〕Ｓ玫倪壿嫼愕仁揭姳?1.2-1，表中符號P、Q和R代表任意命題，符號T代表真命題，符號F代表假命題。,,表 1.2-1 邏 輯 恒 等 式,有些恒等式特別重要，例如E14允許蘊(yùn)含式用析取式表達(dá)，E10、E11允許析取式和合取式互相

37、表達(dá)，另外，E15、E24也是常用的。 表中所有公式都可用構(gòu)造真值表證明。,,1.2.3 永真蘊(yùn)含式　　如果A→B是一永真式，那么稱為永真蘊(yùn)含式，記為A B，讀做“A永真蘊(yùn)含B”?！　〕Ｓ玫挠勒嫣N(yùn)含式如表 1.2-2 所示。,表 1.2-2 永真蘊(yùn)含式,最重要的邏輯蘊(yùn)涵式已列入表1.2-2中.建議大家也記住并使用它們通常的稱謂: 例如I1,I2,…,I6 分別叫做加法式, 簡化式, 假言推理, 拒取式, 析取三段,

38、 前提三段. I6, I9 也叫做(蘊(yùn)涵,等值)傳遞律.,,永真蘊(yùn)含式也可用真值表證明，但也可用以下辦法證明:　　(1) 假定前件是真，若能推出后件是真，則此蘊(yùn)含式是真　　(2) 假定后件是假，若能推出前件是假，則此蘊(yùn)含式是真(因按逆反律: P→Q ? ¬Q→¬P)。,,例 1.2-1 證明　 Q∧(P→Q)　 P　　方法 1: 設(shè)　 Q∧(P→Q)是真，則　 Q、P→Q是真。 所以，Q是假，

39、P是假。 因而　 P是真。 故　 Q∧(P→Q)　 P?！　》椒?2: 設(shè)　 P是假，則P是真。 以下分情況討論。　　(i) 若Q為真，則　 Q是假，所以　 Q∧(P→Q)是假?！　?ii) 若Q是假，則P→Q是假，所以　 Q∧(P→Q)是假。故　 Q∧(P→Q)　 P。,1.2.4 恒等式和永真蘊(yùn)含式的兩個性質(zhì)　　(1) 若A　 B、B　 C，則A　 C; 若A B、B C則AC。這一性質(zhì)也

40、可敘述為: 邏輯恒等和永真蘊(yùn)含都是傳遞的。 前者留給讀者自證，現(xiàn)證明后者。　　證 A→B永真; B→C永真，所以　　 (A→B)∧(B→C)永真。由公式I6得A→C永真，即A C?！　?2) 若A　 B、A　 C，則A　 B∧C?！　∽C A是真時，B和C都真，所以B∧C也真。 因此A→B∧C永真，則A　 B∧C。,,1.2.5 代入規(guī)則和替換規(guī)則　　1. 代入規(guī)則(Rule of Substituti

41、on)　　一重言式中某個命題變元出現(xiàn)的每一處均代入以同一公式后，所得的仍是重言式?！　∵@條規(guī)則之所以正確是由于重言式之值不依賴于變元的值的緣故。 例如,　　　　　　　　　　P∧　 P　 F,,今以R∧Q代P得(R∧Q)∧　 (R∧Q)　 F，仍正確。 它的思想就如同在代數(shù)中，若　　　　　　　　　　x2-y2=(x+y)(x-y)則　　　　　　　(a+b)2-(mn)2=(a+b+mn)(a+b-mn)一樣。,,代入后所

42、得公式稱為原公式的代入實例。 對非重言式通常不作代入運算，特別是偶然式，因所得代入實例的性質(zhì)不確定，沒有用處。 例如:　　　　　　　　　　　B: P→Q原是偶然式，若用R∨　 R代換B中之Q，得　　　　　　　　　　A: P→(R∨　 R)卻是重言式。,,2. 替換規(guī)則(Rule of Replacement)　　設(shè)有恒等式A　 B，若在公式C中出現(xiàn)A的地方替換以B(不必每一處)而得到公式D，則C　 D。　　如果A是合式公

43、式C中完整的一部分，且A本身是合式公式，則稱A是C的子公式，規(guī)則中“公式C中出現(xiàn)A”意指“A是C的子公式”。 這條規(guī)則的正確性是由于在公式C和D中，除替換部分外均相同，但對任一指派，A和B的真值相同，所以C和D的真值也相同，故C　 D。,,應(yīng)用這兩條規(guī)則和已有的重言式可以得出新的重言式?！　±纾瑢紼4: P∨Q　 Q∨P，我們以A∧B代P，　 A∧　 B代Q，就得出公式 　 　A∧B∨　 A∧　

44、B　 　 A∧　 B∨A∧B以　 A代P，　 A∧B∨C代Q，得就出公式 　 A∨(　 A∧B∨C)　 (　 A∧B∨C)∨　 A ……,,對公式E19: P∧T　 P，我們利用公式P∨　 P　 T，對其中的T作替換(注意不是代入，對命題常元不能代入)得公式　　 　 P∧(P∨　 P)　 P 　　 　……　　因此，我們可以

45、說表 1.2-1 和表 1.2-2 中的字符P、Q和R不僅代表命題變元， 而且可以代表命題公式，T和F不僅代表真命題和假命題，而且可以代表重言式和永假式。 用這樣的觀點看待表中的公式，應(yīng)用就更方便了。,,例 1.2-2　　(1) 證明P∧　 Q∨Q　 P∨Q?！　∽C P∧　 Q∨Q 　 Q∨P∧　 QE4　 (Q∨P)∧(Q∨　

46、Q)E9　 (Q∨P)∧TE20和替換規(guī)則　 Q∨PE19　 P∨QE4,,(2) 證明(P→Q)→(Q∨R)　 P∨Q∨R?！　∽C (P→Q)→(Q∨R)　 (　 P∨Q)→(Q∨R)E14和替換規(guī)則　 　 (　 P∨Q)∨(Q∨R)E14　 P∧　 Q∨(Q∨R)E10、E1和替換規(guī)則　 (P∧　 Q∨Q)∨RE6　 P∨Q∨R

47、 例1.2-2(1)和替換規(guī)則,,(3) 試將語句“情況并非如此: 如果他不來，那么我也不去?！被??！　〗?設(shè)P: 他來，Q: 我去，則上述語句可翻譯為　　　　　　　　　 (　 P→　 Q)　　簡化此公式: 　 (　 P→　 Q) 　 　 (　 　 P∨　 Q)E14和替換規(guī)則　 　 　 　 P∧　 　 Q

48、E10　 　 P∧QE1和替換規(guī)則　 Q∧　 PE5化簡后的語句是“我去了，而他不來”。,,(4) 找出P→(P　 Q)∨R的僅含∧和　 兩種聯(lián)結(jié)詞的等價表達(dá)式。　　解 P→(P　 Q)∨R 　 P→(P→Q)∧(Q→P)∨RE15和替換規(guī)則　 　 P∨(　 P∨Q)∧(　 Q∨P)∨R　E14

49、和替換規(guī)則　 (　 P∨　 P∨Q)∧(　 P∨　 Q∨P)∨RE9和替換規(guī)則　 (　 P∨Q)∧(T∨　 Q)∨RE2、E20和替換規(guī)則　 (　 P∨Q)∧T∨RE16和替換規(guī)則　 　 P∨Q∨RE19和替換規(guī)則　 　 (P∧　 Q∧　 R)E1，E11,,1.2.6 對偶原理　　定義1.2-1 設(shè)有公式A，其中僅有聯(lián)結(jié)詞∧、∨、　 。 在A中將∧

50、、∨、T、F分別換以∨、∧、F、T得公式A*，則A*稱為A的對偶公式。　　對A*采取同樣手續(xù)，又得A，所以A也是A*的對偶。 因此，對偶是相互的。,例 1.2-3 　　(1) 　 P∨(Q∧R)和　 P∧(Q∨R)互為對偶?！　?2) P∨F 和P∧T互為對偶。,,定理 1.2-1 設(shè)A和A*是對偶式。 P1，P2，…，Pn是出現(xiàn)于A和A*中的所有命題變元，于是 　 A(P1，P2，…，Pn)　 A*(　

51、 P1，　 P2，…，　 Pn) 定理 1.2-1 的證明留待學(xué)了一般歸納法后再在2.3節(jié)中給出。 但對具體的命題公式，不難連續(xù)應(yīng)用德·摩根定律證得。 如在例1.2-3(1)中,,,,所以,定理 1.2-2 若A　 B，且A、B為由命題變元P1，P2，…，Pn及聯(lián)結(jié)詞∧、∨、　 構(gòu)成的公式，則A*　 B*?！　∽C A　 B意味著　　　　A(P1，P2，…，Pn)　 B(P1，P2，…，Pn)永

52、真所以　　　 A(P1，P2，…，Pn)　 　 B(P1，P2，…，Pn)永真,,由定理 1.2-1 得　　　A*(　 P1，　 P2，…，　 Pn)　 B*(　 P1，　 P2，　　　　　…，　 Pn)永真因為上式是永真式，可以使用代入規(guī)則，以　 Pi代Pi，1≤i≤n，得　　　A*(P1，P2，…，Pn)　 B*(P1，P2，…，Pn)永真所以，A*　 B*。 證畢?！　”径ɡ沓７Q為對偶原理。,,例

53、 1.2-4 若(P∧Q)∨(　 P∨(　 P∨Q))　 　 P∨Q，則由對偶原理得　　　　(P∨Q)∧(　 P∧(　 P∧Q))　 　 P∧Q 定理 1.2-3 如果A　 B，且A、B為由命題變元P1，P2，…，Pn及聯(lián)結(jié)詞∧、∨、　 構(gòu)成的公式，則B*　 A*。,,證 A　 B意味著　　A(P1，P2，…，Pn)→B(P1，P2，…，Pn)永真　　　 B(P1，P2，…，Pn)→　

54、A(P1，P2，…，Pn)永真由定理 1.2-1 得　　B*(　 P1，　 P2，…，　 Pn)→A*(　 P1，　 P2，　　　　…，　 Pn)永真因為上式是永真式，可以使用代入規(guī)則，以　 Pi代Pi，1≤i≤n，得　　　　　　　　　　　B*　 A* 　　　　　　證畢,,例：證明下列等式,,等值演算：利用等值定律(邏輯恒等式，代入和替換規(guī)則，對偶原理)到已有的公式中而推演出新

55、的公式的過程,例：判斷下面公式的類型（重言式，矛盾式，可滿足式）(北京師范大學(xué)2000年考研試題,10分),,1.3 范 式　　命題公式千變?nèi)f化，這對研究其性質(zhì)和應(yīng)用帶來困難。 為此，我們有必要研究如何將命題公式轉(zhuǎn)化為邏輯等價的標(biāo)準(zhǔn)形式問題，以簡化研究工作并方便應(yīng)用。這種標(biāo)準(zhǔn)形式就稱為范式。,,1.3.1 析取范式和合取范式　　為敘述方便，我們把合取式稱為積，析取式稱為和?！　《x 1.3-1 命題公式中的

56、一些命題變元和一些命題變元的否定之積，稱為基本積; 一些命題變元和一些命題變元的否定之和，稱為基本和。（相互對偶的）　　例如，給定命題變元P和Q，則P、　 P∧Q、P∧Q、　 　　　P∧P、　 Q∧P∧Q等都是基本積，Q、　 Q∨P、P∨Q、P∨　 P、P∨Q∨　 Q等都是基本和?！　』痉e(和)中的子公式稱為此基本積(和)的因子。注意：命題變元或命題變元的否定既是基本積也是基本和。,,定理 1.3-1 一個基本

57、積是永假式，當(dāng)且僅當(dāng)它含有P、　 P形式的兩個因子?！　∽C 充分性: P∧　 P是永假式，而Q∧F　 F，所以含有P和　 P形式的兩個因子的基本積是永假式。　　必要性: 用反證法。 設(shè)基本積永假但不含P和　 P形式的兩個因子，則給這個基本積中不帶否定符的命題變元指派真值T， 給帶有否定符的命題變元指派真值F，得基本積的真值是T，但這與假設(shè)矛盾。 證畢。,,定理 1.3-2 一個基本和是永真式，當(dāng)且僅當(dāng)它含有P、　

58、 P形式的兩個因子?！　∽C明留給讀者作練習(xí)?！　《x 1.3-2 一個由基本積之和組成的公式，如果與給定的命題公式A等價，則稱它是A的析取范式，記為　　　　　　　A　 A1∨A2∨…∨An， n≥1這里A1，A2，…，An是基本積。,,任何一個命題公式都可求得它的析取范式，這是因為命題公式中出現(xiàn)的→和　 可用∧、∨和　 表達(dá)，括號可通過德·摩根定律和∧在∨上的分配律消去。 但一個命題公式的析取范式不是唯

59、一的，我們把其中運算符最少的稱為最簡析取范式?！　∪绻o定的公式的析取范式中每個基本積都是永假式，則該式也必定是永假式。,,例 1.3-1　　(1) 求P∧(P→Q)的析取范式?！　〗?P∧(P→Q)　 P∧(　 P∨Q)　　　　　　　　　　　　 P∧　 P∨P∧Q ①　　P∧(P→Q)不是永假式，因為其析取范式中，后一個基本積非永假。,,如果需要

60、求出最簡的析取范式， 那么①式還可化簡成　　　　　　　P∧(P→Q)　 F∨P∧Q　 　　　　　　　　　　　 P∧QP∧Q是P∧(P→Q)的最簡析取范式。 求最簡析取范式的方法有卡諾圖法和奎因—麥克勞斯基方法等，詳見有關(guān)“數(shù)字邏輯”的教材，這里不多敘述。,,(2) 求　 (P∨Q)　 (P∧Q)的最簡析取范式?！　〗?定義 1.3-3 一個由基本和之積組成的公式，如果與給定的命題公式A等價，則稱它是A的合取范式，記為

61、　　　　　　A　 A1∧A2∧…∧An，n≥1這里A1，A2，…，An是基本和。,,任何一個命題公式都可求得它的合取范式，這是因為命題公式中出現(xiàn)的→和　 可用∧、∨和　 表達(dá)，否定號可通過德·摩根定律深入到變元上，再利用∨在∧上的分配律可化成合取范式。 一個公式的合取范式也不是唯一的，其中運算符最少的稱為最簡合取范式。 可利用卡諾圖等方法求得最簡合取范式?！　∪绻o定的公式的合取范式中每個基本和都是永真式，則該式也必定是

62、永真式。,,例 1.3-2　　(1) 證明Q∨P∧　 Q∨　 P∧　 Q是永真式?！　〗?　 Q∨P∧　 Q∨　 P∧　 Q　 　　　　　　　Q∨(P∨　 P)∧　 Q　　　　　　　　 (Q∨P∨　 P)∧(Q∨　 Q)　　在Q∨P∧　 Q∨　 P∧　 Q的合取范式中，每一個基本和都是永真式，所以它是永真式。,,(2) 求　 (P∨Q)　 (P∧Q)的最簡合取范式。　　解 記A　

63、 　 (P∨Q)　 (P∧Q)，則　 所以，A　 (P∨Q)∧(　 P∨　 Q)。,例：求下式的析取范式和合取范式（中國科學(xué)院成都計算機(jī)應(yīng)用研究所有2001年研究生入學(xué)考試試題，15分）,,1.3.2 主析取范式和主合取范式　　定義 1.3-4 在n個變元的基本積中，若每一個變元與其否定不同時存在，而兩者之一必出現(xiàn)一次且僅出現(xiàn)一次，則這種基本積叫極小項。　　n個變元可構(gòu)成 2n個不同的極小項。 例如 3

64、個變元P、Q、R可構(gòu)造 8 個極小項。 我們把命題變元看成 1，命題變元的否定看成 0，那么每一極小項對應(yīng)一個二進(jìn)制數(shù)，因而也對應(yīng)一個十進(jìn)制數(shù)。 對應(yīng)情況如下:,,,我們把對應(yīng)的十進(jìn)制數(shù)當(dāng)作足標(biāo)，用mi表示這一項，即,一般地，n個變元的極小項是:,定義 1.3-5 一個由極小項之和組成的公式，如果與給定的命題公式A等價，則稱它是A的主析取范式?！　∪魏我粋€命題公式都可求得它的主析取范式，這是因為任何一個命題公式都可求得它的析取范式

65、，而析取范式可化為主析取范式。 例如,,,下面我們考察一個命題公式的主析取范式和它的真值表的關(guān)系?！　∏斑呏v過每一極小項和它的足標(biāo)的二進(jìn)制數(shù)一一對應(yīng)，因而和一種指派一一對應(yīng)，例如有三個變元時，　　　　　 極小項 　足標(biāo) 指派　　　　　　P∧　 Q∧R——1 0 1——1、0、1當(dāng)且僅當(dāng)將對應(yīng)的指派代入該極小項，該極小項的值才為 1。 因此，在命題公式的主析取范式中，諸極小項都與真值

66、表中相應(yīng)指派處的該公式的真值 1 相對應(yīng)，反之亦然?！　φ丈侠捅?.3-1所示的真值表，容易驗證這一點。,,表1.3-1,一個命題公式的真值表是唯一的，因此一個命題公式的主析取范式也是唯一的。 兩個命題公式如果有相同的主析取范式，那么這兩個命題公式是邏輯等價的。　　例 1.3-3 證明　 P∨Q和P→((P→Q)∧　 (　 Q∨　 P))二式邏輯等價?！　∽C,,,所以，二式邏輯等價。,定義 1.3-6 在n個變

67、元的基本和中，若每一個變元與其否定不同時存在，而二者之一必出現(xiàn)一次且僅出現(xiàn)一次，則這種基本和叫極大項。　　n個變元可構(gòu)成 2n個不同的極大項。 類似于(但不同于)極小項的記法，它們是:,這里是將命題變元對應(yīng)于 0，命題變元的否定對應(yīng)于 1，恰與極小項記法相反，例如 3 個變元的極大項是這樣對應(yīng)的　　　 極大項 足標(biāo) 指派　　　　　P∨　 Q∨R——0 1 0——0、1、0

68、其目的是當(dāng)且僅當(dāng)將極大項的對應(yīng)指派代入該極大項時，才使該極大項的真值為 0，這樣可使今后許多運算得到方便。,,定義 1.3-7 一個由極大項之積組成的公式，如果與給定的命題公式A等價，則稱它是A的主合取范式?！　∪魏我粋€命題公式都可求得它的主合取范式，這是因為任何一個命題公式都可求得它的合取范式，而合取范式可化為主合取范式。 例如,,,在命題公式的主合取范式中，諸極大項都與真值表中相應(yīng)指派處的該公式的真值 0 相對應(yīng)。 反之亦然。