爱华网第七章 可靠性和完全性（提纲）
1. 可靠性与完全性
现在逻辑基本上都是采用如下结构：
形式语言
语义 语法
语义与语法的关系
形式语言：从初始符号出发，形成主要对象——公式。（可能需要一些其它辅助对象，如在一阶逻辑，就有项的概念）。
公式是一种特殊的符号串（由初始符号组成的符号串）。
语义：给出某种结构，通过某种定义，定义出刻画逻辑规律的有效式。（如在一阶逻辑，我们从结构和赋值出发，给出解释、公式在解释下的真值，用在所有解释下都真定义出有效式）。
有效式是一种特殊的公式，所有有效式的集合是全体公式的一个子集。
语法：由公理和推导规则组成。按某种标准的方法给出证明序列和内定理。（可以有一些推广的概念，最重要的是推演）。
有效式是一种特殊的公式，所有内定理的集合是全体公式的一个子集。
语义与语法的关系：最重要的有两个，可靠性和完全性。
7.1.1定义 可靠性 所有的内定理都是有效式。
7.1.2定义 完全性 所有的有效式都是内定理。
2. 一阶推演系统的可靠性
可靠性有标准的证明方法：
1. 证明每个公理都是有效的。
2. 证明推导规则保持有效性不变。
3. 归纳证明证明序列中的每个公式都是有效式，所以内定理是有效式。
7.2.1引理
(1) ?(???) = T当且仅当（如果?(?) = T，则?(?) = T）。
(2) ?(?1?…??n??) = T 当且仅当（如果?(?1) = T, …, ?(?n) = T，则?(?) = T）。 证 (1) 由定义得?(???) = T当且仅当 ?(?) = F或?(?) = T。?(?) = F或?(?) = T就是（如果?(?) = T，则?(?) = T）。所以，?(???) = T当且仅当（如果?(?) = T，则?(?) = T）。
(2) 对n作归纳。
1. n = 1。由(1)得?(?1??) = T 当且仅当（如果?(?1) = T，则?(?) = T）。
2. n = k+1。?1?…??k+1??也就是?1?…??k?(?k+1??)，由归纳假设?(?1?…??k?(?k+1??)) = T 当且仅当（如果?(?1) = T, …, ?(?k) = T，则?(?k+1??) = T）。由(1)得?(?k+1??) = T 当且仅当（如果?(? k+1) = T，则?(?) = T）。所以，?(?1?…??n??) = T 当且仅当（如果?(?1) = T, …, ?(?n) = T，则?(?) = T）。
7.2.2引理
(1) 如果?(???) = T且?(?) = T，则?(?) = T。
(2) 如果?(???) = T且?(?) = T，则?(?) = T。
证 (1) 如果?(???) = T，则?(?) = F或?(?) = T，又?(?) = T，所以?(?) = T。
7.2.3定理 一阶推演系统的公理都是有效式。
证
A1 ?????。
任给解释?，如果?(?) = T, ?(?) = T，则?(?) = T。
由定理7.2.1(2)，任给解释?，都有?(?????) = T。
A2 (?????)?(???)????。
任给解释?，如果?(?????) = T, ?(???) = T, ?(?) = T，则由?(?) = T和?(?????) = T得?(???) = T，由?(?) = T和?(???) = T得?(?) = T，再由?(?) = T和?(???) = T得?(?) = T。
由定理7.2.1(2)，任给解释?，都有?((?????)?(???)????) = T。
A3 (????)?(?????)??
任给解释?，如果?(????) = T, ?(?????) = T，则用反证法证明?((?) = T。
假设?(?) = F，则?(??) = T，由?(??) = T和?(????) = T得?(?) = T，由?(??) = T和?(?????) = T得?(??) = T，所以?(?) = F。?(?) = T和?(?) = F，矛盾。
由定理7.2.1(2)，任给解释?，都有?((????)?(?????)??) = T。
A4 ?x???(t / x)，在?中t对x代入自由。
任给解释?，如果?(?x?) = T，则任给a?A，都有?x, a(?) = T，取a = ?(t)，由代入引理得?(?(t / x)) = ?x, a(?) = T。
由定理7.2.1(2)，任给解释?，都有?(?x???(t / x)) = T。
A5 ?x(???)?(?x???x?)。
任给解释?，如果?(?x(???)) = T, ?(?x?) = T，则任给a?A，都有?x, a(???) = T且?x, a(?) = T，所以任给a?A，都有?x, a(?) = T，因此?(?x?) = T。
由定理7.2.1(2)，任给解释?，都有?(?x(???)?(?x???x?)) = T。
A6 ???x?，x不是?的自由变项。
任给解释?，如果?(?) = T，则任给a?A，由合同引理得?x, a(?) = ?(?) = T，所以?(?x?) = T。
由定理7.2.1(2)，任给解释?，都有?(???x?) = T。
7.2.4定理 一阶推演系统的推导规则保持有效性不变。
(1) 如果???和?都是有效式，则?也是有效式。
(2) 如果?是有效式，则?x?也是有效式。
证
(1) 任给解释?，因为???和?都是有效式，所以?(???) = T且?(?) = T，因此?(?) = T。这就证明了任给解释?，都有?(?) = T，所以?是有效式。
(2) 任给解释?，任给a?A，因为?是有效式，所以?x, a(?) = T，因此?(?x?) = T。这就证明了任给解释?，都有?((?x?) = T，所以?x?是有效式。
7.2.5定理 一阶推演系统可靠性定理
一阶推演系统的内定理都是有效式。
证 设?是内定理，?1, …, ?n（=?）是它的证明序列，归纳证明任给k（1?k?n），?k都是有效式，当k = n时，就是说?是有效式。
1. ?i是公理，由定理7.2.3得?i是有效式。
2.1 存在j, k?i?n，使得?k = ?j??i。
由归纳假设得?j和?k = ?j??i都是有效式，由定理7.2.4(1)得?i是有效式。
2.2 存在j?i，存在变项x，使得?i = ?x ?j。
由归纳假设得?j是有效式，由定理7.2.4(2)得?i = ?x ?j是有效式。
7.2.6补充 A7和A8是有效式。
证
A7 t ? t。
任给解释?，如果?(t) = ?(t)，所以?(t ? t)。
A8 t ? s?(?(t / x)??(s / x))。
任给解释?，如果?( t ? s) = T, ?(?(t / x)) = T，则?(t) = ?(s)，取a = ?(t) = ?(s)，则由代入引理得?(?(s / x)) = ?x, a(?) = ?(?(t / x)) = T。
由定理7.2.1(2)，任给解释?，都有?( t ? s?(?(t / x)??(s / x))) = T。
7.2.7补充 带等词的一阶推演系统可靠性定理
带等词的一阶推演系统的内定理都是有效式。
证 略。
3. 和谐和极大和谐
7.3.1定义 和谐 ?是公式集。如果存在公式?，使得? |– ?且? |– ??，则称?是不和谐的。否则称?是和谐的。
由定义，?是和谐的条件是：不存在公式?，使得? |– ?且? |– ??。
7.3.2定理 和谐集等价条件
(1) ?是不和谐的 当且仅当（任给公式?，都有? |– ?）。
(2) ?是和谐的 当且仅当（存在公式?，使得? |–/ ?）。
证 (1) 如果（任给公式?，都有? |– ?），当然存在公式?，使得? |– ?且? |– ??。 如果存在公式?，使得? |– ?且? |– ??，则任给公式?，由{?, ??} |– ?得? |– ?。
(2) 由(1)直接可得。
7.3.3定理 和谐集的性质
(1) 单调性 ? ? ?。如果?是不和谐，则?也是不和谐的。所以如果?是和谐的，则?也是和谐的。
(2) 有限性 ?是和谐的 当且仅当 ?的每个有限子集是和谐的。
(3) ? |–/ ? 当且仅当 ??{??}是和谐的。
(4) ? |–/ ?? 当且仅当 ??{?}是和谐的。
证 (1) 如果?是不和谐，则任给公式?，都有? |– ?，所以任给公式?，都有? |– ?，因此?是不和谐的。
(2) 证明：?是不和谐的 当且仅当 存在?的有限子集?是不和谐的。
设?是不和谐的，则存在公式?，使得? |– ?且? |– ??。取?到?的推演序列为?1, …, ?n，令?1 = {?1, …, ?n}??，则?1是?的有限子集且?1 |– ?，类似地存在有限?的有限子集?2，使得?2 |– ??。所以存在?的有限子集? = ?1??2，使得? |– ?且? |–??，因此存在?的有限子集?，使得?是不和谐的。
设存在?的有限子集?是不和谐的，由单调性得?是不和谐的。
(3) 证明：? |– ? 当且仅当 ??{??}是不和谐的。
设? |– ?，则??{??} |– ?，又??{??} |– ??，所以??{??}是不和谐的。
设??{??}是不和谐的，则??{??} |– ?，由演绎定理得? |– ????，由{????} |– ?得? |– ?。
(4) 类似于(3)，留给读者。
7.3.4定义 极大和谐 ?是和谐的公式集。如果任给公式???，都有??{?}是不和谐的，则称?是极大和谐的。
7.3.5定理 极大和谐集的性质 ?是极大和谐的公式集。
(1) 推演封闭性 如果? |– ?，则???。
(2) 内定理封闭性 如果?是内定理，则???。
(3) 分离规则 如果???且?????，则???。
(4) ???? 当且仅当 ???。
(5) ????? 当且仅当 ???或???。
证 (1) 反证法。如果???，则??{?}是不和谐的，由定理7.3.3(4)得? |– ??，又? |– ?，所以?是不和谐的，矛盾。
(2) 如果?是内定理，则由5.3.1(1)得? |– ?，由(1)得???。
(3) 如果???且?????，则? |– ?，由(1)得???。
(4) 如果????，由?的和谐性得???。???
如果???，则??{?}是不和谐的，由定理7.3.3(4)得? |– ??，由(1)得????。
(5) 如果?????，分两种情况证明???或???。
情况1，???。显然有???或???。
情况2，???。由(3)得???，也有???或???。
如果???或???，则分两种情况证明?????。
情况1，???。由(4)得????，因为???(???)是内定理，所以???(???)??，再由(3)得?????。
情况2，???。类似情况1，由内定理??(???)。
由(4)和(5)得：
(4?) ???? 当且仅当 ???。
(5?) ????? 当且仅当 ???且???。
7.3.6推论 ?是极大和谐的公式集。
(1) ????? 当且仅当 ???且???。
(2) ????? 当且仅当 ???或???。
证 (1) ????? 当且仅当 ?(????)?? 当且仅当 ?????? 当且仅当 ???且???? 当且仅当 ???且???。
(2) ????? 当且仅当 ?????? 当且仅当 ????或??? 当且仅当 ???或???。
百度搜索“爱华网”,专业资料、生活学习,尽在爱华网!
