【正文】 →? yQ(x,y)→? zR(x,z) ? ? u P(u,y) →? vQ(x,v)→? zR(x,z) ? ? u P(u,y) →? z(? vQ(x,v)→R(x,z)) ?? u P(u,y) →? z? v (Q(x,v)→R(x,z)) ?? z? v(? u P(u,y) →(Q(x,v)→R(x,z))) ?? z? v? u (P(u,y) →(Q(x,v)→R(x,z))) Homework 求下列各式的前束范式 1） ~? xQ(x)→? yR(x,y) 2) ~(? x P(x,y) ∨ ? yQ(x,y)) 3) ? x P(x) ∨ ? yQ(x,y) 4) ? x(Q(x) ∧ ? y P(x,y,z)) →? zR(x,y,z) 一階邏輯的推理 單前提推理：設(shè) φ, ψ都是命題公式，如果 φ→ψ是恒真式，就稱由 φ推出 ψ是一個(gè)正確的推理，記作 φ? ψ。 Q1x1Q2x2…… Qnxnφ φ是無量詞公式 quantifier free, Qi 或是 ? 或是 ? 。 2 基本等價(jià)公式 命題邏輯的等價(jià)形式也是一階邏輯的等價(jià)形式 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φ→ψ 利用基本公式可以做公式的等價(jià)變換，可以將公式化簡，可以將公式化成某種標(biāo)準(zhǔn)形式。 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)在任何模型，任何指派下都有相同取值，就稱φ(x1,x2,…… ,xn), ψ(x1,x2,…… ,xn)是等價(jià)公式 ，記作 φ(x1,x2,…… ,xn) ?ψ(x1,x2,…… ,xn)。 命題邏輯的所有恒真形式都是恒真式。 可滿足公式 如果公式 φ (x1,x2,…… ,xn), 存在模型，存在指派取值為真，就稱為可滿足公式。 如果公式 φ(x1,x2,…… ,xn), 在任何模型，任何指派下取值都是真，就稱為恒真式 , 記作 ╞φ。 M╞σ φ(x1,x2,…… ,xn) 當(dāng)且僅當(dāng) M╞φ(x1σ ,x2σ ,…… ,xnσ ) 如果 x1σ =a1, x2σ =a2, …… ,xnσ =an, 則 M╞σ φ(x1,x2,…… ,xn)也寫成 M╞φ(a1,a2,…… ,an). 閉公式在模型中的取值與指派 σ無關(guān) ， 如果存在一個(gè)指派 σ ， M╞φ，則對(duì)任意指派 M╞φ。 一階公式的賦值 一階公式在模型 M上的賦值。FM,GM,HM,… 。F,G,H,… 。 一階語言 L的 一個(gè)句子集叫做一個(gè)理論。 v2是約束變?cè)?, v1是自由變?cè)? ? v1 (v1 + v2+1=0 →? v2 (v1+ v2 +10)) ? v2 的轄域是 (v1+ v2 +10) ? v1的轄域是全公式， v1是約束變?cè)?，第二個(gè) v2是約束變?cè)?，第一個(gè) v2是自由變?cè)?. 公式常記作 φ(x1,x2,…… ,xn), φ中自由變?cè)荚?x1,x2,……,x n中。 ? v1 (v1 +1=0) ? v2 (v1+ v2 +10) ? v1 (v1 +1=0 →? v2 (v1+ v2 +10) ) 量詞的轄域約束變?cè)妥杂勺冊(cè)? ? v1 (v1 +1=0) 量詞的轄域是全公式。 v1 +1=0 v1+v2 +10 都是原子公式。 例 L={+， ， 0,1} v1+v2 +1 是 L的項(xiàng)。a,b,c…… } 非邏輯符號(hào)屬于每一個(gè)一階語言。 2 量詞 Quantifier 全稱量詞 Universal Quantifier ? ? xP(x), ? yQ(x,y) 存在量詞 Existencial Quantifier ? ? xP(x), ? x? yQ(x,y) 一階邏輯的符號(hào)集 語言 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 一階語言 L ={P,Q,R,…… 。 對(duì) a,b,c∈ A, 如果 F(a)=b, 就說 F(a)=b 真。 例 . 構(gòu)造下列推理的論證 deduction (1) p∨ q, p→~r, s→t, ~s→r, ~t?q ① s→t hypothesis ② ~t hypothesis ③ ~s Thm5(b) ④ ~s→r hypothesis ⑤ r Thm5(a) ⑥ p→~r hypothesis ⑦ ~p Thm5(b) ⑧ p∨ q hypothesis ⑨ q Thm5(c) Theorem (Deduction Theorem) A1,A2,…, A n ? A→B if and only if A1,A2,…, A n , A? B Homework 1. Prove the following equivalent formulas (1) ~(p?q) ? (p∨ q)∧ ~(p∧ q) (2) (p→r)∨ (q→r) ? (p∨ q) →r 2. Give the normal disjunction formumlas of the following statements (1) ((p∨ q) →r) →p ~q p→ q ~p p→ q q→ r p→ r p∨ q p→ r q→ s r∨ s (2) ~( p→q)∧ q∧ r 3. Give the deductions of the following consequence (1) p→q, r→~q, r∨ s, s→~q? ~p (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ì) 稱 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)唯一確定。 對(duì)任意賦值 σ，若 A1σ=1, A2σ=1, …,A nσ=1 則對(duì)每個(gè) i, 1≤i≤n, 都有 Biσ=1, 因此 Bσ=1。 A1,A2,…,A n ?B 當(dāng)且僅當(dāng) 對(duì)任意賦值 σ， A1σ=1,A2σ=1,…,A nσ=1 ?Bσ=1 由于 A1∧ A2∧ … ∧ An→B ? A1→A2→…→A n→B 若 A1→A2→…→A n→B是恒真式，則 A1,A2,…,A n?B。 命題邏輯的推理 deduction on proposition logic 單前提推理：設(shè) A, B 都是命題公式，如果 A→B是恒真式，就稱由 A推出 B是一個(gè)正確的推理，記作 A? B。 {∨ }， {∧ }， {→}， {~， ? } 都不是全功能集。 令 p↑q? ~( p∧ q) ↑與非 p↓q ? ~(p∨ q) ↓或非 ~p? p↑p ? p↓p p∧ q? ~(p↑q) ? (p↑q)↑(p↑q) p∨ q ? ~( p↓q) ? ( p↓q)↓( p↓q) p q p↑q P↓q 0 0 1 1 0 1 1 0 1 0 1 0 1 1