math-chap1-1.離散數(shù)學(xué)_命題邏輯

1、莊伯金莊伯金 1 1第一章第一章命題邏輯命題邏輯課件下載地址：課件下載地址：http:/ 2 2主要內(nèi)容n命題的基本概念命題的基本概念n等值演算等值演算n范式范式n推理理論推理理論莊伯金莊伯金 3 3命題的基本概念n命題的定義命題的定義n能判斷真假的陳述句能判斷真假的陳述句n命題的兩個(gè)關(guān)鍵要素命題的兩個(gè)關(guān)鍵要素n必須是必須是陳述句陳述句n能明確地能明確地判斷真假判斷真假n命題的真值命題的真值n判斷為判斷為正確正確的命題，其真值為的命題，其真值為真（真（1）；n判斷為判斷為錯(cuò)誤錯(cuò)誤的命題，其真值為的命題，其真值為假（假（0）。莊伯金莊伯金 4 4命題的例n4是素?cái)?shù)。是素?cái)?shù)。nx大于大于y。n充分

2、大的偶數(shù)等于兩個(gè)素?cái)?shù)之和。充分大的偶數(shù)等于兩個(gè)素?cái)?shù)之和。(歌德巴赫猜想歌德巴赫猜想)n2020年年5月月1日北京的天氣是雨天。日北京的天氣是雨天。n請(qǐng)不要吸煙！請(qǐng)不要吸煙！n這朵花真美麗啊！這朵花真美麗??！n我正在說(shuō)假話(huà)。我正在說(shuō)假話(huà)。n你現(xiàn)在好嗎？你現(xiàn)在好嗎？莊伯金莊伯金 5 5命題符號(hào)化n命題常用小寫(xiě)字母表示，如命題常用小寫(xiě)字母表示，如p：4是素?cái)?shù)是素?cái)?shù)n命題的真值表示：命題的真值表示：n1表示真表示真n0表示假表示假n簡(jiǎn)單命題簡(jiǎn)單命題n不能被分解為更簡(jiǎn)單的陳述句的命題不能被分解為更簡(jiǎn)單的陳述句的命題n也稱(chēng)為原子命題也稱(chēng)為原子命題n命題常項(xiàng)與命題變項(xiàng)命題常項(xiàng)與命題變項(xiàng)n命題常項(xiàng)：真值可以確

3、定；命題常項(xiàng)：真值可以確定；n命題變項(xiàng)：真值可以變化。命題變項(xiàng)：真值可以變化。本質(zhì)不是命題本質(zhì)不是命題。莊伯金莊伯金 6 6復(fù)合命題及聯(lián)結(jié)n復(fù)合命題：由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。復(fù)合命題：由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。n常見(jiàn)聯(lián)結(jié)詞常見(jiàn)聯(lián)結(jié)詞n否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞n合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞n析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞n蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞n等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞莊伯金莊伯金 7 7n例例nP：今天是星期二。今天是星期二。np：今天不是星期二。今天不是星期二。nq：所有人都來(lái)上課了。所有人都來(lái)上課了。nq：不是所有人來(lái)上課了。不是所有人來(lái)上課了。有人沒(méi)來(lái)上課。有人沒(méi)來(lái)上課。否定式n定義：復(fù)合命題

4、定義：復(fù)合命題“非非p”稱(chēng)為稱(chēng)為p的否定式，記的否定式，記作作p。為否定聯(lián)結(jié)詞。為否定聯(lián)結(jié)詞。np為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p為假。即為假。即p表示對(duì)表示對(duì)p的真值取的真值取反。反。pp1001莊伯金莊伯金 8 8n例例n小李小李既既勤奮勤奮又又聰明。聰明。n小李小李不僅不僅勤奮勤奮而且而且聰明。聰明。n小李小李雖然雖然聰明，聰明，但是但是不勤奮。不勤奮。n小李小李和和小王都很勤奮。小王都很勤奮。n小李小李和和小王是同學(xué)。小王是同學(xué)。n注注：并不是所有的：并不是所有的“和和”、“與與”都表示合取關(guān)系。都表示合取關(guān)系。合取式n定義：復(fù)合命題定義：復(fù)合命題“p并且并且q”稱(chēng)為稱(chēng)為p與與q的合取式，記

