第9卷第5期 智能系统学报 Vol.9 No.5 2014年10月 CAAI Transactions on Intelligent Systems 0ct.2014 D0:10.3969/j.issn.1673-4785.201310076 逻辑及数学演算中的不动项与不可判定命题（Ⅱ） 张金成 (中央党校函授学院广德教学点，安徽广德242200) 摘要：不动点是一个广泛而深刻的数学现象，它已经渗透到数学的各个领域。文中把不动点推广到逻辑思维领 域，证明Russel悖论是集合论中的不动项，Gdel不可判定命题是自然数系统N中的不动项，Cantor对角线方法构造 的项是不动项，不可判定的Tuig机也是不动项。进一步可以证明，当一个已知集合U可以分割成正、反集合时，不 动项不在正集或反集之中，不动项一定是U外不动项，·外不动项的逻辑性质相对于0已经发生变异，是未定义项， ·外不动项命题是不可判定的，这是系统的固有现象。自然数系统N中同样存在不动项，不动项的存在与不可判 定，并不影响正、反集合的递归性与系统的完全性，因此，Gdel不完全定理的证明不成立，Cantor对角线方法证明是 错误的，Turing停机问题证明也是错误的。“系统N能否完全”、实数是否可数、Turing停机问题是否可判定都必须 重新思考。 关键词：正项；反项；不动项：悖论；U外不动项；不可判定命题：不完全定理；对角线方法；不可数：停机问题。 中图分类号：B813;TP18文献标志码：A文章编号：1673-4785(2014)05-0618-14 中文引用格式：张金成.逻辑及数学演算中的不动项与不可判定命题（Ⅱ）[J].智能系统学报，2014,9(5)：618-631. 英文引用格式：ZHANG Jincheng.Fixed terms and undecidable propositions in logical and mathematical calculus(Ⅱ)[J].CAAI Transactions on Intelligent Systems,2014,9(5):618-631. Fixed terms and undecidable propositions in logical and mathematical calculus (II ZHANG Jincheng (Correspondence School,Communist Party College,Guangde 242200,China) Abstract:As a kind of broad and deep mathematical phenomenon,fixed point has penetrated into all fields of math- ematics.This paper extends the fixed point to the logical thinking.It proves that Russell's paradox is the fixed term in accordance with the set theory.It also proves that Godel's undecidable proposition is the fixed term within the natural number system N.The term formed by Cantor's diagonal method is fixed term and undecidable Turning is also fixed term.Furthermore,it can be proven that when a known set U is divided into a positive set and an inverse set and if the fixed term is neither in the positive set nor in the inverse set,then this fixed term must be that outside U.Thus,it is an inherent phenomenon of the system that the logical property of the fixed term excluded from Uhas changed relative to Uand the theorem of fixed term outside U is undecidable.In addition,there are also fixed terms in the natural number system N,where the existence and undecidability do not exert effect on the recursive nature of positive and inverse sets and the completeness of system.Therefore,the mathematical proof for Godel's theorem cannot be true and Cantor's diagonal method is proved to be false and Turning's halting problem is proved to be false.Whether the system N can be complete,real number is countable or not,whether Turning's halt problem can be decided should be reconsidered. Keywords:positive term;inverse term;fixed term;paradox;fixed term outside U;undecidable proposition;in- complete theorem;diagonal method;uncountable set;halting problem 收稿日期：2013-11-26. 通信作者：张金成.E-mail:656790205@qg.com
第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３１００７６ 逻辑及数学演算中的不动项与不可判定命题（Ⅱ） 张金成 （中央党校函授学院 广德教学点，安徽 广德 ２４２２００） 摘 要：不动点是一个广泛而深刻的数学现象，它已经渗透到数学的各个领域。 文中把不动点推广到逻辑思维领 域，证明 Ｒｕｓｓｅｌ 悖论是集合论中的不动项，Ｇöｄｅｌ 不可判定命题是自然数系统 Ｎ 中的不动项，Ｃａｎｔｏｒ 对角线方法构造 的项是不动项，不可判定的 Ｔｕｒｉｎｇ 机也是不动项。 进一步可以证明，当一个已知集合 Ｕ 可以分割成正、反集合时，不 动项不在正集或反集之中，不动项一定是 Ｕ 外不动项， Ｕ 外不动项的逻辑性质相对于 Ｕ 已经发生变异，是未定义项， Ｕ 外不动项命题是不可判定的，这是系统的固有现象。 自然数系统 Ｎ 中同样存在不动项，不动项的存在与不可判 定，并不影响正、反集合的递归性与系统的完全性，因此，Ｇöｄｅｌ 不完全定理的证明不成立，Ｃａｎｔｏｒ 对角线方法证明是 错误的，Ｔｕｒｉｎｇ 停机问题证明也是错误的。 “系统 Ｎ 能否完全”、实数是否可数、Ｔｕｒｉｎｇ 停机问题是否可判定都必须 重新思考。 关键词：正项；反项；不动项；悖论； Ｕ 外不动项；不可判定命题；不完全定理；对角线方法；不可数；停机问题。 中图分类号： Ｂ８１３； ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０６１８⁃１４ 中文引用格式：张金成． 逻辑及数学演算中的不动项与不可判定命题（Ⅱ）［Ｊ］． 智能系统学报， ２０１４， ９（５）： ６１８⁃６３１． 英文引用格式：ＺＨＡＮＧ Ｊｉｎｃｈｅｎｇ． Ｆｉｘｅｄ ｔｅｒｍｓ ａｎｄ ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎｓ ｉｎ ｌｏｇｉｃａｌ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｃａｌｃｕｌｕｓ （Ⅱ） ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（５）： ６１８⁃６３１． Ｆｉｘｅｄ ｔｅｒｍｓ ａｎｄ ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎｓ ｉｎ ｌｏｇｉｃａｌ ａｎｄ ｍａｔｈｅｍａｔｉｃａｌ ｃａｌｃｕｌｕｓ （Ⅱ） ＺＨＡＮＧ Ｊｉｎｃｈｅｎｇ （Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ Ｓｃｈｏｏｌ， Ｃｏｍｍｕｎｉｓｔ Ｐａｒｔｙ Ｃｏｌｌｅｇｅ， Ｇｕａｎｇｄｅ ２４２２００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓ ａ ｋｉｎｄ ｏｆ ｂｒｏａｄ ａｎｄ ｄｅｅｐ ｍａｔｈｅｍａｔｉｃａｌ ｐｈｅｎｏｍｅｎｏｎ， ｆｉｘｅｄ ｐｏｉｎｔ ｈａｓ ｐｅｎｅｔｒａｔｅｄ ｉｎｔｏ ａｌｌ ｆｉｅｌｄｓ ｏｆ ｍａｔｈ⁃ ｅｍａｔｉｃｓ． Ｔｈｉｓ ｐａｐｅｒ ｅｘｔｅｎｄｓ ｔｈｅ ｆｉｘｅｄ ｐｏｉｎｔ ｔｏ ｔｈｅ ｌｏｇｉｃａｌ ｔｈｉｎｋｉｎｇ． Ｉｔ ｐｒｏｖｅｓ ｔｈａｔ Ｒｕｓｓｅｌｌ’ｓ ｐａｒａｄｏｘ ｉｓ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｉｎ ａｃｃｏｒｄａｎｃｅ ｗｉｔｈ ｔｈｅ ｓｅｔ ｔｈｅｏｒｙ． Ｉｔ ａｌｓｏ ｐｒｏｖｅｓ ｔｈａｔ Ｇöｄｅｌ’ ｓ ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎ ｉｓ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｗｉｔｈｉｎ ｔｈｅ ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｓｙｓｔｅｍ Ｎ． Ｔｈｅ ｔｅｒｍ ｆｏｒｍｅｄ ｂｙ Ｃａｎｔｏｒ’ｓ ｄｉａｇｏｎａｌ ｍｅｔｈｏｄ ｉｓ ｆｉｘｅｄ ｔｅｒｍ ａｎｄ ｕｎｄｅｃｉｄａｂｌｅ Ｔｕｒｎｉｎｇ ｉｓ ａｌｓｏ ｆｉｘｅｄ ｔｅｒｍ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｉｔ ｃａｎ ｂｅ ｐｒｏｖｅｎ ｔｈａｔ ｗｈｅｎ ａ ｋｎｏｗｎ ｓｅｔ Ｕ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ａ ｐｏｓｉｔｉｖｅ ｓｅｔ ａｎｄ ａｎ ｉｎｖｅｒｓｅ ｓｅｔ ａｎｄ ｉｆ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｉｓ ｎｅｉｔｈｅｒ ｉｎ ｔｈｅ ｐｏｓｉｔｉｖｅ ｓｅｔ ｎｏｒ ｉｎ ｔｈｅ ｉｎｖｅｒｓｅ ｓｅｔ， ｔｈｅｎ ｔｈｉｓ ｆｉｘｅｄ ｔｅｒｍ ｍｕｓｔ ｂｅ ｔｈａｔ ｏｕｔｓｉｄｅ Ｕ ． Ｔｈｕｓ， ｉｔ ｉｓ ａｎ ｉｎｈｅｒｅｎｔ ｐｈｅｎｏｍｅｎｏｎ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ｔｈａｔ ｔｈｅ ｌｏｇｉｃａｌ ｐｒｏｐｅｒｔｙ ｏｆ ｔｈｅ ｆｉｘｅｄ ｔｅｒｍ ｅｘｃｌｕｄｅｄ ｆｒｏｍ Ｕ ｈａｓ ｃｈａｎｇｅｄ ｒｅｌａｔｉｖｅ ｔｏ Ｕ ａｎｄ ｔｈｅ ｔｈｅｏｒｅｍ ｏｆ ｆｉｘｅｄ ｔｅｒｍ ｏｕｔｓｉｄｅ Ｕ ｉｓ ｕｎｄｅｃｉｄａｂｌｅ． Ｉｎ ａｄｄｉｔｉｏｎ， ｔｈｅｒｅ ａｒｅ ａｌｓｏ ｆｉｘｅｄ ｔｅｒｍｓ ｉｎ ｔｈｅ ｎａｔｕｒａｌ ｎｕｍｂｅｒ ｓｙｓｔｅｍ Ｎ， ｗｈｅｒｅ ｔｈｅ ｅｘｉｓｔｅｎｃｅ ａｎｄ ｕｎｄｅｃｉｄａｂｉｌｉｔｙ ｄｏ ｎｏｔ ｅｘｅｒｔ ｅｆｆｅｃｔ ｏｎ ｔｈｅ ｒｅｃｕｒｓｉｖｅ ｎａｔｕｒｅ ｏｆ ｐｏｓｉｔｉｖｅ ａｎｄ ｉｎｖｅｒｓｅ ｓｅｔｓ ａｎｄ ｔｈｅ ｃｏｍｐｌｅｔｅｎｅｓｓ ｏｆ ｓｙｓｔｅｍ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｍａｔｈｅｍａｔｉｃａｌ ｐｒｏｏｆ ｆｏｒ Ｇöｄｅｌ’ｓ ｔｈｅｏｒｅｍ ｃａｎｎｏｔ ｂｅ ｔｒｕｅ ａｎｄ Ｃａｎｔｏｒ’ｓ ｄｉａｇｏｎａｌ ｍｅｔｈｏｄ ｉｓ ｐｒｏｖｅｄ ｔｏ ｂｅ ｆａｌｓｅ ａｎｄ Ｔｕｒｎｉｎｇ’ｓ ｈａｌｔｉｎｇ ｐｒｏｂｌｅｍ ｉｓ ｐｒｏｖｅｄ ｔｏ ｂｅ ｆａｌｓｅ． Ｗｈｅｔｈｅｒ ｔｈｅ ｓｙｓｔｅｍ Ｎ ｃａｎ ｂｅ ｃｏｍｐｌｅｔｅ， ｒｅａｌ ｎｕｍｂｅｒ ｉｓ ｃｏｕｎｔａｂｌｅ ｏｒ ｎｏｔ， ｗｈｅｔｈｅｒ Ｔｕｒｎｉｎｇ’ｓ ｈａｌｔ ｐｒｏｂｌｅｍ ｃａｎ ｂｅ ｄｅｃｉｄｅｄ ｓｈｏｕｌｄ ｂｅ ｒｅｃｏｎｓｉｄｅｒｅｄ． Ｋｅｙｗｏｒｄｓ：ｐｏｓｉｔｉｖｅ ｔｅｒｍ； ｉｎｖｅｒｓｅ ｔｅｒｍ； ｆｉｘｅｄ ｔｅｒｍ； ｐａｒａｄｏｘ； ｆｉｘｅｄ ｔｅｒｍ ｏｕｔｓｉｄｅ Ｕ ； ｕｎｄｅｃｉｄａｂｌｅ ｐｒｏｐｏｓｉｔｉｏｎ； ｉｎ⁃ ｃｏｍｐｌｅｔｅ ｔｈｅｏｒｅｍ； ｄｉａｇｏｎａｌ ｍｅｔｈｏｄ； ｕｎｃｏｕｎｔａｂｌｅ ｓｅｔ； ｈａｌｔｉｎｇ ｐｒｏｂｌｅｍ 收稿日期：２０１３⁃１１⁃２６． 通信作者：张金成．Ｅ⁃ｍａｉｌ：６５６７９０２０５＠ ｑｑ．ｃｏｍ．
第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·619 表1单一正集上“蕴含”的真值 4正反命题与谓词演算系统 Table 1 The truth value table of "implication"for the sin- gle positive se 4.1正反命题演算系统L“ Ata AAta 在经典系统L上引入“正反集对偶变换公理 0 P+“Pa”,组建一个新的逻辑系统一命题系 0 1 统L“: 表2单一正集上“否定”的真值 1)初始符号（略）； Table 2 The truth value table of "negation"for the single 2)命题的形成规则（略）： positive se 3)定义（略）； ta B*a A*a→B*a 4)公理。 0 0 (1)正集公理 1 1 1 L1+:A→(Ba→A): 00 1 L2*:(Aa→(B*a→C*a))→ 0 1 1 (Aa→Ba)→(Aa→C+)); 定义3单一反集上的真值表（如表3、4）。 L3*:(A→B*m)→ 表3单一反集上“蕴含”的真值 Table 3 The truth value table of "implication"for the sin- ((Aa→B*a)→Ata)》 gle inverse se (2)正反集对偶变换公理 A-a 7A4 L0:PP“(P是+a,-α的一个完全划分)： 1 0 (3)反集公理 0 L1:Aa→(Ba→A-a): 表4单一正集上“否定”的真值 L2:(Aa→(B-a→C-))→ Table 4 The truth value table of "negation"for the single (A→B“)→(Aa→C-a): positive se L3:(Aa→B-“)→((A-→B“)→A-“) A- B-4 Aa→B4 5)演绎推理规则 S 0 分离规则：若上A且上A→B;则上B; 1 1 1 定义1系统L“ 0 0 1 由以上1)~5)几个部分组成的公理系统，可以 叫做系统L“。 0 定理1经典逻辑的定理封闭域上的有效性 定义4跨正反集上的真值表（如表5）。 在系统L“中，相同集+α，一α中的命题演算， 表5跨正反集上的真值表 所有经典逻辑的定理与演算模式都是有效的。 Table 5 The truth value table for the crossing the positive and inverse sets 证明略。 pta pa 定理2正、反集上的等价替换 1 0 系统L中，设F(M,N)表示含有变项M、N的 命题公式，则如果在相同集中的经典命题上F(P, 0 1 p)成立（即上F(Pa,P+)且上F(P-a, 在表中可以看出经典二值真值表定义仍然不 P“)成立)，则在不同集中上F(P“,P-“),且 变，增加了一个跨正反集上的真值表定义。 上F(一Pa,P)也成立。 在系统L“中，利用以上“真值表”可以证明，下 证明略。 列公式是不可证的。 系统L“的语义很简单，用二值真值表定义为 公式Pa,P-a上Ba,Pa∧P-a上Ba, 定义2单一正集上的真值表 pa→(Pa→B),Pa→(p-a→B") 都不是系统L的定理
４ 正反命题与谓词演算系统 ４．１ 正反命题演算系统 Ｌ α 在经典系统 Ｌ 上引入“正反集对偶变换公理 Ｐ ＋α↔¬ Ｐ －α ”，组建一个新的逻辑系统———命题系 统 Ｌ α ： １）初始符号（略）； ２）命题的形成规则（略）； ３）定义（略）； ４）公理。 （１）正集公理 Ｌ１ ＋ ：Ａ ＋α → （Ｂ ＋α → Ａ ＋α ）； Ｌ２ ＋ ：（Ａ ＋α → （Ｂ ＋α → Ｃ ＋α ）） → （（Ａ ＋α → Ｂ ＋α ） → （Ａ ＋α → Ｃ ＋α ））； Ｌ３ ＋ ：（¬ Ａ ＋α → ¬ Ｂ ＋α ） → （（¬ Ａ ＋α → Ｂ ＋α ） → Ａ ＋α ） （２）正反集对偶变换公理 Ｌ０： Ｐ ＋α↔¬ Ｐ －α （ Ｐ 是 ＋ α， － α 的一个完全划分）； （３）反集公理 Ｌ１ － ： Ａ －α → （Ｂ －α → Ａ －α ）； Ｌ２ － ： （Ａ －α → （Ｂ －α → Ｃ －α ）） → （（Ａ －α → Ｂ －α ） → （Ａ －α → Ｃ －α ））； Ｌ３ － ：（¬ Ａ －α → ¬ Ｂ －α ） → （（¬ Ａ －α → Ｂ －α ） → Ａ －α ） ５）演绎推理规则 分离规则：若├ Ａ 且├ Ａ → Ｂ ；则├ Ｂ ； 定义 １ 系统 Ｌ α 由以上 １） ～５）几个部分组成的公理系统，可以 叫做系统 Ｌ α 。 定理 １ 经典逻辑的定理封闭域上的有效性 在系统 Ｌ α 中，相同集 ＋ α， － α 中的命题演算， 所有经典逻辑的定理与演算模式都是有效的。 证明 略。 定理 ２ 正、反集上的等价替换 系统 Ｌ α 中，设 Ｆ（Ｍ，Ｎ） 表示含有变项 Ｍ、Ｎ 的 命题公式，则如果在相同集中的经典命题 ├ Ｆ（Ｐ α ， ¬ Ｐ α ） 成 立 （ 即 ├ Ｆ（Ｐ ＋α ，¬ Ｐ ＋α ） 且 ├ Ｆ（Ｐ －α ， ¬ Ｐ －α ） 成立），则在不同集中 ├ Ｆ（Ｐ ＋α ，Ｐ －α ） ，且 ├Ｆ（¬ Ｐ －α ，¬ Ｐ ＋α ） 也成立。 证明 略。 系统 Ｌ α 的语义很简单，用二值真值表定义为 定义 ２ 单一正集上的真值表 表 １ 单一正集上“蕴含”的真值 Ｔａｂｌｅ １ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｉｍｐｌｉｃａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎ⁃ ｇｌｅ ｐｏｓｉｔｉｖｅ ｓｅ Ａ ＋α ¬ Ａ ＋α １ ０ ０ １ 表 ２ 单一正集上“否定”的真值 Ｔａｂｌｅ ２ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｎｅｇａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎｇｌｅ ｐｏｓｉｔｉｖｅ ｓｅ Ａ ＋α Ｂ ＋α Ａ ＋α → Ｂ ＋α １ ０ ０ １ １ １ ０ ０ １ ０ １ １ 定义 ３ 单一反集上的真值表（如表 ３、４）。 表 ３ 单一反集上“蕴含”的真值 Ｔａｂｌｅ ３ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｉｍｐｌｉｃａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎ⁃ ｇｌｅ ｉｎｖｅｒｓｅ ｓｅ Ａ －α ¬ Ａ －α １ ０ ０ １ 表 ４ 单一正集上“否定”的真值 Ｔａｂｌｅ ４ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｏｆ “ｎｅｇａｔｉｏｎ” ｆｏｒ ｔｈｅ ｓｉｎｇｌｅ ｐｏｓｉｔｉｖｅ ｓｅ Ａ －α Ｂ －α Ａ －α → Ｂ －α １ ０ ０ １ １ １ ０ ０ １ ０ １ １ 定义 ４ 跨正反集上的真值表（如表 ５）。 表 ５ 跨正反集上的真值表 Ｔａｂｌｅ ５ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｆｏｒ ｔｈｅ ｃｒｏｓｓｉｎｇ ｔｈｅ ｐｏｓｉｔｉｖｅ ａｎｄ ｉｎｖｅｒｓｅ ｓｅｔｓ Ｐ ＋α Ｐ －α １ ０ ０ １ 在表中可以看出经典二值真值表定义仍然不 变，增加了一个跨正反集上的真值表定义。 在系统 Ｌ α 中，利用以上“真值表”可以证明，下 列公式是不可证的。 公式 Ｐ ＋α ，¬ Ｐ －α ├ Ｂ ＋α ， Ｐ ＋α ∧ ¬ Ｐ －α ├ Ｂ －α ， Ｐ ＋α → （¬ Ｐ －α → Ｂ ＋α ） ， Ｐ ＋α → （¬ Ｐ －α → Ｂ －α ） 都不是系统 Ｌ α 的定理［３］ 。 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６１９·
·620· 智能系统学报 第9卷 4.2正反谓词演算系统K 3(x)PaH(x)P-。 1)基本符号（略） Y(x)p-+(x)P*; 2)定义（略） H(x)Pa→3(x)Pa; 3)公理 V(x)P-a3(x)P+“; (1)正集公理 3(x)P-a3(x)P“; K1*:A*a→(B*a→A); 3(x)p-+Y(x)p+a; K2*:(Aa→(B*a→C*a))→ 3(x)P(x)P"。 ((Aa→B)→(A“→Ca)): K的语义解释（略）[] K3*:(Aa→7B“)→(B→A“); 4.3系统L、的完全性与不可判定命题 K4:(x:)Aa→A“: 根据“Pa→一Pa,PaPa”可以得到， K5:H(x:)A(x:)一A(t); 任一个含有-反集的命题公式全部可以转化成正 K6*:(x)(A→B)→(A0→H(x:)B“); 集+α命题公式，即可以转化成经典命题演算公式， (2)正反集对偶变换公理 即以上正反命题演算系统L“与经典命题演算系统L KO:PanP-“(P是+a,-α的一个对称划分)； 等价。 (3)反集公理 注记1P°是U外不动项命题，是未定义命 K1:Aa→(Ba→Aa）; 题，不参与演算。 K2:(A-→(B-a→C-a)）→ 定理5L“等价系统 (A→B)→(A0→C-): 系统L“在+α与一α中的全部公式可以翻译成 K3:(Aa→B-）→(Ba→A“): 经典命题演算系统L的公式，即系统L“在+α与 K4:H(x:)Aa→Aa; -α中与经典命题演算系统L等价。 证明略 K5:(x:)A(x)→A(t); 定理6K等价系统 K6:H(x:)(A-a→B-a)→(Aa→H(x)B-): 系统K中全部公式可翻译成经典谓词演算系 4)系统内推理规则 统的公式，即系统K与经典谓词演算系统K等价。 R1分离规则：若上A且A→B,则上B; 证明略 2概括规则：若上A,则上Hx,A。 由于系统K与经典谓词演算系统K等价，所以 定义5系统K 经典逻辑的元定理在系统K“仍然成立，根据“定理 由以上1)~4)几个部分组成的公理系统，叫做 5、6”很容易证明以下定理。证明方法同经典谓词 系统K。 逻辑系统方法，这里不再给出。 在系统K中，具有与L“类似的定理（证明与L“ 系统L的一致性、可判定性、完全性等元定理， 相同)，即： 在系统L“中都是有效的； 定理3经典逻辑的定理封闭域上的有效性 系统K的一致性、不可判定性、完全性等元定 在系统K中，相同集+，一α中的命题演算， 理，在系统中都是有效的： 所有经典逻辑的定理与演算模式都是有效的。 定理7P是域外命题 定理4正、反集上的等价替换 命题P在系统L中是未定义命题，是域外命 系统K中，设F(M,N)表示含有变项M、N的 题： 命题公式，则如果在相同集中的经典命题F(P“, 证明设P是U的一个完全划分， P)成立（即F(P+“,P“)且F(P-a,P-)成 在命题演算L中，若+a=-a=e(P是+a, 立)，则在不同集中F(P“,P-“),且上F(P-“, -a的一个完全划分)，PP;e={xp}是不动 Pa)也成立。 项，xp年U是未定义项，因此P是未定义命题。 在不同集中，含有量词的公式，可以用下列公式 因此，在命题演算L中，若+a=-a=e,则P 转换： 是不动命题，e,P在U上无定义； (x)Pa→H(x)P-“; 未定义命题与其他命题的混合演算，如P∧ H(x)P+a+3(x)P-“; P→Qa;P∧P→Qa;PVP;(PV Y(x)P*+3(x)P-; P)∧(PaVP-a)等都是无意义的，不合法的。 3(x)P++3(x)P-“; 定理8系统L“完全性定理 3(x)P*+Y(x)P-a; 在系统L中，若上P或V(P)=1则L上P;
４．２ 正反谓词演算系统 Ｋ α １）基本符号（略） ２）定义（略） ３）公理 （１）正集公理 Ｋ１ ＋ ：Ａ ＋α → （Ｂ ＋α → Ａ ＋α ）； Ｋ２ ＋ ：（Ａ ＋α → （Ｂ ＋α → Ｃ ＋α ）） → （（Ａ ＋α → Ｂ ＋α ） → （Ａ ＋α → Ｃ ＋α ））； Ｋ３ ＋ ：（¬ Ａ ＋α → ¬ Ｂ ＋α ） → （Ｂ ＋α → Ａ ＋α ）； Ｋ４ ＋ ：∀（ｘｉ）Ａ ＋α → Ａ ＋α ； Ｋ５ ＋ ：∀（ｘｉ）Ａ ＋α （ｘｉ） → Ａ ＋α （ｔ）； Ｋ６ ＋ ：∀（ｘｉ）（Ａ ＋α → Ｂ ＋α ） → （Ａ ＋α → ∀（ｘｉ）Ｂ ＋α ）； （２）正反集对偶变换公理 Ｋ０：Ｐ ＋α↔¬ Ｐ －α （Ｐ 是 ＋ α， － α 的一个对称划分）； （３）反集公理 Ｋ１：Ａ －α → （Ｂ －α → Ａ －α ）； Ｋ２： （Ａ －α → （Ｂ －α → Ｃ －α ）） → （（Ａ －α → Ｂ －α ） → （Ａ －α → Ｃ －α ））； Ｋ３： （¬ Ａ －α → ¬ Ｂ －α ） → （Ｂ －α → Ａ －α ）； Ｋ４：∀（ｘｉ）Ａ －α → Ａ －α ； Ｋ５：∀（ｘｉ）Ａ －α （ｘｉ） → Ａ －α （ｔ）； Ｋ６：∀（ｘｉ）（Ａ －α → Ｂ －α ） → （Ａ －α → ∀（ｘｉ）Ｂ －α ）； ４）系统内推理规则 Ｒ１ 分离规则：若├ Ａ 且├ Ａ → Ｂ ，则├ Ｂ ； Ｒ２ 概括规则：若├ Ａ ，则├ ∀ｘｉＡ 。 定义 ５ 系统 Ｋ α 由以上 １） ～４）几个部分组成的公理系统，叫做 系统 Ｋ α 。 在系统 Ｋ α 中，具有与 Ｌ α 类似的定理（证明与 Ｌ α 相同），即： 定理 ３ 经典逻辑的定理封闭域上的有效性 在系统 Ｋ α 中，相同集 ＋ α， － α 中的命题演算， 所有经典逻辑的定理与演算模式都是有效的。 定理 ４ 正、反集上的等价替换 系统 Ｋ α 中，设 Ｆ（Ｍ，Ｎ） 表示含有变项 Ｍ、Ｎ 的 命题公式，则如果在相同集中的经典命题 Ｆ（Ｐ α ， ¬ Ｐ α ） 成立（即 Ｆ（Ｐ ＋α ，¬ Ｐ ＋α ） 且 Ｆ（Ｐ －α ，¬ Ｐ －α ） 成 立），则在不同集中 Ｆ（Ｐ ＋α ，Ｐ －α ） ， 且 ├Ｆ（¬ Ｐ －α ， ¬ Ｐ ＋α ） 也成立。 在不同集中，含有量词的公式，可以用下列公式 转换： ∀（ｘ）Ｐ ＋α↔∀（ｘ）¬ Ｐ －α ； ∀（ｘ）Ｐ ＋α↔¬ ∃（ｘ）Ｐ －α ； ¬ ∀（ｘ）Ｐ ＋α↔∃（ｘ）Ｐ －α ； ∃（ｘ）Ｐ ＋α↔∃（ｘ）¬ Ｐ －α ； ∃（ｘ）Ｐ ＋α↔¬ ∀（ｘ）Ｐ －α ； ¬ ∃（ｘ）Ｐ ＋α↔∀（ｘ）Ｐ －α 。 ∀（ｘ）Ｐ －α↔∀（ｘ）¬ Ｐ ＋α ； ∀（ｘ）Ｐ －α↔¬ ∃（ｘ）Ｐ ＋α ； ¬ ∀（ｘ）Ｐ －α↔∃（ｘ）Ｐ ＋α ； ∃（ｘ）Ｐ －α↔∃（ｘ）¬ Ｐ ＋α ； ∃（ｘ）Ｐ －α↔¬ ∀（ｘ）Ｐ ＋α ； ¬ ∃（ｘ）Ｐ －α↔∀（ｘ）Ｐ ＋α 。 Ｋ α 的语义解释（略） ［３］ ４．３ 系统 Ｌ α 、 Ｋ α 的完全性与不可判定命题 根据“ Ｐ ＋α↔¬ Ｐ －α ， Ｐ －α↔¬ Ｐ ＋α ” 可以得到， 任一个含有 － α 反集的命题公式全部可以转化成正 集 ＋ α 命题公式，即可以转化成经典命题演算公式， 即以上正反命题演算系统 Ｌ α 与经典命题演算系统 Ｌ 等价。 注记 １ Ｐ ｅ 是 Ｕ 外不动项命题，是未定义命 题，不参与演算。 定理 ５ Ｌ α 等价系统 系统 Ｌ α 在 ＋ α 与 － α 中的全部公式可以翻译成 经典命题演算系统 Ｌ 的公式，即系统 Ｌ α 在 ＋ α 与 － α 中与经典命题演算系统 Ｌ 等价。 证明 略 定理 ６ Ｋ α 等价系统 系统 Ｋ α 中全部公式可翻译成经典谓词演算系 统的公式，即系统 Ｋ α 与经典谓词演算系统 Ｋ 等价。 证明 略 由于系统 Ｋ α 与经典谓词演算系统 Ｋ 等价，所以 经典逻辑的元定理在系统 Ｋ α 仍然成立，根据“定理 ５、６”很容易证明以下定理。 证明方法同经典谓词 逻辑系统方法，这里不再给出。 系统 Ｌ 的一致性、可判定性、完全性等元定理， 在系统 Ｌ α 中都是有效的； 系统 Ｋ 的一致性、不可判定性、完全性等元定 理，在系统 Ｋ α 中都是有效的； 定理 ７ Ｐ ｅ 是域外命题 命题 Ｐ ｅ 在系统 Ｌ α 中是未定义命题，是域外命 题； 证明 设 Ｐ 是 Ｕ 的一个完全划分， 在命题演算 Ｌ α 中，若 ＋ α ＝ － α ＝ ｅ （ Ｐ 是 ＋ α， － α 的一个完全划分）， Ｐ ｅ↔¬ Ｐ ｅ ； ｅ ＝ ｘＰ { } 是不动 项， ｘＰ ∉ Ｕ 是未定义项，因此 Ｐ ｅ 是未定义命题。 因此，在命题演算 Ｌ α 中，若 ＋ α ＝ － α ＝ ｅ ，则 Ｐ ｅ 是不动命题， ｅ ， Ｐ ｅ 在 Ｕ 上无定义； 未定义命题与其他命题的混合演算，如 Ｐ ｅ ∧ ¬ Ｐ ｅ → Ｑ ＋α ； Ｐ ｅ ∧ ¬ Ｐ ｅ → Ｑ －α ； Ｐ ｅ ∨ ¬ Ｐ ｅ ； （Ｐ ｅ ∨ ¬ Ｐ ｅ ） ∧ （Ｐ ＋α ∨ Ｐ －α ） 等都是无意义的，不合法的。 定理 ８ 系统 Ｌ α 完全性定理 在系统 Ｌ α 中，若 ｜＝Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｌ α ├ Ｐ α ； ·６２０· 智 能 系 统 学 报 第 ９ 卷
第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·621. 证明因为L“L,而系统L是完全的，即： 合，经典逻辑的所有定理只适用于已经定义的集合 若P,则L上Pa:所以，若上P或V(pa)=1 U上。 则L上Pa; 证明设U=+αU-α是一个已定义集合； 所以，系统L“也是完全的。 假设在这个已定义集合外，可以适用经典逻辑 定理9P是不可判定命题 的所有定理，根据U外不动项定理， 命题P在系统L“中是不可判定命题（证明略， 那么，有矛盾命题P(xp)P(xp)成立； 因为不动命题是不可判定命题)。 根据邓一斯各特定理（上A,上一A,那么 注记2悖论P不参与系统演算 上B),这个逻辑系统中一切命题都是定理，这是一 1)虽然系统L中出现了悖论P,但是，P是 个崩溃的系统； 未定义命题，不参与系统演算，不会导致系统L“演 所以，经典逻辑的所有定理只适用于已经定义 算崩遗，系统L“仍然是有效的。 的集合U上。 2)虽然系统L“中出现了不可判定P,但是，P 定理14“反证法”的适用范围 与系统完全性无关，系统L“仍然是完全的，系统L“ U={x,x2,x3,…,x,…}是一个已经定义集 的定理集合是可判定的。 合，“反证法”只适用于已经定义的集合U上。 定理10P(xp)是域外命题 证明因为，反证法是经典逻辑的一条定理， 命题P(xp)在系统K中是未定义命题； 即：如果A上B且A上B,那么上A; 根据定理13，“反证法”只适用于已经定义的集 证明同上，在谓词演算中，若x:=x:=xp,则 合U上。 P(xp)是不动命题，xp、P(xp)在U上无定义。 定理15不动项矛盾用于“反证法”的限制 与系统L一样，未定义命题P(x)与其他命题 U={x1,x2,x3,…,xn,…}是一个已经定义集 的混合演算，如P(xp)A一P(x)、P(xp)A 合，不动项矛盾不能作为“反证法”在已定义的集合 P(xp)→Q(x:)、P(xp)VP(xp)等都是无意 U上的推理依据。 义的，不合法的。 证明因为根据U外不动项定理，不动项矛盾 定理11系统完全性定理 是已定义集合外的矛盾： 系统K中，若=Pa或V(Pa)=1则a上P; 假设不动项矛盾能作为“反证法”在已定义的 证明因为K“一K,而系统K是完全的，即 集合上的推理依据。 若P,则K上pm;所以，若=Pa或V(P)=1 那么，有矛盾命题P(xp)P(xp)成立，而且 则K上P; 这是一个U外恒成立的矛盾； 所以，系统K也是完全的。 根据邓一斯各特定理（上A,上A,那么 定理12P(xp)是不可判定命题 上B),这个逻辑系统中一切命题都是定理，这是一 命题P(xp)在系统K中是不可判定命题（证 个崩溃的系统： 明略，因为不动命题是不可判定命题)。 如果不动项矛盾能作为“反证法”在已定义的集合 注记3悖论P(xp)不参与系统演算 U上的推理依据，将建立不起来任何足道的系统： 1)虽然系统K中出现了悖论P(xp),但是， 所以，不动项矛盾不能作为“反证法”在已定义 P(x)是未定义命题，不参与系统演算，不会导致系 的集合U上的推理依据。 统K演算崩溃，系统仍然是有效的。 在逻辑系统L“、中，若U= 2)虽然系统K中出现了不可判定P(xp),但是， {x1,x2,x3,…,xn,…}是已定义集合，P是U上的任 P(xp)与系统完全性无关，系统K仍是完全的。 意一个有定义的性质，若x:∈U,则P(x:)、一P(x:) 4.4经典逻辑定理的适用范围 是有定义、有意义的命题；若x:U,则P(x:)、 定义6超协调逻辑系统 P(x:)是无定义、无意义的命题。 正反命题演算系统“L“”与正反谓词系统 推论1构造悖论，不能作为“反证法”在已定 “”也称超协调逻辑系统。 义的集合U上的推理依据。 在超协调系统中，可以发现经典逻辑是定义在 例1构造悖论的错误证明方法 一个已知集合U上的，不能无限制地使用到U外， 举出一个具体的例子，U为全体整数集合U= 经典逻辑的推理有一个使用范围。 J,假设在n=n中，任意n∈J;把U=J分成偶数 定理13经典逻辑的适用范围 集合与奇数集合： U={x1,x2,x3,…,xn,…}是一个已经定义集 +a={x|x=2n,n∈U}
证明 因为 Ｌ α⇔Ｌ ，而系统 Ｌ 是完全的，即： 若 ｜＝Ｐ α ，则 Ｌ ├ Ｐ α ；所以，若 ├Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｌ α ├ Ｐ α ； 所以，系统 Ｌ α 也是完全的。 定理 ９ Ｐ ｅ 是不可判定命题 命题 Ｐ ｅ 在系统 Ｌ α 中是不可判定命题（证明略， 因为不动命题是不可判定命题）。 注记 ２ 悖论 Ｐ ｅ 不参与系统演算 １）虽然系统 Ｌ α 中出现了悖论 Ｐ ｅ ，但是， Ｐ ｅ 是 未定义命题，不参与系统演算，不会导致系统 Ｌ α 演 算崩溃，系统 Ｌ α 仍然是有效的。 ２）虽然系统 Ｌ α 中出现了不可判定 Ｐ ｅ ，但是， Ｐ ｅ 与系统完全性无关，系统 Ｌ α 仍然是完全的，系统 Ｌ α 的定理集合是可判定的。 定理 １０ Ｐ（ｘＰ ） 是域外命题 命题 Ｐ（ｘＰ ） 在系统 Ｋ α 中是未定义命题； 证明同上，在谓词演算中，若 ｘｉ ＝ ｘｉ ＝ ｘＰ ，则 Ｐ（ｘＰ ） 是不动命题， ｘＰ 、 Ｐ（ｘＰ ） 在 Ｕ 上无定义。 与系统 Ｌ α 一样，未定义命题 Ｐ（ｘＰ ） 与其他命题 的混 合 演 算， 如 Ｐ（ｘＰ ） ∧ ¬ Ｐ（ｘｉ） 、 Ｐ（ｘＰ ） ∧ ¬ Ｐ（ｘＰ ） → Ｑ（ｘｉ） 、 Ｐ（ｘＰ ） ∨ ¬ Ｐ（ｘＰ ） 等都是无意 义的，不合法的。 定理 １１ 系统 Ｋ α 完全性定理 系统 Ｋ α 中，若 ｜＝Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｋ α ├ Ｐ α ； 证明 因为 Ｋ α⇔Ｋ ，而系统 Ｋ 是完全的，即 若 ｜＝Ｐ α ，则 Ｋ ├ Ｐ α ；所以，若 ｜＝Ｐ α 或 Ｖ（Ｐ α ） ＝ １ 则 Ｋ α ├ Ｐ α ； 所以，系统 Ｋ α 也是完全的。 定理 １２ Ｐ（ｘＰ ） 是不可判定命题 命题 Ｐ（ｘＰ ） 在系统 Ｋ α 中是不可判定命题（证 明略，因为不动命题是不可判定命题）。 注记 ３ 悖论 Ｐ（ｘＰ ） 不参与系统演算 １） 虽然系统 Ｋ α 中出现了悖论 Ｐ（ｘＰ ） ，但是， Ｐ（ｘＰ ） 是未定义命题，不参与系统演算，不会导致系 统 Ｋ α 演算崩溃，系统 Ｋ α 仍然是有效的。 ２）虽然系统 Ｋ α 中出现了不可判定 Ｐ（ｘＰ） ，但是， Ｐ（ｘＰ） 与系统完全性无关，系统 Ｋ α 仍是完全的。 ４．４ 经典逻辑定理的适用范围 定义 ６ 超协调逻辑系统 正反命题演算系统 “ Ｌ α ” 与正反谓词系统 “ Ｋ α ”也称超协调逻辑系统。 在超协调系统中，可以发现经典逻辑是定义在 一个已知集合 Ｕ 上的，不能无限制地使用到 Ｕ 外， 经典逻辑的推理有一个使用范围。 定理 １３ 经典逻辑的适用范围 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，经典逻辑的所有定理只适用于已经定义的集合 Ｕ 上。 证明 设 Ｕ ＝ ＋ α ∪－ α 是一个已定义集合； 假设在这个已定义集合外，可以适用经典逻辑 的所有定理，根据 Ｕ 外不动项定理， 那么，有矛盾命题 Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） 成立； 根 据 邓—斯 各 特 定 理 （ ├ Ａ ， ├ ¬ Ａ ， 那 么 ├ Ｂ ），这个逻辑系统中一切命题都是定理，这是一 个崩溃的系统； 所以，经典逻辑的所有定理只适用于已经定义 的集合 Ｕ 上。 定理 １４ “反证法”的适用范围 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，“反证法”只适用于已经定义的集合 Ｕ 上。 证明 因为，反证法是经典逻辑的一条定理， 即：如果 Ａ ├ Ｂ 且 Ａ ├ ¬ Ｂ ，那么├ ¬ Ａ ； 根据定理 １３，“反证法”只适用于已经定义的集 合 Ｕ 上。 定理 １５ 不动项矛盾用于“反证法”的限制 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，不动项矛盾不能作为“反证法”在已定义的集合 Ｕ 上的推理依据。 证明 因为根据 Ｕ 外不动项定理，不动项矛盾 是已定义集合外的矛盾； 假设不动项矛盾能作为“反证法”在已定义的 集合上的推理依据。 那么，有矛盾命题 Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） 成立，而且 这是一个 Ｕ 外恒成立的矛盾； 根 据 邓—斯 各 特 定 理 （ ├ Ａ ， ├ ¬ Ａ ， 那 么 ├ Ｂ ），这个逻辑系统中一切命题都是定理，这是一 个崩溃的系统； 如果不动项矛盾能作为“反证法”在已定义的集合 Ｕ 上的推理依据，将建立不起来任何足道的系统； 所以，不动项矛盾不能作为“反证法”在已定义 的集合 Ｕ 上的推理依据。 在 逻 辑 系 统 Ｌ α 、Ｋ α 中， 若 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是已定义集合， Ｐ 是 Ｕ 上的任 意一个有定义的性质，若 ｘｉ ∈ Ｕ ，则 Ｐ（ｘｉ）、¬ Ｐ（ｘｉ） 是有定义、有意义的命题；若 ｘｉ ∉ Ｕ ，则 Ｐ（ｘｉ）、 ¬ Ｐ（ｘｉ） 是无定义、无意义的命题。 推论 １ 构造悖论，不能作为“反证法”在已定 义的集合 Ｕ 上的推理依据。 例 １ 构造悖论的错误证明方法 举出一个具体的例子， Ｕ 为全体整数集合 Ｕ ＝ Ｊ， 假设在 ｎ ＝ ｎ 中，任意 ｎ ∈ Ｊ ； 把 Ｕ ＝ Ｊ 分成偶数 集合与奇数集合： ＋ α ＝ {ｘ ｜ ｘ ＝ ２ｎ，ｎ ∈ Ｕ} 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２１·
.622. 智能系统学报 第9卷 -a={xlx=1-2n,n∈U} 在假设M~PM中，任意x∈M对应一个y∈ P(x)代表谓词“x是偶数”，一P(x)代表谓词“x PM,即：x∈M→y∈PM, 是奇数”；n∈+a,或者n∈-a;定义一个新数 y是M的子集之一，yCM, T=1-n;自指代T=n,n=1-n,n是偶数n是 x∈y,或者x庄y;规定：x∈yx生T;x生 奇数；产生悖论，不可判定命题P(n)P(n);即 y→xeT; n=n FP(n)P(n) 假定T∈PM,M~PM,存在 根据反证法得到，十n≠n,这显然是荒唐的结论。 xo∈M→T∈PM; 例2相对无意义的命题 按规定：x0∈T→x0使T;x0生T→x0∈T; 设U为全体整数集合，P(x):表示x是偶数； 矛盾，所以，TPM。 则P(0),P(2),P(7),…等都是有定义、有意义的 注：这证明在很多“数理逻辑”书中都可以见 2 命题：P(,P(了)，P(),…都是无定义、无意 到，如《元数学导论》。 5.1无穷集合演算中的不动项 义的命题。 在以上证明过程中，构造的集合T,如果按照 U={x1,x2,x3,…,xn,…}是一个已经定义集 正反集合分析法，实际上是一个不动项，证明如下。 合，如果A上P(x;)AP(x),且x:∈U,可以使 定理16无穷集合演算中存在不动项 用“反证法”，上一A,这是正确的证明方法。 如果无穷集合与它的幂集合之间能建立一一映 注记5“反证法”的正确推理形式 射，那么，幂集合演算中存在一个不动项。 一般地，设U=+αU-a是一个已定义集合， 证明首先把以上证明过程，整理如下： x:∈U,K(x)是U内的任意一个命题，根据U外不 假设在双射关系F:M~PM中，任意x∈M对 动项定理，上P(xp)P(xp)。 应一个F(x)∈PM, 1)U外不动项所产生的矛盾，使用“反证法”只 即：x∈MF(x)∈PM,F(x))是M的子集 能得出xp主U。即把xp∈U看成假设时，可以使 之一，F(x)SM; 用“反证法”进行推理，正确的推理形式是： x∈F(x),或者xF(x); K(x;),%p EUFP(xp)P(xp), 规定：x∈F(x)x生TM: 上(xp∈U)。 x生F(x)x∈TM; 2)U外不动项所产生的矛盾，不能作为任何“U 假定TM∈PM,M~PM,存在 内演算的推理依据”即把xp∈U看成真命题时，使用 xo∈MF(xo)∈PM,(设TM=F(xo); “反证法”是错误的。不正确的推理形式是： 按规定：x0∈F(xo)x0生F(xo);x0 K(x;)FP(xp)P(xp),HK(x;) F(xo)x∈F(xo)。再把PM分为正反集合，设： 3)一般使用“自指代”所产生的矛盾，都是域外 +a={X:x∈M,x∈X,X∈PM,X=F(x)} 矛盾，不能作为反证法的依据。 -a={X:x∈M,xX,X∈PM,X=F(x)} 可以回顾一下，历史上“直觉主义”者，也认识到 U=PM=+aU-a 无限制地使用“反证法”会有问题，他们转向完全的 按规定：x∈F(x)x生TM;x生F(x)x∈ “构造数学”，他们也看到一些问题，但是，没有把问题 TM,自我指代：TM=F(xo),即xo∈F(xo)→x0 完全搞清。这里真正看到“反证法”的使用范围。 F(x),x0∈TM→x0生TM,P[F(x)]表示x∈ 5无穷集合的幂集中的不可判定命题 F(x);则P[F(x)]表示x生F(x)。 命题x0∈F(xo)x生F(x),TM=F(xo）, 集合论的创立者Cantor证明：无穷集合的幂集 可以表示为P(TM)P(TM);TM是不动项。 合不能与原来的集合建立一一对应关系。可以回顾 如果(TM∈PM),则有悖论 一下其证明过程，使用Cantor的对角线方法。 P(Tu)P(TM);即：如果双射关系F:M~PM 如果PM为M的幂集，且M~PM(M与PM之 成立，那么，T是不动项。 间可以建立一一对应关系，即双射关系)，则存在 这是“Cantor的对角线方法”证明，在这个证明 T,TCM,且TPM。 中，他把T,看成是一个已知项TM∈U,实际上 对于一个M子集而言，如果能够决定M的元素 TM∈U未必成立，他只证明了以下结果： 中哪些属于该子集，那么M的子集就确定了。可以 如果双射关系F:M~PM成立，且TM∈U,那 给出一个一般准则，由它可以对M的任何元素x,决 么，P(TM)nP(TM);即(F:M~PM)A(TM∈ 定该元素是否属于该子集。 U)上P(Tg)P(TM)o
－ α ＝ {ｘ ｜ ｘ ＝ １ － ２ｎ，ｎ ∈ Ｕ} Ｐ（ｘ） 代表谓词“ ｘ 是偶数”， ¬ Ｐ（ｘ） 代表谓词“ ｘ 是奇数”； ｎ ∈＋ α ，或者 ｎ ∈－ α ； 定义一个新数 Ｔ ＝１ － ｎ ；自指代 Ｔ ＝ ｎ ， ｎ ＝ １ － ｎ ， ｎ 是偶数 ↔ ｎ 是 奇数；产生悖论，不可判定命题 Ｐ（ｎ）↔¬ Ｐ（ｎ） ；即 ｎ ＝ ｎ├Ｐ（ｎ）↔¬ Ｐ（ｎ） 根据反证法得到， ├ｎ ≠ ｎ ，这显然是荒唐的结论。 例 ２ 相对无意义的命题 设 Ｕ 为全体整数集合， Ｐ（ｘ） ：表示 ｘ 是偶数； 则 Ｐ（０），Ｐ（２），Ｐ（７），… 等都是有定义、有意义的 命题； Ｐ（ １ ２ ），Ｐ（ １ ３ ），Ｐ（ ２ ３ ），… 都是无定义、无意 义的命题。 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 是一个已经定义集 合，如果 Ａ ├ Ｐ（ｘｉ） ∧ ¬ Ｐ（ｘｉ） ，且 ｘｉ ∈ Ｕ ，可以使 用“反证法”，├ ¬ Ａ ，这是正确的证明方法。 注记 ５ “反证法”的正确推理形式 一般地，设 Ｕ ＝ ＋ α ∪－ α 是一个已定义集合， ｘｉ ∈Ｕ ， Ｋ（ｘｉ） 是 Ｕ 内的任意一个命题，根据 Ｕ 外不 动项定理， ├Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） 。 １） Ｕ 外不动项所产生的矛盾，使用“反证法”只 能得出 ｘＰ ∉ Ｕ 。 即把 ｘＰ ∈ Ｕ 看成假设时，可以使 用“反证法”进行推理，正确的推理形式是： Ｋ（ｘｉ），ｘＰ ∈ Ｕ├Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） ， ├¬ （ｘＰ ∈ Ｕ） 。 ２） Ｕ 外不动项所产生的矛盾，不能作为任何“ Ｕ 内演算的推理依据” 即把 ｘＰ ∈Ｕ 看成真命题时，使用 “反证法”是错误的。 不正确的推理形式是： Ｋ（ｘｉ）├Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） ， ├¬ Ｋ（ｘｉ） 。 ３）一般使用“自指代”所产生的矛盾，都是域外 矛盾，不能作为反证法的依据。 可以回顾一下，历史上“直觉主义”者，也认识到 无限制地使用“反证法”会有问题，他们转向完全的 “构造数学”，他们也看到一些问题，但是，没有把问题 完全搞清。 这里真正看到“反证法”的使用范围。 ５ 无穷集合的幂集中的不可判定命题 集合论的创立者 Ｃａｎｔｏｒ 证明：无穷集合的幂集 合不能与原来的集合建立一一对应关系。 可以回顾 一下其证明过程，使用 Ｃａｎｔｏｒ 的对角线方法。 如果 ＰＭ 为 Ｍ 的幂集，且 Ｍ ～ ＰＭ （ Ｍ 与 ＰＭ 之 间可以建立一一对应关系，即双射关系），则存在 Ｔ ， Ｔ ⊆ Ｍ ，且 Ｔ ∉ ＰＭ 。 对于一个 Ｍ 子集而言，如果能够决定 Ｍ 的元素 中哪些属于该子集，那么 Ｍ 的子集就确定了。 可以 给出一个一般准则，由它可以对 Ｍ 的任何元素 ｘ， 决 定该元素是否属于该子集。 在假设 Ｍ ～ ＰＭ 中，任意 ｘ ∈ Ｍ 对应一个 ｙ ∈ ＰＭ ，即： ｘ ∈ Ｍ↔ｙ ∈ ＰＭ ， ｙ 是 Ｍ 的子集之一， ｙ ⊆ Ｍ ， ｘ ∈ ｙ ，或者 ｘ ∉ ｙ ；规定： ｘ ∈ ｙ↔ｘ ∉ Ｔ ； ｘ ∉ ｙ↔ｘ ∈ Ｔ ； 假定 Ｔ ∈ ＰＭ ， Ｍ ～ ＰＭ ，存在 ｘ０ ∈ Ｍ↔Ｔ ∈ ＰＭ ； 按规定： ｘ０ ∈ Ｔ↔ｘ０ ∉ Ｔ ； ｘ０ ∉ Ｔ↔ｘ０ ∈ Ｔ ； 矛盾，所以， Ｔ ∉ ＰＭ 。 注：这证明在很多“数理逻辑” 书中都可以见 到，如《元数学导论》 ［７］ 。 ５．１ 无穷集合演算中的不动项 在以上证明过程中，构造的集合 Ｔ ，如果按照 正反集合分析法，实际上是一个不动项，证明如下。 定理 １６ 无穷集合演算中存在不动项 如果无穷集合与它的幂集合之间能建立一一映 射，那么，幂集合演算中存在一个不动项。 证明 首先把以上证明过程，整理如下： 假设在双射关系 Ｆ：Ｍ ～ ＰＭ 中，任意 ｘ ∈ Ｍ 对 应一个 Ｆ（ｘ） ∈ ＰＭ ， 即： ｘ ∈ Ｍ↔Ｆ（ｘ） ∈ ＰＭ ， Ｆ（ｘ） ）是 Ｍ 的子集 之一， Ｆ（ｘ） ⊆ Ｍ ； ｘ ∈ Ｆ（ｘ） ，或者 ｘ ∉ Ｆ（ｘ） ； 规定： ｘ ∈ Ｆ（ｘ）↔ｘ ∉ ＴＭ ； ｘ ∉ Ｆ（ｘ）↔ｘ ∈ ＴＭ ； 假定 ＴＭ ∈ ＰＭ ， Ｍ ～ ＰＭ ，存在 ｘ０ ∈ Ｍ↔Ｆ（ｘ０ ） ∈ ＰＭ ，（设 ＴＭ ＝ Ｆ（ｘ０ ） ； 按 规 定： ｘ０ ∈ Ｆ（ｘ０ ）↔ｘ０ ∉ Ｆ（ｘ０ ） ； ｘ０ ∉ Ｆ（ｘ０ ）↔ｘ０ ∈ Ｆ（ｘ０ ） 。 再把 ＰＭ 分为正反集合，设： ＋ α ＝ {Ｘ：ｘ ∈ Ｍ，ｘ ∈ Ｘ，Ｘ ∈ ＰＭ，Ｘ ＝ Ｆ（ｘ）} － α ＝ {Ｘ：ｘ ∈ Ｍ，ｘ ∉ Ｘ，Ｘ ∈ ＰＭ，Ｘ ＝ Ｆ（ｘ）} Ｕ ＝ ＰＭ ＝ ＋ α ∪－ α 按规定： ｘ ∈ Ｆ（ｘ）↔ｘ ∉ ＴＭ ； ｘ ∉ Ｆ（ｘ）↔ｘ ∈ ＴＭ ，自我指代： ＴＭ ＝ Ｆ（ｘ０ ）， 即 ｘ０ ∈ Ｆ（ｘ０ ）↔ｘ０ ∉ Ｆ（ｘ０ ），ｘ０ ∈ ＴＭ↔ｘ０ ∉ ＴＭ ， Ｐ［Ｆ（ｘ）］ 表 示 ｘ ∈ Ｆ（ｘ）； 则 ¬ Ｐ［Ｆ（ｘ）］ 表示 ｘ ∉ Ｆ（ｘ） 。 命题 ｘ０ ∈ Ｆ（ｘ０ ）↔ｘ０ ∉ Ｆ（ｘ０ ） ， ＴＭ ＝ Ｆ（ｘ０ ）， 可以表示为 Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） ； ＴＭ 是不动项。 如 果 （ＴＭ ∈ ＰＭ） ， 则 有 悖 论 Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ）； 即：如果双射关系 Ｆ：Ｍ ～ ＰＭ 成立，那么， ＴＭ 是不动项。 这是“Ｃａｎｔｏｒ 的对角线方法”证明，在这个证明 中，他把 ＴＭ 看成是一个已知项 ＴＭ ∈ Ｕ ，实际上 ＴＭ ∈Ｕ 未必成立，他只证明了以下结果： 如果双射关系 Ｆ：Ｍ ～ ＰＭ 成立，且 ＴＭ ∈ Ｕ ，那 么， Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） ；即 （Ｆ：Ｍ ～ ＰＭ） ∧ （ＴＭ ∈ Ｕ） ├ Ｐ（ＴＭ ）↔¬ Ｐ（ＴＭ ） 。 ·６２２· 智 能 系 统 学 报 第 ９ 卷