離散數(shù)學(xué) 精品課程 考研 大學(xué)課程 數(shù)學(xué)一 第一章 命題邏輯ppt課件

1、第第1章章 命題邏輯命題邏輯 數(shù)理邏輯是用數(shù)學(xué)方法來(lái)研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科。 現(xiàn)代數(shù)理邏輯可分為邏輯演算邏輯演算、證明論證明論、公理集公理集合論合論、遞歸論遞歸論和模型論模型論。 本課程介紹的是數(shù)理邏輯最基本的內(nèi)容，也是與計(jì)算機(jī)科學(xué)關(guān)系最為密切的：命題邏輯命題邏輯和謂詞邏謂詞邏輯（一階邏輯）輯（一階邏輯） 主要內(nèi)容 1.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 1.2 命題公式及分類(lèi)命題公式及分類(lèi) 1.3 等值演算等值演算 1.4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 1.5 對(duì)偶與對(duì)偶與范式范式 1.6 推理理論推理理論 1.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞 命題命題：能判斷

2、真假的陳述句。 真值真值：一個(gè)命題表達(dá)的判斷結(jié)果稱(chēng)為命題的真值。命題的真值有“真”和“假”兩種，分別用True、T、1(真)和False、F、0(假)來(lái)表示。真值為真的命題稱(chēng)為真命題，真值為假的命題稱(chēng)為假命題。任何命題的真值是惟一的。 注: 一切沒(méi)有判斷內(nèi)容的句子，無(wú)所謂是非的句子，如感嘆句、疑問(wèn)句、祈使句等都不是命題。例1：1. 2是素?cái)?shù)。2. 雪是黑色的。3. 2+3=5 。4. 明年十月一日是晴天。5. 這朵花多好看呀！6. 3能被2整除.7. 明天下午有會(huì)嗎？8. 請(qǐng)關(guān)上門(mén)！9. x+y5 。10.地球外的星球上也有人。命題判斷的關(guān)鍵：1.是否是陳述句；2.真值是否是唯一的。 簡(jiǎn)單命題

3、簡(jiǎn)單命題（原子命題）：不能分解為更簡(jiǎn)單的陳述句。 簡(jiǎn)單命題又稱(chēng)為命題常項(xiàng)命題常項(xiàng)或命題常元。命題常元。對(duì)于真值可以變化的簡(jiǎn)單陳述句稱(chēng)為命題變命題變項(xiàng)項(xiàng)或命題變?cè)?。命題變?cè)?復(fù)合命題復(fù)合命題：由聯(lián)結(jié)詞把幾個(gè)原子命題聯(lián)結(jié)起來(lái)的命題。表示法：表示法：表示法例子有關(guān)概念簡(jiǎn)單命題p,q,r,pi,qi,ri,p: 2是素?cái)?shù)q:雪是黑色的命題符號(hào)化：將命題命題符號(hào)化：將命題的符號(hào)放在該命題的的符號(hào)放在該命題的前面前面命題常項(xiàng)（常元）同上同上真值確定的簡(jiǎn)單命題命題變項(xiàng)（變?cè)┩蟨: x+y5真值可以變化的簡(jiǎn)單陳述句復(fù)合命題pq2是素?cái)?shù)和偶數(shù)注：一個(gè)符號(hào)表示的是命題常項(xiàng)還是命題變項(xiàng)由上下文決定。注：一個(gè)符

