離散數(shù)學(xué)2(已修改)
2025-08-17 10:36 本頁面
【正文】 范式 ? 析取范式與合取范式 ? 簡單析取式與簡單合取式 ? 析取范式與合取范式 ? 主析取范式與主合取范式 ? 極小項與極大項 ? 主析取范式與主合取范式 ? 主范式的用途 1 簡單析取式與簡單合取式 文字 :命題變項及其否定的統(tǒng)稱 簡單析取式 :有限個文字構(gòu)成的析取式 如 p, ?q, p??q, p?q?r, … 簡單合取式 :有限個文字構(gòu)成的合取式 如 p, ?q, p??q, p?q?r, … 定理 (1) 一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含 某個命題變項和它的否定 (2) 一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含某個命題 變項和它的否定 2 析取范式與合取范式 析取范式 :由有限個簡單合取式組成的析取式 A1?A2??? Ar, 其中 A1,A2,? ,Ar是 簡單合取式 合取范式 :由有限個簡單析取式組成的合取式 A1?A2??? Ar , 其中 A1,A2,? ,Ar是 簡單析取式 范式 :析取范式與合取范式的統(tǒng)稱 定理 (1) 一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個 簡單合取式都是矛盾式 (2) 一個合取范式是重言式當(dāng)且僅當(dāng)它的每一個簡單析取 式都是重言式 3 范式存在定理 定理 任何命題公式都存在著與之等值的析取范式與合 取范式 . 證 求公 式 A的范式的步驟： (1) 消去 A中的 ?, ? A?B??A?B A?B?(?A?B)?(A??B) (2) 否定聯(lián)結(jié)詞 ?的內(nèi)移或消去 ? ?A? A ?(A?B)??A??B ?(A?B)??A??B 4 范式存在定理 (續(xù) ) (3) 使用分配律 A?(B?C)?(A?B)?(A?C) 求合取范式 A?(B?C)? (A?B)?(A?C) 求析取范式 例 1 求 ?(p?q)??r 的析取范式與合取范式 解 ?(p?q)??r ? ?(?p?q)??r ? (p??q)??r 析取范式 ? (p??r)?(?q??r) 合取范式 注意 : 公式的析取范式與合取范式不惟一 . 5 極小項與極大項 定義 在含有 n個命題變項的簡單合取式 (簡單析取式 ) 中 ,若每個命題變項均以文字的形式出現(xiàn)且僅出現(xiàn)一次 ， 而且第 i(1?i?n)個文字 (按下標(biāo)或字母順序排列 )出現(xiàn)在左 起第 i位上 ,稱這樣的簡單合取式 (簡單析取式 )為 極小項 (極大項 ) 說明 : (1) n個命題變項產(chǎn)生 2n個極小項和 2n個極大項 (2) 2n個極小項 (極大項 )均互不等值 (3) 用 mi表示第 i個極小項 ,其中 i是該極小項成真賦值的十 進制表示 . 用 Mi表示第 i個極大項 ,其中 i是該極大項成假賦 值的十進制表示 , mi(Mi)稱為極小項 (極大項 )的名稱 .
試題試卷相關(guān)推薦
鄂ICP備17016276號-1