【正文】 (2) ~(p∧ ~q), ~q∨ r, ~r? ~p (3) p→ (q→r), q, p∨ ~s? s→r First Order Logic 謂詞和量詞 Predicate and Quantifiers 1 謂詞 Predicate 關(guān)系 Relation 集合 {x|P(x)}中 P(x) 變?cè)?x滿足某種性質(zhì) 稱(chēng) P(x)為一元謂詞 ,或一元關(guān)系 Q(x,y) 二元謂詞二元關(guān)系 R(x,y,z) 三元謂詞三元關(guān)系 論域 A中元素 a,b,c∈ A,滿足關(guān)系 P,Q,R，記作 P(a),Q(a,b),R(a,b,c). 不滿足關(guān)系記作 ~P(a),~Q(a,b),~R(a,b,c). 函數(shù) Function 論域 A上的函數(shù)是一種特殊的關(guān)系，也是謂詞 F:A→A，一元函數(shù)，也是二元關(guān)系 對(duì)任意 x∈ A, F(x) ∈ A, F(x)唯一確定。 2 量詞 Quantifier 全稱(chēng)量詞 Universal Quantifier ? ? xP(x), ? yQ(x,y) 存在量詞 Existencial Quantifier ? ? xP(x), ? x? yQ(x,y) 一階邏輯的符號(hào)集 語(yǔ)言 Language 1 邏輯符號(hào) 個(gè)體變?cè)?v1,v2,v3,…… 命題聯(lián)結(jié)符號(hào) ~， ∨ ， ∧ ， →， ? 量詞符號(hào) ? ， ? 等號(hào) = 技術(shù)符號(hào)），（ 2 非邏輯符號(hào) 關(guān)系符號(hào) P,Q,R,…… 每個(gè)關(guān)系符號(hào)都指定是幾元關(guān)系 函數(shù)符號(hào) F,G,H,…… 每個(gè)函數(shù)符號(hào)都指定是幾元函數(shù) 常量符號(hào) a,b,c,…… 2 一階語(yǔ)言 L ={P,Q,R,…… 。 例 L={+， ， 0,1} v1+v2 +1 是 L的項(xiàng)。 ? v1 (v1 +1=0) ? v2 (v1+ v2 +10) ? v1 (v1 +1=0 →? v2 (v1+ v2 +10) ) 量詞的轄域約束變?cè)妥杂勺冊(cè)? ? v1 (v1 +1=0) 量詞的轄域是全公式。 一階語(yǔ)言 L的 一個(gè)句子集叫做一個(gè)理論。FM,GM,HM,… 。 M╞σ φ(x1,x2,…… ,xn) 當(dāng)且僅當(dāng) M╞φ(x1σ ,x2σ ,…… ,xnσ ) 如果 x1σ =a1, x2σ =a2, …… ,xnσ =an, 則 M╞σ φ(x1,x2,…… ,xn)也寫(xiě)成 M╞φ(a1,a2,…… ,an). 閉公式在模型中的取值與指派 σ無(wú)關(guān) ， 如果存在一個(gè)指派 σ ， M╞φ，則對(duì)任意指派 M╞φ。 可滿足公式 如果公式 φ (x1,x2,…… ,xn), 存在模型，存在指派取值為真，就稱(chēng)為可滿足公式。 4) ╞? x(φ∧ ψ) →? xφ∧ ? xψ 5) ╞? x (φ∨ ψ) →? xφ∨ ? xψ Prove each of the following is not a tautology 1) φ(x) →? xφ(x), 2)? x? yφ(x,y)→? y? xφ(x,y). 一階公式的等價(jià)變換 1 等價(jià)公式 如果一階公式 φ(x1,x2,…… ,xn), ψ(x1,x2,…… ,xn)在任何模型，任何指派下都有相同取值，就稱(chēng)φ(x1,x2,…… ,xn), ψ(x1,x2,…… ,xn)是等價(jià)公式 ，記作 φ(x1,x2,…… ,xn) ?ψ(x1,x2,…… ,xn)。 Q1x1Q2x2…… Qnxnφ φ是無(wú)量詞公式 quantifier free, Qi 或是 ? 或是 ? 。 φ1, φ2,……, φn? ψ當(dāng)且僅當(dāng) ╞φ1, ╞φ2,…, ╞φn ? ╞ψ。 基本推理 1) φ(x)? ? xφ(x)， 2) ? x(φ→ψ)? ? xφ→? xψ 3) ? x(φ→ψ)? ? xφ→? xψ。 10) 推廣法則 G φ(x) ? ? xφ(x), x 不在前提條件中資又出現(xiàn)。 設(shè) A ??, 由 N是歸納集， A 有最小元 k， k A? , k A? . 由 a) 有 k0, k1?0。 證明 令 A={n?N | P(n)}, A?N. 則滿足 a) 0?A, b) k∈ A?k+1∈ A. 由歸納原理 A=N,即 ? n?N P(n) 成立。 第一歸納法的推廣 關(guān)于整數(shù)的一個(gè)性質(zhì) P(x), 如果有 a) P(n0)成立， n0?Z b) P(k)?P(k+1), k?n0. 則 ? n?n0P(n)成立。 由 b)有 k?A，得到矛盾。 設(shè) A??, 由 A是歸納集， A有最小元 k， ~P(k). 由 a) 有 k0。 例 6． 每個(gè)大于 1 的正整數(shù) n都能唯一地表示為素因子的乘積： n= p1?1p2?2…… ps?s, 其中 p1p2…… ps 都是素?cái)?shù)。 i 如果 k 是素?cái)?shù)，命題成立。 如果 pi=qj=tw , ?i=?j +?w. 由 l， m 唯一分解，知 k 唯一分解。 設(shè) A有 k 個(gè)命題聯(lián)結(jié)詞。這時(shí) A*=B*?C*， B,C所含聯(lián)結(jié)詞少于 k 個(gè)，歸納假設(shè) 1)對(duì) B,C都成立。 3 雙重歸納法 關(guān)于自然數(shù)的一個(gè)性質(zhì) P(x, y), 如果有 a) P(0,0)成立， b) P(s,t) ?P(s+1,t) ?P(s,t+1) 則 ? xyP(x,y) 成立。 補(bǔ) {an}的遞推關(guān)系是 an+1=2an+1(n∈ N)， a1=1，求數(shù)列的通項(xiàng)公式 an. 。 2） ? x P(x,t) ?? x P(x,t+1) a) P(x,t)成立 b) P(x,t) ?P(x,t+1) 由第一歸納法 ? xyP(x,y) 成立。 A(~p1,~p2,…… ,~pn) =B(~p1,~p2,…… ,~pn)?C(~p1,~p2,…… ,~pn) ?~ B*(p1,p2,…… ,pn)?~C*(p1,p2,…… ,pn) ?~(B*(p1,p2,…… ,pn)?C*(p1,p2,…… ,pn)) ?~A*(p1,p2,…… ,pn) 歸納完成，因此 1)對(duì)任意不含聯(lián)結(jié)詞 ?， ?的命題公式成立。這時(shí) A*=~B*， B所含聯(lián)結(jié)詞少于 k 個(gè)，歸納假設(shè) 1)對(duì) B成立。 例 7. 設(shè) A(p1,p2,…… ,pn)是一個(gè)不含聯(lián)結(jié)詞 ?， ?的命題公式， A*是 A的對(duì)偶公式，則 1) A(~p1,~p2,…… ,~pn) ?~A*(p1,p2,…… ,pn) 2) A?B當(dāng)且僅當(dāng) A* ?B* 證明 1) 對(duì)公式的復(fù)雜性 (聯(lián)結(jié)詞的 個(gè)數(shù) n)歸納， n=0, 即公式 A(p1,p2,…… ,pn)= pi, 是單個(gè)命題變?cè)獩](méi)有聯(lián)結(jié)詞 . A(~p1,~p2,…… ,~pn)= ~pi ~A*(p1,p2,…… ,pn)= ~pi. 設(shè)對(duì)少于 k 個(gè)聯(lián)結(jié)詞的命題公式， 1）都成立。 如果 pi=qj , ?i=?j。 b) 設(shè) n=2,3,…… ,k1 時(shí)命題真。 因此 ? nP(n) 成立。 第二歸納法 strong form of mathematical induction, Strong Induction 關(guān)于自然數(shù)的一個(gè)性質(zhì) P(x), 如果有 a) P(0)成立， b) ? skP(s)?P(k), 則 ? nP(n)成立。 設(shè) A ??, 由 N是歸納集， A 有最小元 k， k A? , k A? . 由 a) 有 k0。 || 11iniA???= || 11??niniAA ?? = ||1iniA??+|An+1| || 11??niniAA ?? = ||1iniA??+|An+1| |)(| 11??niniAA ?? = ?? ?? ??? ??nji jijinii AAA1,1|||| ????????? ????niiiikiikkAAA1,21112,1||)1(||)1( 211 nn AAA ??????? +|An+1|????? ?? ??? ?????nji jinjninini AAAAAA1,1111 ||||( ?????????? ?????niiinikiikkAAAA1,121112,1||)1(|)|)1( 1211 ???? nnn AAAA ????? = ?? ?? ?? ?? ???11,11|||| nji jijinii AAA ????????? ?????11,21112,1||)1( niiiikiikkAAA||)1( 121 ??? nn AAA ???? 例 3 Function SQ(A) 1. C?0 2. D?0 (D?A) a. C?C+A b. D?D+1 4. Return(C) End of Function SQ 解 . 先猜測(cè)結(jié)果 第一輪 C1=A , D1=1 第二輪 C2=A+A=2A, D2=2 第三輪 C3=2A+A=3A, D3=3 猜 Cn=