【正文】 。 – 永真式：沒有大項 – 永假式：包含所有的大項 – 可滿足式：包含部分大項 ?給出命題公式的成真賦值或成假賦值 。 5) 除去相同的大項，并將大項按編號由小到大的順序排列。 3) 在析取式中合并相同的命題變元。 定理 4 命題邏輯 115 of 145 解： 例 求公式的主合取范式 QP ?Q11000 011 1101PPQ?()PQ? ? ?2??0 ,1 , 3? ?為了表達簡潔，用 ?表示大項的合取 命題邏輯 116 of 145 解 例求公式的主合（析）取范式 R AQ10000111100111001011010001000P111( ) ( )P Q R P Q R? ? ? ? ? ?)()( RQPRQP ?????????( ) ( )P Q R P Q R? ? ? ? ? ? ? ?)()( RQPRQP ???????A ?1 , 3 , 6 , 7? ?0 , 2 , 4 , 5???命題邏輯 117 of 145 主合取范式的求法 — 等價演算法 1) 化為合取范式。 3) 全體大項的合取式永為假，記為 2101 210nniiM M M M F???? ? ? ? ??命題邏輯 113 of 145 例 RQPM ???0 0 0RQPM ????0 0 1RQPM ????0 1 0RQPM ?????0 1 1RQPM ?????1 1 0RQPM ??????1 1 1RQPM ????1 0 0RQPM ?????1 0 1命題邏輯 114 of 145 主合取范式及其求法 ? 對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則該等價式稱作原式的主合取范式。 例 : 由 P 和 Q 構(gòu)成的大項有： PQ? ? ?PQ??PQ??PQ?11M? 10M?01M? 00M?大項的編碼： 命 題 變 元 ———— 0 命題變元的否定 —— 1 命題邏輯 112 of 145 大項的性質(zhì) QPM ??00QPM ???10QPM ???01QPM ????1100M 01M 10M 11MQP0 001111001110111011110111) 每一個大項當其真值指派與編碼相同時，其真值為 F，在其余 2n1 種指派情況下均為 T。 – 成真賦值：出現(xiàn)的小項對應的真值指派 – 成假賦值：沒有出現(xiàn)的小項對應的真值指派 ?判別兩個命題公式是否等價。 命題邏輯 108 of 145 例 求下式的主析取范式 )()()( RQRPQP ??????( ) ( ) ( ) ( )P Q R R P R Q Q? ? ? ? ? ? ? ? ? ? ?)()( PPRQ ?????( ) 1 ( ) 1 ( ) 1P Q P R Q R? ? ? ? ? ? ? ? ? ?( ) ( ) ( )P Q R P Q R P Q R? ? ? ? ? ? ? ? ? ? ?( ) ( ) ( )P Q R P Q R P Q R? ? ? ? ? ? ? ? ? ? ? ?)()( RQPRQP ???????)()( RQPRQP ?????????命題邏輯 109 of 145 例 求下式的主析取范式 ( ) ( )P P P Q P Q Q? ? ? ? ? ? ? ? ?))()(( PPP ???????))()(( QPQPP ???????( ) ( ) ( )P Q P Q P Q? ? ? ? ? ? ? ? ?()P P Q? ? ? ?)(1 QPP ?????)()( QPP ???????命題邏輯 110 of 145 主析取范式的用途 ?判別命題公式的類型 。 4) 對合取式補入沒有出現(xiàn)的命題變元，即添加 （ P ? ?P） 式，然后應用分配律展開公式。 2) 除去其中所有永假的合取式。 主析取范式的求法： 1. 真值表法 2. 等價演算法 一個公式的真值為 T 的指派所對應的小項的析取，即為此公式的主析取范式。 3) 全體小項的析取式永為真，記為 2101 210nniim m m m T???? ? ? ? ??命題邏輯 102 of 145 例 RP Q1 1 10 1 00 0 11 0 11 1 00 1 10 0 01 0 0010000000100000001000000?000m 001m 111m?001m P Q R? ? ? ? ?RQPm ???1 1 1RQPm ??????000一般說來， n 個命題變元共有 2n 個小項。 例 : 由 P 和 Q 構(gòu)成的小項有： PQ? ? ?PQ??PQ??PQ?00m? 01m?10m? 11m?小項的編碼： 命 題 變 元 ———— 1 命題變元的否定 —— 0 命題邏輯 101 of 145 小項的性質(zhì) QPm ????00QPm ???10QPm ???01QPm ??1100m 01m 10m 11mQP0 001111010001000010010001) 每一個小項當其真值指派與編碼相同時，其真值為 T，在其余 2n1 種指派情況下均為 F。 3) 利用分配律、結(jié)合律將公式規(guī)約為合取 (析取 )范式。 ( ) ( )P P Q P Q R? ? ? ? ? ? ?例： 命題邏輯 97 of 145 范式的求法 1) 將公式中的聯(lián)結(jié)詞化歸成 ?,? ,? 。 命題定律 ? 由對偶定理可推證一些命題公式 . 例 ( ) ( ( ) )P Q P P Q P Q? ? ? ? ? ? ? ? ?( ) ( ( ) )P Q P P Q P Q? ? ? ? ? ? ? ? ?命題邏輯 95 of 145 合取范式 ? 一個命題公式稱為合取范式，當且僅當它具有型式： A1 ? A2 ? … ? An ( n ≥ 1) ? 其中 A1 , A2, … ,An都是由命題變元或其否定所組成的 析取式 。 ??? ???FT ? TF ?命題邏輯 92 of 145 例 * : ( ) ( ( ) )A P Q P Q S? ? ? ? ? ? ?RQPA ?? )(:: ( ) ( ( ) )A P Q P Q S? ? ? ? ? ? ?RQPA ?? )(:*QPQPA ???? )(:QPQPA ???? )(:*命題邏輯 93 of 145 定理 1 ? 設(shè) A 和 A* 是對偶式， P1,P2,…,Pn是出現(xiàn)在 A 和 A* 中的原子變元，則 *11( , , ) ( , , )nnA P P A P P? ? ? ?由摩根定律 證明 ( ) ( )P Q P Q? ? ? ? ? ?( ) ( )P Q P Q? ? ? ? ? ?所以 *11( , , ) ( , , )nnA P P A P P? ? ? ?*11( , , ) ( , , )nnA P P A P P? ? ? ?同理 *11( , , ) ( , , )nnA P P A P P? ? ? ?命題邏輯 94 of 145 定理 2 ? 如果 A ? B, 則 A* ? B*。 命題邏輯 86 of 145 n = 1 P F0 F1 F2 F3 0 0 1 0 1 1 0 0 1 1 0 0F ? 1FP??2FP? 3 1F ?命題邏輯 87 of 145 n = 2 P Q 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1