【正文】 天，那么 2+3=6. (除星期天外，天天真 ） ?在漢語中，“ 如果 ? ， 則? ” 是有因果關系的，但在命題邏輯中Ｐ→ Ｑ總是有意義的． 命題邏輯 29 of 145 逆換式、反換式、逆反式 ? P → Q 如果下雨，則地濕。 ? 逆換式： Q → P 如果地濕，則下雨。 ? 反換式： ? P → ? Q 如果不下雨，則地不濕。 ? 逆反式： ? Q → ? P 如果地不濕，則不下雨。 命題邏輯 30 of 145 條件運算的性質 PP ?????QPQP ????? )(QPQP ????PPT ??TPF ??命題邏輯 31 of 145 條件運算的性質 (續(xù) ) TTP ??PPP ???PPP ????PFP ???TPP ??命題邏輯 32 of 145 5. 雙條件 ? 定義 5 給定兩個命題 P 和 Q ,其復合命題 P ? Q稱作雙條件命題 , 讀作“ P當且僅當 Q”. P Q PQ?010 01 10 1真值表 同則真 不同則假 1100命題邏輯 33 of 145 例 P ? Q ? 兩個三角形全等 ,當且僅當它們的三組對應邊相等 . ? 燕子飛回北方 , 春天來了 . ? 2+2=4 當且僅當雪是白的 . ? 1+1=10當且僅當數(shù)是二進制的 . ? 騙子講真理當且僅當太陽從西邊出來 . 命題邏輯 34 of 145 雙條件運算的性質 PP ???)()( RQPRQP ?????PFP ???TPP ?? FPP ???PTP ??命題邏輯 35 of 145 雙條件運算的性質 (續(xù) ) QPQP ????? )()()( PPQP ?????)()( QPQP ?????? 北京理工大學 鄭軍 13 命題公式與翻譯 命題邏輯 37 of 145 命題公式 命題演算的合式公式 (wff)，規(guī)定為： 1) 單個命題變元本身是一個合式公式。 2) 如果 A是合式公式，則 ? A是合式公式。 3) 如果 A和 B是合式公式，那么 (A ? B), (A ? B), (A → B), (A ? B)是合式公式。 命題邏輯 38 of 145 命題公式（續(xù)） 4) 當且僅當能夠有限次地應用（ 1）、（ 2）、（ 3）所得到的包含命題變元，聯(lián)結詞和括號的符號串是合式公式。 通常我們約定聯(lián)結詞的優(yōu)先次序為： ? ， ?， ? ， ? ， ? 命題邏輯 39 of 145 例 是命題公式 ),( QP ?? ,QP ??),( QPP ?? QPP ??,( QP ? ,?P QP ??不是命題公式 命題邏輯 40 of 145 例：試以符號形式寫出下列命題 1. 選修過微積分或計算機科學的學生可以選修這門課 。 2. 選小王或小李中的一人當班長。 3. 小王是計算機系的學生，他生于 1982年，他是一個好學生。 4. 如果我上街，我就去書店看看，除非我很累。 5. 只有你是計算機系的學生或不是一個新生，才可以通過校園網訪問 Inter。 命題邏輯 41 of 145 例：試以符號形式寫出下列命題 : 選修過微積分的學生選修這門課。 Q: 選修過計算機科學的學生選修這門課。 P ? Q : 小王當班長。 Q: 小李當班長 。 ( P ? ? Q) ? (? P ? Q) 3. P: 小王是計算機系的學生。 Q: 他生于 1982年。 R: 他是一名好學生。 P ? Q ? R 4. P: 我上街。 Q: 我去書店看看。 R: 我很累。 ? R →(P→Q) 5. C: 你是計算機系的學生。 F: 你是一個新生。 A: 你可以通過校園網訪問 Inter。 A → (C ? ?F) 北京理工大學 鄭軍 14 真值表與等價公式 命題邏輯 43 of 145 真值表 ? 在命題公式中，對于分量指派真值的各種可能組合，就確定了這個命題公式的各種真值情況，把它匯列成表，就是命題公式的真值表。 01110011010 10011P? QP ??QP PQ?0111命題邏輯 44 of 145 例 1111RP Q QP ? RQP ??0000000001111 1000 000 111 01 0 010 011 101 1一般說來， n個命題變元組成的命題公式有 2n 種真值情況。 命題邏輯 45 of 145 重言式（永真式） ? 給定一命題公式，若無論對分量作怎樣的指派，其對應的真值永為真，則稱該命題公式為重言式或永真公式。 QP000011111111)?( QP ??PQ? ) ( 命題邏輯 46 of 145 矛盾式（永假式） ? 給定一命題公式，若無論對分量作怎樣的指派，其對應的真值永為假，則稱該命題公式為矛盾式或永假公式。 0001QP ?P?0011QP00001111PQP ??? )(0000命題邏輯 47 of 145 可滿足式 ? 如果命題公式既不是重言式，也不是矛盾式，則稱該命題公式是可滿足式。 命題邏輯 48 of 145 定理 ? 任何兩個重言式的合取或析取，仍然是一個重言式。 設 A 和 B 為兩個重言式， 則不論 A和 B 的分量指派任何真值，總有 A 為 T, B 為 T, 故 A ? B ? T A ? B ? T 證明 : 命題邏輯 49 of 145 定理 ? 一個重言式，對同一分量都用任何合式公式置換，其結果仍為一重言式。 由于重言式的真值與分量的指派無關， 故對同一分量以任何合式公式置換后，重言式的真值仍永為 T. 證明 : 命題邏輯 50 of 145 等價 ? 給定兩個命題公式 A 和 B，設P1,P2,…,Pn為出現(xiàn)于 A 和 B 中的原子變元，若給 P1,P2,…,Pn任一組真值指派， A 和 B 的真值都相同，則稱 A 和 B 是等價的或邏輯相等。記作 A ? B。 設 A、 B為兩個命題公式 , A ? B 當且僅當 A ? B 為一重言式。 定理 命題邏輯 51 of 145 例 用真值表說明命題公式等價 010100001111( ) ( )P Q Q P P Q? ? ? ? ?0101QP )()( PP ??? QP ?命題邏輯 52 of 145 命題定律 PPP ??)()( RQPRQP ?????PP ???冪等律 交換律 結合律 PPP ??PP ???)()( RQPRQP ?????PP ???對和律 (雙重否定律 ) 命題邏輯 53 of 145 命題定律 (續(xù) ) )( RQP ?? )()( RPQP ????分配律 PQPP ??? )()()( RPQP ????)( RQP ??PQPP ??? )(吸收律 QPQP ?????? )(QPQP ?????? )(摩根律 命題邏輯 54 of 145 命題定律（續(xù)完） PFP ??TPP ???TTP ??同一律 零 律 否定律 PTP ??FFP ??FPP ???命題邏輯 55 of 145 其它等價式 PP ?????QPQP ????? )(QPQP ????( ) ( )P Q R P Q R? ? ? ? ?QPQP ????? )()()( PPQP ?????)()( QPQP ??????命題邏輯 56 of 145 子公式與等價置換 ? 若 X 是合式公式 A 的一部分，且 X 本身也是一個合式公式，則稱 X是公式 A 的子公式。 設 X 是合式公式 A 的子公式，若 X ? Y ，如果將 A 中的 X 用 Y 來置換，所得到的公式 B 與公式 A 等價，即 A ? B 。 定理 滿足該定理條件的置換稱為 等價置換 。 命題邏輯 57 of 145 例 試證 PPPQ ????? ))((( ( ) ( ) )Q P P P Q? ? ? ? ? ?證法 1 ))(( QPPQ ???)()( P