主析取范式的求法.ppt

,第一章 命題邏輯,第七講,定義 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式 僅由小項(xiàng)的析取所組成，則該等價(jià)式稱(chēng)為原式的主析 取范式。,內(nèi)容回顧,小項(xiàng) 定義 n個(gè)命題變?cè)暮先∈?，稱(chēng)為布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。,每個(gè)小項(xiàng)可用n位二進(jìn)制編碼表示。以變?cè)陨沓霈F(xiàn)的用1 表示，以其否定出現(xiàn)的用0表示： 小項(xiàng)的性質(zhì)如下： （1）每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為1，其余的2n1種均為0; （2）任意兩個(gè)不同小項(xiàng)的合取式永假： （3）全體小項(xiàng)的析取式永為真，記為：,主析取范式的求法,真值表法 等值演算法,趣味推理題,A、B、C三人去餐館吃飯，他們每人要的不是火腿就是豬排。 （1）如果A要的是火腿，那么B要的就是豬排。 （2）A或C要的是火腿，但是不會(huì)兩人都要火腿。 （3）B和C不會(huì)兩人都要豬排。 誰(shuí)昨天要的是火腿，今天要的是豬排？,只有B才能昨天要火腿，今天要豬排。,154 主合取范式,定義1- n個(gè)命題變?cè)奈鋈∈?，稱(chēng)為布爾析取或極大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。,例如，2個(gè)命題變?cè)猵和Q 的大項(xiàng)為： 3個(gè)命題變?cè)猵、Q、R的大項(xiàng)為： n個(gè)命題變?cè)灿?n個(gè)大項(xiàng)，每個(gè)大項(xiàng)可表示為n位二進(jìn)制編碼，以變?cè)陨沓霈F(xiàn)的用0表示，以變?cè)姆穸ǔ霈F(xiàn)的用1表示；且對(duì)應(yīng)十進(jìn)制編碼。這一點(diǎn)與小項(xiàng)的表示剛好相反。 若n= 2，則有,若n= 3，則有: 大項(xiàng)的性質(zhì)如下： (1)每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為0，其余的2n1種賦值均為1; (2)任意兩個(gè)不同大項(xiàng)的析取式永真： (3)全體大項(xiàng)的合取式必為假，記為：,定義1- 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式僅由極大項(xiàng)的合取所組成，則該等價(jià)式稱(chēng)為原式的主合取范式。 定理1- （主合取范式存在惟一定理） 任何命題公式的主合取范式一定存在，并且惟一。 由真值表方法可知：一個(gè)公式的真值為0的真值指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。 例1- 用真值表方法求 的主合取范式 解: 公式的真值表如下,所以公式 的主合取范式為: 用等值演算方法構(gòu)成主合取范式的主要步驟如下： （1）將原命題公式化歸為合取范式； （2）除去合取范式中所有永真的合取項(xiàng)； （3）合并相同的析取項(xiàng)和相同的變?cè)?（4）對(duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添加?pp) 的式子，再按分配律進(jìn)行演算； （5）將大項(xiàng)按下標(biāo)由小到大的順序排列。,例1- 用等值演算方法求 的主合取范式。 解：,【說(shuō)明】 (1)主析取范式的析取項(xiàng)為小項(xiàng)，用小m加下標(biāo)表示。如m010，其中0表示對(duì)應(yīng)的命題變?cè)姆穸ǔ霈F(xiàn)在析取項(xiàng)中,1表示對(duì)應(yīng)的命題變?cè)霈F(xiàn)在析取項(xiàng)中。 (2)主合取范式的合取項(xiàng)為大項(xiàng),用大M加下標(biāo)表示,如M010,其中0表示對(duì)應(yīng)的命題變?cè)霈F(xiàn)在合取項(xiàng)中,1表示對(duì)應(yīng)命題變?cè)姆穸ǔ霈F(xiàn)在合取項(xiàng)中。 (3)在真值表中,一個(gè)公式的主析取范式由其真值為1的真值指派所在對(duì)應(yīng)的小項(xiàng)的析取組成。 (4)在真值表中,一個(gè)公式的主合取范式由其真值為0的真值指派所對(duì)應(yīng)的大項(xiàng)的合取所組成。,極小項(xiàng)與極大項(xiàng),由p, q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),由p, q, r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),1.6 蘊(yùn)含公式,如果雙條件命題AB 為重言式，則A B 。而條件命題AB 是不對(duì)稱(chēng)的，如果AB為真，B不一定能推出A 。那么A和B究竟存在什么關(guān)系呢？ 161 蘊(yùn)含公式 定義1-26 設(shè)A，B是命題公式, 若AB是重言式, 則稱(chēng)AB是蘊(yùn)含重言式，記為AB ，讀作“A永真蘊(yùn)含B”。簡(jiǎn)稱(chēng)A蘊(yùn)含B 即 AB iff AB 1 注意: 與 是意義不同的符號(hào)。,證明：,所以P(pQ)Q,下面介紹幾種證明A永真蘊(yùn)含B的方法。 方法一：用真值表法或等價(jià)變換(推導(dǎo))法證明AB 1 。 例1-24 證明 。,方法二：通過(guò)分析的方法來(lái)證明一個(gè)條件命題是蘊(yùn)含式。由于原命題等于其逆反命題，即 ABBA ，所以用分析法證明AB ， 有如下兩種方法: (1) 假設(shè)前件A為真時(shí), 推出后件B也為真, 則AB ; (2) 假設(shè)后件B為假時(shí), 推出前件A也為假, 則AB 。,例1-25 證法1：,證法2：,例1-26 如果我認(rèn)真學(xué)習(xí)，我的“離散數(shù)學(xué)”不會(huì)不及格， 如果我不熱衷于玩電子游戲，我將認(rèn)真學(xué)習(xí)， 但我的“離散數(shù)學(xué)”不及格。 結(jié)論：我熱衷于玩電子游戲。,證明： 設(shè)P：我認(rèn)真學(xué)習(xí)。 Q：我的“離散數(shù)學(xué)”及格。 R：我熱衷于玩電子游戲。,常見(jiàn)的蘊(yùn)含重言式,析取三段論 假言推論 拒取式 假言三段論 二難推論,化簡(jiǎn)式一 附加式 化簡(jiǎn)式二,例1-27 分析證明 。 證明：假設(shè)后件 為0，則P為1，R 為 0。 (a)若Q為1，則 為0，所以 為0； (b)若Q為0，則 為0，所以 為0。 故此： 成立。,162 蘊(yùn)含公式的性質(zhì) （1）設(shè)A、B是命題公式，若AB 且A為重言式，則B必是重言式。 證明: 因?yàn)锳B ，所以 AB 為1，又因?yàn)锳為1，所以B為1，即B為重言式。 （2）蘊(yùn)含關(guān)系是傳遞的，即AB 且BC ， 則AC 。,1.8 推理理論,邏輯學(xué)的主要任務(wù)是提出一套推理規(guī)則，按照公認(rèn)的推理規(guī)則從前提集合中推導(dǎo)出一個(gè)結(jié)論來(lái)，這個(gè)推理過(guò)程稱(chēng)為演繹或形式證明。 在一般的論證中，主要是根據(jù)實(shí)踐經(jīng)驗(yàn)。如果確認(rèn)前提為真，并遵守恰當(dāng)?shù)耐评硪?guī)則，則可期望所得的結(jié)論也是真的。倘若認(rèn)定前提是真的，從前提推導(dǎo)出結(jié)論的論證是遵守邏輯推理規(guī)則，且公認(rèn)此結(jié)論是真實(shí)的，則這個(gè)論證稱(chēng)為合法論證。一般論證中必須特別注意論證的合法性。 所謂合法是指前提和結(jié)論都符合客觀實(shí)際情況，大家公認(rèn)是真實(shí)的。即合情、合理、合法，令人信服。,在數(shù)理邏輯中情況稍有不同，它把注意力集中在推理規(guī)則的研究上，如果依據(jù)這些推理規(guī)則，從前提推導(dǎo)出來(lái)的任何結(jié)論都稱(chēng)為有效結(jié)論，這種論證稱(chēng)為有效論證。在確認(rèn)論證有效性時(shí)，前提與結(jié)論的真實(shí)性不起任何作用，也就是說(shuō)，在數(shù)理邏輯中，只關(guān)心論證的有效性，而不大關(guān)心論證的合法性。,前提：如果馬會(huì)飛或羊吃草，則母雞就會(huì)是飛鳥(niǎo)；如果母雞是飛鳥(niǎo)，那么烤熟的鴨子還會(huì)跑；烤熟的鴨子不會(huì)跑。 結(jié)論：羊不吃草。,蘊(yùn)含式的定義是：給定兩個(gè)命題公式A和B，當(dāng)且僅當(dāng)AB 是一個(gè)重言式，則稱(chēng)A蘊(yùn)含B，記為 AB ，又稱(chēng)B是A的有效結(jié)論或B由A邏輯推出。這個(gè)定義可以推廣到有n個(gè)前提的情況。 定義1-27 設(shè) 是命題公式，當(dāng)且僅當(dāng) 則稱(chēng)C是前提集合 的有效結(jié)論。 判別有效結(jié)論的過(guò)程就是論證的過(guò)程，論證方法千變?nèi)f化，但基本方法是真值表法、直接證法和間接證法。,（一）真值表法 設(shè) 是出現(xiàn)的前提集合 和C中的所有命題分量，假定對(duì) 作全部的真值指派就能確定 和C的真值，那么通過(guò)真值表就可以確定結(jié)論C是否是前提集合的有效論證，這個(gè)方法稱(chēng)為真值表法。,利用真值表判別一個(gè)有效論證的方法： 方法一： 在真值表上，若前提 H1,H2,H3,Hn 均為真的所有行，結(jié)論C也為真，則論證有效。 方法二： 在真值表上，若結(jié)論C為假的每一行，其前提 H1,H2,H3,Hn 中至少有一個(gè)為假，則論證有效。 例1-28 如果我認(rèn)真學(xué)習(xí)，我的“離散數(shù)學(xué)”不會(huì)不及格， 如果我不熱衷于玩電子游戲，我將認(rèn)真學(xué)習(xí)， 但我的“離散數(shù)學(xué)”不及格。 結(jié)論：我熱衷于玩電子游戲。 P:我認(rèn)真學(xué)習(xí)， Q:我的“離散數(shù)學(xué)”及格， R:我熱衷于玩電子游戲。,符號(hào)化為： 其真值表如下： 解： 判斷法一：真值表中，只有第2行的前提都為1，其結(jié)論也為1，所以論證有效。 判斷法二：真值表中，第1、3、5、7行為0，每行的前提至少有一個(gè)為0，所以論證有效。,（二）構(gòu)造證明法 (1)推理規(guī)則 常用的推理規(guī)則有： P規(guī)則： 在推導(dǎo)的任意一步都可以引入一個(gè)前提。 T規(guī)則： 如果公式S等價(jià)于或被重言蘊(yùn)含在一個(gè)或多個(gè)前提或中間結(jié)果命題中，則推導(dǎo)中可以引入S。 CP規(guī)則： 如果能從R及一組前提推導(dǎo)出C，則可從這組前提推導(dǎo)出RC。 設(shè)前提 若 則,(2)推理定律 在推導(dǎo)過(guò)程除推理規(guī)則外,還需要推理定律,這些推理定律就是前面所講的常用的蘊(yùn)含式（用I表示）和命題定律（用E表示）。現(xiàn)在將蘊(yùn)含式和命題定律再次顯示如下。,化簡(jiǎn)