数理逻辑 I Mathematical Logic I

Size: px

Start display at page:

Download "数理逻辑 I Mathematical Logic I"

泔计贺
5 years ago
Views:

1 前情提要

2 前情提要一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法

3 前情提要一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法

4 前情提要一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法

5 前情提要一阶逻辑公理系统的元定理承自命题逻辑的元定理 : 演绎定理重言规则逆否命题反证法

6 前情提要一阶逻辑公理系统的元定理一阶逻辑特色的元定理 : 概括定理常数概括定理约束变元替换定理

7 前情提要一阶逻辑公理系统的元定理一阶逻辑特色的元定理 : 概括定理常数概括定理约束变元替换定理

8 前情提要一阶逻辑公理系统的元定理一阶逻辑特色的元定理 : 概括定理常数概括定理约束变元替换定理

9 前束范式

10 前束范式定义 ( 量词前束公式 ) 我们称具有 Q 1 x 1... Q n x n α 形式 ( 其中 Q i 是或, 且 α 不含量词 ) 的公式为量词前束公式

11 前束范式定理 ( 前束范式定理 ) 对任何公式 α 都存在量词前束公式 α, 使得 α α

12 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

13 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

14 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

15 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

16 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

17 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

18 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

19 前束范式用到的元定理 Q1a xα x α Q1b xα x α Q2a (α xβ) x(α β) Q2b (α xβ) x(α β) Q3a ( xα β) x(α β) Q3b ( xα β) x(α β) 如果 x 不在 α 中自由出现如果 x 不在 α 中自由出现如果 x 不在 β 中自由出现如果 x 不在 β 中自由出现

20 前束范式 Proof. 对公式 α 归纳证明 : 若 α 是原子公式若 α = xβ 若 α = β 若 α = β γ

21 前束范式 Proof. 对公式 α 归纳证明 : 若 α 是原子公式若 α = xβ 若 α = β 若 α = β γ

22 前束范式 Proof. 对公式 α 归纳证明 : 若 α 是原子公式若 α = xβ 若 α = β 若 α = β γ

23 前束范式 Proof. 对公式 α 归纳证明 : 若 α 是原子公式若 α = xβ 若 α = β 若 α = β γ

24 一阶逻辑语言的语义

25 回顾命题逻辑的语义命题逻辑的语义 : 命题符号的语义由真值指派给出 :v : S {0, 1} 命题 ( 公式 ) 的语义 v : WFF {0, 1} 取决于命题符号的语义命题联词 ( 逻辑符号 ) 的语义及其自身构造而命题联词的语义体现于映射 v v, 不依赖于特定的语义解释 v

26 一阶逻辑语言的语义具有固定语义解释的符号 : 命题联词等词可以有不同解释的符号 : 常数符号谓词符号函数符号量词

27 一阶逻辑语言的语义具有固定语义解释的符号 : 命题联词等词可以有不同解释的符号 : 常数符号谓词符号函数符号量词

28 一阶逻辑语言的语义具有固定语义解释的符号 ( 逻辑符号 ): 命题联词等词可以有不同解释的符号 : 常数符号谓词符号函数符号量词

29 一阶逻辑语言的语义具有固定语义解释的符号 ( 逻辑符号 ): 命题联词等词可以有不同解释的符号 ( 参数符号 ): 常数符号谓词符号函数符号量词

30 一阶逻辑的语义需要特殊处理的符号变元约束出现的变元自由出现的变元

31 一阶逻辑的语义对参数符号的解释结构定义 ( 结构 ) L 是一阶语言, 一个 L- 结构 A 是一个以 L 中参数符号为定义域的函数并满足 : A( ) 是一个非空集合, 记 A, 称作 A 的论域对 n 元谓词符号 P,A(P) 记作 P A,P A A n 对 n 元函数符号 f,a(f) 记作 f A,f A : A n A 对常数符号 c,a(c) 记作 c A,c A A

32 一阶逻辑的语义例给定语言 L = {R},R 是一个二元谓词符号 v 1 v 2 Rv 1 v 2 和 v 2 v 1 Rv 1 v 2 的意思是? 若令 A 是一个 L- 结构, 且 A = N,R A 是 N 上的大于等于关系 N, 那么上述公式在这个解释下的意思是? R A 是小于关系 < N 呢? A = {0, 1, 2, 3, 4, 5} 呢?

33 一阶逻辑的语义例给定语言 L = {R},R 是一个二元谓词符号 v 1 v 2 Rv 1 v 2 和 v 2 v 1 Rv 1 v 2 的意思是? 若令 A 是一个 L- 结构, 且 A = N,R A 是 N 上的大于等于关系 N, 那么上述公式在这个解释下的意思是? R A 是小于关系 < N 呢? A = {0, 1, 2, 3, 4, 5} 呢?

