数理逻辑 I Mathematical Logic I

Size: px

Start display at page:

Download "数理逻辑 I Mathematical Logic I"

审冉
4 years ago
Views:

1 前情提要

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

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

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

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

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

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

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

9 前情提要同态与同构 : 给定同语言的两个结构, 其间的对应同态 : 保持对谓词符号函数符号常数符号的解释嵌入 : 同态且保持对等词的解释满同态 : 同态且保持对量词的解释同构 : 保持所有解释, 逻辑等同

10 前情提要同态与同构 : 给定同语言的两个结构, 其间的对应同态 : 保持对谓词符号函数符号常数符号的解释嵌入 : 同态且保持对等词的解释满同态 : 同态且保持对量词的解释同构 : 保持所有解释, 逻辑等同

11 前情提要同态与同构 : 给定同语言的两个结构, 其间的对应同态 : 保持对谓词符号函数符号常数符号的解释嵌入 : 同态且保持对等词的解释满同态 : 同态且保持对量词的解释同构 : 保持所有解释, 逻辑等同

12 前情提要同态与同构 : 给定同语言的两个结构, 其间的对应同态 : 保持对谓词符号函数符号常数符号的解释嵌入 : 同态且保持对等词的解释满同态 : 同态且保持对量词的解释同构 : 保持所有解释, 逻辑等同

13 前情提要同态与同构 : 给定同语言的两个结构, 其间的对应同态 : 保持对谓词符号函数符号常数符号的解释嵌入 : 同态且保持对等词的解释满同态 : 同态且保持对量词的解释同构 : 保持所有解释, 逻辑等同

14 前情提要同态定理 :(A, s) α (B, h s) α 自同构 :h : A A 证明 ( 结构内 ) 不可定义的一个方法 : 由同态定理, 所有可定义的关系在自同构下保持构造一个自同构, 使之不保持

15 前情提要同态定理 :(A, s) α (B, h s) α 自同构 :h : A A 证明 ( 结构内 ) 不可定义的一个方法 : 由同态定理, 所有可定义的关系在自同构下保持构造一个自同构, 使之不保持

16 前情提要同态定理 :(A, s) α (B, h s) α 自同构 :h : A A 证明 ( 结构内 ) 不可定义的一个方法 : 由同态定理, 所有可定义的关系在自同构下保持构造一个自同构, 使之不保持

17 前情提要同态定理 :(A, s) α (B, h s) α 自同构 :h : A A 证明 ( 结构内 ) 不可定义的一个方法 : 由同态定理, 所有可定义的关系在自同构下保持构造一个自同构, 使之不保持

18 吁, 终于

19 一阶逻辑希尔伯特系统的可靠性与完全性定理

20 定理 ( ) 给定语言 L 的公式集 Γ 和公式 φ, Γ φ Γ φ Proof. 对证明序列归纳

21 定理 ( ) 给定语言 L 的公式集 Γ 和公式 φ, Γ φ Γ φ Proof. 对证明序列归纳

22 假设 (β 1,..., β n ) 见证 Γ φ 归纳证明, 对任意 1 i n 有,Γ β i 如果 β i Γ 如果 β i 是公理如果存在 j, k < i, 使得 β k = β j β i 因此, 我们只需证明所有公理是有效的

23 假设 (β 1,..., β n ) 见证 Γ φ 归纳证明, 对任意 1 i n 有,Γ β i 如果 β i Γ 如果 β i 是公理如果存在 j, k < i, 使得 β k = β j β i 因此, 我们只需证明所有公理是有效的

24 假设 (β 1,..., β n ) 见证 Γ φ 归纳证明, 对任意 1 i n 有,Γ β i 如果 β i Γ 如果 β i 是公理如果存在 j, k < i, 使得 β k = β j β i 因此, 我们只需证明所有公理是有效的

25 假设 (β 1,..., β n ) 见证 Γ φ 归纳证明, 对任意 1 i n 有,Γ β i 如果 β i Γ 如果 β i 是公理如果存在 j, k < i, 使得 β k = β j β i 因此, 我们只需证明所有公理是有效的

26 假设 (β 1,..., β n ) 见证 Γ φ 归纳证明, 对任意 1 i n 有,Γ β i 如果 β i Γ 如果 β i 是公理如果存在 j, k < i, 使得 β k = β j β i 因此, 我们只需证明所有公理是有效的

27 假设 (β 1,..., β n ) 见证 Γ φ 归纳证明, 对任意 1 i n 有,Γ β i 如果 β i Γ 如果 β i 是公理如果存在 j, k < i, 使得 β k = β j β i 因此, 我们只需证明所有公理是有效的