5、作的合取式，記作pq。 為合取聯(lián)結(jié)詞。為合取聯(lián)結(jié)詞。npq為真當(dāng)前僅當(dāng)為真當(dāng)前僅當(dāng)p與與q同時(shí)為真。其他情況時(shí)同時(shí)為真。其他情況時(shí)pq為假。為假。pqpq111100010000莊伯金莊伯金 9 9n例例n小李?lèi)?ài)唱歌小李?lèi)?ài)唱歌或者或者愛(ài)打籃球。愛(ài)打籃球。n小李在打籃球小李在打籃球或者或者在踢足球。在踢足球。n小李可以坐火車(chē)小李可以坐火車(chē)或者或者乘飛機(jī)回家。乘飛機(jī)回家。析取式n定義：復(fù)合命題定義：復(fù)合命題“p或者或者q”稱(chēng)為稱(chēng)為p與與q的析取式，記作的析取式，記作pq。為析取聯(lián)結(jié)詞。為析取聯(lián)結(jié)詞。npq為假當(dāng)且僅當(dāng)為假當(dāng)且僅當(dāng)p與與q同時(shí)為假。其他情況同時(shí)為假。其他情況pq為真。為真。pqpq1

6、11101011000莊伯金莊伯金 1010析取式n自然語(yǔ)言中的自然語(yǔ)言中的“或或”具有具有二義性二義性，與析取式中的，與析取式中的“或或”含義不含義不完全相同。完全相同。n析取式可表示析取式可表示“相容或相容或”和和“不同時(shí)為真排斥或不同時(shí)為真排斥或”；n“能同時(shí)為真的排斥或能同時(shí)為真的排斥或”可用可用“異或異或”關(guān)系表示。關(guān)系表示。莊伯金莊伯金 1111蘊(yùn)涵式n定義：復(fù)合命題定義：復(fù)合命題“如果如果p，則則q”稱(chēng)為稱(chēng)為p與與q的蘊(yùn)涵式，的蘊(yùn)涵式，記作記作pq。 npq為假當(dāng)前僅當(dāng)為假當(dāng)前僅當(dāng)p為真且為真且q為假。其他情況時(shí)，為假。其他情況時(shí)， pq為真。為真。pqpq11110001100

7、1n自然語(yǔ)言中自然語(yǔ)言中p與與q具有聯(lián)系，而具有聯(lián)系，而數(shù)理邏輯中數(shù)理邏輯中p與與q可以沒(méi)有聯(lián)系?？梢詻](méi)有聯(lián)系。n例例n如果如果336，則雪是黑的。，則雪是黑的。n如果如果3+3 6，則雪是黑的。，則雪是黑的。莊伯金莊伯金 1212蘊(yùn)涵式npq在邏輯上表明在邏輯上表明p為為q的充分條件，的充分條件，q為為p的必要條的必要條件。件。n例例n只要只要a能被能被4整除，整除，則則a一定能被一定能被2整除。整除。na能被能被4整除，整除，僅當(dāng)僅當(dāng)a能被能被2整除。整除。n除非除非a能被能被2整除，整除，a才能才能被被4整除。整除。n只有只有a能被能被2整除，整除，a才能才能被被4整除。整除。n只有只有

8、a能被能被4整除，整除，a才能才能被被2整除。整除。莊伯金莊伯金 1313等價(jià)式n定義：復(fù)合命題定義：復(fù)合命題“p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”稱(chēng)為稱(chēng)為p與與q的等價(jià)式，的等價(jià)式，記作記作pq。稱(chēng)作等價(jià)聯(lián)結(jié)詞。稱(chēng)作等價(jià)聯(lián)結(jié)詞。npq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q真值相同。其他情況時(shí)，真值相同。其他情況時(shí)，pq為為假。假。pqpq111100010001npq在邏輯上表明在邏輯上表明p與與q互為充要互為充要條件。條件。n例：例：n若今天為若今天為1號(hào)，則明天是號(hào)，則明天是2號(hào)，反之號(hào)，反之亦然。亦然。n今天是雨天當(dāng)且僅當(dāng)雪是黑的。今天是雨天當(dāng)且僅當(dāng)雪是黑的。莊伯金莊伯金 1414基本復(fù)合命題真值表pqp