4、號(hào)表示的是命題常項(xiàng)還是命題變項(xiàng)由上下文決定。例2：將下列各命題符號(hào)化1. 3不是偶數(shù).2. 2是素?cái)?shù)和偶數(shù).3. 林芳學(xué)過(guò)英語(yǔ)或日語(yǔ).4. 如果角A和角B是對(duì)頂角,則角A等于角B. 1. 否定聯(lián)結(jié)詞 定義1.1 設(shè)p為命題，則p的否定是一個(gè)復(fù)合命題，記作：p，讀作“非p”或“p的否定”。 為否否定聯(lián)結(jié)詞定聯(lián)結(jié)詞。p為真當(dāng)且僅當(dāng)p為假。 表1.1 p p 0 1 1 0 【例】否定下列命題。 p：王強(qiáng)是一名大學(xué)生。 p：王強(qiáng)不是一名大學(xué)生。 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞 常用的邏輯聯(lián)結(jié)詞有五種：否定聯(lián)結(jié)詞、合取聯(lián)結(jié)詞、析取聯(lián)結(jié)詞、蘊(yùn)涵聯(lián)結(jié)詞和等價(jià)聯(lián)結(jié)詞。 2. 合取聯(lián)結(jié)詞 定義1.2 設(shè)p和q均為命題，

5、則p和q的合取是一個(gè)復(fù)合命題，記作pq，讀作“p與q”或“p合取q”。 為合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞。 pq為真當(dāng)且僅當(dāng)p和q同時(shí)為真。 表1.2 pqpq0 00010100111 【例】設(shè) p：北京成功舉辦了第29屆夏季奧運(yùn)會(huì)。 q：今年10月1日是我國(guó)國(guó)慶60周年。則pq：北京成功舉辦了第29屆夏季奧運(yùn)會(huì)并且今年10月1日是我國(guó)國(guó)慶60周年。例3：將下列各命題符號(hào)化1. 李平既聰明又用功.2. 李平雖然聰明，但不用功.3. 李平不但聰明，而且用功.4. 李平不是不聰明，而是不用功. 3. 析取聯(lián)結(jié)詞 定義1.3 設(shè)p和q均為命題，則p和q的析取是一個(gè)復(fù)合命題，記作pq，讀作“p或q”或者“p析

6、取q”。 為析取析取聯(lián)結(jié)詞聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p與q中至少一個(gè)為真。 表1.3pqpq000011101111 “”與漢語(yǔ)中的“或”相似，但又不相同。漢語(yǔ)中的或有可兼或與不可兼或(排斥或)的區(qū)分。 【例】下列兩個(gè)命題中的“或”，哪個(gè)是可兼或？哪個(gè)是不可兼或？ 在家里看奧運(yùn)會(huì)或在現(xiàn)場(chǎng)看奧運(yùn)會(huì)。(不可兼或) 燈泡有故障或開(kāi)關(guān)有故障。(可兼或) 注：“”是可兼或。 4. 蘊(yùn)涵聯(lián)結(jié)詞 定義1.4 設(shè)p和q均為命題， p與q的蘊(yùn)涵式是個(gè)復(fù)合命題，記為：pq。讀作“如果p，那么q”或“若p，則q”。 為蘊(yùn)涵聯(lián)蘊(yùn)涵聯(lián)結(jié)詞結(jié)詞。pq為假當(dāng)且僅當(dāng)p為真且q為假。p稱(chēng)為條件命題pq的前件，q稱(chēng)為條件命題pq的

7、后件。 表1.4 pqpq001011100111 【例】 p：小王努力學(xué)習(xí)。q：小王學(xué)習(xí)成績(jī)優(yōu)秀。 pq：如果小王努力學(xué)習(xí)，那么他的學(xué)習(xí)成績(jī)就優(yōu)秀。 聯(lián)結(jié)詞“”與漢語(yǔ)中的“如果，那么”或“若，則”相似，但又是不相同的。 例4：將下列各命題符號(hào)化1. 只要不下雨，我就騎自行車(chē)上班.2. 只有不下雨，我才騎自行車(chē)上班.3. 若2+2=4，則太陽(yáng)從東方升起.4. 若2+24，則太陽(yáng)從東方升起.5. 若2+2=4，則太陽(yáng)從西方升起.6. 若2+24，則太陽(yáng)從西方升起. 5. 等價(jià)聯(lián)結(jié)詞 定義1.5 設(shè)p和q均為命題，其復(fù)合命題pq稱(chēng)為等價(jià)式等價(jià)式， pq讀作：“p當(dāng)且僅當(dāng)q”。 為等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)

