北京理工大學(xué)劉瓊昕-資料下載頁(yè)
2025-07-18 13:14本頁(yè)面
【正文】 11 1 00 1 10 0 01 0 0010000000100000001000000?000m 001m 111m?001m P Q R? ? ? ? ?RQPm ???1 1 1RQPm ??????000一般說(shuō)來(lái)， n 個(gè)命題變?cè)灿? 2n 個(gè)小項(xiàng)。 命題邏輯 103 of 145 主析取范式及其求法 ? 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱作原式的主析取范式。 主析取范式的求法： 1. 真值表法 2. 等價(jià)演算法 一個(gè)公式的真值為 T 的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式的主析取范式。 定理 3 命題邏輯 104 of 145 解： 例 求公式的主析取范式 QP ?Q11000 011 1101P)( QP ???PQ?)( QP ??()PQ? ? ? ?0 ,1 , 3? ?為了表達(dá)簡(jiǎn)潔，用 Σ 表示小項(xiàng)的析取 命題邏輯 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 主析取范式的求法 — 等價(jià)演算法 1) 化為析取范式。 2) 除去其中所有永假的合取式。 3) 在合取式中合并相同的命題變?cè)? 4) 對(duì)合取式補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添?（ P ? ?P） 式，然后應(yīng)用分配律展開(kāi)公式。 5) 除去相同的小項(xiàng)，并將小項(xiàng)按編號(hào)由小到大的順序排列。 命題邏輯 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 主析取范式的用途 ?判別命題公式的類型 。 – 永真式：包含所有的小項(xiàng) – 矛盾式：沒(méi)有小項(xiàng) – 可滿足式：包含部分小項(xiàng) ?給出命題公式的成真賦值或成假賦值 。 – 成真賦值：出現(xiàn)的小項(xiàng)對(duì)應(yīng)的真值指派 – 成假賦值：沒(méi)有出現(xiàn)的小項(xiàng)對(duì)應(yīng)的真值指派 ?判別兩個(gè)命題公式是否等價(jià)。 命題邏輯 111 of 145 大項(xiàng) (主合取范式 ) ? n 個(gè)命題變?cè)奈鋈∈剑Q作布爾析取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 例 : 由 P 和 Q 構(gòu)成的大項(xiàng)有： PQ? ? ?PQ??PQ??PQ?11M? 10M?01M? 00M?大項(xiàng)的編碼： 命 題 變 元 ———— 0 命題變?cè)姆穸? —— 1 命題邏輯 112 of 145 大項(xiàng)的性質(zhì) QPM ??00QPM ???10QPM ???01QPM ????1100M 01M 10M 11MQP0 001111001110111011110111) 每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為 F，在其余 2n1 種指派情況下均為 T。 2) 任意兩個(gè)不同大項(xiàng)的析取式永真。 3) 全體大項(xiàng)的合取式永為假，記為 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 主合取范式及其求法 ? 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由大項(xiàng)的合取所組成，則該等價(jià)式稱作原式的主合取范式。 主合取范式的求法： 1. 真值表法 2. 等價(jià)演算法 一個(gè)公式的真值為 F 的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。 定理 4 命題邏輯 115 of 145 解： 例 求公式的主合取范式 QP ?Q11000 011 1101PPQ?()PQ? ? ?2??0 ,1 , 3? ?為了表達(dá)簡(jiǎn)潔，用 ?表示大項(xiàng)的合取 命題邏輯 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 主合取范式的求法 — 等價(jià)演算法 1) 化為合取范式。 2) 除去其中所有永真的析取式。 3) 在析取式中合并相同的命題變?cè)? 4) 對(duì)析取式補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添?（ P ? ?P） 式，然后應(yīng)用分配律展開(kāi)公式。 5) 除去相同的大項(xiàng)，并將大項(xiàng)按編號(hào)由小到大的順序排列。 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 例（續(xù)） ( ) ( )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 主合取范式的用途 ?判別命題公式的類型 。 – 永真式：沒(méi)有大項(xiàng) – 永假式：包含所有的大項(xiàng) – 可滿足式：包含部分大項(xiàng) ?給出命題公式的成真賦值或成假賦值 。 – 成真賦值：沒(méi)有出現(xiàn)的大項(xiàng)對(duì)應(yīng)的真值指派 – 成假賦值：出現(xiàn)的大項(xiàng)對(duì)應(yīng)的真值指派 ?判別兩個(gè)命題公式是否等價(jià)。
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1