34 一阶逻辑的语义例给定语言 L = {R},R 是一个二元谓词符号 v 1 v 2 Rv 1 v 2 和 v 2 v 1 Rv 1 v 2 的意思是? 若令 A 是一个 L- 结构, 且 A = N,R A 是 N 上的大于等于关系 N, 那么上述公式在这个解释下的意思是? R A 是小于关系 < N 呢? A = {0, 1, 2, 3, 4, 5} 呢?

35 一阶逻辑的语义例给定语言 L = {R},R 是一个二元谓词符号 v 1 v 2 Rv 1 v 2 和 v 2 v 1 Rv 1 v 2 的意思是? 若令 A 是一个 L- 结构, 且 A = N,R A 是 N 上的大于等于关系 N, 那么上述公式在这个解释下的意思是? R A 是小于关系 < N 呢? A = {0, 1, 2, 3, 4, 5} 呢?

36 一阶逻辑的语义例给定语言 L = {R},R 是一个二元谓词符号 v 1 v 2 Rv 1 v 2 和 v 2 v 1 Rv 1 v 2 的意思是? 若令 A 是一个 L- 结构, 且 A = N,R A 是 N 上的大于等于关系 N, 那么上述公式在这个解释下的意思是? R A 是小于关系 < N 呢? A = {0, 1, 2, 3, 4, 5} 呢?

37 一阶逻辑的语义对变元的解释赋值定义 ( 赋值 ) 给定语言 L 以及 L- 结构 A 我们称 s 是一个 A 赋值, 当且仅当 s 是从所有变元的集合 V 到 A 的函数 s : V A

38 一阶逻辑的语义对项的解释定义 ( 项的赋值 ) 给定语言 L L- 结构 A 令 s 是一个 A 赋值, 我们递归定义对项的解释 s : T A 如下 : 对每个变元符号 x, s(x) = s(x); 对每个常数符号 c, s(c) = c A 如果 t 1,..., t n 是项,f 是一个 n 元函数符号, 则 s(ft 1... t n ) = f A ( s(t 1 ),..., s(t n ))

39 一阶逻辑的语义对公式的解释定义 ( 满足关系 ) 给定语言 L 令 A 是一个 L- 结构,s 是一个 A 赋值,α 是一个 L 公式, 我们对 α 递归定义 A 和 s 满足 α( 记 (A, s) α) 如下 α 是原子公式 (A, s) t 1 t 2, 当且仅当 s(t 1 ) = s(t 2 ) (A, s) Pt 1... t n, 当且仅当 ( s(t1 ),..., s(t n ) ) P A