8、詞。pq為真當(dāng)且僅當(dāng)p和q的真值相同。 表1.5 pqpq001010100111【例】 p：張華是三好學(xué)生。 q：張華德、智、體全優(yōu)秀。 pq：張華是三好學(xué)生當(dāng)且僅當(dāng)?shù)?、智、體 全優(yōu)秀。 例5 分析下列各命題的真值1. 2+2=4當(dāng)且僅當(dāng)3是奇數(shù). 2. 2+2=4當(dāng)且僅當(dāng)3不是奇數(shù).3. 2+24當(dāng)且僅當(dāng)3是奇數(shù).4. 2+24當(dāng)且僅當(dāng)3不是奇數(shù).聯(lián)結(jié)詞的比較表聯(lián)結(jié)詞的比較表p,q為兩個(gè)命題注：以上5種聯(lián)結(jié)詞也稱(chēng)真值聯(lián)結(jié)詞真值聯(lián)結(jié)詞或邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞或邏輯運(yùn)邏輯運(yùn) 算符。算符。1. 小王是游泳冠軍或百米賽跑冠軍.2. 小王現(xiàn)在在宿舍或圖書(shū)館里.3. 選小王或小李中的一人當(dāng)班長(zhǎng).4. 如

9、果我上街，我就去書(shū)店看看，除非我很累.5. 王一樂(lè)是計(jì)算機(jī)系的學(xué)生，他生于1968或1969年，他是三好學(xué)生. 例6：將下列命題符號(hào)化1.2 1.2 命題公式及分類(lèi)命題公式及分類(lèi) 定義1.6 按下列規(guī)則構(gòu)成的符號(hào)串稱(chēng)為命題演算的合式公式合式公式，也稱(chēng)為命題公式命題公式，簡(jiǎn)稱(chēng)公式公式。 單個(gè)命題常項(xiàng)或變項(xiàng)p,q,r,pi,qi,ri,，0，1是合式公式； 如果A是合式公式，那么(A)是合式公式； 如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)是合式公式； 只有有限次地應(yīng)用了、所得到的符號(hào)串是合式公式。 命題公式一般的用大寫(xiě)的英文字母A，B，C，表示。 依照這個(gè)定義，下列符號(hào)串是

10、合式公式： (pq)， (p(pq)， (pq)(qr)(st)下列符號(hào)串不是合式公式： (pq)(q)，(pq(pq)q) 定義1.6給出合式公式定義的方法稱(chēng)為歸納定歸納定義義，它包括三部分：基礎(chǔ)，歸納和界限。定義1.6中的是基礎(chǔ)，和是歸納，是界限。 今后還將多次出現(xiàn)這種形式的定義。 為方便起見(jiàn)，對(duì)命題公式約定如下： 最外層括號(hào)可以省略； 規(guī)定聯(lián)結(jié)詞的優(yōu)先級(jí)由高到低依次為，。按此優(yōu)先級(jí)別，如果去掉括號(hào)，不改變?cè)竭\(yùn)算次序，也可以省掉這些括號(hào)。 一般地說(shuō)，命題公式中包含命題變?cè)蚨鵁o(wú)法計(jì)算其真值，所以不是命題。 命題公式中的命題變?cè)?，也叫命題公式的分量。 定義定義1.7 命題公式的層次的定

11、義：1. 若A是單個(gè)命題（常項(xiàng)或變項(xiàng)），p,q,r,pi,qi,ri,0,1,則稱(chēng)A是0層公式.2. 稱(chēng)A是n+1(n0)層公式是指A符合下列情況之一： A= B,B是n層公式； A= BC，其中B，C分別為i層和j層公式，且 n=max(i,j)； A= BC，其中B，C的層次同； A= BC，其中B，C的層次同； A= BC，其中B，C的層次同；若A的最高層次為k，則稱(chēng)A是k層公式. 對(duì)一個(gè)公式的解釋和賦值定義如下： 定義定義1.8 設(shè)A為一個(gè)命題公式，p1, p2,，pn為出現(xiàn)在A中的所有的命題變項(xiàng)。給p1, p2,，pn指定一組真值，稱(chēng)為對(duì)A的一個(gè)賦值賦值或解釋解釋。若指定的一組值使A

