2.4 P 的完全性
定义 2.4.1. 设 Γ ⊆ F ormula, 若对每个 A ∈ F ormula 皆有 A ∈ Γ 或 ¬A ∈ Γ, 则称 Γ 为完全的
集合 ∆
Γ
是极大协调的,
即完全且协调.
为证明 P 的完全性，引入一种运算 ∆
Γ
定义. 设 A ∈ F ormula 且 Γ ⊆ F ormula 为协调的, 因为 F ormula 为可数集，故假定
F ormula = {A
0
, A
1
, · · · }
再令
∆
0
= Γ
∆
n+1
=
∆
n
∪ {A
n
} if ∆
n
⊢ A
n
∆
n
∪ {¬A
n
} else
n = 0, 1, · · ·
∆
Γ
=
∞
n=0
∆
n
φ
Γ
(A) =
t if A ∈ ∆
Γ
f else
下面是 ∆
n
, ∆
Γ
, φ
Γ
的一些简单性质
1. 若 n ∈ N, 则 ∆
n
为协调的
2. 若 n ∈ N, 则 Γ ⊆ ∆
n
⊆ ∆
n+1
⊆ ∆
Γ
.
3. ∆
Γ
是完全的
4. 若 A ∈ F ormula, 且 ∆
Γ
⊢ A, 则有 n ∈ N 使 ∆
n
⊢ A.
5. 若 A ∈ F ormula, 则 A ∈ ∆
Γ
当且仅当 ∆
Γ
⊢ A
6. ∆
Γ
为协调的
7. φ
Γ
为 P 的一个指派，且对每个 A ∈ F ormula 皆有
φ
Γ
是否为指派(对公式
的指派)仍需证明, 使用
公式结构归纳法.
φ
Γ
(A) = t当且仅当A ∈ ∆
Γ
定理 2.4.1. (P 的完全性(completeness)定理) 设 Γ ⊆ F ormula 且 A ∈ F ormula, 若 Γ |= A, 则
Γ ⊢ A.
说明:其证明使用反证法. 若 Γ ⊢ A, 则 Γ ∪ {¬A} 为协调的. 构造指
派 φ
Γ∪{¬A}
, 使得 ∆
Γ∪{¬A}
可满足, 从而保证了 Γ 和 ¬A 都可满足,
即 A 和 ¬A 都可满足, 从而出现矛盾.
定理 2.4.2. (G¨odel 完全性定理) 设 Γ ⊆ F ormula 且 A ∈ F ormula
1. ⊢ A 当且仅当 |= A
2. Γ ⊢ A 当且仅当 Γ |= A
定理 2.4.3. 设 A, A
1
, · · · , A
n
∈ F ormula, Γ ⊆ F ormula 且 p
1
, · · · , p
n
在 Γ 中不出现的 n 个互不
相同的命题的变元
1. 若 |= A, 则 |= S
p
1
···p
n
A
1
···A
n
A.
2. 若 Γ |= A, 则 Γ |= S
p
1
···p
n
A
1
···A
n
A.
定义 2.4.2. 设 φ 为 P 的一个指派，若 A ∈ F ormula, 则令
A
φ
=
A if φ(A) = t
¬A else
由此定义，显然有 φ(A
φ
) = t, A ∈ F ormula
定理 2.4.4. 设 A ∈ F ormula, φ 为 P 的指派且 p
1
, · · · , p
n
包括了出现在 A 中所有的命题变元
1. 若 φ(A) = t, 则 p
φ
1
, · · · , p
φ
n
⊢ A.
2. 若 φ(A) = f, 则 p
φ
1
, · · · , p
φ
n
⊢ ¬A.
说明:构造一个完全的析取范式, φ 为满足某个合取支的指派, 该合支
包括了 A 的所有命题变元.
12
剩余77页未读，继续阅读
LML1995
- 粉丝: 0
- 资源: 11
我的内容管理
展开
最新资源
- 多功能HTML网站模板：手机电脑适配与前端源码
- echarts实战：构建多组与堆叠条形图可视化模板
- openEuler 22.03 LTS专用openssh rpm包安装指南
- H992响应式前端网页模板源码包
- Golang标准库深度解析与实践方案
- C语言版本gRPC框架支持多语言开发教程
- H397响应式前端网站模板源码下载
- 资产配置方案：优化资源与风险管理的关键计划
- PHP宾馆管理系统（毕设）完整项目源码下载
- 中小企业电子发票应用与管理解决方案
- 多设备自适应网页源码模板下载
- 移动端H5模板源码，自适应响应式网页设计
- 探索轻量级可定制软件框架及其Http服务器特性
- Python网站爬虫代码资源压缩包
- iOS App唯一标识符获取方案的策略与实施
- 百度地图SDK2.7开发的找厕所应用源代码分享
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