9、pqpqpqpq0010011011011010001001101111莊伯金莊伯金 1515聯(lián)結(jié)詞的優(yōu)先順序n()nnnnn莊伯金莊伯金 1616練習(xí)n判斷下列命題的真值判斷下列命題的真值n若若224，則，則336n若若224，則，則336n若若224，則，則336n若若224，則，則336n224當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)336n224當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)336n224當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)336n224當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)336莊伯金莊伯金 1717練習(xí)n將下列命題符號(hào)化將下列命題符號(hào)化n2是偶數(shù)又是素?cái)?shù)是偶數(shù)又是素?cái)?shù)n他一邊吃飯一邊看電視他一邊吃飯一邊看電視n如果天下雨，他就乘公共汽車(chē)上班如果天下雨，他就乘公

10、共汽車(chē)上班n只有天下雨，他才乘公共汽車(chē)上班只有天下雨，他才乘公共汽車(chē)上班n不經(jīng)一事，不長(zhǎng)一智不經(jīng)一事，不長(zhǎng)一智莊伯金莊伯金 1818練習(xí)n設(shè)設(shè)p、q的真值為的真值為0，r、s的真值為的真值為1，求下列命題公，求下列命題公式的真值式的真值np(qr)n(pr)(qs)莊伯金莊伯金 1919命題公式n命題常項(xiàng)（命題常元）：簡(jiǎn)單命題，真值唯一確定。命題常項(xiàng)（命題常元）：簡(jiǎn)單命題，真值唯一確定。n命題變項(xiàng)（命題變?cè)赫嬷悼梢宰兓年愂鼍?。命題變項(xiàng)（命題變?cè)赫嬷悼梢宰兓年愂鼍?。n命題常項(xiàng)和命題變?cè)加眯?xiě)字母表示。命題常項(xiàng)和命題變?cè)加眯?xiě)字母表示。n合式公式（命題公式）合式公式（命題公式）：將

11、命題變項(xiàng)用聯(lián)結(jié)詞和圓括：將命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串。號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串。莊伯金莊伯金 2020合式公式的定義n遞歸定義遞歸定義n1. 單個(gè)命題變項(xiàng)是合式公式，并稱(chēng)為原子命題公式；單個(gè)命題變項(xiàng)是合式公式，并稱(chēng)為原子命題公式；n2. 若若A是合式公式，則是合式公式，則(A)也是合式公式；也是合式公式；n3. 若若A，B是合式公式，則是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式；也是合式公式；n4. 只有只有有限次有限次地應(yīng)用地應(yīng)用13形式的符號(hào)串才是合式公式。形式的符號(hào)串才是合式公式。n子公式定義子公式定義n若若A為合式公式，為合

12、式公式，B為為A的一部分，且的一部分，且B也是合式公式，則稱(chēng)也是合式公式，則稱(chēng)B為為A的子公式。的子公式。莊伯金莊伯金 2121公式的賦值n定義定義n設(shè)設(shè)A為一命題公式，為一命題公式，p1, p2, , pn, 為所有在為所有在A中出現(xiàn)的命中出現(xiàn)的命題變項(xiàng)。給題變項(xiàng)。給p1, p2, , pn指定一組真值，稱(chēng)其為指定一組真值，稱(chēng)其為A的一個(gè)的一個(gè)賦賦值值或或解釋解釋。n若指定的一組賦值使若指定的一組賦值使A的真值為的真值為真真，則稱(chēng)這組值為，則稱(chēng)這組值為A的的成真成真賦值賦值。n若指定的一組賦值使若指定的一組賦值使A的真值為的真值為假假，則稱(chēng)這組值為，則稱(chēng)這組值為A的的成假成假賦值賦值。n將一

13、個(gè)命題公式在所有賦值下的情況列成表，稱(chēng)為這個(gè)公將一個(gè)命題公式在所有賦值下的情況列成表，稱(chēng)為這個(gè)公式的式的真值表真值表。nn個(gè)命題變項(xiàng)共有個(gè)命題變項(xiàng)共有2n組賦值。組賦值。莊伯金莊伯金 2222例np(qr)的真值表的真值表pqrqrp(qr)0000000100010000111110001101011100111111莊伯金莊伯金 2323例np(pq)的真值表的真值表pqppqp(pq)00111011111000111011莊伯金莊伯金 2424例np(pq)的真值表的真值表pqppqp(pq)00100011101000011000莊伯金莊伯金 2525n重言式（永真式）重言式（永真式