12、的值為真，則稱(chēng)這組值為A的成真賦值成真賦值，若使A的值為假，則稱(chēng)這組值為A的成假賦值成假賦值。例如，給公式(pqr)賦值011是指p=0，q=1，r=1，它是該公式的成真賦值；賦值110是指p=1，q=1，r=0，它是該公式的成假賦值。含n個(gè)命題變項(xiàng)的命題公式，共有2n組賦值。將命題公式A在所有賦值之下取值的情況列成表，稱(chēng)為A的真值表真值表。構(gòu)造真值表的步驟：1. 找出命題公式中所含的所有命題變項(xiàng)p1, p2,，pn ，列出所有可能賦值（ 2n 個(gè)）；2. 按從低到高的順序?qū)懗龈鲗哟危?. 對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的值，直到最后計(jì)算出命題公式的值。pqrrq rp (q r)00011

13、0001000010110011010100111101000110111111011 例7：求下列命題公式的真值表（1） p (q r)；（2）(p(pq)q ；pqpqp(pq) (p(pq)q00101011011000111111（3） (pq)q ；pqpq(pq)(pq)q00100011001001011100 定義定義1.9 設(shè)A為一個(gè)命題公式1.若A在它的各種賦值下取值為真，則稱(chēng)A為重言式或永真式.2.若A在它的各種賦值下取值為假，則稱(chēng)A為矛盾式或永假式.3.若A至少存在一組賦值是成真賦值，則稱(chēng)A為可滿(mǎn)足式.由定義1.9可以看出，任何重言式都是可滿(mǎn)足的。顯然，重言式的真值表的

14、最后一列全為1，矛盾式的真值表的最后一列全為0，可滿(mǎn)足的公式真值表的最后一列至少有一個(gè)1。1.3 等值演算等值演算 定義定義1.10 設(shè)A,B為兩個(gè)命題公式，若等價(jià)式AB是重言式，則稱(chēng)A與B是等值的，記作AB. AB不是命題公式 可通過(guò)判斷A與B的真值表是否相同，來(lái)判斷A與B是否等值。 例8：判斷下列命題公式是否等值（1） (pq)與pq ；（2） (pq)與pq ；pqp qpq(pq)pqpq00110111011010101001101011001000l根據(jù)已知的等值式推演出另外一些等值式的過(guò)程稱(chēng)為等值演算等值演算。定理定理1.1（置換定理）（置換定理） 設(shè)(A) 是含命題公式A的命題

15、公式，(B)是用命題公式B置換了(A)中的A之后得到的命題公式。如果AB，則(A)(B)。l等值演算的用途：（1）驗(yàn)證兩個(gè)公式等值；（2）判別命題公式的類(lèi)型；（3）解決實(shí)際問(wèn)題. 例9：驗(yàn)證下列等值式.（1） p(qr) (pq)r；（2） p(pq)(pq). 例10：判別下列公式的類(lèi)型.（1） q(pq)p)；（2） (pp)(qq)r)；（3） (pq)p. 例11：用等值演算法解決下面問(wèn)題.A、B、C、D四人百米競(jìng)賽.觀眾甲、乙、丙預(yù)測(cè)比賽名次為：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四.比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人預(yù)測(cè)的情況都各對(duì)一半，試問(wèn)實(shí)際名次如何（假設(shè)無(wú)并列情