40 一阶逻辑的语义 (A, s) β, 当且仅当 (A, s) β (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ (A, s) xβ, 当且仅当对任何 d A, 有 (A, s x d ) φ 其中 s x d 是一个新的 A 赋值 : s x d (y) = s(y) d 若 y x 若 y = x

41 一阶逻辑的语义 (A, s) β, 当且仅当 (A, s) β (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ (A, s) xβ, 当且仅当对任何 d A, 有 (A, s x d ) φ 其中 s x d 是一个新的 A 赋值 : s x d (y) = s(y) d 若 y x 若 y = x

42 一阶逻辑的语义 (A, s) β, 当且仅当 (A, s) β (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ (A, s) xβ, 当且仅当对任何 d A, 有 (A, s x d ) φ 其中 s x d 是一个新的 A 赋值 : s x d (y) = s(y) d 若 y x 若 y = x

43 一阶逻辑的语义 (A, s) β, 当且仅当 (A, s) β (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ (A, s) xβ, 当且仅当对任何 d A, 有 (A, s x d ) φ 其中 s x d 是一个新的 A 赋值 : s x d (y) = s(y) d 若 y x 若 y = x

44 一阶逻辑的语义当我们说 (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ, 我们是不是在循环定义? 形式上, 我们只是定义了一个三元关系 :, 或以结构赋值公式为定义域的布尔值函数 :S(A, s, α) = 1 当且仅当 (A, s) α 这一切都可以看作是在, 例如集合论语言中的工作正如, 我们在数论语言中定义整除关系一样我们也可以认为, 该定义刻画了我们对真的直观但这不仅仅是一个数学问题了

45 一阶逻辑的语义当我们说 (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ, 我们是不是在循环定义? 形式上, 我们只是定义了一个三元关系 :, 或以结构赋值公式为定义域的布尔值函数 :S(A, s, α) = 1 当且仅当 (A, s) α 这一切都可以看作是在, 例如集合论语言中的工作正如, 我们在数论语言中定义整除关系一样我们也可以认为, 该定义刻画了我们对真的直观但这不仅仅是一个数学问题了

46 一阶逻辑的语义当我们说 (A, s) β γ, 当且仅当或者 (A, s) β 或者 (A, s) γ, 我们是不是在循环定义? 形式上, 我们只是定义了一个三元关系 :, 或以结构赋值公式为定义域的布尔值函数 :S(A, s, α) = 1 当且仅当 (A, s) α 这一切都可以看作是在, 例如集合论语言中的工作正如, 我们在数论语言中定义整除关系一样我们也可以认为, 该定义刻画了我们对真的直观但这不仅仅是一个数学问题了

47 一阶逻辑的语义定义 ( 语义蕴含 ) 给定语言 L 称公式集 Γ 逻辑蕴含 (logically imply)φ, 记 Γ φ, 当且仅当对任意 L- 结构 A 和每个 A 赋值 s 都有, 如果 A 和 s 满足 Γ 中所有公式, 那么 A 和 s 也满足 φ 约定以后依语境主要表示满足关系和逻辑蕴涵关系 α β 即 {α} β;α β ( 逻辑等效 ) α 即 α ( 逻辑有效 )

48 一阶逻辑的语义定义 ( 语义蕴含 ) 给定语言 L 称公式集 Γ 逻辑蕴含 (logically imply)φ, 记 Γ φ, 当且仅当对任意 L- 结构 A 和每个 A 赋值 s 都有, 如果 A 和 s 满足 Γ 中所有公式, 那么 A 和 s 也满足 φ 约定以后依语境主要表示满足关系和逻辑蕴涵关系 α β 即 {α} β;α β ( 逻辑等效 ) α 即 α ( 逻辑有效 )

49 一阶逻辑的语义引理 ( 合同引理 ) 给定语言 L L- 结构 A 任给 A 赋值 s 1, s 2 如果它们关于在公式 φ 中自由出现的变元的赋值相同, 那么 (A, s 1 ) φ 当且仅当 (A, s 2 ) φ Proof. 对公式 φ 归纳

50 一阶逻辑的语义引理 ( 合同引理 ) 给定语言 L L- 结构 A 任给 A 赋值 s 1, s 2 如果它们关于在公式 φ 中自由出现的变元的赋值相同, 那么 (A, s 1 ) φ 当且仅当 (A, s 2 ) φ Proof. 对公式 φ 归纳

51 一阶逻辑的语义约定 : 我们用 φ(x 1,..., x n ) 表示公式 φ 且预设 φ 中自由出现的变元至多有 x 1,..., x n 对 φ(x 1,... x n ), 我们用 A φ[d 1,..., d n ] 表示 (A, s) φ, 其中 s(x i ) = d i (1 i n)

52 一阶逻辑的语义约定 : 我们用 φ(x 1,..., x n ) 表示公式 φ 且预设 φ 中自由出现的变元至多有 x 1,..., x n 对 φ(x 1,... x n ), 我们用 A φ[d 1,..., d n ] 表示 (A, s) φ, 其中 s(x i ) = d i (1 i n)

53 一阶逻辑的语义推论给定语言 L L- 结构 A 给定语言对任何闭语句 σ, 或者 (1) 对所有 A 赋值 s 都有,(A, s) σ; 或者 (2) 对所有 A 赋值 s 都有,(A, s) σ 定义 ( 真 ) 给定语言 L L- 结构 L 中闭语句 σ 我们称 σ 在 A 中为真, 记 A σ, 当且仅当 (1) 成立

54 一阶逻辑的语义推论给定语言 L L- 结构 A 给定语言对任何闭语句 σ, 或者 (1) 对所有 A 赋值 s 都有,(A, s) σ; 或者 (2) 对所有 A 赋值 s 都有,(A, s) σ 定义 ( 真 ) 给定语言 L L- 结构 L 中闭语句 σ 我们称 σ 在 A 中为真, 记 A σ, 当且仅当 (1) 成立

55 习题 4.4 (1), (2) 5.1 (1), (2), (3), (5), (7), (8), (9), (11)

数理逻辑 I Mathematical Logic I

数理逻辑 I Mathematical Logic I 前情提要前情提要我们定义了两种可定义概念结构内的可定义性 : 给定结构关于该结构论域上的 k 元关系的性质由一个公式定义定义结构类 : 给定语言关于该语言的结构类的由一则闭语句定义 ( 初等类 ); 由一集闭语句定义 ( 广义初等类 ) 前情提要我们定义了两种可定义概念结构内的可定义性 : 给定结构关于该结构论域上的 k 元关系的性质由一个公式定义定义结构类 : 给定语言关于该语言的结构类的由一则闭语句定义