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

1、會(huì)計(jì)學(xué)1 離散數(shù)學(xué)離散數(shù)學(xué)14 1.4 析取范式與合取范式 定義： 一個(gè)命題公式為合取范式，當(dāng)且僅當(dāng)它具有形式： A1 A2 A3 An,（n=1）其中）其中A1，A2， A3An均是由命題變元及其否定組成的析取式。 一個(gè)命題公式為析取范式，當(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、等值的析取范式和合取范式。 范式的求法：消去公式中的蘊(yùn)涵、等價(jià)和異或聯(lián)結(jié)詞 使用雙重否定律和德摩根律，將公式中出現(xiàn) 的否定 詞移到命題變元之前。 利用分配律、結(jié)合律將公式化為合（析）取 范式。 注意：范式形式不唯一。 1.4 析取范式與合取范式 第3頁/共18頁 q (pr)(qr)(pqr) 第4頁/共18頁 第5頁/共18頁 極小項(xiàng)極大項(xiàng) 公式成真賦 值 名稱公式成假賦 值 名稱 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兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)由下表給出

3、 第6頁/共18頁 極小項(xiàng)極大項(xiàng) 公式 成真 賦值名稱公式 成假 賦值 名稱 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三個(gè)命題變項(xiàng)形成的極小項(xiàng)與

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