【正文】 中所有命題變?cè)拿恳唤M真值指派作出該公式的真值表，看是否為永真 。 (2) 若 F的主合取范式是一空公式且為 1， 則 F是永真公式 。 永真公式 的主合取范式是一空公式，用 1表示。 (P1??P2?P3)?(P1?P2?P3)?(?P1??P2??P3)?(?P1?P2??P3)是一個(gè)主合取范式 。 由上可知 ， 該公式是一可滿足公式 。于是由定理 94知，每一 Ai(1≤i≤n)都為矛盾式，因此 A1∨ A2∨ … ∨ An必為矛盾式，即 A為矛盾式。 按下列步驟進(jìn)行： （ 1）利用 E11， E12和 E14消去公式中的運(yùn)算符“ ?” 和 “ ?” ； (2) 利用德 ?摩根定律將否定符號(hào) “ ?” 向內(nèi)深入，使之只作用于命題變?cè)? （ 3）利用雙重否定律 E6將 ? (?P)置換成 P； （ 4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。 46 定義 914 質(zhì)合取式的析取稱為析取范式。 證明 （ 2） 必要性 ：假設(shè) A= P1*∨ P2*∨ … ∨ Pn*為一質(zhì)析取式，且 A為一永真式。Pi ，則稱其為 質(zhì)析取式 。 于是 P為真， Q?R為假。 于是 Q為假，因而 P也為假。 33 A?B是偏序關(guān)系 即 自反性 ： A?A。 （ 1） Q∧ ? (?P?（ ?P∧ Q） ) （ 2）（ P?Q） ∧ ?P 解 （ 1） Q∧ ?（ ?P?（ ?P∧ Q） ） ?Q∧ ?（ P∨ （ ?P∧ Q） ） E11,E6 ?Q∧ ?（ （ P∨ ?P） ∧ （ P∨ Q） ） E3ノ ?Q∧ ?（ 1∧ （ P∨ Q） ） E5 ?Q∧ ?（ P∨ Q） E4ノ ?Q∧ ?P∧ ?Q E10 ?（ Q∧ ?Q） ∧ ?P E1ノ ,E2 ?0 E5ノ ,E8ノ 所以 Q∧ ? (?P? (?P∧ Q))是矛盾式。 注意：因?yàn)?A ? B當(dāng)且僅當(dāng) A ? B 是重言式。 即 自反性 ：對(duì)任意公式 A，有 A?A。P∧ Q F2 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 由上可知： F1是 重言式 , F2是 矛盾式。R）。R P∨ Q Q∧ R (P∨ Q)→(Q∧ R) P∧ 172。（ Q∧ R）） 解 （ 1） 不是命題公式。 2．命題變?cè)? 一個(gè)沒有指定具體內(nèi)容的命題符號(hào)。 ( 是 假 ) ( 不是 ) ( 是 真 ) ( 不是 ) 2． 將下列命題符號(hào)化 （ 1） 我看見的既不是小張也不是老李。Q ） → 172。 解 （ 1） 令 P：派小王出差； Q：派小李出差。 解 令 P：明天早上下雨； Q：明天早上下雪； R：我去學(xué)校。 10 例 11 黃山比喜馬拉雅山高 ， 當(dāng)且僅當(dāng) 3是素?cái)?shù) 令 P：黃山比喜馬拉雅山高； Q： 3是素?cái)?shù) 本例可符號(hào)化為 P?Q 從漢語的語義看， P與 Q之間并無聯(lián)系，但就聯(lián)結(jié) 詞 ?的定義來看，因?yàn)?P的真值為假， Q的真值為真， 所以 P?Q的真值為假。 解 令 P：我得到這本小說； Q：我今夜就讀完它。Q ∨ (172。 P Q P∨ Q 0 0 0 0 1 1 1 0 1 1 1 1 例 6 將命題“他可能是 100米或 400米賽跑的冠軍。 P 172。 命題 P取值為真時(shí)，命題 172。 例 3 A：李明既是三好學(xué)生又是足球隊(duì)員。 （ 3）南京是中國(guó)的首都。因此 , 數(shù)理邏輯又稱為符號(hào)邏輯。然后 ,在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊(yùn)含關(guān)系 ,并給出推理規(guī)則 ,進(jìn)行命題演繹。 解 語句（ 1） ,（ 3） ,（ 5）， (7)是陳述句 （ 1）、（ 3）、 (7)是命題 用真值來描述命題是 “ 真 ” 還是 “ 假 ” 。 4 定義五種聯(lián)結(jié)詞（或稱命題的五種運(yùn)算）。 例 4 設(shè) P：上海是一個(gè)城市； Q：每個(gè)自然數(shù)都是偶數(shù)。 例 5 設(shè) P：我們?nèi)タ措娪啊? 則命題可表示為 P∨ Q。 ”表示，故我們不把它當(dāng)作 基本 聯(lián)結(jié)詞。 則 P→Q 和 P→R 所表示的命題都是真的 . 9 5．等值“ ? ” 定義 95 由命題 P和 Q，利用“ ? ”組成的復(fù)合命題，稱為等值式復(fù)合命題，記作“ P?Q” （讀作“ P當(dāng)且僅當(dāng) Q”）。基本步驟如下： （ 1）從語句中分析出各原子命題，將它們符號(hào)化； （ 2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個(gè)聯(lián)結(jié)起來，組成復(fù)合命題的符號(hào)化表示。Q） → R； （ 1）（ P∨ Q） → 172。則命題可 表示為 172。P → Q） ∧ （ P→ R） 。P∧ 172。 定義 96 （命題公式的遞歸定義。 定義 9—7 設(shè) F為含有命題變?cè)?P1， P2， … ,Pn的命題公式，對(duì) P1， P2， … ,Pn分別指定一個(gè)真值 ,稱為對(duì)公式 F的一組 真值指派 。如果至少有一組真值指派使公式 F的真值為真，則稱 F為 可滿足公式 。（ P ? Q）， F2=（ Q→ P） ∧ （ 172。 注意 ： （ 1）符號(hào) “ ?” 與 “ ? ” 的區(qū)別與聯(lián)系。 （ 3）當(dāng) A是重言式時(shí)， A?1；當(dāng) A是矛盾式時(shí)，則 A?0。 例如 設(shè)公式 A=（ ?P∨Q ） ?（（ P?Q） ∨ （ R∧ ?S））。稱 “ A?B”為 蘊(yùn)含式 。 反對(duì)稱性的證明： 設(shè) A?B且 B?A， 由定義 711 A?B?1且 B?A?1 于是 A?B?(A?B)?(B?A) E14 ? 1?1 ? 1 因此 A?B 34 傳遞性的證明： 設(shè) A?B， B?C， 則 A?B?1， B?C?1 ? (?A?B?C)?(?A??B?C) ? ((A?B) ?C)?(?A?(B?C)) ? (1?C)?(?A?1) ? 1?1 ? 1 因此 A?C. 于是 A?C ?? A?C ? (?A?C)?(B??B) 35 四 、 基本的蘊(yùn)含式 編號(hào) 蘊(yùn) 含 式 I1 P?Q?P I2 P?Q?Q I3 P ?P?Q I4 Q?P?Q I5 ?P ?P?Q I6 Q?P?Q I7 ?(P?Q)?P I8 ?(P?Q)? ?Q 設(shè) P、 Q、 R是命題變?cè)?， 下表中列出了 16個(gè)最基本的蘊(yùn)含式 。 41 假定后件 B假 假定后件 B為假，檢查在此情況下，其前件 A是否也為假 . 例 7 證明蘊(yùn)含式 (P?Q) ? (R?S) ? (P?R) ? (Q?S) 證明 令后件 (P?R)?(Q?S)為假 ， 則 P?R為真 ， Q?S為假 , 于是 P、 R均為真 ， 而 Q和 S至少一個(gè)為假 。 44 范式 一、 析取范式和合取范式 定義 912 一個(gè)命題公式若它具有P1*∧P 2*∧ … ∧P n*的形式（ n≥1 ），其中 Pi*是命題變?cè)?Pi或其否定 172。R是由命題變?cè)?P、 Q、 R組成的一質(zhì)析取式。(i =1,2,… n).這樣的一組真值指派使 A的真值取 0，這與 A為永真式矛盾。 定義 915 質(zhì)析取式的合取稱為合取范式。 三、利用范式判定公式類型 證明 （ 2） 必要性 （用反證法）： 假設(shè) A＝ A1∨ A2∨ … ∨ An中某個(gè) Ai不包含一對(duì)互為否定的合取項(xiàng)， （ 2）公式 A為永假式的充分必要條件是， A的析取范式中每一質(zhì)合取式至少包含一對(duì)互為否定的合取項(xiàng)。 解 A? ?P∨(P∧( ?Q∨P)) E 11 ? ?P∨(P∧ ?Q)∨(P∧P) ( 析取范式 ) E3 根據(jù)定理 95， A不是矛盾式。其中 Pi*為 Pi或?yàn)? ?Pi(i=1,2,… n). 例如 ,P1∧P 2∧P 3， ?P1∧P 2∧ ?P3均是由 P1， P2， P3所產(chǎn)生的最小項(xiàng)。 永真公式 的主析取范式包含所有 2n個(gè)最小項(xiàng)。 (2) 若 F的主析取范式是一空公式且為 0，則 F是永假公式。 62 (2) 求 F的主合取范式 F ?（ ?Q?(P??Q))?P ? P??Q 由前分析和舉例可知： 僅需求出公式 F的任一種主范式即可判定 F的類型 。Q P→ Q （ P→ Q） ∧ P (（ P→ Q） ∧ P) →Q 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 例 1 考察結(jié)論 C是否是下列前提 H1， H2的結(jié)論。Q 1 0 1 1 P Q 0 0 0 1 1 0 1 1 在這里，我們不關(guān)心結(jié)論是真還是假，而主要關(guān)心由給定的前提是否能推出這個(gè)結(jié)論來。通過合理證明而得到的結(jié)論稱作合理的結(jié)論。 S ? R∧ （ P∨ Q) 編號(hào) 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） P→ S 172。 Q∨ （ 172。 A， D→ 172。D 前提 前提 （ 1），（ 2）； I11 （ 2）； E6 前提 （ 4），（ 5）； I12 （ 3），（ 6）； I10 前提 （ 7） ,（ 8）； I12 74 間接證明 (或反證法 ) 定義 920 如果對(duì)于出現(xiàn)在公式 H1， H2， … ,Hn中的命題變?cè)娜魏我唤M真值指派，公式 H1， H2， … ,Hn中至少有一個(gè)為假，即它們的合取式 H1 ∧H 2∧ … ∧H n是矛盾式，則稱公式 H1， H2， … Hn是不相容的。 則意味著（ H1 ∧H 2∧ … ∧H n） → （ R∧ 172。（ 172。Q Q∧ 172。S的結(jié)論。Q 前提 前提 （ 1），（ 2）； I10 前提 （ 4）； E11 （ 4），（ 5）； I10 （ 6）； E10ノ 因此，（ P∧ Q） → R， 172。 （ 2） R 前提 （ 3） 172。 Q， 172。 80 因此，由上述推理知張三說假話，王五說假話，只有李四說真話。P∨ （ 172。R （ 7），（ 9），（ 11）； I9