14、）：n所有的賦值都是所有的賦值都是A的成真賦值。的成真賦值。n矛盾式（永假式）矛盾式（永假式）：n所有的賦值都是所有的賦值都是A的成假賦值。的成假賦值。n可滿(mǎn)足式可滿(mǎn)足式：n至少存在一組賦值使至少存在一組賦值使A為真。為真。莊伯金莊伯金 2626等值演算n等值式（等價(jià)式）等值式（等價(jià)式）n設(shè)設(shè)A，B為兩命題公式，若為兩命題公式，若AB為為重言式重言式，則稱(chēng)，則稱(chēng)A與與B為為等等值式值式，記為，記為AB。n不是邏輯聯(lián)結(jié)詞，表示對(duì)任意的賦值，不是邏輯聯(lián)結(jié)詞，表示對(duì)任意的賦值，A與與B的值相同。的值相同。n是等價(jià)聯(lián)結(jié)詞，它與是等價(jià)聯(lián)結(jié)詞，它與不能混為一談。不能混為一談。n等值式的性質(zhì)（等價(jià)關(guān)系的通性

15、）等值式的性質(zhì)（等價(jià)關(guān)系的通性）n自反性：自反性：AA；n對(duì)稱(chēng)性：若對(duì)稱(chēng)性：若AB，則則BA；n傳遞性：若傳遞性：若AB和和BC，則則AC。莊伯金莊伯金 2727例npq與與pq是否等值？是否等值？莊伯金莊伯金 2828基本等值規(guī)律(1)n雙重否定律雙重否定律nAAn等冪律等冪律nAAAnAAAn交換律交換律nABBAnABBAn結(jié)合律結(jié)合律nA(BC)(AB)CnA(BC)(AB)C莊伯金莊伯金 2929基本等值規(guī)律(2)n分配律分配律nA(BC)(AB)(AC)nA(BC)(AB)(AC)n德德.摩根律摩根律n(AB)ABn(AB)ABn吸收律吸收律nA(AB)AnA(AB)A莊伯金莊伯金

16、 3030基本等值規(guī)律(3)n零律零律nA11nA00n同一律同一律nA0AnA1An排中律排中律nAA1n矛盾律矛盾律nAA0莊伯金莊伯金 3131基本等值規(guī)律(4)n蘊(yùn)涵等值式蘊(yùn)涵等值式nABABn等價(jià)等值式等價(jià)等值式nAB(AB)(BA) (AB)(BA)n假言易位假言易位nABBAn等價(jià)否定等值式等價(jià)否定等值式nABABn歸謬論歸謬論n(AB)(AB)A莊伯金莊伯金 3232置換規(guī)則n設(shè)設(shè)(A)為含公式為含公式A的命題公式，的命題公式，(B)為用公式為用公式B置置換了換了A的命題公式，若的命題公式，若AB，則則(A)(B)。n利用等值規(guī)律及置換規(guī)則可以進(jìn)行利用等值規(guī)律及置換規(guī)則可以進(jìn)行