16、況）？1.4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 一個(gè)n(n1)維卡氏積0,1n到0,1的函數(shù)稱(chēng)為一個(gè)n元真值函數(shù)。設(shè)F是一個(gè)n元真值函數(shù)元真值函數(shù)，則可記為F：0,1n0,1 在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱(chēng)此聯(lián)結(jié)詞為冗余的冗余的聯(lián)結(jié)詞聯(lián)結(jié)詞，否則稱(chēng)為獨(dú)立的聯(lián)結(jié)詞獨(dú)立的聯(lián)結(jié)詞。 若任一真值函數(shù)都可以用僅含某一聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題公式表示，則稱(chēng)該聯(lián)結(jié)詞集為全功全功能集能集。若一個(gè)聯(lián)結(jié)詞的全功能集中不含冗余的聯(lián)結(jié)詞，則稱(chēng)它是極小全功能集極小全功能集。 例12：分別以下列給出的各聯(lián)結(jié)詞集中的聯(lián)結(jié)詞寫(xiě)出命題公式(pq)的等值式. (1),; (2), ;(3); (

17、4). 定義定義1.17 僅含有聯(lián)結(jié)詞,的命題公式A中,將換成,換成,若A中含0或1,就將0換成1,1換成0,所得命題公式稱(chēng)為A的對(duì)偶式,記作A*. 從定義不難看出,A是A*的對(duì)偶式,即對(duì)偶式是相互的.又(A*)*A.1.5 對(duì)偶與范式對(duì)偶與范式定理定理1.2 設(shè)A和A*互為對(duì)偶式,p1,p2,pn是出現(xiàn)在A和A*中的全部的命題變項(xiàng),若將A和A*寫(xiě)成n元函數(shù)形式,則(1) A(p1,p2, ,pn)A*( p1, p2, , pn); (2) A( p1, p2, , pn) A*(p1,p2,.,pn). 例:A(p,q,r) p ( qr) 0 則 A*(p,q,r) p( qr) 1 A

18、(p,q,r) p(q r) 1;A*(p,q,r) p(qr)1; 所以, A(p,q,r) A*( p, q, r).類(lèi)似地,有A(p, q, r) A*(p,q,r) 定理定理1.3(對(duì)偶原理) 設(shè)A,B為兩命題公式,若A B,則A* B*,其中A*,B*分別為A,B的對(duì)偶式. 由對(duì)偶原理可知, 若A為重言式,則A*必為矛盾式. 例如, 設(shè) A p( p(q q), 則 A* p( p(q q) A p( p0) p p 1, A* 0. 已知A B,且B是比A簡(jiǎn)單的命題公式,則由對(duì)偶原理可直接求出較簡(jiǎn)單的B*與A*等值.例如 (pq) ( p(pq) pq,則 (pq)(p( pq)

19、pq.判定問(wèn)題及判定方法判定問(wèn)題及判定方法 方法1: 真值表法; 方法2: 等值演算法. 方法3: 當(dāng)命題變項(xiàng)的數(shù)目較多時(shí), 可把命題公式化成標(biāo)準(zhǔn)型(主析取范式和主合取范式).使同一真值函數(shù)所對(duì)應(yīng)的所有命題公式具有相同的標(biāo)準(zhǔn)型 定義定義1.18.1 僅由有限個(gè)命題變項(xiàng)或其否定構(gòu)成的析取式稱(chēng)為簡(jiǎn)單析取式. 例如 pq、pq、pq、q、p、q 定義定義1.18.2 僅由有限個(gè)命題變項(xiàng)或其否定構(gòu)成的合取式稱(chēng)為簡(jiǎn)單合取式. 例如 pq、pq、pq、p、q、p 從定義不難看出(1)一個(gè)簡(jiǎn)單析取式是重言式,當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題變項(xiàng)及其否定;(2)一個(gè)簡(jiǎn)單合取式是矛盾式,當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題變項(xiàng)及其

20、否定. 定義定義1.19 (1)僅由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱(chēng)為析取范式; (2)僅由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱(chēng)為合取范式. 設(shè)AA1A2An,Ai(i1,2,n)為簡(jiǎn)單合取式,則A是析取范式, 設(shè)AA1A2An,Ai(i1,2,n)為簡(jiǎn)單析取式,則A是合取范式. 任何析取范式的對(duì)偶式為合取范式; 任何合取范式的對(duì)偶式為析取范式.性質(zhì)性質(zhì):(1)一個(gè)析取范式是矛盾式,當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式;(2)一個(gè)合取范式是重言式,當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式. 定理定理1.4(范式存在定理范式存在定理) 任一命題公式都存在著與之等值的析取范式和合取范式. 所用的基本等值式是

21、p q pq; p q ( pq)(p q); p q (p q)(pq); pq (pq); pq (pq).v(1)消去對(duì),來(lái)說(shuō)冗余的聯(lián)結(jié)詞;求范式的具體步驟(3步) 利用雙重否定律和德摩根律,即 p p; (pq) p q; (pq) p q; v(2)否定號(hào)的消去或內(nèi)移; 最后,若是求析取范式,應(yīng)該利用“”對(duì)“”的分配律;若是求合取范式,應(yīng)該利用“”對(duì)“”的分配律. 任給一個(gè)命題公式A,經(jīng)過(guò)以上三步演算,即得到一個(gè)與A等值的析取范式或合取范式. 任何命題公式的析取范式和合取范式都不是唯一的.v(3)利用分配律. 例1.14 求下面命題公式的合取范式和析取范式. (pq) r) p. 解

22、 (1)求合取范式 (pq ) r) p ( (pq)r) p (消去第一個(gè)) (pq)r)p (消去第二個(gè)) (p q)r)p (內(nèi)移) ( p q) r)p (內(nèi)移) (pq) r)p (消去) (pqp)(rp) (對(duì)分配律) 再利用交換律和等冪律得 (pqp)(rp) (pq)(rp), 可見(jiàn),(pq)(rp)也是原公式的合取范式,這說(shuō)明與某個(gè)命題公式等值的合取范式是不唯一的.(2)求析取范式用對(duì)的分配律就可得到析取范式,即 (pq) r) p (pq) r)p (p r)(q r)p (對(duì)分配律) 最后結(jié)果為原公式的析取范式.利用交換律和吸收律得p(q r),也是原公式的析取范式,由

