北京理工大學劉瓊昕-資料下載頁

　　

【正文】 11 1 00 1 10 0 01 0 0010000000100000001000000?000m 001m 111m?001m P Q R? ? ? ? ?RQPm ???1 1 1RQPm ??????000一般說來， n 個命題變元共有 2n 個小項。 命題邏輯 103 of 145 主析取范式及其求法 ? 對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱作原式的主析取范式。 主析取范式的求法： 1. 真值表法 2. 等價演算法 一個公式的真值為 T 的指派所對應的小項的析取，即為此公式的主析取范式。 定理 3 命題邏輯 104 of 145 解： 例 求公式的主析取范式 QP ?Q11000 011 1101P)( QP ???PQ?)( QP ??()PQ? ? ? ?0 ,1 , 3? ?為了表達簡潔，用 Σ 表示小項的析取 命題邏輯 105 of 145 解： 例求公式的主析取范式 QP ?QP01000 011 1111)( QP ???PQ?)( QP ??()PQ? ? ?1 , 2 , 3? ?命題邏輯 106 of 145 解： 例求公式的主析取范式 R AQ10000111100111001011010001000P111( ) ( )P Q R P Q R? ? ? ? ? ? ? ?)()( RQPRQP ???????A ?1 , 3 , 6 , 7? ?命題邏輯 107 of 145 主析取范式的求法 — 等價演算法 1) 化為析取范式。 2) 除去其中所有永假的合取式。 3) 在合取式中合并相同的命題變元。 4) 對合取式補入沒有出現的命題變元，即添加 （ P ? ?P） 式，然后應用分配律展開公式。 5) 除去相同的小項，并將小項按編號由小到大的順序排列。 命題邏輯 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 主析取范式的用途 ?判別命題公式的類型 。 – 永真式：包含所有的小項 – 矛盾式：沒有小項 – 可滿足式：包含部分小項 ?給出命題公式的成真賦值或成假賦值 。 – 成真賦值：出現的小項對應的真值指派 – 成假賦值：沒有出現的小項對應的真值指派 ?判別兩個命題公式是否等價。 命題邏輯 111 of 145 大項 (主合取范式 ) ? n 個命題變元的析取式，稱作布爾析取或大項，其中每個變元與它的否定不能同時存在，但兩者必須出現且僅出現一次。 例 : 由 P 和 Q 構成的大項有： PQ? ? ?PQ??PQ??PQ?11M? 10M?01M? 00M?大項的編碼： 命 題 變 元 ———— 0 命題變元的否定 —— 1 命題邏輯 112 of 145 大項的性質 QPM ??00QPM ???10QPM ???01QPM ????1100M 01M 10M 11MQP0 001111001110111011110111) 每一個大項當其真值指派與編碼相同時，其真值為 F，在其余 2n1 種指派情況下均為 T。 2) 任意兩個不同大項的析取式永真。 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 主合取范式及其求法 ? 對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則該等價式稱作原式的主合取范式。 主合取范式的求法： 1. 真值表法 2. 等價演算法 一個公式的真值為 F 的指派所對應的大項的合取，即為此公式的主合取范式。 定理 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) 化為合取范式。 2) 除去其中所有永真的析取式。 3) 在析取式中合并相同的命題變元。 4) 對析取式補入沒有出現的命題變元，即添加 （ P ? ?P） 式，然后應用分配律展開公式。 5) 除去相同的大項，并將大項按編號由小到大的順序排列。 118 of 145 例 求下式的主合取范式 ( ) ( )A P Q P R? ? ? ? ?))(())(( RQPPQP ???????( ) ( ) ( ) ( )P P P Q P R Q R? ? ? ? ? ? ? ? ? ?)()( RQPRQP ???????( ) ( ) ( )P Q P R Q R? ? ? ? ? ? ?))()(( RP ?????))()(( RQPP ?????))()(( RRQP ??????)()( RQPRQP ?????????命題邏輯 119 of 145 例（續） ( ) ( )A P Q P R? ? ? ? ?)()( RQPRQP ???????)()( RQPRQP ?????????0 , 2 , 4 , 5??( ) ( )P Q R P Q R? ? ? ? ? ? ? ? ?)()( RQPRQP ???????1 , 3 , 6 , 7? ?命題邏輯 120 of 145 例 求下面公式的主合取范式 )))(()(( RQPQP ?????)()( RPQP ????????)))(()(( RQPQP ????????( ( ) )P Q R? ? ? ? ? ?( ( ) )P Q R? ? ? ? ? ?( ( ) ( ) )P Q P R? ? ? ?( ) ( )P Q Q R P R Q R? ? ? ? ? ? ? ? ? ? ? ?( ) ( )P Q P P R P? ? ? ? ? ? ? ?T?永真式 命題邏輯 121 of 145 主合取范式的用途 ?判別命題公式的類型 。 – 永真式：沒有大項 – 永假式：包含所有的大項 – 可滿足式：包含部分大項 ?給出命題公式的成真賦值或成假賦值 。 – 成真賦值：沒有出現的大項對應的真值指派 – 成假賦值：出現的大項對應的真值指派 ?判別兩個命題公式是否等價。