数理逻辑逻辑公理系统.PPTVIP

主要内容 逻辑公理系统 命题逻辑公理系统 谓词逻辑公理系统 定理证明 公理系统性质 理论与模型 判定问题 判定问题 判定问题有两个主要内容： 普遍有效性和可证明性。 普遍有效性问题是逻辑公式所表达的命题的正确性问题,可证明性问题是一公理系统的推演能力问题。 可判定性 定理：只含有一元谓词变项的公式是能行可判定的。 定理： ?x1… ?xnQ(x1,…, xn) 定理： ? x1… ? xnQ(x1,…, xn) 定理： ?x1… ?xm? y1… ? ynQ(x1,…, xm, y1,…, yn) 逻辑基本判断问题 能行方法来判定如下问题： （1）一个符号是否为一个初始符号； （2）一个符号序列是否合式； （3）一个公式是否为一条公理； （4）一个有穷长的公式序列是否为一个证明。 判定性 一阶逻辑系统能否找到一种有效的方法可以判断任意一个命题是否是定理？ David Hilbert 1826-1943 歌德尔编码 定义：符号歌德尔数 g(()=3 g())=5 g(,)=7 g(?)=9 g(?)=11 g(?)=13 g(xk)=7+8k k=1,2,3 g(ak)=9+8k k=1,2,3 g(fnk)=11+8×(2n×3k) g(pnk)=13+8×(2n×3k) Kurt G?dels 1906-1978 歌德尔编码 定义：公式歌德尔数 若u1u2...uk是公式符号串，则公式的歌德尔数为 g(u1u2...uk)=2g(u1)×3g(u2)×...×qg(uk) 定义：证明的公式序列歌德尔数 若ω1ω2... ωk是证明的公式序列，则其歌德尔数为 g(ω1ω2... ωk)= 2g(ω1)×3g(ω2)×...×qg(ωk) 符号的歌德尔数一定是奇数，公式的歌德尔数一定是偶数且素数2是奇数次幂，证明的公式序列一定是偶数且素数2是偶数次幂。 歌德尔不完全性定理 设公式ω的歌德尔数是m，公式有穷序列ω1ω2... ωk是的歌德尔数n。 公式有穷序列ω1ω2... ωk是公式ω的证明关系 即，如果ω = ωk ，则m和n有W(m,n)关系，否则m和n没有W(m,n)关系。 素数原理:W(m,n)可求 谓词φ(x,y)对应于关系W(m,n) ，歌德尔构造的公式 (?x)?φ(0(p),x) ?(?x)?φ(0(p),x)=(?x)φ(0(p),x) 歌德尔不完全性定理 包含自然数的系统一定存在形式不可判定的语句。 可判定、半可判定和不可判定 命题演算是可判定的。 任给一个公式，有一种机械的方法在有穷多步之内判定它是不是一条定理。 丘奇(Church)首先指出“任何至少含有一个二元谓词的一阶谓词演算系统都是不可判定的。” 定理 FC是半可判定的 存在一个可机械地实现的过程，能对FC的定理作出肯定的判决，但对非定理的FC的公式却未必能作出否定的判决。 定理：设Γ为FC的一个可判定的公式集(递归集)，那么Γ的演绎结果集合Γ├Q是半可判定的，或者说Γ├Q是否成立的问题是半可判定的。 罗丹-思想者 * * 可靠性定理(4)—MP规则 若Qi?Γ，则Γ├ Qi, 对于v(Γ)=1， Qi?Γ有v(Qi)=1，所以 Γ ╞ Qi 假设in时定理成立 证明i=n时， 设Qi由Qj, Qk用MP规则推出， 其中j,ki，Qk为Qj→Qi。 由归纳假设知，Γ├ Qj且Γ├ Qj→Qi ， 所以Γ ╞ Qj， Γ ╞ Qj→Qi Γ ╞ Qi 。 因此Γ ╞ Q 即Γ ╞ Q 可靠性定理(5 )—UG规则 证明i=n时， 设Qi由Qk用UG规则推出，其中ki， Qi=?xQk 由归纳假设知，Γ├ Qk， 所以Γ ╞ Qk。 因为Qi=?xQk ，对于任意d?D，I(Qk)(v[x/d])=1， 所以， I(?xQk )(v[x/d])=1 因此Γ ╞ Qn 即Γ ╞ Q。 协调 定义3.6 如果对于每个公式Q，Γ├ Q，则Γ称不协调，否则称Γ协调。 定理3.12若Γ├ ?p(x) ∧ p(x) ，则Γ不协调。 定理3.13 若Γ协调，则Γ可满足。 完备性定理—命题 若Γ╞Q，则Γ├ Q 证明： 若真值赋值v满足Γ?{?Q}， 则v(?Q)=1且v(Q)=1，出现矛盾 因此，Γ?{?Q}不可满足 所以Γ?{?Q}不协调，即Γ?{?Q}├Q Γ├ ?Q ?Q 又因为├ (?Q ?Q)? Q 所以Γ├ Q 推论： 若╞Q，则├Q 完备性定理—谓词 若Γ╞Q，则Γ├ Q 证明 设R是Q的闭包。 若解释I满足Γ，必然满足R，即不满足?R， 所以Γ?{?R }不可满足，Γ?{?R }不协调， Γ?{?R }├ R 。 由演绎定理知，Γ├ ?R ? R， 因为