28 一阶逻辑希尔伯特系统的公理 : 下列公式的全称概括 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现

29 若语言中含有等词, 则还有 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

30 引理 θ xθ 因此, 如果 θ 是有效的, 那么它的所有全称概括都是有效的所以, 只需证所列 1-6 组的公式是有效的

31 引理 θ xθ 因此, 如果 θ 是有效的, 那么它的所有全称概括都是有效的所以, 只需证所列 1-6 组的公式是有效的

32 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

33 任给 L 结构 A 和 A 赋值 s, 定义命题逻辑真值指派 v (A,s), 使得对任意素公式 β 有 v (A,s) (β P ) = 1 (A, s) β 归纳证明, 对所有 L 公式 α 有, v (A,s) (α P ) = 1 (A, s) α 若 α P 是重言式, 则对任意 (A, s), 有 v (A,s) (α P ) = 1

34 任给 L 结构 A 和 A 赋值 s, 定义命题逻辑真值指派 v (A,s), 使得对任意素公式 β 有 v (A,s) (β P ) = 1 (A, s) β 归纳证明, 对所有 L 公式 α 有, v (A,s) (α P ) = 1 (A, s) α 若 α P 是重言式, 则对任意 (A, s), 有 v (A,s) (α P ) = 1

35 任给 L 结构 A 和 A 赋值 s, 定义命题逻辑真值指派 v (A,s), 使得对任意素公式 β 有 v (A,s) (β P ) = 1 (A, s) β 归纳证明, 对所有 L 公式 α 有, v (A,s) (α P ) = 1 (A, s) α 若 α P 是重言式, 则对任意 (A, s), 有 v (A,s) (α P ) = 1

36 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

37 假设 t 可以在公式 φ 中替换变元 x 并且 (A, s) xφ, 我们只需证明 (A, s) φ x t 由下述引理, 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ 我们只需证 :(A, s x s(t) ) φ, 而由 (A, s) xφ, 这显然成立

38 假设 t 可以在公式 φ 中替换变元 x 并且 (A, s) xφ, 我们只需证明 (A, s) φ x t 由下述引理, 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ 我们只需证 :(A, s x s(t) ) φ, 而由 (A, s) xφ, 这显然成立

39 假设 t 可以在公式 φ 中替换变元 x 并且 (A, s) xφ, 我们只需证明 (A, s) φ x t 由下述引理, 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ 我们只需证 :(A, s x s(t) ) φ, 而由 (A, s) xφ, 这显然成立

40 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ Proof. 对公式 φ 归纳

41 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ Proof. 对公式 φ 归纳 φ 是原子公式引理 : s(u x t) = s x s(tr)

42 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ Proof. 对公式 φ 归纳 φ 是原子公式引理 : s(u x t) = s x s(tr)

43 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ Proof. 对公式 φ 归纳 φ 是几个子公式的布尔组合

44 引理 ( 替换引理 ) 如果项 t 可以在公式 φ 中替换变元 x, 则 (A, s) φ x t (A, s x s(t) ) φ Proof. 对公式 φ 归纳 φ = yψ

45 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

46 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

47 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

48 1 对应的命题逻辑公式 α P 是重言式的一阶逻辑公式 α 2 xα α x t, 其中项 t 可以在 α 中替代 x 3 x(α β) ( xα xβ) 4 α xα, 其中 x 不在 α 中自由出现 5 x x 6 x y α α, 其中 α 为原子公式, 且 α 是将 α 中若干个 x 的出现替换为 y 所得到的公式

49 一阶逻辑希尔伯特系统的完全性

50 完全性定理定理 ( 完全性定理 ) 给定语言 L Γ 是 L 公式集,φ 是 L 公式, 则 Γ φ Γ φ

51 完全性定理引理给定语言 L, 下述等价 : 对任意公式集 Γ 公式 φ,γ φ Γ φ 对任意公式集 Σ, 如果 Σ 一致, 那么 Σ 可满足因此, 我们只需要证明后者

52 完全性定理证明思路给定一致的 L 公式集 Σ, 我们要构造一个它的 L 模型 A 以及赋值 s: 将 Σ 扩张为一个极大一致集, 以获得足够多的信息将 L 中的所有项作为论域中元素变元常数符号函数符号解释依据项本身的构造关系依据中原子公式的提示证明 (A, s)

53 习题无

数理逻辑 I Mathematical Logic I

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