17、等值演算等值演算。n例例n(pq)(qp)n(qp)pn(pq)(qp)n(pq) rn(p(pq)r莊伯金莊伯金 3333聯(lián)結(jié)詞的完備集n問(wèn)題：含問(wèn)題：含n個(gè)命題變項(xiàng)的命題公式其真值表的可能性個(gè)命題變項(xiàng)的命題公式其真值表的可能性有多少種？有多少種？nn元真值函數(shù)元真值函數(shù)：F：0,1n0,1為為n元真值函數(shù)。元真值函數(shù)。n聯(lián)結(jié)詞完備集：設(shè)聯(lián)結(jié)詞完備集：設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何是一個(gè)聯(lián)結(jié)詞集合，如果任何n元真值函數(shù)都可以由僅含元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱(chēng)示，則稱(chēng)S是聯(lián)結(jié)詞完備集。是聯(lián)結(jié)詞完備集。n, , n, n, n, 莊伯金莊伯金 34

18、34對(duì)偶n對(duì)偶的定義：在僅含有對(duì)偶的定義：在僅含有, , 的命題公式的命題公式A中，將中，將換成換成， 換成換成，若若A中含中含0或或1，將，將0換成換成1，1換成換成0，所得的命題公式稱(chēng)為，所得的命題公式稱(chēng)為A的對(duì)偶式，記為的對(duì)偶式，記為A*。n定理：設(shè)定理：設(shè)A和和A*互為對(duì)偶式，互為對(duì)偶式， p1, p2, , pn是出現(xiàn)是出現(xiàn)在在A和和A*中的全部命題變項(xiàng)，若將中的全部命題變項(xiàng)，若將A和和A*寫(xiě)成寫(xiě)成n元函元函數(shù)形式，則：數(shù)形式，則：(1)A(p1, p2, , pn)A*(p1,p2, ,pn)(2) A(p1,p2, ,pn)A*(p1, p2, , pn)n對(duì)偶原理：設(shè)對(duì)偶原理：

19、設(shè)A、B為兩命題公式，若為兩命題公式，若AB，則則A*B*。莊伯金莊伯金 3535范式的概念n命題公式的規(guī)范表示方法命題公式的規(guī)范表示方法n析取范式析取范式n合取范式合取范式n文字：命題變項(xiàng)及其否定式統(tǒng)稱(chēng)文字文字：命題變項(xiàng)及其否定式統(tǒng)稱(chēng)文字n簡(jiǎn)單析取式簡(jiǎn)單析取式n僅有有限個(gè)文字構(gòu)成的析取式僅有有限個(gè)文字構(gòu)成的析取式n簡(jiǎn)單合取式簡(jiǎn)單合取式n僅有有限個(gè)文字構(gòu)成的合取式僅有有限個(gè)文字構(gòu)成的合取式n定理：定理：n一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及其否定式一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及其否定式n一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及其否定式一個(gè)簡(jiǎn)單合

20、取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及其否定式莊伯金莊伯金 3636析取范式n定義定義n由有限個(gè)由有限個(gè)簡(jiǎn)單合取式簡(jiǎn)單合取式構(gòu)成的構(gòu)成的析取式析取式n例例npqn(pq)rn析取范式性質(zhì)析取范式性質(zhì)n析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式是矛盾式析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式是矛盾式莊伯金莊伯金 3737合取范式n定義定義:n由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式n例例npqn(pq)rn合取范式性質(zhì)合取范式性質(zhì)n合取范式是重言式，當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式是重言合取范式是重言式，當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式是重言式式莊伯金莊伯金 3838范式存在定理n

21、定理：定理：任一命題公式都存在與之等值的析取范式（合任一命題公式都存在與之等值的析取范式（合取范式）。取范式）。n求范式的步驟求范式的步驟n利用蘊(yùn)涵等值式和等價(jià)等值式消去聯(lián)結(jié)詞利用蘊(yùn)涵等值式和等價(jià)等值式消去聯(lián)結(jié)詞 、。n用雙重否定律消去否定聯(lián)結(jié)詞，利用德用雙重否定律消去否定聯(lián)結(jié)詞，利用德.摩根律將否定聯(lián)結(jié)摩根律將否定聯(lián)結(jié)詞內(nèi)移。詞內(nèi)移。n利用分配律求析取范式或合取范式。利用分配律求析取范式或合取范式。n例：例：n(pq)r范式的求解n例：例：n(pq)r莊伯金莊伯金 3939莊伯金莊伯金 4040極小項(xiàng)與極大項(xiàng)n極小項(xiàng)的定義極小項(xiàng)的定義n在含在含n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中，如果每個(gè)變項(xiàng)與其否定

22、個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中，如果每個(gè)變項(xiàng)與其否定式不同時(shí)存在，但兩者之一恰出現(xiàn)式不同時(shí)存在，但兩者之一恰出現(xiàn)1次，且第次，且第i個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)或否定式出現(xiàn)在從左起的第或否定式出現(xiàn)在從左起的第i位上。位上。n極大項(xiàng)的定義極大項(xiàng)的定義n在含在含n個(gè)命題變項(xiàng)的簡(jiǎn)單析取式中，如果每個(gè)變項(xiàng)與其否定個(gè)命題變項(xiàng)的簡(jiǎn)單析取式中，如果每個(gè)變項(xiàng)與其否定式不同時(shí)存在，但兩者之一恰出現(xiàn)式不同時(shí)存在，但兩者之一恰出現(xiàn)1次，且第次，且第i個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)或否定式出現(xiàn)在從左起的第或否定式出現(xiàn)在從左起的第i位上。位上。nn個(gè)命題變項(xiàng)共可形成個(gè)命題變項(xiàng)共可形成2n個(gè)極小項(xiàng)和個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)。個(gè)極大項(xiàng)。莊伯金莊伯金

