数理逻辑第四章.pdf

马琦 2010.10.16 maqi08@ 非形式化命题演算非形式化命题演算 语句形式演算系统语句形式演算系统L 非形式化命题演算非形式化命题演算 语句形式演算系统语句形式演算系统 基本要素基本要素 p,q,r,…~,∧, ∨, →,↔, A,B,C,… ~,→,( , ) , p , p , p ,… 基本要素基本要素 1 2 3 真值表 合式公式，公理，演绎规则 真值指派真值指派 重言式：对任意变元真值都取T 。 重言式：对每一赋值都取T 。 真值指派真值指派 逻辑推理逻辑推理 论证形式的有效性 定理和证明(推演和后承) 逻辑推理逻辑推理 等价性等价性 论证形式是有效论证形式是有效的当且仅当相应的命题形式是重言式。重言式是定理，定理是重言式。 等价性等价性 论证形式是有效论证形式是有效 一阶语言一阶语言LL 一阶语言一阶语言LL 形式系统形式系统 K 形式系统形式系统 LL LL x ,x ,…,a ,a ,…, A n, f n, (,),,,~, →,∀∀ ∀∀ LL 的合式公式，公理，规则 基本要素基本要素 LL 基本要素基本要素 1 2 1 2 i i 真值指派真值指派 解释：变元域以及其他元素的指定。 真值指派真值指派 赋值：对变元的指定。 重言式：LL中重言式的代换实例。 LL 逻辑推理逻辑推理 逻辑有效：对每一解释都是真的。 定理和证明(推演和后承) 逻辑推理逻辑推理 等价性等价性 重言式是逻辑有效逻辑有效的。 定理是逻辑有效的。 等价性等价性 逻辑有效逻辑有效 逻辑有效的是定理。 公理公理 公理公理 • 设A,B,C 是L 的任意wf. ，下列为KL 的公理。 • (K ) (A →(B→A)) 1 • (K2) (A →(B→C))→((A→B)→(A→C)) •• ((KK ) ) ((~A~A→→~B)~B)→→(B(B→→AA)))) 33 • (K ) ((∀x )A →A)) ，x 不在A 中自由出现。 4 i i • (K ) ((∀x )A(x )→A(t))) ，A(x )是L 的wf. ，而L 的项t 对A(x ) 中的x 是自由的。 5 i