【正文】 稱此合取式為含n個變元的 小項 。 ? 由于含有 n個變元的每個小項都是 n項的合取，而每一項或者是變元出現(xiàn)或者是變元否定出現(xiàn)。這樣每個小項就對應一個 n位二進制數(shù)。如 ┐P∧ Q的編碼為 m01， P∧ ┐Q∧ R的編碼為 m101，因此小項與編碼是一一對應的，編碼為 m010的小項為┐P∧ Q∧ ┐R。即其它任何指派都使此小項為假。 ?有了對小項的充分討論，下面我們研究主析取范式的概念、性質與求法。 ?我們可以有兩種方法求主析取范式： ?方法 1：真值表法 ?真值表中使公式 A為真的指派所對應的小項組成的析取式即為 A的主析取范式。 ? 例 用真值表求 P → Q 的主析取范式 ? 解： P → Q 的真值表為： ? 表 ? 因此 P → Q 的主析取范式為 m00 ∨ m01 ∨ m11 ? （ ?P∧ ?Q） ∨ （ ?P∧ Q） ∨ （ P∧ Q） ? 由此我們知道，一個公式的主析取范式是惟一的?，F(xiàn)將這范式中的合取式 P添加變元 Q, 合取式 Q添加 P, 即填滿變元 P、 Q, 以構成小項） ??（ ?P∧ （ Q∨ ?Q）） ∨ （ Q∧ （ P∨ ?P）） ??（ ?P∧ Q） ∨ （ ?P∧ ?Q） ∨ （ P∧ Q） ? 由此得出利用等價變形法求公式的主析取范式的方法步驟： ? 第一步：求出該公式的析取范式； ? 第二步：除去范式中所有恒假的合取式，即化掉含有互補對的合取式；同時，將合取式中同一變元的多個出現(xiàn)合并為一個； ? 第三步：對并非每一變元都出現(xiàn)的析取范式中的合取式，利用 P?P∧ T?P∧ (Q∨ ┐Q)把未出現(xiàn)的變元（ Q）補進來，并用分配律將其展開，最后得到給定公式的主析取范式。 ??主合取范式 ? 主合取范式與合取范式的區(qū)別就在于對合取范式中的析取式有更嚴格的要求，即要達到都是大項。 ? 如：兩個變元 P， Q能夠組成的大項有： 4 = 22 個 ? P∨ Q， P∨ ┐Q， ┐P∨ Q， ┐P∨ ┐Q ? 三個變元 P， Q， R能夠組成的大項有： 8 = 23 個 ? P∨ Q∨ R， ┐P∨ Q∨ R， P∨ ┐Q∨ R， P∨ Q∨ ┐R，┐P∨ ┐Q∨ R， ┐P∨ Q∨ ┐R， P∨ ┐Q∨ ┐R，┐P∨ ┐Q∨ ┐R ? 因此， n個變元能夠組成的大項有 2N個 . ? 同樣，下面討論一下對大項編碼問題。 ?我們約定：當變元出現(xiàn)時相應位置記為“ 0”；當變元否定出現(xiàn)時相應位置記為“ 1”。那么這個大項的編碼就用 M帶上這個 n位二進制數(shù)為右下標組成。 ?再來看看大項的性質，我們也從它們的真值表去分析：（表 8 .15和表 8 .16分別是兩個變元的大項與三個變元的大項真值表） ?由上兩個大項真值表不難看出，大項具有如下性質： ?任兩大項均不等價； ?每個大項有且僅有一組指派使其真值為假，且恰當指派與大項編碼一致時。如大項 M101只在指派101時為假，其它指派都是真。 ?定義 對一合取范式，若其每一個合取式均為大項時，即是 主合取范式 （ conjunctive normal form）。其道理不難從大項的性質得出這樣的主合取范式與 A等價，因而可作為 A的主合取范式。 ?方法 2：等價變形法 ?例 求公式 (P∧ Q)∨ R的主合取范式。 ? 應用主析取范式分析和解決實際問題。由于工作需要，選派時要滿足以下條件： ? （ 1） 若 A去，則 C同去； ? （ 2） 若 B去，則 C不能去； ? （ 3） 若 C不去，則 A或 B可以去。 練習 ? *把公式 (p→q) ?( ┐q→┐p)變換為與之等價的、只含聯(lián)結詞 ┐， ∧ 的公式。 ? A、 B、 C、 D四人做競賽游戲，其中三人報告情況如下： ? A： C第一， B第二； ? B： C第二， D第三； ? C： A第二， D第四。 8． 4命題邏輯在邏輯電路與語句邏輯中的應用 1 簡單開關電路的化簡 例 化簡如圖 。這在實際生產(chǎn)過程中，在自動控制和電路設計中，有著很重要的意義。 ? 很顯然，我們可以得到如下的方法： ? 電路工作的條件： ? ① 寫出給定的開關電路相對應的邏輯命題公式； ? ② 將該表達式化為析取標準式； ? ③ 令其某一項取值為 1即可。 ? 解：該電路的表達式為 ? f=（ ?X∧ y∧ z） ∨（ u∧ v∧ x） ? 此為析取范式。 ? 以上結果表明使電路工作時，各開關 x、 y、 z、 u、 v所應取的開或閉的狀態(tài)。 ? 對于塔型開關電路，可化為 1值小項范式（即主析取范式）或 0值大項范式（即主合取范式），以分別確定其工作或不工作的條件。每臺計算機能給出飛行計劃正確或者有誤的回答。由所給信息，根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷。 4 指令變換 ? 例 一位觀測者看著在自己面前緩緩移動的紙帶上的數(shù)字，他必須按照指令把某些數(shù)字消除掉。” ? 解：設 A——表示能被 3除盡； ? B——表示末尾是 0； ? C——表示各數(shù)之和大于 31的數(shù)。”這樣，命題演算能把給出的指令變換成非常簡單的易于理解的指令。 5 語句邏輯問題 ? 例 （ 著名的邏輯學家的故事）有一邏輯學家誤入某部落，被拘于牢獄，酋長意欲放行，他對邏輯學家說：“今有兩門，一為自由，一為死亡，你可任意開啟一門，為協(xié)助你逃脫，今加派兩名戰(zhàn)士負責解答你所提出的問題?！边壿媽W家沉思片刻，即向一戰(zhàn)士發(fā)問，然后開門從容離去。當被問戰(zhàn)士回答“否”，則邏輯學家將開啟另一扇門從容離去。如果被問戰(zhàn)士是誠實戰(zhàn)士，他回答“否”，則另一名戰(zhàn)士是說謊戰(zhàn)士，他回答“不是”，那么，這扇門是死亡門。 ? 設 P：被問戰(zhàn)士是誠實戰(zhàn)士， ? Q：被問戰(zhàn)士回答是“對”， ? R：另一名戰(zhàn)士回答是“是”， ? S：這扇門是死亡門 ? 練習 ? 1．牛牛想用兩個事實來判斷三位工作伙伴的相對薪水。其次他知道如果大山的薪水不是三人中最低的，那么中元的最高。 ? 2．五個朋友都能進入談話室。袁莫或劉儀在談話，但沒有同時談話。劉儀和張元或者兩人都在談話，或者都不談話。解釋你的推理。他們已對審訊員作了陳述。” C說“我沒干。” D說“ B說是我干的，他說謊。 ? （ 2）如果審訊員知道四個嫌疑犯中恰有一人說謊，那么誰干的？解釋你的