23、 4141極小項(xiàng)的成真賦值n每個(gè)極小項(xiàng)僅有一個(gè)成真賦值每個(gè)極小項(xiàng)僅有一個(gè)成真賦值n每個(gè)極小項(xiàng)的成真賦值均不相同每個(gè)極小項(xiàng)的成真賦值均不相同n可以利用不同的成真賦值區(qū)別每個(gè)極小項(xiàng)，給予標(biāo)記可以利用不同的成真賦值區(qū)別每個(gè)極小項(xiàng)，給予標(biāo)記二元極小項(xiàng)二元極小項(xiàng)取值取值成真賦值成真賦值簡(jiǎn)記名稱(chēng)簡(jiǎn)記名稱(chēng)pq100m0pq101m1pq110m2pq111m3莊伯金莊伯金 4242極大項(xiàng)的成假賦值n每個(gè)極大項(xiàng)僅有一個(gè)成假賦值每個(gè)極大項(xiàng)僅有一個(gè)成假賦值n每個(gè)極大項(xiàng)的成假賦值均不相同每個(gè)極大項(xiàng)的成假賦值均不相同n可以利用不同的成假賦值區(qū)別每個(gè)極大項(xiàng)，給予標(biāo)記可以利用不同的成假賦值區(qū)別每個(gè)極大項(xiàng)，給予標(biāo)記二元極大

24、項(xiàng)二元極大項(xiàng)取值取值成假賦值成假賦值簡(jiǎn)記名稱(chēng)簡(jiǎn)記名稱(chēng)pq000M0pq001M1pq010M2pq011M3莊伯金莊伯金 4343主析取范式與主合取范式n主析取范式的定義主析取范式的定義n若若A的命題公式由若干個(gè)極小項(xiàng)進(jìn)行析取構(gòu)成，則稱(chēng)該析取的命題公式由若干個(gè)極小項(xiàng)進(jìn)行析取構(gòu)成，則稱(chēng)該析取范式為范式為A的主析取范式的主析取范式n從主析取范式中很容易得到成真賦值從主析取范式中很容易得到成真賦值n主合取范式的定義主合取范式的定義n若若A的命題公式由若干個(gè)極大項(xiàng)進(jìn)行合取構(gòu)成，則稱(chēng)該合取的命題公式由若干個(gè)極大項(xiàng)進(jìn)行合取構(gòu)成，則稱(chēng)該合取范式為范式為A的主合取范式的主合取范式n從主合取范式中很容易得到成假

25、賦值從主合取范式中很容易得到成假賦值n定理：任何命題公式都存在與之等值的定理：任何命題公式都存在與之等值的主析?。ê先。┲魑鋈。ê先。┓妒椒妒?，且，且唯一唯一。莊伯金莊伯金 4444主析取范式的求解方法(1)n用等值演算求得析取范式用等值演算求得析取范式n依次掃描析取范式中的每個(gè)簡(jiǎn)單合取式依次掃描析取范式中的每個(gè)簡(jiǎn)單合取式Bn若若B為極小項(xiàng)，則繼續(xù)掃描下一個(gè)為極小項(xiàng)，則繼續(xù)掃描下一個(gè)n若若B不為極小項(xiàng)，將不含的命題變項(xiàng)不為極小項(xiàng)，將不含的命題變項(xiàng)p及其否定式及其否定式p用等值用等值變換添入變換添入BB(pp) (Bp)(Bp) n消去重復(fù)出現(xiàn)的命題變項(xiàng)、極小項(xiàng)和矛盾式。消去重復(fù)出現(xiàn)的命題變項(xiàng)、

