【正文】 E14 ?（ P∨ R） ?Q E11 43 2．判定蘊含式 P?（ Q?R） ?（ P?Q） ?（ P?R）是否成立 解 假定后件（ P?Q） ?（ P?R）為假， 則 P?Q為真， P?R為假。 1. 真值表方法 例 4 證明 I14 ： (（ P∨ Q） ∧ （ P ? R） ∧ （ Q ? R） ) ? R 證明 令公式 F =（ （ P∨ Q） ∧ （ P?R） ∧ （ Q?R） ） ?R， 其真值表如下： 38 公式 F對任意的一組真值指派取值均為 1，故 F是重言式。 “?”不是聯(lián)結(jié)詞， “ A?B”不是公式，它表示公式 A與 B之間存在蘊含關(guān)系。如果將公式 A中的子公式 C置換成公式 D之后，得到的公式是 B，則 A?B。 1 0 1 0 0 0 0 1 25 例 2 用真值表方法證明 E11： P?Q??P?Q 解 令 A=P?Q， B=?P?Q 構(gòu)造 A， B以及 A?B的真值表如下： P Q ?P ?P?Q P?Q A?B 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 由于公式 A?B所標記的列全為 1， 因此 A?B. 1 1 0 1 1 1 26 例 3 用真值表方法判斷 P?Q??P??Q是否成立 . 解 令 A=P?Q， B=?P??Q 構(gòu)造 A， B以及 A?B的真值表 P Q ?P ?Q ?P??Q P?Q A?B 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 由于公式 A?B所標記的列不全為 1， A?B不是永真公式 ， 因此 A?B不成立 。 “? ”是聯(lián)結(jié)詞， A? B是一個公式。P 172。P?Q ） ? 172。 17 例 2 給 出公式 F=(（ P∨Q ） ?（ Q∧R ） )? (P∧ 172。A 是命題公式； （ 4） 如果 A和 B是命題公式，則（ A∨ B）， （ A∧ B） ,(A→B ） ,(A? B ）也是命題公式； 有限次地利用上述（ 1） —（ 4）而產(chǎn)生的符號串是命題公式。 解 令 P：他晚上做完了作業(yè)； Q：他晚上有其它的事； R：他看電視； S：他聽音樂。 （ 1） 只有小孩才愛哭。 （ 3） 令 P：你來了； Q：他唱歌； R：你伴奏。P ∧ 172。 （ 1） 如果明天早上下雨或下雪，那么我不去學校 （ 2） 如果明天早上不下雨且不下雪，那么我去學校。 ?P Q P Q 0 0 1 0 1 0 1 0 0 1 1 1 例 10 非本倉庫工作人員，一律不得入內(nèi)。 當 P為真， Q為假時， P→ Q為假，否則 P→Q 為真。 例 7 今天晚上我在家看電視或去劇場看戲。則P ∧ Q表示 “ 我們?nèi)タ措娪安⑶曳块g里有十張桌子。 P：上海不是一個城市 ?！? 定義 91 設(shè) P是一個命題，利用“ 172。 例 2 判斷下列陳述句是否是命題。 例 1 判斷下列語句是否是命題。1 第九章 命題邏輯 數(shù)理邏輯是用數(shù)學方法研究思維規(guī)律的一門學科。 （ 1）空氣是人生存所必需的。 P：地球外的星球上也有人； Q：小王是我的好朋友； 解 P、 Q是命題 3 二、命題聯(lián)結(jié)詞 原子命題 ： 由簡單句形成的命題?！焙?P組成的復合命題稱為 P的否命題，記作“ 172。 172。 ” P Q P∧ Q 0 0 0 0 1 0 1 0 0 1 1 1 6 3. 析取“ ∨ ” 定義 93 由命題 P和 Q利用 “ ∨ ” 組成的復合命題，稱為析取式復合命題，記作 “ P∨Q ”（讀作 “ P或 Q”）。 令 P：今天晚上我在家看電視。 P Q P→ Q 0 0 1 0 1 1 1 0 0 1 1 1 例 8 將命題“如果我得到這本小說，那么我今夜就讀完它。 解 令 P：某人是倉庫工作人員； Q：某人可以進入倉庫。 （ 3） 如果明天早上不是雨夾雪，那么我去學校。 Q） （ 3） 172。 則命題可表示為 P→ （ Q?R ） （ 4） 令 P：李明是體育愛好者； Q：李明是文藝愛好者。 （ 2） X+6=Y （ 3） 銀是白的。 則該命題可表示為 （ P∧ 172。 例 1 下列符號串是否為命題公式。R）的真值表。（ P?Q ）； （ 2）（ Q→P ） ∧ （ 172。P?Q P ?Q 172。 A?B當且僅當 A?B 是永真公式。 1 0 1 1 0 0 1 1 1 27 (1) 代入規(guī)則 代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。 29 (3) 等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導出另外一些等值式的過程。 “?”是聯(lián)系詞， A?B是一個公式。 P Q R P∨Q P→R Q →R (P∨Q)∧ (P→R ）∧ （ Q →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 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 39 2. 等值演算方法 例 5 證明 I11： P∧ （ P?Q） ? Q 證明 （ P∧ （ P?Q） ） ? Q ? ?（ P∧ （ ?P∨Q ） ） ∨ Q E11 ? （ ?P∨ ?（ ?P∨Q ） ） ∨ E10ノ ?（ ?P∨Q ） ∨ ?（ ?P∨Q ） E2 ? 1 代入規(guī)則 ,E5 因此 P∧ （ P?Q） ? Q 40 3. 假定前件 A真 假定前件 A為真，檢查在此情況下，其后件 B是否也為真。 由 P?R為假 ,得 P為真， R為假。P∧Q∧R∧S 是由命題變元 P、 Q、 R、 S組成的一質(zhì)合取式。 （ 2） 一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。P i，而 Pi∨ 172。 F3=(?P∨R∨Q)∧(P∨Q)∧R∧(P∨ ?R)也是一合取范式。 對同一組真值指派， A的取值也必為真，這與 A是矛盾式不符，假設(shè)不成立。 解 P?(P?Q) ?(P?(P?Q))?(?P??(P?Q)) E12 ?(P?Q)?(?P?(?P??Q)) E?10 ?(P?Q)??P (析取范式 ) E?9 由定理 95，該公式不是永假公式。 定義 918 由不同最大項所組成的合取式，稱為 主合取范式 。 57 例 5 求公式 F1= (P?Q)?(P??Q)和 公式 F2=P?(P?(Q?P))的主合取范式 F1? (?P?Q)?(P??Q) E11 ? (?P?Q)?(P?(Q??Q))?(?Q?(P??P)) E?5, E4 ? (?P?Q)?(P?Q)?(P??Q)?(P??Q)?(?P??Q) E?3 ? (P?Q)?(P??Q)?(?P?Q)?(?P??Q) E?7 58 解 F2 ??P∨ (P∧ (?Q∨ P)) E11 ? (?P∨ P)∧ (?P∨ ?Q∨ P) E3ノ ?1∧ 1 E5,E1 ? 1 定理 97 每一個不為永真的公式 F(P1, P2, … , Pn）必與一個由 P1, P2, … , Pn所產(chǎn)生的主合取范式等值。 60 2 利用主合取范式判定 (1) 若公式 F（ P1, P2, … , Pn） 的主合取范式包含所有 2n個最大項 ， 則 F是永假公式 。 定義 919 設(shè) A和 B是兩個命題公式，如果 A?B，即如果命題公式 A?B為重言式，則稱 B是前提 A的結(jié)論或從 A推出結(jié)論 B。 Q 解 構(gòu)造其真值表如下： 172。 有效的結(jié)論 ：通過有效的證明而得到結(jié)論，稱作是有效的結(jié)論。 置換規(guī)則 ： 在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換。 R∨P 和 Q的有效結(jié)論。 ,)()( RQPRQP ?????RQPRSQP 、 ???? )( 編 號 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） R 172。(172。 R 則公式 H1， H2， … ,Hn是不相容的。 這意味著當 H1?H2?… ?Hn為真時， ?C必為假，因而 C必為真。（ 172。 Q） ∧ （ P→ Q)? 172。S 172。P∨ 172。P （ 3），（ 4）； I12 則上述推理過程符號化為 P → Q， R → 172。 Q→ R， R→ （ 172。 Q→ R 前 提 （ 3） P→ R （ 1），（ 2）； I13 （ 4） R→ （ 172。P （ 6）； E9 （ 8） 172。R 前 提 （ 11） 172。Q） 前 提 （ 5） P→ （ 172。 Q）， 172。 P 79 2. 張三說李四在說謊，李四說王五在說謊，王五說張三、 李四都在說謊。 解 先將已知條件符號化 , 令 P：這里有球賽； Q：通行是困難的； R：他們按指定的時間到達了。（ P∧ Q） ∨ R 172。P∨ 172。Q 172。 Q、 R∨S 、 S→ 172。 R ， 而 R∧ 172。A 172。“如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實是甲已得冠軍，可知丁不能得亞軍”。R∨ P R→ P P→ （ Q→ S） R→ （ Q→ S） 172。 70 例 2 證明 R∧ （ P∨Q ）是前提 P∨Q ， Q→ R，P→ S ， 172。 如果所有的前提都是真的，那么通過有效的證明所得到的結(jié)論 也是真的。Q P→ Q （ P→ Q） ∧ 172。有時也記作H1， H2， … ,Hn ? C 65 真值表法 對于命題公式