【正文】 Q：他可能是 400米賽跑冠軍。 當(dāng)且僅當(dāng)命題 P和 Q均取值為真時， P ∧ Q才取值為真。P取值為真。 C：如果明天天氣晴朗，那么我們舉行運(yùn)動會。（ 6）啊，真美呀！ (7) 明年春節(jié)是個大晴天。首先引入命題、命題公式等概念。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。 （ 4）你吃飯了嗎？ （ 5） x=3。 B：張平或者正在釣魚或者正在睡覺。P取值為假；命題 P取值為假時，命題 172。P 1 0 0 1 5 2．合取“ ∧ ” 定義 92 設(shè) P和 Q是兩個命題，由 P、 Q利用“ ∧ ”組成的復(fù)合命題，稱為合取式復(fù)合命題，記作“ P ∧ Q”（讀作“ P且 Q”）。”符號化。P∧ Q)。 于是上述命題可表示為 P→Q 。 對于上述五種聯(lián)結(jié)詞 ， 應(yīng)注意到： 復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真 值 ， 而與這些原子命題的內(nèi)容含義無關(guān) 。 （ 2）（ 172。 命題符號化為 P∨ Q。（ P ∧ Q） （ 5） 令 P：上午下雨； Q：我去看電影； R：我在家讀書。 解 令 P：我看見的是小張； Q：我看見的是老李。 一個命題變元當(dāng)沒有對其賦予內(nèi)容時，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。 （ 2） 是命題公式。R F 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 18 三、公式類型 定義 98 如果對于命題公式 F所包含的命題變元的任何一組真值指派， F的真值恒為真，則稱公式 F為 重言式（或 永真公式 ），常用“ 1”表示。 19 解 令 F1=（ 172。 (3)的真值表如第 4頁所示，它是可滿足公式。 對稱性 ：對任意公式 A， B，若 A?B，則B?A。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。 （ 2） （ P?Q） ∧ ?P ?（ ?P∨ Q） ∧ ?P E11 ? ?P E9ノ 于是該公式是可滿足式。 反對稱 ：若 A?B， B?A，則 A?B。由此 ?P為真。 從而 P?（ Q?R）為假。 例如 , 172。 (反證法 ) 假設(shè) A式中不同時包含任一命題變元及其否定 ， 則在 A中，當(dāng) Pi*為 Pi時指派 Pi取 0，當(dāng) Pi*為 172。即具有 A1∨A 2∨ … ∨A n(n≥1) 的形式的公式，其中 Ai是質(zhì)合取式。 48 例 1 求 F1=(P∧ (Q?R))?S的合取范式和析取范式 解 F1? ? (P∧ (?Q∨ R))∨ S E11 ? ?P∨ ?(? Q∨ R)∨ S E10ノ ? ?P∨ (Q∧ ?R)∨ S (析取范式 ) E10 ,E6 又 F1? ?P∨ (Q∧ ?R)∨ S ? (?P∨ S)∨ (Q∧ ?R) E1 ,E2 ? (?P∨ S∨ Q)∧ (?P∨ S∨ ?R) （合取范式） E3ノ 另外由 F1? (?P∨ S∨ Q)∧ (?P∨ S∨ ?R) ?(?P∧ (?P∨ S∨ ?R))∨ (S∧ (?P∨ S∨ ?R))∨ (Q∧ (?P∨ S∨ ?R)) E3 ??P∨ S∨ (Q∧ ?P)∨ (Q∧ S)∨ (Q∧ ?R) （析取范式） E9 ,E13 49 例 2 求 F2= ?(P∨Q) ? (P∧Q) 的析取范式、合取范式。 因此 A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。 又 P?(P?Q) ? (P?Q)??P 53 四、主析取范式和主合取范式 定義 916 設(shè)有命題變元 P1， P2， … ,Pn ， 形如 的命題公式稱為是由命題變元 P 1， P2， … ， Pn所產(chǎn)生的最小項。 55 例 4 求公式 F1 = P?(P?(Q?P))和公式 F2 = (P?Q)?(P??Q)的主析取范式 . 解 F1??P∨ (P∧ (?Q∨ P)) E11 ? ? P∨ (P∧ ?Q)∨ (P∧ P) E3 ?(?P∧ (Q∨ ?Q))∨ (P∧ ?Q)∨ (P∧ (Q∨ ?Q)) E7ノ ,E4ノ ,E5 ? (?P∧ Q)∨ (?P∧ ?Q)∨ (P∧ ?Q)∨ (P∧ Q)∨ (P∧ ?Q) E3 ? (?P∧ Q)∨ (?P∧ ?Q)∨ (P∧ ?Q)∨ (P∧ Q) E1,E7 五、求公式的主析取范式和主合取范式 對任一給定的公式除了用求范式時的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進(jìn)一步將質(zhì)合取式（質(zhì)析取式）變換為最小項（最大項）的形式。 59 六 、 利用主范式判定公式類型 1. 利用主析取范式判定 (1) 若公式 F(P1, P2， … ， Pn)的主析取范式包含所有 2n個最小項，則 F是永真公式。 例如 ， 例 5中的 F2。 CHHH n ???? )( 21 ?P Q 0 0 0 1 1 0 1 1 解 構(gòu)造其真值表如下： 172。P 1 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 (（ P→ Q） ∧ 172。這樣的證明稱作是合理的。S的結(jié)論。R∨ （ 172。 解 設(shè) A：甲得冠軍； B：乙得亞軍； C：丙得亞軍； D：丁得亞軍。B C D→ 172。R是矛盾式，所以前件 H1∧ … ∧ Hn必永假。 Q、 P→Q ? 172。R R∨ S S S→ 172。Q是前提（ P∧ Q） → R， 172。（ P∧ Q） 172。 編 號 公 式 依 據(jù) （ 1） R→ 172。問張三、李四、王五三人，到底誰說真話，誰說假話？ 解 先將簡單命題符號化。 R→ （ P∨ Q）。P∧ 172。R （ 9），（ 10）； I11 （ 12） 172。 Q） （ 5）； E11 （ 7） 172。 Q 前 提 （ 2） 172。R， 172。I11 （ 4） P→ Q 前提 （ 5） 172。 S ? 172。R∨ S 172。Q） ∧ （ R∨ S） ∧ （ S→ 172。 證明 編 號 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （ 10） （ 11） 172。 即 H1?H2?… ?Hn??C是永假公式 。 定理 98 若存在一個公式 R，使得 H1∧ H2∧ … ∧ Hn ? R∧ 172。 D 編號 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） A→ （ B∨C ） A B∨C 172。R∨ S R→ S 前提 （ 1）； E11 前提 （ 2），（ 3）； I13 （ 4）； E11 （ 5）； E1， E2 前提 （ 6），（ 7）； I10 （ 8）； E11 72 利用蘊(yùn)含證明規(guī)則： 可將例 3等價地改為證明由前提 推出結(jié)論 S。P P∨ Q Q Q→ R R R∧ （ P∨ Q） 前提（前提引入規(guī)則） 前提（前提引入規(guī)則） （ 1），（ 2）； I12 前提 （ 3），（ 4）； I10 前提 （ 5），（ 6）； I11 （ 4），（ 7）； I9 71 例 3 證明 R→S 是前提 P→ （ Q→S ）， 172。 結(jié)論引用規(guī)則 ： 在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。 有效的證明 ：如果證明過程中的每一步所得到的結(jié)論 都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的。 P ， C： 172。 64 命題演算的推理理論 一、推理 推理是由已知的命題得到新命題的思維過程。 (3) 否則， F為可滿足的公式。 用 0表示 。 *1 ini P??*1 ini P??54 定義 917 由不同最小項所組成的析取式，稱為 主析取范式 。 52 例 4 利用范式判斷公式 P?(P?Q)的類型 。 于是存在一組真值指派使 Ai取值為真。 例如 ， F2=?P∧(P∨Q)∧R∧(P∨ ?Q∨R) 是一合取范式。P 2∨ (P1,P2,P3)=(0,1,0)的指派，使 A的真值為 0. 充分性 ：設(shè) A含命題變元 Pi和 172。P 。 例如 ,172。 42 練習(xí) 73 1．判斷下列等值式是否成立 （ 1）（ P?Q） ∧ （ R ? Q） ?（ P∨ R） ? Q （ 2） ?（ P?Q） ?（ P∧ ? Q） ∨ （ ?P∧ Q） 解 （ 1）（ P?Q） ∧ （ R?Q） ?（ ?P∨ Q） ∧ （ ?R∨ Q） E11 ?（ ?P∧ ?R） ∨ Q E3ノ ??（ P∨ R） ∨ Q E10 （ 2）（ P∧ ?Q） ∨ （ ?P∧ Q） ? ? (（ ?P∨ Q） ∧ （ ?Q∨ P） ) E6， E10ノ ? ? (（ P?Q） ∧ （ Q?P） ) E11 ? ?（ P?Q）