26、極小項(xiàng)和矛盾式。莊伯金莊伯金 4545主析取范式的求解方法(2)n根據(jù)公式構(gòu)造真值表根據(jù)公式構(gòu)造真值表n寫(xiě)出每個(gè)公式成真賦值對(duì)應(yīng)的極小項(xiàng)寫(xiě)出每個(gè)公式成真賦值對(duì)應(yīng)的極小項(xiàng)n將極小項(xiàng)進(jìn)行析取，即得主析取范式將極小項(xiàng)進(jìn)行析取，即得主析取范式莊伯金莊伯金 4646主析取范式n例：求例：求(p(qr)(p(qr)莊伯金莊伯金 4747主合取范式的求解方法(1)n用等值演算求得合取范式用等值演算求得合取范式n依次掃描合取范式中的每個(gè)簡(jiǎn)單析取式依次掃描合取范式中的每個(gè)簡(jiǎn)單析取式Bn若若B為極大項(xiàng)，則繼續(xù)掃描下一個(gè)為極大項(xiàng)，則繼續(xù)掃描下一個(gè)n若若B不為極大項(xiàng)，將不含的命題變項(xiàng)不為極大項(xiàng)，將不含的命題變項(xiàng)p及其

27、否定式及其否定式p用等值用等值變換添入變換添入BB (pp) (Bp)(Bp) n消去重復(fù)出現(xiàn)的命題變項(xiàng)、極大項(xiàng)和重言式。消去重復(fù)出現(xiàn)的命題變項(xiàng)、極大項(xiàng)和重言式。莊伯金莊伯金 4848主合取范式的求解方法(2)n根據(jù)公式構(gòu)造真值表根據(jù)公式構(gòu)造真值表n寫(xiě)出每個(gè)公式成假賦值對(duì)應(yīng)的極大項(xiàng)寫(xiě)出每個(gè)公式成假賦值對(duì)應(yīng)的極大項(xiàng)n將極大項(xiàng)進(jìn)行合取，即得主合取范式將極大項(xiàng)進(jìn)行合取，即得主合取范式莊伯金莊伯金 4949主合取范式n例：求例：求(p(qr)(p(qr)莊伯金莊伯金 5050主析取范式與主合取范式n主析取范式與主合取范式之間的關(guān)系？主析取范式與主合取范式之間的關(guān)系？莊伯金莊伯金 5151推理的形式結(jié)構(gòu)

28、n設(shè)兩命題公式設(shè)兩命題公式A、B，若若AB為為重言式，重言式，則稱(chēng)則稱(chēng)A蘊(yùn)涵蘊(yùn)涵B，記為記為AB。n設(shè)設(shè)A1、A2、.、An、B為命題公式，若為命題公式，若A1A2. An B，則稱(chēng)則稱(chēng)B為為A1、A2、.、An的的邏輯結(jié)論邏輯結(jié)論或或有有效結(jié)論效結(jié)論，也稱(chēng)，也稱(chēng)B可由一組前提可由一組前提A1、A2、.、An邏輯推邏輯推出。記為出。記為A1，A2，.，AnB。n正確推理的本質(zhì)是正確推理的本質(zhì)是A1A2. AnB為重言式。為重言式。n當(dāng)當(dāng)A1A2. An為假時(shí)，不論為假時(shí)，不論B是真是假，是真是假， A1A2. AnB均為真。所以均為真。所以B為有效結(jié)論并不為有效結(jié)論并不意味意味B為真。為真。莊伯金莊伯金 5252推理的基本方法n簡(jiǎn)單證明法：簡(jiǎn)單證明法： 證明證明A1A2. AnB是重言式，是重言式，即即A1A2. AnB1。n真值表法真值表法n等值演算法等值演算法n主析取范式法主析取范式法n例：若例：若a能被能被4整除，則整除，則a能被能被2整除。因?yàn)檎?。因?yàn)閍能被能被2整整除，所以除，所以a能被能被4整除。整除。莊伯金莊伯金 5353推理的基本方法(2)n直接構(gòu)造證明法直接構(gòu)造證明法n由給定的一組前提出發(fā)，利用推理規(guī)則逐步演算得到結(jié)論。由給定的一組前提出發(fā)，利用推理規(guī)則逐步演算得到結(jié)論。n常用推理規(guī)則常用推理規(guī)則n前提引入規(guī)則：在證明過(guò)程的任何步驟