N的推理规则(续三) ∧消去律 若Fa∧, 则厂Fa,「月 ∧ ∧引入律: 若厂Fa,「FB, 则+(aA6) (∧+)
N ( ) ∧ : Γ ` α ∧ β, Γ ` α, Γ ` β. (∧−) ∧ : Γ ` α, Γ ` β, Γ ` (α ∧ β). (∧+) 10
N的推理规则(续四) ∽→消去律 (1)若「a46,「a 则厂FB. (2)若「a台B,「FB 则十 ←引入律 若「U{a}+,「U{}a 则+(a+B) (+)
N ( ) ↔ : (1) Γ ` α ↔ β, Γ ` α Γ ` β. (↔ −) (2) Γ ` α ↔ β, Γ ` β Γ ` α. (↔ −) ↔ : Γ ∪ {α} ` β, Γ ∪ {β} ` α, Γ ` (α ↔ β). (↔ +) 11
用形式系统N可以做什么? 例2.12 (1){(a→6),(6→),a}+(a→) (∈) (2){(a→B),(→y),a}+a (3){(a→),(→?),a}+B )(1)(2 (4){(a→),(6→),a}+(→) ∈ (5){(α→3),(→?),y}hy (→-)(3)(4) (6){(a→B),(→)}F(a→?) (→+)(5)
N ? 2.12 (1) {(α → β), (β → γ), α} ` (α → β) (∈) (2) {(α → β), (β → γ), α} ` α (∈) (3) {(α → β), (β → γ), α} ` β (→ −)(1)(2) (4) {(α → β), (β → γ), α} ` (β → γ) (∈) (5) {(α → β), (β → γ), α} ` γ (→ −)(3)(4) (6) {(α → β), (β → γ)} ` (α → γ) (→ +)(5) 12
N的证明序列 定义13若有限序列 1Fa1,2Fa2, 满足: 「1,「2,…,「n为N中有限公式集; a1,Q2,…,am为N中公式; 每个「}a;(1<≤m)都是对(*)中它之前的若干个 a;(1≤j<i≤n)应用N的某条推演规则得到的。 则称(米)为「n+an在N的一个(形式)证明序列。 此时,也称αn在N中可由「n(形式)证明或(形式)推出,记为 N 由例12知:{(a→),(3→?)}N(a→7)
N ✢✣13 ✤✥✦✧★ Γ1 ` α1, Γ2 ` α2, · · · , Γn ` αn (∗) ✩✪✫ • Γ1, Γ2, · · · , Γn✬N✥✭✦✮✯✰✱ • α1, α2, · · · , αn✬N✭✮✯; • ✲✳Γi ` αi (1 ≤ i ≤ n)✴✵✶(∗)✭✷✸✹✺✤✻✳ Γj ` αj (1 ≤ j < i ≤ n)✼✽✺N ✾✿❀❁❂❃❄❅✺❆ ❃❇(∗✬) Γn ` αn❈✺N ❉ ✳(❊✯)❋●✧★❆ ❍■, ❏❇α❈n N✭❑▲Γn(❊✯)❋●▼(❊✯❀) ◆, ❖✬ Γn `N αn. ▲P12◗: {(α → β), (β → γ)} `N (α → γ) 13
汪记 1.命题形式与N公式在定义上虽然一样,木质上也 样,都是命题的抽象,但他们仍有差别:N公 式仅由N中符号构成。命题形式由命题符号构 成,而命题符号要广泛得多 2.形式语言与与元语言 (a)N中的符号和公式称为N的形式语言。它描写 了N的组成部分。 (b)在叙述N的构成和性质时使用了非N中符号, 如a,等,这些符号称为元语言符号。 元语言一般为自然语言
1. N ❘ , ❘ ✙✙: N ❙N ✖❙ ✙ 2. (a) N N ✖ N ✖ (b) N N ✙ α, β ✙✖ ❘ ❚✖ 14