離散數(shù)學(xué)14PPT學(xué)習(xí)教案

1、會計學(xué)1 離散數(shù)學(xué)離散數(shù)學(xué)14 1.4 析取范式與合取范式 定義： 一個命題公式為合取范式，當(dāng)且僅當(dāng)它具有形式： A1 A2 A3 An,（n=1）其中）其中A1，A2， A3An均是由命題變元及其否定組成的析取式。 一個命題公式為析取范式，當(dāng)且僅當(dāng)它具有形式： A1 A2 A3 An,（n=1）其中）其中A1，A2， A3An均是由命題變元及其否定組成的析取式。 注意：在合取范式和析取范式中都沒有聯(lián)結(jié)詞注意：在合取范式和析取范式中都沒有聯(lián)結(jié)詞， 在合取范式和析取范式中否定詞在合取范式和析取范式中否定詞只出現(xiàn)在原子命題的前面。 第1頁/共18頁 第2頁/共18頁 定理3.任一命題公式都存在與之

2、等值的析取范式和合取范式。 范式的求法：消去公式中的蘊涵、等價和異或聯(lián)結(jié)詞 使用雙重否定律和德摩根律，將公式中出現(xiàn) 的否定 詞移到命題變元之前。 利用分配律、結(jié)合律將公式化為合（析）取 范式。 注意：范式形式不唯一。 1.4 析取范式與合取范式 第3頁/共18頁 q (pr)(qr)(pqr) 第4頁/共18頁 第5頁/共18頁 極小項極大項 公式成真賦 值 名稱公式成假賦 值 名稱 pq pq pq pq 0 0 0 1 1 0 1 1 m0 m1 m2 m3 pq pq pq pq 0 0 0 1 1 0 1 1 M0 M1 M2 M3 由p, q兩個命題變項形成的極小項與極大項由下表給出

3、 第6頁/共18頁 極小項極大項 公式 成真 賦值名稱公式 成假 賦值 名稱 p q r p q r p q r p q r p q r p q r p q r p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 m1 m2 m3 m4 m5 m6 m7 p q r p q r p q r p q r p q r p q r p q r p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M0 M1 M2 M3 M4 M5 M6 M7 由p, q, r三個命題變項形成的極小項與

4、極大項如下表 第7頁/共18頁 第8頁/共18頁 公式法：求析取范式 用同一律補(bǔ)進(jìn)未出現(xiàn)的命題變元 消去永假或重復(fù)出現(xiàn)的變元和極小項 將極小項按下標(biāo)從小到大排列 真值表法：列出公式及各極小項的真值表，將每組賦值下 公式及極小項真值都為真的極小項進(jìn)行析取。 主析取范式的求法：1.公式法 2.真值表法 第9頁/共18頁 1.4 析取范式與合取范式 應(yīng)用：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極小項的編碼的二進(jìn)制數(shù) 成假賦值為合取范式中所含極大項的編碼的二進(jìn)制數(shù) 12 i , m; i iii Mp p MMm in 定理.設(shè)m 與是,p 形成的極小項、極大項， 則， 由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的極小項 2求出與1中求出的極小項下標(biāo)相同的極大項 3做2中極大項之合取 第10頁/共18頁 第11頁/共18頁 第12頁/共18頁 第13頁/共18頁 第14頁/共18頁 P Q RPRPQ(PR)(PQ) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0