主析取范式的求法.ppt

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