23、此可見(jiàn),與命題公式等值的析取范式也是不唯一的. 定義定義1.20 在含n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中,若每個(gè)命題變項(xiàng)與其否定不同時(shí)存在,而二者之一必出現(xiàn)且僅出現(xiàn)一次,且第i個(gè)命題變項(xiàng)或其否定出現(xiàn)在從左起的第i位上(若命題變項(xiàng)無(wú)角標(biāo),則按字典順序排序),這樣的簡(jiǎn)單合取式稱(chēng)為極小項(xiàng). 3個(gè)命題變項(xiàng)，8個(gè)極小項(xiàng)對(duì)應(yīng)情況如下： pqr 000 0, 記作m0； pqr 001 1, 記作m1； p qr 010 2, 記作m2； p qr 011 3, 記作m3； pqr 100 4, 記作m4； p q r 101 5, 記作m5； p qr 110 6, 記作m6； p qr 111 7, 記作m7.

24、 一般情況下,n個(gè)命題變項(xiàng)共產(chǎn)生2n個(gè)極小項(xiàng),分別記為m0,m1,.m2n-1. 定義定義1.21 設(shè)命題公式A中含n個(gè)命題變項(xiàng),如果A的析取范式中的簡(jiǎn)單合取式全是極小項(xiàng),則稱(chēng)該析取范式為A的主析取范式. 定理定理1.5 任何命題公式的主析取范式都是存在的,并且是唯一的. 求給定命題公式A的主析取范式的步驟(1)求A的析取范式A.(2)若A的某簡(jiǎn)單合取式B中不含命題變項(xiàng)pi或其否定 pi,則將B展成如下形式： B B1 B(pipi) (Bpi)(Bpi).(3)將重復(fù)出現(xiàn)的命題變項(xiàng)、矛盾式及重復(fù)出現(xiàn)的極小項(xiàng)都“消去”,如pp用p代,pp用0代,mimi用mi代.(4)將極小項(xiàng)按由小到大的順序

