【正文】 證明 1) ? xP(x,0)成立： a) P(0,0)成立， b) P(s,0) ?P(s+1,0) 由第一歸納法 ? xP(x,0) 成立。 情形 i) A=~B。 ii 如果 k 不是素數(shù)， k=lm, 2?l?k1, 2?m?k1. 對 l,m 命題成立 : l= q1?1q2?2…… qu?u, m= t1?1t2?2…… tv?v, 則 k=lm= q1?1q2?2…… qu?u t1?1t2?2…… tv?v = p1?1p2?2…… ps?s。 于是有 ? skP(s)成立 . 由 b)有 P(k)成立，得到矛盾。 例 4. 證明存 在 n0?Z,使 ? n? n0 (2nn3) 2 第二歸納原理 如果 A?N, A 是自然數(shù)集合 N的具有以下性質(zhì)的子集： a) 0∈ A b) ? sk(s∈ A)?k∈ A 那么 A=N 證明 . 我們只要證明 A =?。于是有 k1 A? , k1 A? . 由 b)有 k?A，得到矛盾。 4) ? xφ∨ ? xψ? ? x(φ∨ ψ) 5) ? x (φ∧ ψ) ? ? xφ∧ ? xψ 6) ? xφ(x)? φ(x/t), t 相對于 x在 φ(x)中自由，即 t是 x或是不在 φ(x)中出現(xiàn)的變元或是一個常量。 定理 任何一個一階公式都等價于一個前束標(biāo)準(zhǔn)型公式。 ╞φ→ φ， ╞φ→ ψ→ φ。aM,bM,cM… 〉 A 是論域 Universe， PM,QM,RM,…是 A的關(guān)系 FM,GM,HM,…是 A上函數(shù) aM,bM,cM… 是 A 的元素 例 〈N,+,0〉,〈N,+,?,0〉, 〈Z,+,?,0,1〉,〈R,+,?,0,1〉, 〈Zn,+,?,0,1〉 都是模型。 v1是約束變元 ? v2 (v1+ v2 +10) 量詞的轄域是全公式。F,G,H,…… 。 Theorem 5 多前提基本推理 (a) p, p→q ? q (b) ~q, p→q ? ~p (c) ~q, p∨ q ? p (d) p→q, q→r ? p→r (e) p∨ q, p→r , q→s ? r∨ s (f) p∨ q, p→r , q→r ? r p→q p q ~q p∨ q p 稱命題公式序列 B1,B2,……,B m=B為從 A1,A2,……,A n到 B的一個證明 (論證Deduction), 如果每個 Bi, 1≤i≤m, 或是某個 Aj, 或是由其前面若干公式推出 . 如果存在 A1,A2,……,A n到 B的一個論證則 A1,A2,…,A n? B。 由 p∨ q ?~ p→q知 {~， →}也是全功能集。 先給出命題公式 A的真值表，找出取值為 0的所有賦值，這些賦值對應(yīng)的基本析取項的合取就是 A的合取范式。 p1p2p3的 8 個基本合取項為 p1∧ p2∧ p3， p1∧ p2∧ ~p3， p1∧ ~p2∧ p3， ~p1∧ p2∧ p3， p1∧ ~p2∧ ~p3， ~p1∧ ~p2∧ p3， ~p1∧ p2∧ ~p3， ~p1∧ ~p2∧ ~p3。 但 pσ不可能同時取值 1和 0，矛盾。 存在賦值 σ， Aσ=1, A就是可滿足的。 例 A=((p∧ (~q)) →(((~p)∨ q) ∧ q)) 是命題公式 . 可以省略最外層的括號 : A=(p∧ (~q)) →(((~p)∨ q) ∧ q). 規(guī)定命題連接詞的優(yōu)先級： ~， ∧ ， ∨ ， →， ?，左邊高于右邊。 (1) 地球是圓的并且 2+3=5. p∧ q (2) 土星表面溫度不是華氏 800度。 r (7) 明天會出太陽。 q→s (6) 明天出太陽，僅當(dāng) 2+3=5。 恒假式 矛盾式 contradiction, absurdity 無論命題變元取什么值，命題公式取值都是 0(假 )的公式。 用真值表可以判定一個公式是否恒真式，恒假式，可滿足公式，可以判斷兩個公式是否等價。 化簡命題公式 A= p∧ ~q →(~p∨ q) ∧ q. 解 A ? ~(p∧ ~q) ∨ (~p∨ q) ∧ q ?(~p∨ q)∨ ((~p∨ q) ∧ q) ?~p∨ q 對偶公式 dual propositions formula 不含聯(lián)結(jié)詞 →， ?的命題公式 A中，將 ∨ 換成 ∧ ，將 ∧ 換成 ∨ ，如果有 0， 1，就將0 換成 1， 1換成 0，所的命題公式稱為 A的對偶公式 ,記作 A*. (A*)*=A, 即 A, A*互為對偶公式 . (p∧ q )*= p∨ q (~(p∨ q))*=~( p∧ q ) (~p ∨ (q ∧ r))*=~p∧ (q∨ r) Proposition 設(shè) A, B 是兩個命題公式， A ? B 則 A* ? B*。 p1p2p3的 8 個基本合取項為 p1∨ p2∨ p3， p1∨ p2∨ ~p3， p1∨ ~p2∨ p3， ~p1∨ p2∨ p3， p1∨ ~p2∨ ~p3， ~p1∨ ~p∨ p3， ~p1∨ p2∨ ~p3， ~p1∨ ~p2∨ ~p3。 {~， ∨ ， ∧ } 是一個全功能集。 命題邏輯的推理 deduction on proposition logic 單前提推理：設(shè) A, B 都是命題公式，如果 A→B是恒真式，就稱由 A推出 B是一個正確的推理，記作 A? B。 對 a,b,c∈ A, 如果 F(a)=b, 就說 F(a)=b 真。 v1 +1=0 v1+v2 +10 都是原子公式。F,G,H,… 。 如果公式 φ(x1,x2,…… ,xn), 在任何模型，任何指派下取值都是真，就稱為恒真式 , 記作 ╞φ。 2 基本等價公式 命題邏輯的等價形式也是一階邏輯的等價形式 1) ? xφ?~? x ~φ 2) ? xφ?~? x ~φ 3) ~? xφ?? x ~φ 4) ~? xφ?? x ~φ 4) ? x(φ∧ ψ) ?? xφ∧ ? xψ 5) ? x(φ∨ ψ) ?? xφ∨ ? xψ 如果 x 不在 φ中自由出現(xiàn) 6) ? x(φ∨ ψ) ? φ∨ ? xψ 7) ? x(φ∧ ψ) ? φ∧ ? xψ 如果 x 不在 φ中自由出現(xiàn) 8） ? x (φ→ψ) ?φ→? xψ 9） ? x (φ→ψ) ?φ→? xψ 如果 x 不在 ψ中自由出現(xiàn) 10） ? x(φ→ψ)?? xφ→ψ 11） ? x(φ→ψ)?? xφ→ψ 利用基本公式可以做公式的等價變換，可以將公式化簡，可以將公式化成某種標(biāo)準(zhǔn)形式。 若 ╞φ1, ╞φ2,…, ╞φn 則對每個 i, 1≤i≤n, 都有 ╞ψi, 因此 ╞ψ。 Proof. Let W(x) : x 是學(xué)術(shù)委員會成員， S(x) : x 是教師， Z(x): x 是專家 Q(x): x 年輕 To prove: ? x(W(x) →S(x) ∧ Z(x) ), ? x(W(x) ∧ Q(x)) ? ? x(W(x) ∧ Q(x) ∧ S(x)) 1) ? x(W(x) ∧ Q(x)) 2) W(c)∧ Q(c) 3) W(c) 4) Q(c) 5) ? x(W(x) →S(x)∧ Z(x)) 6) W(c) →S(c) ∧ Z(c) 7) S(c) ∧ Z(c) 8) S(c) 9) W(c) ∧ Q(c) ∧ S(c) 10) ? x(W(x) ∧ Q(x)∧ S(x)) 例 . ~? x(F(x) ∧ H(x)), ? x(G(x) →H(x)) ? ? x (G(x) →~F(x)) Proof 1) ~? x(F(x)∧ H(x)) 2) ? x ~( F(x) ∧ H(x)) 3) ? x(~F(x)∨ ~H(x)) 4) ~F(x) ∨ ~ H(x) 5) H(x) →~F(x) 6) ? x(G(x) →H(x)) 7) G(x) →H(x) 8) G(x) →~F(x) 9) ? x(G(x) →~F(x)) 指出下列推理的錯誤： 1） ? x(F(x)∧ H(x))? ? yF(y) 2) ? x F(x),? x H(x) ? ? y(F(y)∧ H(y)) 3) ? x(G(x) →F(x)), ~F(x) ? ? y~G(y) Homework Give proves for the following 1) ? x(F(x) →G(x)), ? yF(y) ? ? zG(z) 2) ? x(F(x)→G(x)), ~G(y)? ~F(y) 3) 每個喜歡看書的人都不喜歡看電影， 每個人或者喜歡看電影或者喜歡聽音樂，有人不喜歡聽音樂，因此有人不喜歡看書 。 || 11iniA???= || 11??niniAA ?? = ||1iniA??+|An+1| || 11??niniAA ?? = ||1iniA??+|An+1| |)(| 11??niniAA ?? = ?? ?? ??? ??nji jijinii AAA1,1|||| ????????? ????niiiikiikkAAA