【正文】 命題邏輯 74 of 145 1. 不可兼析取 P Q PQ?010 01 10 1真值表 同為假 , 不同為真 ?定義 1 給定兩個命題 P 和 Q ,復(fù)合命題 稱作 P 和 Q的不可兼析取 . PQ?0101命題邏輯 75 of 145 不可兼析取的性質(zhì) )()( QPQPQP ???????)()( RQPRQP ?????( ) ( ) ( )P Q R P Q P R? ? ? ? ? ?PP ???)( QP ???命題邏輯 76 of 145 不可兼析取的性質(zhì) (續(xù) ) PFP ??FPP ??PTP ???RQP ??若 ,則 ,QRP ?? PRQ ??FRQP ???且 命題邏輯 77 of 145 2. 條件否定 010 01 10 1真值表 前真后假 則真 C定義 2 給定兩個命題 P 和 Q ,復(fù)合命題 P Q稱作 P 和 Q的條件否定 . CP Q PQ?C0001命題邏輯 78 of 145 條件否定的性質(zhì) FPP ?CPFP ?CPPP ???CFTP ?CPPP ??CPPT ??CCFPF ?)( QPQP ???C命題邏輯 79 of 145 3. 與非 ? 定義 3 給定兩個命題 P 和 Q ,復(fù)合命題 P ? Q稱作 P 和 Q的與非 . P Q PQ?010 01 10 1真值表 同真則假 1101命題邏輯 80 of 145 與非運算的性質(zhì) )( QPQP ????? PPPPP ????? )(??? )()( QPQP? )( QP??QP ??命題邏輯 81 of 145 與非運算的性質(zhì) (續(xù) ) QP ??)( QP ?????PTP ???QP ??? ?)()( PP ???? TFP ?無結(jié)合律 命題邏輯 82 of 145 4. 或非 ? 定義 4 給定兩個命題 P 和 Q ,復(fù)合命題 P ? Q稱作 P 和 Q的或非 . P Q PQ?010 01 10 1真值表 同假則真 1000命題邏輯 83 of 145 或非的性質(zhì) QP ??)( QP?? ?)()( QPQP ???PPPPP ????? )(?)( QPQP ????命題邏輯 84 of 145 或非運算的性質(zhì) (續(xù) ) QP ??)( QP ?????FTP ??PFP ???QP ??? ?)()( PP ???無結(jié)合律 命題邏輯 85 of 145 小結(jié) 1. 九個聯(lián)結(jié)詞 ? C ? ? ? ? ? ? ? 1?n2?n 1622 422 ??2 5 622 82 3 ??3?n42 12 ?... ...2. n 個命題變元共有 2n個真值指派， 所以可以構(gòu)成 22n 個不等價的命題公式。 顯然， A 也是 A*的對偶式。 ? 等價式的對偶式等價。 ( ) ( )P Q R P Q Q? ? ? ? ? ? ? ?例： 命題邏輯 96 of 145 析取范式 ? 一個命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有型式： A1 ? A2 ? … ? An ( n ≥ 1) ? 其中 A1 , A2, … ,An都是由命題變元或其否定所組成的 合取式 。 2) 利用德 ?摩根律將 ? 消去或內(nèi)移。 命題邏輯 98 of 145 例 求下式的合取范式 ( ( ) )P Q R P? ? ?( ( ) )P Q R P? ? ? ? ?( ( ) )P Q R P? ? ? ? ? ?( ( ) )P Q R P? ? ? ? ?( ) ( )P Q P R P? ? ? ? ? ?( ) ( )P Q R P? ? ? ? ?與命題公式等價的合取范式不唯一 命題邏輯 99 of 145 ( ) ( )P Q P R P? ? ? ? ? ?( ) ( )P Q R P? ? ? ? ?例 求下式的析取范式 ( ( ) )P Q R P? ? ?( ( ) )P Q R P? ? ? ? ?( ( ) )P Q R P? ? ? ? ? ?( ( ) )P Q R P? ? ? ? ?( ) ( )P R Q R P? ? ? ? ? ? ?()Q R P? ? ? ?與命題公式等價的析取范式不唯一 命題邏輯 100 of 145 小項 (主析取范式 ) ? n 個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 2) 任意兩個不同小項的合取式永假。 命題邏輯 103 of 145 主析取范式及其求法 ? 對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱作原式的主析取范式。 定理 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) 化為析取范式。 3) 在合取式中合并相同的命題變元。 5) 除去相同的小項，并將小項按編號由小到大的順序排列。 – 永真式：包含所有的小項 – 矛盾式：沒有小項 – 可滿足式：包含部分小項 ?給出命題公式的成真賦值或成假賦值 。 命題邏輯 111 of 145 大項 (主合取范式 ) ? n 個命題變元的析取式，稱作布爾析取或大項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 2) 任意兩個不同大項的析取式永真。 主合取范式的求法： 1. 真值表法 2. 等價演算法 一個公式的真值為 F 的指派所對應(yīng)的大項的合取，即為此公式的主合取范式。 2) 除去其中所有永真的析取式。 4) 對析取式補入沒有出現(xiàn)的命題變元，即添加 （ P ? ?P） 式，然后應(yīng)用分配律展開公式。 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 主合取范式的用途 ?判別命題公式的類型 。 – 成真賦值：沒有出現(xiàn)的大項對應(yīng)的真值指派 – 成假賦值：出現(xiàn)的大項對應(yīng)的真值指派 ?判別兩個命題公式是否等