25、排列,并用表示之.如m1m2m5用(1,2,5)表示. 例1.15 求例1.14中給出的命題公式的主析取范式. (pq) r) p.解解 由例1.14可知, 原公式的析取范式為, p (q r)用p(qq)(rr)取代p.用(pp)(q r)取代(q r).然后展開(kāi)得極小項(xiàng). (pq) r) p p(q r) (析取范式) (p(qq) (rr) (pp)(q r) (pqr)(pqr) (p q r)(p q r) (pqr)(p q r) m4 m5 m6m7m2m6 m2m4m5m6m7 (2,4,5,6,7). 由極小項(xiàng)的定義可知,上式中,2,4,5,6,7的二進(jìn)制表示010,100,

26、101,110,111為原公式的成真賦值,而此公式的主析取范式中沒(méi)出現(xiàn)的極小項(xiàng)m0,m1,m3的角碼0,1,3的二進(jìn)制表示000,001,011為原公式的成假賦值.因而,只要知道了一個(gè)命題公式A的主析取范式,可立即寫(xiě)出A的真值表. 反之,若知道了A的真值表,找出所有的成真賦值,及其對(duì)應(yīng)的十進(jìn)制數(shù)作為角碼的極小項(xiàng)即為A的主析取范式中所含的全部極小項(xiàng),從而可立即寫(xiě)出A的主析取范式. 例例1.16 試由試由pqr的真值表求它的主析取范式的真值表求它的主析取范式.pqrp qp q r0000000101010000110110000101011101111111pqr m1m3m5m6m7 (1,3

27、,5,6,7).主析取范式的用途由于任何命題公式的主析取范式都是唯一的,因而若A B,說(shuō)明A與B有相同的主析取范式.反之,若A,B有相同的主析取范式,必有A B.1.判斷兩命題公式是否等值.2.判斷命題公式的類(lèi)型設(shè)A是含n個(gè)命題變項(xiàng)的命題公式, A為重言式,當(dāng)且僅當(dāng)A的主析取范式中含全部2n個(gè)極小項(xiàng). A為矛盾式,當(dāng)且僅當(dāng)A的主析取范式中不含任何極小項(xiàng),可設(shè)A的主析取范式為0. 若A的主析取范式中至少含一個(gè)極小項(xiàng),則A是可滿(mǎn)足式. 例1.17 判斷下列命題公式的類(lèi)型. (1) (pq)q； (2)(pq)p)q； (3)(pq)q. 解 (1) (pq)q (pq)qpqq 0.(2)(pq)

28、p) q (pq)p)q (pq) pq (pq) pq (pq)p(qq)(pp)q (pq)( pq)(p q)(pq) m0m1m2m3 (0,1,2,3).(3)(pq)q (pq)q(pq)q (pp)(pq)(pq)m1m3. (1,3).由以上推演可知,(1)矛盾式,(2)為重言式,(3)為可滿(mǎn)足式. 3.求命題公式的成真和成假賦值. 在上例(2)中(pq)q (1,3). 01,11是成真賦值,00,10是成假賦值.定義定義1.22 在含n個(gè)命題變項(xiàng)的簡(jiǎn)單析取式中,若每個(gè)命題變項(xiàng)與其否定不同時(shí)存在,而二者之一必出現(xiàn)且僅出現(xiàn)一次,且第i個(gè)命題變項(xiàng)或其否定出現(xiàn)在左起的第i位上(若命

29、題變項(xiàng)無(wú)角碼,則按字典順序排列),這樣的簡(jiǎn)單析取式稱(chēng)為極大項(xiàng). 同極小項(xiàng)情況類(lèi)似,n個(gè)命題變項(xiàng)可產(chǎn)生2n個(gè)極大項(xiàng),每個(gè)極大項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)和一個(gè)十進(jìn)制數(shù).二進(jìn)制數(shù)為該極大項(xiàng)的成假賦值,十進(jìn)制數(shù)作為該極大項(xiàng)抽象表示的角碼.3個(gè)命題變項(xiàng)，8個(gè)極大項(xiàng)對(duì)應(yīng)情況如下：pqr 0000，記作M0pqr 0011，記作M1pqr 0102，記作M2pqr 0113，記作M3pqr 1004，記作M4pqr 1015，記作M5pqr 1106，記作M6pq r 1117，記作M7 定義定義1.23 設(shè)命題公式A中含n個(gè)命題變項(xiàng),如果A的合取范式中的簡(jiǎn)單析取式全是極大項(xiàng),則稱(chēng)該合取范式為主合取范式. 任一命題

30、公式的主合取范式一定存在,且是唯一的. 求一命題公式A的主合取范式的步驟:（1）先求出合取范式A.（2）若A的某簡(jiǎn)單析取式B中不含命題變項(xiàng)pi ,或其否定pi,則將B展成如下形式：BB0B(pi pi)(Bpi)(B pi). 例1.18 求pqr的主合取范式. 解 (pq) r (pr)(qr) (合取范式) (p(q q)r)(p p)qr) (pqr)(p qr) (pqr) ( pqr) (pqr)(p qr)(pqr) M0M2M4 (0,2,4),其中表示合取.mi Mi， Mi mi. 設(shè)命題公式A中含n個(gè)命題變項(xiàng),且設(shè)A的主析取范式中含k個(gè)極小項(xiàng)mil,mi2,mik則 A的主

31、析取范式中必含2n-k個(gè)極小項(xiàng),設(shè)為mjl,mj2, , ,即 A mjl mj2 A A (mjl mj2 ) mjl mj2 Mjl Mj2 22nknkjjMm22nknkjjMm22nknkjjMm22nknkjjMm22nknkjjMm極小項(xiàng)與極大項(xiàng)之間的關(guān)系22nknkjjMm22nknkjjMm由A的主析取范式求主合取范式的步驟(1)求出A的主析取范式中沒(méi)包含的極小項(xiàng)mj1,mj2, . (2)求出與(1)中極小項(xiàng)角碼相同的極大項(xiàng)Mj1,Mj2, . (3)由以上極大項(xiàng)構(gòu)成的合取式為A的主合取范式.例如,A中含3個(gè)命題變項(xiàng),主析取范式為 A m0m1m5m7 (0,1,5,7)則

32、主合取范式為 A M2M3M4M6 (2,3,4,6). 通過(guò)主合取范式也可以判斷公式之間是否等值，判斷公式的類(lèi)型，求成假賦值等.1.6 推理理論 數(shù)理邏輯的主要任務(wù)是用邏輯的方法研究數(shù)學(xué)中的推理。所謂推理推理是指從前提出發(fā)，應(yīng)用推理規(guī)則推出結(jié)論的思維過(guò)程。任何一個(gè)推理都由前提前提和結(jié)論結(jié)論兩部分組成。前提前提就是已知的命題公式，結(jié)論結(jié)論則是從前提應(yīng)用推理規(guī)則推出的命題公式。 定義1.24 若(A1A2Ak)B為重言式，則稱(chēng)A1,A2,Ak推出結(jié)論B的推理正確，B是A1, A2, , Ak的 邏 輯 結(jié) 論邏 輯 結(jié) 論 或 有 效 結(jié) 論有 效 結(jié) 論 . 稱(chēng)(A1A2Ak)B為由前提A1,A2,Ak推出結(jié)論B的推理的形式結(jié)構(gòu). 用“AB”表示“AB”是重言式. 因而，若由前提A1，A2，Ak推出結(jié)論B的推理正確，也記(A1A2Ak)B.由定義1.24可以看出，要證明B是一組前提A1，A2，Ak 的有效結(jié)論，只需證明A1A2AkB為重言式。證明一個(gè)公式為重言式，可以用真值表、等價(jià)演算、主析(合)取范式等方法進(jìn)行。 例例1.19 判斷下面各推理是否正確.（1）如果天氣涼快，小王就不去游泳. 天氣涼快.所以小王沒(méi)去游泳.（2）如果我上街，我一定去新華書(shū)店. 我