第9卷第4期 智能系统学报 Vol.9 No.4 2014年8月 CAAI Transactions on Intelligent Systems Agu.2014 D0I:10.3969/j.issn.1673-4785.201310076 网络出版t地址:http://www.cnki.net/kcms/doi/10.3969/j.issn.1673-4785.201310076.html 逻辑及数学演算中的不动项与不可判定命题(「) 张金成 (中央党校函授学院,安徽广德242200) 摘要:不动点是一个广泛而深刻的数学现象,它已经渗透到数学的各个领域。把不动点推广到逻辑思维领域,将证明 Russel悖论是集合论中的不动项,Gdel不可判定命题是自然数系统N中的不动项,Cantor对角线方法构造的项是不动项, 不可判定的Tig机也是不动项。进一步可以证明,当一个已知集合U可以分割成正、反集合时,不动项不在正集或反集 之中,不动项一定是·外不动项,·外不动项的逻辑性质相对于U已经发生变异,是未定义项,U外不动项命题是不可判定 的,这是系统的固有现象。自然数系统N中同样存在不动项,不动项的存在与不可判定,并不影响正、反集合的递归性与系 统的完全性,因此,Gdel不完全定理的证明不成立,Cantor对角线方法证明是错误的,Turing停机问题证明也是错误的。 “系统N能否完全”?实数是否可数?Tuig停机问题是否可判定?都必须重新思考。 关键词:正项;反项;不动项:悖论:U外不动项:不可判定命题;不完全定理;对角线方法;不可数:停机问题 中图分类号:TP18:0141文献标志码:A文章编号:1673-4785(2014)04-499-12 中文引用格式:张金成.逻辑及数学演算中的不动项与不可判定命题(I)[J].智能系统学报,2014,9(4):499510. 英文引用格式:ZHANG Jincheng.Fixed terms and undecidable propositions in logical and mathematical calculus(I)[J].CAAI Transactions on Intelligent Systems,2014,9(4):499-510. Fixed terms and undecidable propositions in logical and mathematical calculus(I) ZHANG Jincheng (Correspondence School of the C.P.C.Central Party School,Guangde 242200,China) Abstract:As a kind of broad and deep mathematical phenomenon,the fixed point has penetrated into all fields of mathematics.In this paper,the fixed point is extended to the logic thinking area and is about to prove that Russell' s paradox is the fixed term that is in accordance with the set theory and that Godel's undecidable proposition is the fixed term within the natural number system N,a term formed by Cantor's diagonal method is the fixed term and un- decidable Turning is also a fixed term.Furthermore it can be shown that when a known set U can be 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 logic property of the fixed term excluded from U has changed relative to U and the theorem of the fixed term outside U is undecidable.In addition, there are also fixed terms in the natural number system N,where the existence and undecidability does not have an effect on the recursive nature of the positive and inverse sets as well as the completeness of the system.Therefore,the mathematical proof for Godel's theorem cannot be true and Cantor's diagonal method is proved to be false and Turn- ing's halting problem is also proved to be false.Whether or not the system N can be complete,the real number is countable or not,or whether or not 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.网络出版日期:2014-06-21. 通信作者:张金成.E-mail:656790205@qg-com 一个多世纪以来,出现了众多的解决方案。然而,这
第 怨 卷第 源 期摇摇摇摇摇 摇摇摇 摇摇摇 摇摇摇 智 能 系 统 学 报摇摇摇摇摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 灾燥造援怨 翼援源 圆园员源 年 愿 月摇摇摇摇摇摇摇摇摇摇摇摇 悦粤粤陨 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 陨灶贼藻造造蚤早藻灶贼 杂赠泽贼藻皂泽 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 粤早怎援 圆园员源 阅韵陨院员园援猿怨远怨 辕 躁援蚤泽泽灶援员远苑猿鄄源苑愿缘援圆园员猿员园园苑远 网络出版地址院澡贼贼责院 辕 辕 憎憎憎援糟灶噪蚤援灶藻贼 辕 噪糟皂泽 辕 凿燥蚤 辕 员园援猿怨远怨 辕 躁援蚤泽泽灶援员远苑猿鄄源苑愿缘援圆园员猿员园园苑远援澡贼皂造 逻辑及数学演算中的不动项与不可判定命题渊玉冤 张金成 渊中央党校函授学院袁安徽 广德 圆源圆圆园园冤 摘 要院不动点是一个广泛而深刻的数学现象袁它已经渗透到数学的各个领域遥 把不动点推广到逻辑思维领域袁将证明 砸怎泽泽藻造 悖论是集合论中的不动项袁郧觟凿藻造 不可判定命题是自然数系统 晕 中的不动项袁悦葬灶贼燥则 对角线方法构造的项是不动项袁 不可判定的 栽怎则蚤灶早 机也是不动项遥 进一步可以证明袁当一个已知集合 哉 可以分割成正尧反集合时袁不动项不在正集或反集 之中袁不动项一定是哉 外不动项袁哉 外不动项的逻辑性质相对于哉 已经发生变异袁是未定义项袁哉 外不动项命题是不可判定 的袁这是系统的固有现象遥 自然数系统 晕 中同样存在不动项袁不动项的存在与不可判定袁并不影响正尧反集合的递归性与系 统的完全性袁因此袁郧觟凿藻造 不完全定理的证明不成立袁悦葬灶贼燥则 对角线方法证明是错误的袁栽怎则蚤灶早 停机问题证明也是错误的遥 野系统 晕 能否完全冶钥 实数是否可数钥 栽怎则蚤灶早 停机问题是否可判定钥 都必须重新思考遥 关键词院正项曰反项曰不动项曰悖论曰 哉 外不动项曰不可判定命题曰不完全定理曰对角线方法曰不可数曰停机问题 中图分类号院 栽孕员愿曰韵员源员摇 文献标志码院粤摇 文章编号院员远苑猿鄄源苑愿缘渊圆园员源冤园源鄄源怨怨鄄员圆 中文引用格式院张金成援 逻辑及数学演算中的不动项与不可判定命题渊玉冤 咱允暂援 智能系统学报袁 圆园员源袁 怨渊源冤 院 源怨怨鄄缘员园援 英文引用格式院在匀粤晕郧 允蚤灶糟澡藻灶早援 云蚤曾藻凿 贼藻则皂泽 葬灶凿 怎灶凿藻糟蚤凿葬遭造藻 责则燥责燥泽蚤贼蚤燥灶泽 蚤灶 造燥早蚤糟葬造 葬灶凿 皂葬贼澡藻皂葬贼蚤糟葬造 糟葬造糟怎造怎泽渊玉冤 咱 允暂援 悦粤粤陨 栽则葬灶泽葬糟贼蚤燥灶泽 燥灶 陨灶贼藻造造蚤早藻灶贼 杂赠泽贼藻皂泽袁 圆园员源袁 怨渊源冤 院 源怨怨鄄缘员园援 云蚤曾藻凿 贼藻则皂泽 葬灶凿 怎灶凿藻糟蚤凿葬遭造藻 责则燥责燥泽蚤贼蚤燥灶泽 蚤灶 造燥早蚤糟葬造 葬灶凿 皂葬贼澡藻皂葬贼蚤糟葬造 糟葬造糟怎造怎泽渊玉冤 在匀粤晕郧 允蚤灶糟澡藻灶早 渊悦燥则则藻泽责燥灶凿藻灶糟藻 杂糟澡燥燥造 燥枣 贼澡藻 悦援孕援悦援 悦藻灶贼则葬造 孕葬则贼赠 杂糟澡燥燥造袁 郧怎葬灶早凿藻 圆源圆圆园园袁 悦澡蚤灶葬冤 粤遭泽贼则葬糟贼院粤泽 葬 噪蚤灶凿 燥枣 遭则燥葬凿 葬灶凿 凿藻藻责 皂葬贼澡藻皂葬贼蚤糟葬造 责澡藻灶燥皂藻灶燥灶袁 贼澡藻 枣蚤曾藻凿 责燥蚤灶贼 澡葬泽 责藻灶藻贼则葬贼藻凿 蚤灶贼燥 葬造造 枣蚤藻造凿泽 燥枣 皂葬贼澡藻皂葬贼蚤糟泽援 陨灶 贼澡蚤泽 责葬责藻则袁 贼澡藻 枣蚤曾藻凿 责燥蚤灶贼 蚤泽 藻曾贼藻灶凿藻凿 贼燥 贼澡藻 造燥早蚤糟 贼澡蚤灶噪蚤灶早 葬则藻葬 葬灶凿 蚤泽 葬遭燥怎贼 贼燥 责则燥增藻 贼澡葬贼 砸怎泽泽藻造造爷 泽 责葬则葬凿燥曾 蚤泽 贼澡藻 枣蚤曾藻凿 贼藻则皂 贼澡葬贼 蚤泽 蚤灶 葬糟糟燥则凿葬灶糟藻 憎蚤贼澡 贼澡藻 泽藻贼 贼澡藻燥则赠 葬灶凿 贼澡葬贼 郧觟凿藻造爷泽 怎灶凿藻糟蚤凿葬遭造藻 责则燥责燥泽蚤贼蚤燥灶 蚤泽 贼澡藻 枣蚤曾藻凿 贼藻则皂 憎蚤贼澡蚤灶 贼澡藻 灶葬贼怎则葬造 灶怎皂遭藻则 泽赠泽贼藻皂 晕 袁 葬 贼藻则皂 枣燥则皂藻凿 遭赠 悦葬灶贼燥则爷泽 凿蚤葬早燥灶葬造 皂藻贼澡燥凿 蚤泽 贼澡藻 枣蚤曾藻凿 贼藻则皂 葬灶凿 怎灶鄄 凿藻糟蚤凿葬遭造藻 栽怎则灶蚤灶早 蚤泽 葬造泽燥 葬 枣蚤曾藻凿 贼藻则皂援 云怎则贼澡藻则皂燥则藻 蚤贼 糟葬灶 遭藻 泽澡燥憎灶 贼澡葬贼 憎澡藻灶 葬 噪灶燥憎灶 泽藻贼 哉 糟葬灶 遭藻 凿蚤增蚤凿藻凿 蚤灶贼燥 葬 责燥泽蚤贼蚤增藻 泽藻贼 葬灶凿 葬灶 蚤灶增藻则泽藻 泽藻贼 葬灶凿 蚤枣 贼澡藻 枣蚤曾藻凿 贼藻则皂 蚤泽 灶藻蚤贼澡藻则 蚤灶 贼澡藻 责燥泽蚤贼蚤增藻 泽藻贼 灶燥则 蚤灶 贼澡藻 蚤灶增藻则泽藻 泽藻贼袁 贼澡藻灶 贼澡蚤泽 枣蚤曾藻凿 贼藻则皂 皂怎泽贼 遭藻 贼澡葬贼 燥怎贼泽蚤凿藻 哉 援 栽澡怎泽 蚤贼 蚤泽 葬灶 蚤灶澡藻则藻灶贼 责澡藻灶燥皂藻灶燥灶 燥枣 贼澡藻 泽赠泽贼藻皂 贼澡葬贼 贼澡藻 造燥早蚤糟 责则燥责藻则贼赠 燥枣 贼澡藻 枣蚤曾藻凿 贼藻则皂 藻曾糟造怎凿藻凿 枣则燥皂 哉 澡葬泽 糟澡葬灶早藻凿 则藻造葬贼蚤增藻 贼燥 哉 葬灶凿 贼澡藻 贼澡藻燥则藻皂 燥枣 贼澡藻 枣蚤曾藻凿 贼藻则皂 燥怎贼泽蚤凿藻 哉 蚤泽 怎灶凿藻糟蚤凿葬遭造藻援 陨灶 葬凿凿蚤贼蚤燥灶袁 贼澡藻则藻 葬则藻 葬造泽燥 枣蚤曾藻凿 贼藻则皂泽 蚤灶 贼澡藻 灶葬贼怎则葬造 灶怎皂遭藻则 泽赠泽贼藻皂 晕 袁 憎澡藻则藻 贼澡藻 藻曾蚤泽贼藻灶糟藻 葬灶凿 怎灶凿藻糟蚤凿葬遭蚤造蚤贼赠 凿燥藻泽 灶燥贼 澡葬增藻 葬灶 藻枣枣藻糟贼 燥灶 贼澡藻 则藻糟怎则泽蚤增藻 灶葬贼怎则藻 燥枣 贼澡藻 责燥泽蚤贼蚤增藻 葬灶凿 蚤灶增藻则泽藻 泽藻贼泽 葬泽 憎藻造造 葬泽 贼澡藻 糟燥皂责造藻贼藻灶藻泽泽 燥枣 贼澡藻 泽赠泽贼藻皂援 栽澡藻则藻枣燥则藻袁 贼澡藻 皂葬贼澡藻皂葬贼蚤糟葬造 责则燥燥枣 枣燥则 郧觟凿藻造爷泽 贼澡藻燥则藻皂 糟葬灶灶燥贼 遭藻 贼则怎藻 葬灶凿 悦葬灶贼燥则爷泽 凿蚤葬早燥灶葬造 皂藻贼澡燥凿 蚤泽 责则燥增藻凿 贼燥 遭藻 枣葬造泽藻 葬灶凿 栽怎则灶鄄 蚤灶早爷泽 澡葬造贼蚤灶早 责则燥遭造藻皂 蚤泽 葬造泽燥 责则燥增藻凿 贼燥 遭藻 枣葬造泽藻援 宰澡藻贼澡藻则 燥则 灶燥贼 贼澡藻 泽赠泽贼藻皂 晕 糟葬灶 遭藻 糟燥皂责造藻贼藻袁 贼澡藻 则藻葬造 灶怎皂遭藻则 蚤泽 糟燥怎灶贼葬遭造藻 燥则 灶燥贼袁 燥则 憎澡藻贼澡藻则 燥则 灶燥贼 栽怎则灶蚤灶早爷泽 澡葬造贼 责则燥遭造藻皂 糟葬灶 遭藻 凿藻糟蚤凿藻凿 泽澡燥怎造凿 遭藻 则藻糟燥灶泽蚤凿藻则藻凿援 运藻赠憎燥则凿泽院责燥泽蚤贼蚤增藻 贼藻则皂曰 蚤灶增藻则泽藻 贼藻则皂曰 枣蚤曾藻凿 贼藻则皂曰 责葬则葬凿燥曾曰 枣蚤曾藻凿 贼藻则皂 燥怎贼泽蚤凿藻 哉 曰 怎灶凿藻糟蚤凿葬遭造藻 责则燥责燥泽蚤贼蚤燥灶曰 蚤灶鄄 糟燥皂责造藻贼藻 贼澡藻燥则藻皂曰 凿蚤葬早燥灶葬造 皂藻贼澡燥凿曰 怎灶糟燥怎灶贼葬遭造藻 泽藻贼曰 澡葬造贼蚤灶早 责则燥遭造藻皂 收稿日期院圆园员猿鄄员员鄄圆远援 摇 网络出版日期院圆园员源鄄园远鄄圆员援 通信作者院张金成援耘鄄皂葬蚤造院远缘远苑怨园圆园缘岳 择择援糟燥皂援 摇 摇 自从罗素悖论在数学中出现袁围绕着悖论问题袁 一个多世纪以来袁出现了众多的解决方案遥 然而袁这
·500 智能系统学报 第9卷 些解决方案,并不能令人完全满意,悖论的数学本质 不动点3/4把实数分成2个性质相反的集R、R。 并没有解释清楚,矛盾仍然没有解决。 1.2二项划分与双射关系 1931年Gdel证明:如果系统N是一致的,那 从以上分析可以看出,实数可以分成2个性质 么,系统N中存在不可判定命题,“系统N”是不能 相反的集,满足性质P与不满足性质P的集合。 完全的。这就是具有广泛影响的不完全定理。 定义3设P是U={x1x2,…,x,…}上的-个 以下在分析实数集不动点的基础上,可以证明: 性质,如果性质P把集合U划分成2个集合,满足 悖论、不可判定命题可以统一转化成逻辑思维领域 +a={xIP(x)∧x∈U) 中的不动点。不动点广泛存在,Gdel不可判定命 -a={xIP(x)∧x∈U} 题是系统N中的不动点,它与系统V能否完全没有 U=+x U-a 直接关系,一般递归集合中也存在类似Gdel的不 则+a,-α叫做集合U二项划分。 可判定命题,因此,Gdel不完全定理的证明是不成 例2设U={…,-2,-1,0,1,2,…},即全 立的。 体整数集合J,设P(x):x是偶数,则P(x)对U是 一个二项划分,即: 1 正集、反集、不动项 +a={xlx=2n,n∈J} 1.1自指代与不动点 -a=xI x=1-2n,n EJ);U=+aU-a 定义1一般地,函数y=f代x),x∈R,如果用 设f是从集合A到集合B的映射,若y=f(x), x取代y,得函数方程x=f(x),则把x=f代(x)叫做 x∈A→y∈B,即B中任一元素y,都是A中某元素 y=f(x)的自指代方程。 x的像,则称f为A到B上的满射;若对A中任意2 定义2如果U是一个集合,f:U→U是一个 个不同元素x1≠x2,他们的像f代x,)≠f八x2),则称 连续映射,且存在x∈U,使得f八x)=x,就称x是不f为A到B的单射: 动点。 定义4若映射∫既是单射,又是满射,则称映 例1函数f八x)=1-x/3,它的自指代方程 射f为A到B的“双射”(或“一一映射”)关系。 是:x=1-x/3,函数f(x)=1-x/3的不动点是方 函数f:A→B为双射,当且仅当对任意y∈B存 程x=1-x/3的解,即3/4,从图像上看是直线y= 在惟一x∈A,满足y=f(x);映射∫为A到B的“双 1-x/3与y=x的交点。 射关系”,记为f:A~B[]。 关于函数不动点有以下Brouwer不动点定理。 例3在上例中U={…,-2,-1,0,1,2,…}, Brouwer不动点定理设f:[0,1]→[0,1]是 即全体整数集合的一个二项划分,即: 连续映射,则必存在x∈[0,1],使f八xo))=xo。 +a={x|x=2n,n∈J}是偶数集合: 以上是R中,即1维的Brouwer不动点定理,不 -a={x1x=1-2n,n∈J}是奇数集合; 动点定理可以推广到2维以及n维欧氏空间中(即: fx)=1-x,x∈+a+f(x)∈-a 平面上的单位闭圆盘B2具有不动点性质,即任一 f八x)=1-x是二分集合+a,-a上的双射关系,即 连续映射f:B2→B2具有不动点。) f:+a~-a。 不动点的性质已经不仅仅局限于代数、函数领 1.3正集、反集、不动项 域,它已经延伸到集合论、离散数学、计算机、经济等 定义5设U={x1,出2,…,x,…}为一个集合, 其他各个领域。四 如果U被性质P二项划分为+a,-a,那么: 从函数自指代方程f代x)=1-x/3的不动点分析 1)满足性质P的元素x组成的集合,叫做正集, 开始,不动点3/4把实数分成2类性质的实数集合: 即命题P(x)成立,记为+a= 大于3/4的实数集合: {xIP(x)八x∈U},正集中的元素叫正项; R*={x|x>3/4,x∈R} 2)不满足性质P的元素x组成的集合,叫做反 小于3/4的实数集合: 集,即命题一P(x)成立,记为-a= R={xx3/4,若把不动点3/4扣 3)如果正、反集合+,-a上存在双射关系, 除,A(x)为命题:x2
些解决方案袁并不能令人完全满意袁悖论的数学本质 并没有解释清楚袁矛盾仍然没有解决遥 员怨猿员 年 郧觟凿藻造 证明院如果系统 晕 是一致的袁那 么袁系统 晕 中存在不可判定命题袁野系统 晕 冶是不能 完全的遥 这就是具有广泛影响的不完全定理遥 以下在分析实数集不动点的基础上袁可以证明院 悖论尧不可判定命题可以统一转化成逻辑思维领域 中的不动点遥 不动点广泛存在袁郧觟凿藻造 不可判定命 题是系统 晕 中的不动点袁它与系统 晕 能否完全没有 直接关系袁一般递归集合中也存在类似 郧觟凿藻造 的不 可判定命题袁因此袁郧觟凿藻造 不完全定理的证明是不成 立的遥 员摇 正集尧反集尧不动项 员援员摇 自指代与不动点 摇 摇 定义 员 摇 一般地袁函数 赠 越 枣渊曾冤 袁曾 沂 砸 袁如果用 曾 取代 赠袁 得函数方程 曾 越 枣渊曾冤 袁 则把 曾 越 枣渊曾冤 叫做 赠 越枣渊曾冤 的自指代方程遥 定义 圆摇 如果 哉 是一个集合袁 枣院哉 寅 哉 是一个 连续映射袁且存在 曾 沂 哉袁 使得 枣渊曾冤 越 曾 袁就称 曾 是不 动点遥 例 员 摇 函数 枣渊曾冤 越 员 原 曾 辕 猿袁 它的自指代方程 是院 曾 越 员 原 曾 辕 猿袁 函数 枣渊曾冤 越 员 原 曾 辕 猿 的不动点是方 程 曾 越 员 原 曾 辕 猿 的解袁即 猿 辕 源袁从图像上看是直线 赠 越 员 原曾 辕 猿 与 赠 越 曾 的交点遥 关于函数不动点有以下 月则燥怎憎藻则 不动点定理遥 月则燥怎憎藻则 不动点定理 设 枣院咱园袁员暂 寅 咱园袁员暂 是 连续映射袁则必存在 曾园 沂 园袁员 袁 使 枣渊曾园 冤 越 曾园 遥 以上是 砸员 中袁即 员 维的 月则燥怎憎藻则 不动点定理袁不 动点定理可以推广到 圆 维以及 灶 维欧氏空间中渊即院 平面上的单位闭圆盘 月圆 具有不动点性质袁 即任一 连续映射 枣院月圆 寅 月圆 具有不动点遥冤 不动点的性质已经不仅仅局限于代数尧函数领 域袁它已经延伸到集合论尧离散数学尧计算机尧经济等 其他各个领域遥咱员暂 从函数自指代方程 枣渊曾冤 越 员 原 曾 辕 猿 的不动点分析 开始袁不动点 猿辕源 把实数分成 圆 类性质的实数集合院 大于 猿辕源 的实数集合院 砸垣 越 曾渣 曾 跃 猿 辕 源袁曾 沂 砸 摇 摇 小于 猿辕源 的实数集合院 砸原 越 曾渣 曾 约 猿 辕 源袁曾 沂 砸 摇 摇 设 粤渊曾冤 为命题院 曾 跃 猿 辕 源袁 若把不动点 猿辕源 扣 除袁 劭 粤渊曾冤 为命题院 曾 约 猿 辕 源袁 即有院 砸垣 越 曾渣 粤渊曾冤 袁曾 沂 砸 砸原 越 曾渣 劭 粤渊曾冤 袁曾 沂 砸 摇 摇 不动点猿辕 源 把实数分成圆 个性质相反的集砸垣 尧砸原 遥 员援圆 摇 二项划分与双射关系 从以上分析可以看出袁实数可以分成 圆 个性质 相反的集袁满足性质 孕 与不满足性质 孕 的集合遥 定义 猿摇 设 孕 是 哉 越 曾员袁曾圆袁噎袁曾蚤袁噎 上的一个 性质袁如果性质 孕 把集合 哉 划分成 圆 个集合袁满足 垣 琢 越 曾渣 孕渊曾冤 夷 曾 沂 哉 原 琢 越 曾渣 劭 孕渊曾冤 夷 曾 沂 哉 哉 越 垣 琢 胰原 琢 摇 摇 则 垣 琢袁 原 琢 叫做集合 哉 二项划分遥 例 圆摇 设 哉 越 噎袁 原 圆袁 原 员袁园袁员袁圆袁噎 袁 即全 体整数集合 允 袁设 孕渊曾冤 院 曾 是偶数袁则 孕渊曾冤 对 哉 是 一个二项划分袁即院 垣 琢 越 曾渣 曾 越 圆灶袁灶 沂 允 原 琢 越 曾渣 曾 越 员 原 圆灶袁灶 沂 允 曰哉 越 垣 琢 胰原 琢 摇 摇 设 枣 是从集合 粤 到集合 月 的映射袁若 赠 越 枣渊曾冤 袁 曾 沂粤 寅赠 沂月袁 即 月 中任一元素 赠袁 都是 粤 中某元素 曾 的像袁则称 枣 为 粤 到 月 上的满射曰若对 粤 中任意 圆 个不同元素 曾员 屹 曾圆 袁 他们的像 枣渊曾员 冤 屹 枣渊曾圆 冤 袁 则称 枣 为 粤 到 月 的单射曰 定义 源摇 若映射 枣 既是单射袁又是满射袁则称映 射 枣 为 粤 到 月 的野双射冶 渊或野一一映射冶 冤关系遥 函数 枣院粤 寅 月 为双射袁当且仅当对任意 赠 沂 月 存 在惟一 曾 沂 粤袁 满足 赠 越 枣渊曾冤 曰映射 枣 为 粤 到 月 的野双 射关系冶 袁记为 枣院粤耀月 咱圆暂 遥 例 猿摇 在上例中 哉 越 喳噎袁 原 圆袁 原 员袁园袁员袁圆袁噎札 袁 即全体整数集合的一个二项划分袁即院 垣 琢 越 曾渣 曾 越 圆灶袁灶 沂 允 是偶数集合曰 原 琢 越 曾渣 曾 越 员 原 圆灶袁灶 沂 允 是奇数集合曰 枣渊曾冤 越 员 原 曾袁曾 沂垣 琢圮枣渊曾冤 沂原 琢 枣渊曾冤 越 员 原 曾 是二分集合 垣 琢袁 原 琢 上的双射关系袁即 枣院 垣 琢 耀 原 琢 遥 员援猿摇 正集尧反集尧不动项 定义 缘摇 设 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 为一个集合袁 如果 哉 被性质 孕 二项划分为 垣 琢袁 原 琢袁 那么院 员冤满足性质 孕 的元素 曾 组成的集合袁叫做正集袁 即命题 孕渊曾冤 成 立袁 记 为 垣 琢 越 曾渣 孕渊曾冤 夷 曾 沂 哉 袁 正集中的元素叫正项曰 圆冤不满足性质 孕 的元素 曾 组成的集合袁叫做反 集袁 即命题 劭 孕渊曾冤 成 立袁 记 为 原 琢 越 曾渣 劭 孕渊曾冤 夷 曾 沂 哉 袁 反集中的元素叫反项曰 猿冤如果正尧反集合 垣 琢袁 原 琢 上存在双射关系袁 即 枣院 垣 琢 耀 原 琢袁 则叫 垣 琢袁 原 琢 为正尧反对称集合遥 例 源 摇 设 哉 越 匝垣 为全体正有理数集合袁给定一 个划分 孕渊曾冤 院 曾圆 跃 圆遥 窑缘园园窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷
第4期 张金成:逻辑及数学演算中的不动项与不可判定命题(【) ·501· 正集:平方大于2的有理数集合,即:+α= 例7设U=Q为全体正有理数集合,给定一 {x1x2>2,x∈Q); 个划分P(x):x2>2,对应关系f(x)=2/x。 反集:平方小于2的有理数集合,即:-α= 不动集:x=2/x,x0=√2是不动项。 {x1x20,对应关 例5设U=(-0,0)U(0,+o),不为0的 系f(x)=-1/x。 全体实数集合,给定一个划分P(x):x>0。 不动集:x=-1/x,x。=√一I=i是不动项, 正集:大于0的实数集合,即: iU,x。=i是在U外。 +={x1x>0,x∈U}=(0,+0)】 这可以看成从实数到虚数的发现。 反集:小于0的实数集合,即: “不动项”是通常数学中“不动点”概念的推广, -a={x1x<0,x∈U}=(-0,0) 它不再单指是一个点、一个数,它可能是一个点、一 存在双射f天:+a~-a对应关系f八x)=-1/x, 个数、一个集合、一个命题等。 +a,-α是正反对称集合。 对应关系∫也不再是单指数之间的运算,而可 在一个集合U={x1,x2,…,x,…}上,并不是 能是点、集合、或者命题之间的对应关系; 任意一个划分,都可以构成正反对称集合,有些划分 “不动项”和“不动点”都有相同的形式结构x= 不构成正反对称集合。 (x),“不动项”比“不动点”具有更广泛的意义。 构成正反对称集合+α与-α必须满足的2个 对不动点,一定有x。∈U,对“不动项”没有U的 条件,也可以通俗地表达为: 内外限制,满足x=f(x)的x。存在或者不存在问题,在 1)正、反对称集合是不相容的+a∩-a=☑; U外可以找到满足x=f(x)的xo,也是不动项。 2)正、反对称集合可以建立一一对应的函数关 定义7设U={x1,x2,…,x,…}为一个集合, 系,x:∈+af(x:)e-a。 映射f:U一U,x。满足自指代方程x。=f八xo)。若 下文专门讨论正、反对称集合,不再特别指出。 x∈U,则元素x。叫U内不动项;若x。生U,则元素 自指代方程上的不动点的定义可以推广如下: x。叫U外不动项。 定义61)函数f:A→B,即f为集合A到B的 不动项元素x。存在,方程x=f(x)有解,且 映射,对任意x∈A,y∈B,y=f(x),把满足自指代 x。∈U,即:存在U内不动项; 方程x0=f(xo)的解xo称为不动项。 U外不动项有2种形式: 2)设U={x1,x2,…,x,…}为一个集合,如果 1)方程x=f(x)有解,不动项元素x。存在,但 U被性质P二项划分为正、反对称集合+,-α,即 f:+a~一a,x满足性质Pf(x)满足性质一P,即 x生U,即:不动项x。已经构造: 2)方程x=八x)无解,不动项元素x。不存在,或 :∈+afx:)∈-a,那么: 者说不动项x。没有构造;这种情况,不动集e为空 如果存在一个x。,满足自指代方程x。=f(x。) 元素x。叫正反对称集合上的不动项:由元素x,构成 集,e=☑也可以看成U外不动项的特例。 的集合,叫做不动集,记为:e={xIx=f(x)}= 在例1中,设U=R,f:U→U,函数f八x)=1- {xo}。 x/3中,x0=3/4是U内不动项: 如果自指代方程xo=f(xo)无解,记为:e= 设U=Qf:U→U,函数f八x)=2/x中,x。= {x1x=f(x)}=☑。 √2,√2∈U,2是U外不动项,即以上第1)种情形, 例6设U={…,-2,-1,0,1,2,…},即全 在无理数没有发现之前,可以看成第2)种情形; 体整数集合,给定一个划分P(x):x是偶数,对应 设U={x:x≠0,x∈R}f:U→U,函数 关系f(x)=1-x。 fx)=-1/x中,x=√I,√I年U,√I是U 正集:+a={x1x=2n,n∈J}; 外不动项,即以上第1种情形,在虚数没有发现之 反集:-a={xlx=1-2n,n∈J}: 前,可以看成第2种情形; U=+aU-a。 设U=J,f:U→U,函数f(x)=x+1中,x= 不动集:x=1-x,x。=1/2是不动项。 x+1无解,不动项x。不存在,即第2种情形e=☑。 这可以看成从整数到分数的发现。 以后将证明:一个集合U如果能够严格地二项
正集院平方大于 圆 的有理数集合袁即院 垣 琢 越 曾渣 曾圆 跃 圆袁曾 沂 匝 曰 反集院平方小于 圆 的有理数集合袁即院 原 琢 越 曾渣 曾圆 约 圆袁曾 沂 匝 遥 存在双射 枣院 垣 琢 耀 原 琢 对应关系 枣渊曾冤 越 圆 辕 曾袁 垣 琢袁 原 琢 是正反对称集合遥 例 缘摇 设 哉 越 渊 原 袁园冤 胰 渊园袁 垣 冤 袁 不为 园 的 全体实数集合袁给定一个划分 孕渊曾冤 院 曾 跃 园遥 正集院大于 园 的实数集合袁即院 垣 琢 越 曾渣 曾 跃 园袁曾 沂 哉 越 渊园袁 垣 冤 摇 摇 反集院小于 园 的实数集合袁即院 原 琢 越 曾渣 曾 约 园袁曾 沂 哉 越 渊 原 袁园冤 摇 摇 存在双射 枣院 垣 琢 耀 原 琢 对应关系 枣渊曾冤 越 原 员 辕 曾袁 垣 琢袁 原 琢 是正反对称集合遥 在一个集合 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 上袁并不是 任意一个划分袁都可以构成正反对称集合袁有些划分 不构成正反对称集合遥 构成正反对称集合 垣 琢 与 原 琢 必须满足的 圆 个 条件袁也可以通俗地表达为院 员冤正尧反对称集合是不相容的 垣 琢 疑原 琢 越 芰 曰 圆冤正尧反对称集合可以建立一一对应的函数关 系袁 曾蚤 沂垣 琢圮枣渊曾蚤冤 沂原 琢 遥 下文专门讨论正尧反对称集合袁不再特别指出遥 自指代方程上的不动点的定义可以推广如下院 定义 远摇 员冤函数 枣院粤 寅 月袁 即 枣 为集合 粤 到 月 的 映射袁对任意 曾 沂 粤袁赠 沂 月袁 赠 越 枣渊曾冤 袁 把满足自指代 方程 曾园 越 枣渊曾园 冤 的解 曾园 称为不动项遥 圆冤设 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 为一个集合袁 如果 哉 被性质 孕 二项划分为正尧反对称集合 垣 琢袁 原 琢袁 即 枣院 垣 琢 耀 原 琢袁曾 满足性质 孕袁枣渊曾冤 满足性质 劭 孕袁 即 曾蚤 沂垣 琢圮枣渊曾蚤冤 沂原 琢袁 那么院 如果存在一个 曾园 袁 满足自指代方程 曾园 越 枣渊曾园 冤 元素 曾园 叫正反对称集合上的不动项曰由元素 曾园 构成 的集合袁 叫做不动集袁 记为院 藻 越 曾渣 曾 越 枣渊曾冤 越 曾园 遥 如果自指代方程 曾园 越 枣渊曾园 冤 无解袁记为院 藻 越 曾渣 曾 越 枣渊曾冤 越 芰 遥 例 远摇 设 哉 越 噎袁 原 圆袁 原 员袁园袁员袁圆袁噎 袁 即全 体整数集合袁给定一个划分 孕渊曾冤 院 曾 是偶数袁对应 关系 枣渊曾冤 越 员 原 曾 遥 正集院 垣 琢 越 曾渣 曾 越 圆灶袁灶 沂 允 曰 反集院 原 琢 越 曾渣 曾 越 员 原 圆灶袁灶 沂 允 曰 哉 越 垣 琢 胰原 琢 遥 不动集院 曾 越 员 原 曾袁曾园 越 员 辕 圆 是不动项遥 这可以看成从整数到分数的发现遥 例 苑摇 设 哉 越 匝垣 为全体正有理数集合袁给定一 个划分 孕渊曾冤 院 曾圆 跃 圆袁 对应关系 枣渊曾冤 越 圆 辕 曾 遥 不动集院 曾 越 圆 辕 曾袁曾园 越 圆 是不动项遥 这就是从有理数构造无理数的野戴德金分割冶 遥 例 愿摇 设 哉 越 渊 原 袁园冤 胰 渊园袁 垣 冤 袁 不为 园 的 全体实数集合袁给定一个划分 孕渊曾冤 院 曾 跃 园袁 对应关 系 枣渊曾冤 越 原 员 辕 曾 遥 不动集院 曾 越 原 员 辕 曾袁曾园 越 原 员 越 蚤 是不动项袁 蚤 埸哉袁曾园 越 蚤 是在 哉 外遥 这可以看成从实数到虚数的发现遥 野不动项冶是通常数学中野不动点冶概念的推广袁 它不再单指是一个点尧一个数袁它可能是一个点尧一 个数尧一个集合尧一个命题等遥 对应关系 枣 也不再是单指数之间的运算袁而可 能是点尧集合尧或者命题之间的对应关系曰 野不动项冶和野不动点冶都有相同的形式结构 曾 越 枣渊曾冤袁 野不动项冶比野不动点冶具有更广泛的意义遥 对不动点袁一定有 曾园 沂 哉袁 对野不动项冶没有 哉 的 内外限制袁满足 曾 越 枣渊曾冤 的 曾园 存在或者不存在问题袁在 哉 外可以找到满足 曾 越 枣渊曾冤 的 曾园袁 也是不动项遥 定义 苑摇 设 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 为一个集合袁 映射 枣院哉 寅 哉袁曾园 满足自指代方程 曾园 越 枣渊曾园 冤 遥 若 曾园 沂哉袁 则元素 曾园 叫 哉 内不动项曰若 曾园 埸 哉袁 则元素 曾园 叫 哉 外不动项遥 不动项元素 曾园 存在袁方程 曾 越 枣渊曾冤 有解袁且 曾园 沂哉袁 即院存在 哉 内不动项曰 哉 外不动项有 圆 种形式院 员冤方程 曾 越 枣渊曾冤 有解袁不动项元素 曾园 存在袁但 曾园 埸 哉袁 即院不动项 曾园 已经构造曰 圆冤方程 曾 越 枣渊曾冤 无解袁不动项元素 曾园 不存在袁或 者说不动项 曾园 没有构造曰这种情况袁不动集 藻 为空 集袁 藻 越 芰 也可以看成 哉 外不动项的特例遥 在例 员 中袁设 哉 越 砸袁枣院哉 寅 哉 袁函数 枣渊曾冤 越 员 原 曾 辕 猿 中袁 曾园 越 猿 辕 源 是 哉 内不动项曰 设 哉 越 匝垣 袁枣院哉 寅 哉 袁函数 枣渊曾冤 越 圆 辕 曾 中袁 曾园 越 圆 袁 圆 沂 哉袁 圆 是 哉 外不动项袁即以上第 员冤种情形袁 在无理数没有发现之前袁可以看成第 圆冤种情形曰 设 哉 越 曾院曾 屹 园袁曾 沂 砸 袁枣院哉 寅 哉 袁 函 数 枣渊曾冤 越 原 员 辕 曾 中袁 曾园 越 原 员 袁 原 员 埸 哉 袁 原 员 是 哉 外不动项袁即以上第 员 种情形袁在虚数没有发现之 前袁可以看成第 圆 种情形曰 设 哉 越 允袁枣院哉 寅 哉 袁函数 枣渊曾冤 越 曾 垣 员 中袁 曾 越 曾 垣员 无解袁不动项 曾园 不存在袁即第 圆 种情形 藻 越 芰遥 摇 摇 以后将证明院一个集合 哉 如果能够严格地二项 第 源 期摇摇摇摇摇摇摇摇摇摇摇摇摇 张金成院 逻辑及数学演算中的不动项与不可判定命题渊玉冤 窑缘园员窑
·502 智能系统学报 第9卷 划分成正反对称集合,那么不动项它一定在正反集 A1:A0→(B-a→Aa) 合之外,即:都是U外不动项,正反对称集合上的不 A2:(Aa→(B-a→C-a)) 动项有(1)、(2)2种情形。 →(Aa→B“)→(Aa→Ca) f是+a到-a上的一个一一对应关系,满足函数 A3:(A8→B-)→(Ba→A)[] 关系y=f(x),正集+a、反集-a,也可以表示为: 由于经典逻辑的公理在正集、反集上都是成立 +a={x1,x2,…,xm,…} 的,今后对2个集上都成立的命题,上标不再区分2 -a={fx).fx2),…f(xn),…} 1)若x∈+,则y∈-a,满足x≠f(x)f(x) 个集“+a,-α”,和经典逻辑公式一样不标“+a, -α”。如:A→(B→A),认为在2个集上都成立。 也记为x,所以,反集也记为一= 定义9正集+a、反集-的并集U,即:U= {x1,x2,…,xn,…}。 +U-a,叫做全集。 2)若满足x=f(x),元素x一个特殊的集合,设 对于全集U按某性质P划分为正集项、反集 x=x,不动集e={xo}。 项,即x、x:; 即x=fx),x∈+a台x∈-a,P(x)P(x)。 U={…,x,…,x,…}对应有正集命题、反集 对于P(x)P(x),当x满足 命题,即P(x)、P(x:); P(x)P(x)时,x。即为不动项。 任何一个性质,如果可以对全集形成一个正反 正、反集是关于某个映射f的对称变换,+中的 对称集划分,如果。恰恰是性质P划分的不动项, 项x对应一α中的项x,不动集中的项对应它自己。 这是一个特殊的命题。 1.4正、反集对偶变换公理 定义10不动项x0,关于其划分P的性质断定 在以上概念基础上,把矛盾命题重新进行形式 的命题,叫做不动项命题,即命题P(x)或P(x) 描述: 是不动项命题。 用Aa表示正集+a中的命题A,A“表示反集 如果关于性质M,N、P的不动项记为xMxw -a中的命题A,如: xp,则M(xw)、N(xx)、P(xp)是不动项命题,并且 设+α为欧氏平面上的点集,则-α为非欧平 有P(xp)P(xp)。 面上的点集, 设命题P是关于正集+a、反集-α的一个划 A“:在欧氏平面上,过已知直线外一点,只能 分,即: 作惟一一条直线与已知直线平行。 若+a={x1P(x)},则-a={xIP(x)}, A“:在非欧平面上,过已知直线外一点,只能 f是+a,-a上的一个一一映射,f:U→U,x:∈ 作惟一一条直线与已知直线平行。 +a,x:∈-a,x=f八x),有P(x)P(x:)。 一A“、?A“就是以上命题的否定命题,这样以 通过一些分析发现P+“与P-“是等价的,例 来,矛盾命题都有2种表示方式。 如:欧氏几何与罗氏几何是同构的,它说明一个命题 定义8在相同集上的否定命题A“与一A“(即 等价于它反集中的否定命题,即应有公理 A“与一A+“或Aa与Aa),叫做经典矛盾命题:在 “PaP-a”成立。 不同集上的否定命题(Aa与一Aa或A“与 根据以上分析,引进一条新公理“PaPa” A“),叫做非经典矛盾命题(它与辩证矛盾类似)。 实际上,矛盾命题在不同集上成立,矛盾也就化解 或“P(x)P(x)”。 了。辩证矛盾就是已经化解或者解释清晰后的矛盾?。 定义11称公理“P“P-a” 或 由于公式的变化,公理在不同的集中有那些变 “P(x)→P(x)”为“正反集对偶变换公理”。 化,经典逻辑公理在正集中变为: 定理1(不动项定理)在“正反集对偶变换 A1:A*a→(Ba→A+a) 公理”中,若存在xp,x=x:=xp,则有 A2:(Aa→(B*a→C*)) “P(xp)P(xp)”。 →((Aa→B“)→(Aa→C*)) 证明:在“正反集对偶变换公理”P(x:)P(x) A3:(Aa→B+“)→(Ba→A“) 中,x:=元=xp,用xp替换xx,得:P(xp)P(xp)。 经典逻辑公理在反集中变为: 由于正项、反项、不动项定义可以是任何一个集合的
划分成正反对称集合袁那么不动项它一定在正反集 合之外袁即院都是 哉 外不动项袁正反对称集合上的不 动项有渊员冤尧渊圆冤 圆 种情形遥 枣 是 垣 琢 到 原 琢 上的一个一一对应关系袁满足函数 关系 赠 越 枣渊曾冤袁 正集 垣 琢 尧反集 原 琢袁 也可以表示为院 垣 琢 越 曾员 袁曾圆 袁噎袁曾 灶 袁噎 原 琢 越 枣渊曾员 冤 袁枣渊曾 圆 冤 袁噎袁枣渊曾灶 冤袁噎 摇 摇 员冤若 曾 沂垣 琢袁 则 赠 沂原 琢袁 满足 曾 屹 枣渊曾冤 袁枣渊曾冤 也记为 曾 耀 袁 所 以袁 反集也记为 原 琢 越 曾 耀 员 袁曾 耀 圆 袁噎袁曾 耀 灶 袁噎 遥 圆冤若满足 曾 越 枣渊曾冤 袁 元素 曾 一个特殊的集合袁设 曾 越 曾园 袁 不动集 藻 越 曾园 遥 即 曾 耀 越 枣渊曾冤 袁 曾 沂垣 琢圳曾 耀 沂原 琢袁孕渊曾冤圮劭 孕渊曾 耀 冤 遥 对 于 孕渊曾冤圮劭 孕渊 曾 耀 冤 袁 当 曾园 满 足 孕渊曾园 冤圮劭 孕渊曾园 冤 时袁 曾园 即为不动项遥 正尧反集是关于某个映射 枣 的对称变换袁 垣 琢 中的 项 曾 对应 原 琢 中的项 曾 耀 袁 不动集中的项对应它自己遥 员援源摇 正尧反集对偶变换公理 在以上概念基础上袁把矛盾命题重新进行形式 描述院 用 粤垣琢 表示正集 垣 琢 中的命题 粤袁粤原琢 表示反集 原 琢 中的命题 粤袁 如院 设 垣 琢 为欧氏平面上的点集袁则 原 琢 为非欧平 面上的点集袁 粤垣琢 院在欧氏平面上袁过已知直线外一点袁只能 作惟一一条直线与已知直线平行遥 粤原琢 院在非欧平面上袁过已知直线外一点袁只能 作惟一一条直线与已知直线平行遥 劭 粤垣琢 尧劭 粤原琢 就是以上命题的否定命题袁这样以 来袁矛盾命题都有 圆 种表示方式遥 定义 愿摇 在相同集上的否定命题 粤琢 与 劭 粤琢 渊即 粤垣琢 与 劭 粤垣琢 或 粤原琢 与 劭 粤原琢 冤袁叫做经典矛盾命题曰在 不同集上的否定命题 渊 粤垣琢 与 劭 粤原琢 或 粤原琢 与 劭 粤垣琢 冤袁叫做非经典矛盾命题渊它与辩证矛盾类似冤遥 实际上袁矛盾命题在不同集上成立袁矛盾也就化解 了遥 辩证矛盾就是已经化解或者解释清晰后的矛盾咱圆暂 遥 由于公式的变化袁公理在不同的集中有那些变 化袁经典逻辑公理在正集中变为院 粤员 院粤垣琢 寅 渊月垣琢 寅 粤垣琢 冤 粤圆 院渊粤垣琢 寅 渊月垣琢 寅 悦垣琢 冤 冤 寅 渊 渊粤垣琢 寅 月垣琢 冤 寅 渊粤垣琢 寅 悦垣琢 冤 冤 粤猿 院渊劭 粤垣琢 寅 劭 月垣琢 冤 寅 渊月垣琢 寅 粤垣琢 冤 摇 摇 经典逻辑公理在反集中变为院 粤员 院粤原琢 寅 渊月原琢 寅 粤原琢 冤 粤圆 院渊粤原琢 寅 渊月原琢 寅 悦原琢 冤 冤 寅 渊 渊粤原琢 寅 月原琢 冤 寅 渊粤原琢 寅 悦原琢 冤 冤 粤猿 院渊劭 粤原琢 寅 劭 月原琢 冤 寅 渊月原琢 寅 粤原琢 冤咱猿暂 摇 摇 由于经典逻辑的公理在正集尧反集上都是成立 的袁今后对 圆 个集上都成立的命题袁上标不再区分 圆 个集野 垣 琢袁 原 琢 冶 袁和经典逻辑公式一样不标野 垣 琢袁 原 琢 冶 遥 如院 粤 寅 渊月 寅 粤冤 袁 认为在 圆 个集上都成立遥 定义 怨摇 正集 垣 琢 尧反集 原 琢 的并集 哉袁 即院 哉 越 垣 琢 胰原 琢袁 叫做全集遥 对于全集 哉 按某性质 孕 划分为正集项尧反集 项袁即 曾蚤尧曾 耀 蚤 曰 哉 越 噎袁曾蚤袁噎袁曾 耀 蚤袁噎 对应有正集命题尧反集 命题袁即 孕渊曾蚤冤 尧孕渊 曾 耀 蚤冤 曰 任何一个性质袁如果可以对全集形成一个正反 对称集划分袁如果 曾园 恰恰是性质 孕 划分的不动项袁 这是一个特殊的命题遥 定义 员园摇 不动项 曾园 袁 关于其划分 孕 的性质断定 的命题袁叫做不动项命题袁即命题 孕渊曾园 冤 或 劭 孕渊曾园 冤 是不动项命题遥 如果关于性质 酝尧晕尧孕 的不动项记为 曾酝尧曾晕尧 曾孕 袁 则 酝渊曾酝冤 尧晕渊曾晕冤 尧孕渊曾孕 冤 是不动项命题袁并且 有 孕渊曾孕 冤圮劭 孕渊曾孕 冤 遥 设命题 孕 是关于正集 垣 琢 尧反集 原 琢 的一个划 分袁即院 若 垣 琢 越 曾渣 孕渊曾冤 袁 则 原 琢 越 曾渣 劭 孕渊曾冤 袁 枣 是 垣 琢袁 原 琢 上的一个一一映射袁 枣院哉 寅 哉袁曾蚤 沂 垣 琢袁曾 耀 蚤 沂原 琢 袁 曾 耀 蚤 越 枣渊曾蚤冤 袁 有 孕渊曾蚤冤圮劭 孕渊 曾 耀 蚤冤 遥 通过一些分析发现 孕垣琢 与 劭 孕原琢 是等价的袁例 如院欧氏几何与罗氏几何是同构的袁它说明一个命题 等价于它反集中的否定命题袁 即应有公理 野 孕垣琢 圮劭 孕原琢 冶成立遥 根据以上分析袁引进一条新公理野 孕垣琢 圮劭 孕原琢 冶 或野 孕渊曾冤圮劭 孕渊曾 耀 冤 冶遥 定 义 员员 摇 称公理 野 孕垣琢 圮劭 孕原琢 冶 或 野 孕渊曾冤圮劭 孕渊 曾 耀 冤 冶为野正反集对偶变换公理冶 遥 定理 员 渊不动项定理冤 摇 在野正反集对偶变换 公 理 冶 中袁 若存在 曾孕 袁曾蚤 越 曾 耀 蚤 越 曾孕 袁 则 有 野 孕渊曾孕 冤圮劭 孕渊曾孕 冤 冶遥 证明院在野正反集对偶变换公理冶 孕渊曾蚤冤圮劭 孕渊曾 耀 蚤冤 中袁 曾蚤 越 曾 耀 蚤 越 曾孕袁用曾孕 替换曾蚤尧曾 耀 蚤袁得院孕渊曾孕冤圮劭 孕渊曾孕冤遥 由于正项尧反项尧不动项定义可以是任何一个集合的 窑缘园圆窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷
第4期 张金成:逻辑及数学演算中的不动项与不可判定命题(【) ·503· 元素。如果X是一个命题,“正反集对偶变换公理” 体形成的集合,不动集是一个既具备正集性质又具 同样成立,即有: 备反集性质的集合。在不动集中P(a)与P[f(a)] P(X)→P(X),当X,=Xp是不动项时,有: 相互否定,即自身与自身相互否定。从以上例子,还 P(Xp)P(Xe)。 可以轻松观察到,如果U是一个已知集合,形成悖 1.5悖论是正、反集上的不动项 论的不动项xp,一定是U外不动项,即xp年U(这 在“正反集对偶变换公理”P(x)P(x:) 个性质以后还要详细讨论)。 例9罗素悖论中的集合分为2类: 中,:∈+Q,x:∈-a,这并不矛盾,但是,当x= 一类集合是自身的元素,即x∈x,+α= x=x。时,即:x。为不动点时,有P(x)P(xo)就 {xIx∈x}; 表现为悖论。 二类集合不是自身的元素,即(x∈x), 在例1中,对于一个确定的实数a: -a={x|(x∈x)}; 如果a>3/4台-a/3-1/4→1-a/3> R一(x∈x),问集合R是那类集合?即用R去自 3/4台则f(a)>3/4,即:A(a)→A(f(a))。 指代。 由于a=f(a),这就形成了类似悖论命题 无论集合R是那类集合,即得到罗素悖论:R∈ A(a)A(a),这个悖论的解就是:a=3/4。 R(R∈R)。 一般地,设∫是R上的一个一一映射,f:R→ 设P(x)表示命题x∈x,+a={xIP(x)},则 R,如果性质P是R上的一个二项划分,对任意一个 P(x)表示命题(x∈x),-a={x|P(x)}。 x,x满足性质P,x)满足性质一P,即R*= 第2类集合全体组成的集合R= {x1P(x),x∈R},R={x|P(x),x∈R},x∈ x1P(x)); R*f(x)∈R,P(x)P(f(x))。 即x∈R→P(x)→R∈RP(R); 不动点x。把实数集合分成正、反集合,其中一 即P(R)P(R)。 个集合中的元素满足性质P,另一个集合中的元素 所以,R={x:x庄x}是关于谓词P(x)的不动 满足性质P,而不动点x。可以看成具有2个矛盾 项,即罗素悖论是不动项命题]。 性质P与P的点,即P(xo)Pf(x),这就 1.6逻辑演算中的不动项 是悖论形成的内在机理。 在“正反集对偶变换公理”P“P-“中,当 在例4中,设P(x)表示命题x2>2,对于一 存在不动项时,就存在悖论。如果把“正反集对偶 个确定的数a: 变换公理”Pa一Pa引进逻辑演算系统中,逻辑 P(a):a2>2→a2=4/a2 演算系统中就会同样存在悖论。 4/a2>2→a22→P(a) 由于a=f(a),这就形成了类似悖论命题 即若+a=-a=e,则上PrP; 在谓词演算系统L中,如果承认“正反集对偶变 P(a)P(a),这个悖论的解就是:a=√2。 在例5中,设P(x)表示命题“x>0”,对于一 换公理”P(x)P(x:),则有不动项存在,存在 个确定的数a: 悖论;即若x:=无:=xp,则PP(xp)P(xp)。 P(a):a>0台a=-1/a, 由于在经典系统中,定理P,P上B成立,所 -1/a>0曰a0=P(a); 在以前的命题逻辑系统L,谓词逻辑系统K中, 为什么没有发现不动项的存在,是因为在其中没有 所以,得到悖论:P(a)→P(a); 建立起来正反演算,一个公理系统中是否存在不动 由于a=-1/a,a2=-1,a=i=√/1,不动集 项(悖论),跟演算方式有关。 是从正集到反集映射过程中保持原地不变的所有个 由于不动项、悖论的存在,是不是“命题逻辑系
元素遥 如果 载蚤 是一个命题袁野正反集对偶变换公理冶 同样成立袁即有院 孕渊载蚤冤圮劭 孕渊载蚤 耀 冤 袁 当 载蚤 越 载孕 是不动项时袁有院 孕渊载孕 冤圮劭 孕渊载孕 冤 咱猿暂 遥 员援缘摇 悖论是正尧反集上的不动项 在野正反集对偶变换公理冶 孕渊曾蚤冤圮劭 孕渊 曾 耀 蚤冤 中袁 曾蚤 沂垣 琢袁曾 耀 蚤 沂原 琢 袁这并不矛盾袁但是袁当 曾 越 曾 耀 越曾园 时袁即院 曾园 为不动点时袁有 孕渊曾园 冤圮劭 孕渊曾园 冤 就 表现为悖论遥 在例 员 中袁对于一个确定的实数 葬 院 如果 葬 跃 猿 辕 源圯 原 葬 辕 猿 约 原 员 辕 源圯员 原 葬 辕 猿 约 猿 辕 源圯 则 枣渊葬冤 约 猿 辕 源袁 即院 粤渊葬冤 寅 劭 粤渊枣渊葬冤冤 曰 如果 葬 约 猿 辕 源圯 原 葬 辕 猿 跃 原 员 辕 源圯员 原 葬 辕 猿 跃 猿 辕 源圯 则 枣渊葬冤 跃 猿 辕 源袁 即院 劭 粤渊葬冤 寅 粤渊枣渊葬冤冤 遥 由于 葬 越 枣渊葬冤 袁 这就形成了类似悖论命题 粤渊葬冤圮劭 粤渊葬冤 袁 这个悖论的解就是院 葬 越 猿 辕 源遥 一般地袁设 枣 是 砸 上的一个一一映射袁 枣院砸 寅 砸袁 如果性质 孕 是 砸 上的一个二项划分袁对任意一个 曾袁曾 满足性质 孕袁枣渊曾冤 满足性质 劭 孕袁 即 砸垣 越 曾渣 孕渊曾冤 袁曾 沂 砸 袁 砸原 越 曾渣 劭 孕渊曾冤 袁曾 沂 砸 袁曾 沂 砸垣 圮枣渊曾冤 沂 砸原 袁孕渊曾冤圮劭 孕渊枣渊曾冤冤 遥 不动点 曾园 把实数集合分成正尧反集合袁其中一 个集合中的元素满足性质 孕袁 另一个集合中的元素 满足性质 劭 孕袁 而不动点 曾园 可以看成具有 圆 个矛盾 性质 孕 与 劭 孕 的点袁即 孕渊曾园 冤圮劭 孕渊枣渊曾园 冤冤袁 这就 是悖论形成的内在机理遥 在例 源 中袁设 孕渊曾冤 表示命题 曾圆 跃 圆袁 对于一 个确定的数 葬 院 孕渊葬冤 院葬圆 跃 圆圯葬圆 越 源 辕 葬圆 源 辕 葬圆 跃 圆圯葬圆 约 圆圯劭 孕渊葬冤 劭 孕渊葬冤 院葬圆 约 圆圯葬圆 越 源 辕 葬圆 源 辕 葬圆 约 圆圯葬圆 跃 圆圯孕渊葬冤 摇 摇 由于 葬 越 枣渊葬冤 袁 这就形成了类似悖论命题 孕渊葬冤圮劭 孕渊葬冤 袁 这个悖论的解就是院 葬 越 圆 遥 在例 缘 中袁设 孕渊曾冤 表示命题野 曾 跃 园冶袁对于一 个确定的数 葬 院 孕渊葬冤 院 葬 跃 园圯 葬 越 原 员 辕 葬袁 原 员 辕葬 跃 园圯 葬 约 园圯 劭 孕渊葬冤 曰 劭 孕渊葬冤 院 葬 约 园圯 葬 越 原 员 辕 葬袁 原 员 葬 约 园圯 葬 跃 园圯 孕渊葬冤 曰 所以袁得到悖论院 孕渊葬冤圮劭 孕渊葬冤 曰 由于 葬 越 原 员 辕 葬袁葬圆 越 原 员袁葬 越 蚤 越 原 员 袁不动集 是从正集到反集映射过程中保持原地不变的所有个 体形成的集合袁不动集是一个既具备正集性质又具 备反集性质的集合遥 在不动集中 孕渊葬冤 与 孕咱枣渊葬冤 暂 相互否定袁即自身与自身相互否定遥 从以上例子袁还 可以轻松观察到袁如果 哉 是一个已知集合袁形成悖 论的不动项 曾孕 袁 一定是 哉 外不动项袁即 曾孕 埸 哉 渊这 个性质以后还要详细讨论冤 遥 例 怨摇 罗素悖论中的集合分为 圆 类院 一类集合是自身的元素袁 即 曾 沂 曾袁 垣 琢 越 曾渣 曾 沂 曾 曰 二类集合不是自身的元素袁即 劭 渊曾 沂 曾冤 袁 原 琢 越 曾渣 劭 渊曾 沂 曾冤 曰 现在构造第 圆 类集合全体组成的集合 渊 即 原 琢 冤 袁 用 砸 越 曾渣 劭 渊曾 沂 曾冤 表 示袁 即 曾 沂 砸圮劭 渊曾 沂曾冤 袁 问集合 砸 是那类集合钥 即用 砸 去自 指代遥 无论集合 砸 是那类集合袁即得到罗素悖论院 砸沂 砸圮劭 渊砸 沂 砸冤 遥 设 孕渊曾冤 表示命题 曾 沂 曾袁 垣 琢 越 曾渣 孕渊曾冤 袁 则 劭 孕渊曾冤 表示命题 劭 渊曾 沂 曾冤 袁 原 琢 越 曾渣 劭 孕渊曾冤 遥 第 圆 类集合全体组成的集合 砸 越 曾渣 劭 孕渊曾冤 曰 即 曾 沂 砸圮劭 孕渊曾冤 圯 砸 沂 砸圮劭 孕渊砸冤 曰 即 孕渊砸冤圮劭 孕渊砸冤 遥 所以袁 砸 越 曾院曾 埸 曾 是关于谓词 孕渊曾冤 的不动 项袁即罗素悖论是不动项命题咱猿暂 遥 员援远摇 逻辑演算中的不动项 在野正反集对偶变换公理冶 孕垣琢 圮劭 孕原琢 中袁当 存在不动项时袁就存在悖论遥 如果把野正反集对偶 变换公理冶 孕垣琢 圮劭 孕原琢 引进逻辑演算系统中袁逻辑 演算系统中就会同样存在悖论遥 在命题演算系统 蕴 中袁如果承认野正反集对偶 变换公理冶 孕垣琢 圮劭 孕原琢 袁 则不动项存在袁存在悖论遥 即若 垣 琢 越 原 琢 越 藻袁 则诹 孕藻 圮劭 孕藻 曰 在谓词演算系统 蕴 中袁如果承认野正反集对偶变 换公理冶 孕渊曾蚤冤圮劭 孕渊 曾蚤 耀 冤 袁 则有不动项存在袁存在 悖论曰即若 曾蚤 越 曾蚤 耀 越 曾孕 袁 则诹 孕渊曾孕 冤圮劭 孕渊曾孕 冤 遥 由于在经典系统中袁定理 孕藻 袁劭 孕藻 诹 月 成立袁所 以袁如果承认悖论存在袁无论是系统 蕴 还是系统 运 袁 会导致整个系统崩溃遥 在以前的命题逻辑系统 蕴 袁谓词逻辑系统 运 中袁 为什么没有发现不动项的存在袁是因为在其中没有 建立起来正反演算袁一个公理系统中是否存在不动 项渊悖论冤 袁跟演算方式有关遥 由于不动项尧悖论的存在袁是不是野命题逻辑系 第 源 期摇摇摇摇摇摇摇摇摇摇摇摇摇 张金成院 逻辑及数学演算中的不动项与不可判定命题渊玉冤 窑缘园猿窑
·504 智能系统学报 第9卷 统L”、“谓词逻辑系统K”都是不足道的,是一个崩 [0,11上的奇数集合。 溃的逻辑系统?以后的证明表明:“命题逻辑系统 构造函数f(x)=11-x,若x∈[0,11CN,则 L”、“谓词逻辑系统K”都是在已知集合U上的封 fx)∈[0,11]CN: 闭演算,其中的不动项都是U外不动项。U外不动 利用函数f(x)=11-x,可以在A与A上建立一 项的存在是正常的,它不会导致“命题逻辑系统 一对应关系 L”、“谓词逻辑系统K”崩溃。 1.7自然数系统中的一般不动项 即x∈Af(x)∈A; 已经证明,命题逻辑系统L演算中存在不动项: 设P(n)表示:n是偶数:则P(n)表示:n是 奇数: 谓词逻辑系统K演算中存在不动项:同理,自然数 系统N演算中也存在不动项。 P[n]+P[f(n)]; 定理2自然数系统N的演算中,有不动项存 让fn)=11-n自指代,即:n=f(n),n=np是 它的不动项: 在,即若n:=m:=np,则FP(np)P(np)。 则得到:P(np)P(np)。 证明设N={0,1,2,3,…},构造V的子集合 承认正反集对偶变换公理P+“一P“,命题逻 U,U二N,命题P是关于正集+α、反集-的一个 辑系统L演算中存在不动项:谓词逻辑系统K演算 划分,U=+U-a,即:若+a={nlP(n)},则- 中存在不动项:自然数系统N演算中也存在不动 a={nlP(n)}f是+a,-a上的一个一一映 项,不动项及不动项命题的存在是不可否认的。 射,f:U→U,n:e+a,n:∈-a,=f(n:),有 正、反集对偶变换公理P“→一P“产生不动项 P(n)nP(n)。 的本质是自指代,也就是说,只要允许自指代,就可 如果有不动项np存在,则悖论存在。即若n:= 能产生不动项,悖论就不可能避免。 n=np,则P(n:)nP(n), 2U外不动项的逻辑性质 或P(np)P(np);以后也将证明:自然数 2.1正反对称集上的不动项一定是U外不动项 系统N演算中的不动项,也是外不动项。 对于一个全集U={x1,x2,…,x,…},P是 由于自然数系统N是一个具体的数学系统,已 一个划分标准,如果性质P可以把U划分成正、 经不需要正反集对偶变换公理P“一P“,只要进 反2个对称集。 行类似正反集对偶变换的运算(即自指代运算),就 会产生不动项。 当x=x=xp时,即:xp为不动项时,有 在自然数系统N中,设U={n1,n2,…,n:, P(xr)P(xp),或PP就表现为悖论。 …{。上P(xp)nP(xp)具有一般性,性质P可 定理3(U外不动项定理)设全集U= 以是任何一个性质。 {x1,x2,…,x…}是一个已经定义的集合,U可以 二分成正反对称集合U=+U-a,如果正集、反集 如果P(x)表示:x是偶数; 那么P(np)P(np)表示:np是偶数np 上的演算是一致的,那么,不动项xp不属于正集+ a,也不属于反集-a,即xpU;即:正、反集合上 是奇数。 的不动项,是U外不动项。 如果设U表示自然数系统N中的所有命题, 证明 P(x)表示:x可以证明:即x是系统N可证命题, l)上xp∈+a …假设; Fnxo 2)上P(xp)nP(xp) …不动项定理; 那么P(np)P(np)表示:np可以证明 3)上P(xp)AP(xp)…经典定理,正集 一np不可以证明。 +α中存在矛盾命题,这与正集是一致的相矛盾: 或者上wnp→片wnp,np就是Gdel不可判定 4)上xp生+a …(1),反证法: 命题。 同理可证:xp华一a。 例10取自然数集合N的一个子集合U= 即如果不动项属于正集+α,那么,将导致正集 [0,11];把这个集合,分成偶数集合与奇数集合, 矛盾:同样,如果不动项属于反集-α,那么,将导致 偶数集合A={xlx=2n,n∈N∧x∈[0,11]}; 反集矛盾:所以,不动项不属于正集+α,也不属于 则A={x1x=2n+1,n∈N八x∈[0,11]}是 反集-a,即xp生U
统 蕴 冶尧野谓词逻辑系统 运 冶都是不足道的袁是一个崩 溃的逻辑系统钥 以后的证明表明院野命题逻辑系统 蕴 冶尧野谓词逻辑系统 运 冶都是在已知集合 哉 上的封 闭演算袁其中的不动项都是 哉 外不动项遥 哉 外不动 项的存在是正常的袁它不会导致野 命题逻辑系统 蕴 冶尧野谓词逻辑系统 运 冶崩溃遥咱源暂 员援苑摇 自然数系统中的一般不动项 已经证明袁命题逻辑系统 蕴 演算中存在不动项曰 谓词逻辑系统 运 演算中存在不动项曰同理袁自然数 系统 晕 演算中也存在不动项遥 定理 圆摇 自然数系统 晕 的演算中袁有不动项存 在袁即若 灶蚤 越 灶蚤 耀 越 灶孕 袁 则诹 孕渊灶孕 冤圮劭 孕渊灶孕 冤 遥 证明 设 晕 越 园袁员袁圆袁猿袁噎 袁 构造 晕 的子集合 哉袁哉 哿 晕袁 命题 孕 是关于正集 垣 琢 尧反集 原 琢 的一个 划分袁 哉 越 垣 琢 胰原 琢 袁即院若 垣 琢 越 灶渣 孕渊灶冤 袁 则 原 琢 越 灶渣 劭 孕渊灶冤 袁枣 是 垣 琢袁 原 琢 上的一个一一映 射袁 枣院哉 寅 哉袁灶蚤 沂垣 琢袁 灶蚤 耀 沂原 琢 袁 灶蚤 耀 越 枣渊灶蚤冤 袁 有 孕渊灶冤圮劭 孕渊 灶 耀 冤 遥 如果有不动项 灶孕 存在袁则悖论存在遥 即若 灶蚤 越 灶蚤 耀 越 灶孕 袁 则 孕渊灶蚤冤圮劭 孕渊灶蚤 耀 冤 袁 或 孕渊灶孕 冤圮劭 孕渊灶孕 冤 曰以后也将证明院自然数 系统 晕 演算中的不动项袁也是 哉 外不动项遥 由于自然数系统 晕 是一个具体的数学系统袁已 经不需要正反集对偶变换公理 孕垣琢 圮劭 孕原琢 袁 只要进 行类似正反集对偶变换的运算渊即自指代运算冤 袁就 会产生不动项遥 在自然数系统 晕 中袁 设 哉 越 喳灶员 袁灶圆 袁噎袁灶蚤袁 噎札遥 诹晕孕渊曾孕 冤圮劭 孕渊曾孕 冤 具有一般性袁性质 孕 可 以是任何一个性质遥 如果 孕渊曾冤 表示院 曾 是偶数曰 那么 孕渊灶孕 冤圮劭 孕渊灶孕 冤 表示院 灶孕 是偶数 圮 灶孕 是奇数遥 如果设 哉 表示自然数系统 晕 中的所有命题袁 孕渊 曾冤 表示院 曾 可以证明曰即 曾 是系统 晕 可证命题袁 诹晕 曾 遥 那么 孕渊灶孕 冤圮劭 孕渊灶孕 冤 表 示院 灶孕 可以证明 圮 灶孕 不可以证明遥 或者 诹晕 灶孕圮 晕 灶 孕 袁灶 孕 就是 郧觟凿藻造 不可判定 命题遥 例 员园 摇 取自然数集合 晕 的一个子集合 哉 越 园袁员员 曰把这个集合袁分成偶数集合与奇数集合袁 偶数集合 粤 越 曾渣 曾 越 圆灶袁灶 沂 晕 夷 曾 沂 园袁员员 曰 则 粤 原 越 曾渣 曾 越 圆灶 垣 员袁灶 沂 晕 夷 曾 沂 园袁员员 是 园袁员员 上的奇数集合遥 构造函数 枣渊曾冤 越 员员 原 曾袁 若 曾 沂 园袁员员 奂 晕袁 则 枣渊曾冤 沂 园袁员员 奂 晕 曰 利用函数 枣渊曾冤 越 员员 原 曾袁 可以在 粤 与 粤 原 上建立一 一对应关系 即 曾 沂 粤圮枣渊曾冤 沂 粤 原 曰 设 孕渊灶冤 表示院 灶 是偶数曰则 劭 孕渊灶冤 表示院 灶 是 奇数曰 孕咱灶暂圮劭 孕咱枣渊灶冤暂 曰 让 枣渊灶冤 越 员员 原 灶 自指代袁即院 灶 越 枣渊灶冤 袁灶 越 灶孕 是 它的不动项曰 则得到院 孕渊灶孕 冤圮劭 孕渊灶孕 冤 遥 承认正反集对偶变换公理 孕垣琢 圮劭 孕原琢 袁 命题逻 辑系统 蕴 演算中存在不动项曰谓词逻辑系统 运 演算 中存在不动项曰自然数系统 晕 演算中也存在不动 项袁不动项及不动项命题的存在是不可否认的遥 正尧反集对偶变换公理 孕垣琢 圮劭 孕原琢 产生不动项 的本质是自指代袁也就是说袁只要允许自指代袁就可 能产生不动项袁悖论就不可能避免遥 圆摇 哉 外不动项的逻辑性质 圆援员摇 正反对称集上的不动项一定是 哉 外不动项 对于一个全集 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 袁孕 是 一个划分标准袁如果性质 孕 可以把 哉 划分成正尧 反 圆 个对称集遥 当 曾 越 曾 耀 越 曾孕 时袁 即院 曾孕 为不动项时袁 有 孕渊曾孕 冤圮劭 孕渊曾孕 冤 袁或 孕藻 圮劭 孕藻 就表现为悖论遥 定理 猿 渊 哉 外不动项定理冤 摇 设全集 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 是一个已经定义的集合袁 哉 可以 二分成正反对称集合 哉 越 垣 琢胰原 琢袁 如果正集尧反集 上的演算是一致的袁那么袁不动项 曾孕 不属于正集 垣 琢袁 也不属于反集 原 琢袁 即 曾孕 埸 哉 曰即院正尧反集合上 的不动项袁是 哉 外不动项遥 证明 员冤 诶曾孕 沂垣 琢 诂诂假设曰 圆冤诶 孕渊曾孕 冤圮劭 孕渊曾孕 冤 诂诂不动项定理曰 猿冤诶 孕渊曾孕 冤 夷 劭 孕渊曾孕 冤 诂诂经典定理袁正集 垣 琢 中存在矛盾命题袁这与正集是一致的相矛盾曰 源冤诶 曾孕 埸垣 琢 诂诂渊员冤袁反证法曰 同理可证院 曾孕 埸原 琢 遥 即如果不动项属于正集 垣 琢袁 那么袁将导致正集 矛盾曰同样袁如果不动项属于反集 原 琢袁 那么袁将导致 反集矛盾曰所以袁不动项不属于正集 垣 琢袁 也不属于 反集 原 琢袁 即 曾孕 埸 哉 遥 窑缘园源窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷
第4期 张金成:逻辑及数学演算中的不动项与不可判定命题(【) ·505. 例11从整数到分数的发现:U为全体整数集 推论5N={0,1,2,3,…},UCN, 合J,把这个集合,分成偶数集合与奇数集合。 +a=(nI P(n)),-a (nl P(n)), +a={x1x=2n,n∈U}偶数集合; P(np)P(np)自然数系统N上的不动项np,是 -a={xlx=1-2n,n∈U}是奇数集合。 U外不动项。 正反集对应函数f(x)=1-x;x=f八x),x=1- 定理4设全集U={x,x2,…,x,…}是一个 x,x=1/2,所以,1/2为不动项,但是,1/2主+, 已经定义的集合,不动项xp具有正集+性质 1/2主-a,1/2主U,即:1/2为0外不动项,1/2不 P(x),也具有反集-性质一P(x),不动项xp具 再是整数。 有双重性质,同时与正集+α性质P(x)相矛盾,也 例12从有理数到无理数的发现:U为全体 与反集-α性质P(x)相矛盾。 正有理数集合Q。 证明: +a={xlx2>2,x∈U} 1)上P(xp)P(xp) …不动项定理 -a={xlx20,x∈U} 不动项x也具有反集-α性质一P(x); -a={x1x<0,x∈U} 8)卜(P(xp)→P(xp))A(P(xP)→ 正反集对应函数f(x)=-1/x;x=f(x),x=-1/x, P(xp)) …(1),经典定义 x=-T=i, 9)F(P(xp)VP(xp))A (P(xp)V 所以,i为不动项,但是,i+a,i使-a,i主U, P(xp)) …(8)经典定理 即:不动项i=√一1,为U外不动项,不再是实数。 10)上一P(xp)八P(xp)…不动项xp具有双 进一步可以探明:凡是通过自指代方程x=f(x) 重性质;同时与正集+α性质P(x)相矛盾,也与反 形成的正、反集合上的不动项,都存在类似的性质,是 集-α性质一P(x)相矛盾。 U外不动项,既不在正集中,也不在反集中。 定义12设全集U={x1,x2,…,x,…}是一个 U外不动项xp,不具有原集合U的性质,是变 已经定义的集合,不动项不属于正集+α,也不属于 反集-a,即不动项不属于已定义的集合,xp主U, 异项。 根据U外不动项定理3,设U=+aU-α,如果 单独给不动项命名一个集,叫做相对于U的未定义 存在正、反集合上的不动项,那么,它们都是U外不 集,即:不动集e={xp};不动项xp叫做相对于U的 动项,由这个定理,很容易得到以下推论: 未定义项;如果xp是未定义项,P是U上的一个谓 词,那么P(x。)叫做未定义命题。 推论1U=+aU-a,P是U的一个分割,任 何悖论P(xp)P(xp)其中项xp是U外不动项。 正、反对称集合+α,-α是相互矛盾的集合,通 常矛盾集合中的项是不能进行自指代的,当进行自 推论2U=+aU-a,+a={x|x∈x},- a={xI(x∈x)},罗素悖论P(R)P(R), 指代时,满足x=f(x)的项xp,在U中不存在; R={x:x生x}是U外不动项。 如果存在xp满足x=f(x),就会发生变异,x即 在U中无定义,只能把U拓展到U外定义xp,所 推论3U=+U-a,+a={P|V(P)=1}, +a={PIV(P)=0},PP命题演算系统L上的 以,U外不动项xp,也称为变异项。 例14在前面的例11~13中,1/2年J,1/2相 不动项P,是U外不动项。 推论4U=+aU-a,P是U的一个分割, 对于整数集合J的是未定义项;√万主Q,√2相对于 P(xp)P(xp)谓词演算系统K上的不动项xp, 有理数集合Q是未定义项;i=√~1,√一1生R, 是U外不动项。 √一工相对于实数集合R是未定义项。1/2,2
例 员员摇 从整数到分数的发现院 哉 为全体整数集 合 允袁 把这个集合袁分成偶数集合与奇数集合遥 垣 琢 越 曾渣 曾 越 圆灶袁灶 沂 哉 偶数集合曰 原 琢 越 曾渣 曾 越 员 原 圆灶袁灶 沂 哉 是奇数集合遥 正反集对应函数 枣渊曾冤 越 员 原 曾 曰 曾 越 枣渊曾冤 袁曾 越 员 原 曾袁曾 越 员 辕 圆袁 所以袁 员 辕 圆 为不动项袁但是袁 员 辕 圆 埸垣 琢袁 员 辕 圆 埸原 琢袁员 辕 圆 埸 哉袁 即院 员 辕 圆 为 哉 外不动项袁 员 辕 圆 不 再是整数遥 例 员圆 摇 从有理数到无理数的发现院 哉 为全体 正有理数集合 匝垣 遥 垣 琢 越 曾渣 曾圆 跃 圆袁曾 沂 哉 原 琢 越 曾渣 曾圆 约 圆袁曾 沂 哉 正反集对应函数 枣渊曾冤 越 圆 辕 曾 曰 曾 越 枣渊曾冤 袁曾 越 圆 辕 曾袁曾 越 圆 袁 所以袁 圆 为不动项袁但是袁 圆 埸垣 琢袁 圆 埸原 琢袁 圆 埸 哉袁 即院 圆 为 哉 外不动项袁 圆 不再是有理数遥 例 员猿摇 从实数到虚数的发现院 哉 为不为 园 的全 体实数集合 砸 遥 垣 琢 越 曾渣 曾 跃 园袁曾 沂 哉 原 琢 越 曾渣 曾 约 园袁曾 沂 哉 正反集对应函数 枣渊曾冤 越 原 员 辕 曾 曰 曾 越 枣渊曾冤 袁曾 越 原 员 辕 曾袁 曾 越 原 员 越 蚤袁 所以袁 蚤 为不动项袁但是袁蚤埸垣 琢袁蚤 埸原 琢袁蚤 埸 哉袁 即院不动项 蚤 越 原 员袁 为 哉 外不动项袁不再是实数遥 进一步可以探明院凡是通过自指代方程 曾 越 枣渊曾冤 形成的正尧反集合上的不动项袁都存在类似的性质袁是 哉 外不动项袁既不在正集中袁也不在反集中遥 哉 外不动项 曾孕 袁 不具有原集合 哉 的性质袁是变 异项遥 根据 哉 外不动项定理 猿袁设 哉 越 垣 琢 胰原 琢袁 如果 存在正尧反集合上的不动项袁那么袁它们都是 哉 外不 动项袁由这个定理袁很容易得到以下推论院 推论 员 摇 哉 越 垣 琢 胰原 琢袁孕 是 哉 的一个分割袁任 何悖论 孕渊曾孕 冤圮劭 孕渊曾孕 冤 其中项 曾孕 是 哉 外不动项遥 推论 圆 摇 哉 越 垣 琢 胰原 琢袁 垣 琢 越 曾渣 曾 沂 曾 袁 原 琢 越 曾渣 劭 渊曾 沂 曾冤 袁 罗素悖论 孕渊砸冤圮劭 孕渊砸冤 袁 砸 越 曾院曾 埸 曾 是 哉 外不动项遥 推论猿 摇 哉 越 垣 琢胰原 琢袁 垣 琢 越 孕渣 灾渊孕冤 越 员 袁 垣 琢 越 孕渣 灾渊孕冤 越 园 袁孕藻 圮劭 孕藻 命题演算系统 蕴 上的 不动项 孕藻 袁 是 哉 外不动项遥 推论 源 摇 哉 越 垣 琢 胰原 琢袁孕 是 哉 的一个分割袁 孕渊曾孕 冤圮劭 孕渊曾孕 冤 谓词演算系统 运 上的不动项 曾孕 袁 是 哉 外不动项遥 推 论 缘 摇 晕 越 园袁员袁圆袁猿袁噎 袁哉 哿 晕 袁 垣 琢 越 灶渣 孕渊灶冤 袁 原 琢 越 灶渣 劭 孕渊灶冤 袁 孕渊灶孕 冤圮劭 孕渊灶孕 冤 自然数系统 晕 上的不动项 灶孕 袁 是 哉 外不动项遥 定理 源摇 设全集 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 是一个 已经定义的集合袁不动项 曾孕 具有正集 垣 琢 性质 孕渊曾冤 袁 也具有反集 原 琢 性质 劭 孕渊曾冤 袁 不动项 曾孕 具 有双重性质袁同时与正集 垣 琢 性质 孕渊曾冤 相矛盾袁也 与反集 原 琢 性质 劭 孕渊曾冤 相矛盾遥 证明院 员冤诶 孕渊曾孕 冤圮劭 孕渊曾孕 冤 诂诂不动项定理 圆冤诶 劭 孕渊曾孕 冤 寅 孕渊曾孕 冤 诂诂渊员冤袁经典定理 猿冤诶 孕渊曾孕 冤 遗 孕渊曾孕 冤 诂诂渊圆冤袁经典定理 源冤诶 孕渊曾孕 冤 诂诂渊猿冤 不动项 曾孕 具有正集 垣 琢 性质 孕渊曾冤 曰 缘冤诶 孕渊曾孕 冤 寅 劭 孕渊曾孕 冤 诂诂渊员冤袁经典定理 远冤诶 劭 孕渊曾孕 冤 遗 劭 孕渊曾孕 冤 诂诂渊缘冤袁经典定理 苑冤诶 劭 孕渊曾孕 冤 诂诂渊远冤袁 不动项 曾孕 也具有反集 原 琢 性质 劭 孕渊曾冤 曰 愿冤 诶 渊孕渊曾孕 冤 寅 劭 孕渊曾孕 冤冤 夷 渊劭 孕渊曾孕 冤 寅 孕渊曾孕 冤冤 诂诂渊员冤袁经典定义 怨冤 诶 渊劭 孕渊曾孕 冤 遗 劭 孕渊曾孕 冤冤 夷 渊孕渊曾孕 冤 遗 孕渊曾孕 冤冤 诂诂渊愿冤经典定理 员园冤诶 劭 孕渊曾孕 冤 夷孕渊曾孕 冤 诂诂不动项 曾孕 具有双 重性质曰同时与正集 垣 琢 性质 孕渊曾冤 相矛盾袁也与反 集 原 琢 性质 劭 孕渊曾冤 相矛盾遥 定义 员圆摇 设全集 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 是一个 已经定义的集合袁不动项不属于正集 垣 琢袁 也不属于 反集 原 琢袁 即不动项不属于已定义的集合袁 曾孕 埸 哉袁 单独给不动项命名一个集袁叫做相对于 哉 的未定义 集袁即院不动集 藻 越 曾孕 曰不动项 曾孕 叫做相对于 哉 的 未定义项曰如果 曾孕 是未定义项袁 孕 是 哉 上的一个谓 词袁那么 孕渊曾孕 冤 叫做未定义命题遥 正尧反对称集合 垣 琢袁 原 琢 是相互矛盾的集合袁通 常矛盾集合中的项是不能进行自指代的袁当进行自 指代时袁满足 曾 越 枣渊曾冤 的项 曾孕 袁 在 哉 中不存在曰 如果存在 曾孕 满足 曾 越 枣渊曾冤 袁 就会发生变异袁 曾孕 在 哉 中无定义袁只能把 哉 拓展到 哉 外定义 曾孕 袁 所 以袁 哉 外不动项 曾孕 袁 也称为变异项遥 例 员源 摇 在前面的例 员员 耀 员猿 中袁 员 辕 圆 埸 允袁员 辕 圆 相 对于整数集合 允 的是未定义项曰 圆 埸 匝袁 圆 相对于 有理数集合 匝 是未定义项曰 蚤 越 原 员 袁 原 员 埸 砸袁 原 员 相对于实数集合 砸 是未定义项遥 员 辕 圆袁 圆 袁 第 源 期摇摇摇摇摇摇摇摇摇摇摇摇摇 张金成院 逻辑及数学演算中的不动项与不可判定命题渊玉冤 窑缘园缘窑
·506· 智能系统学报 第9卷 √~I相对于原来的集合U都是变异项。 -a={xIx0”;则有不动项 K上的不动项xp,自然数系统N上的不动项np,相 命题P(i),P(i)都是U外不可判定命题。 对于它们原始的已定义集合U,都是未定义项。 按照定理5,所有正、反集合上的不动项命题, 2.2U外不动项命题的不可判定性 都是U外不可判定命题。由这个定理,很容易得到 定理5U外不动项命题P(xp)或P(x), 以下推论: 相对于任何一致系统都是不可判定命题。 推论6任何悖论都是U外不可判定命题。 证明假设存在某个一致系统H,若 推论7罗素悖论是U外不可判定命题。 HP(xp),P(xp)P(xp),则HP(xp),与 推论8命题演算系统L上的不动项命题P, 系统H是一致的相矛盾,所以,HFP(xp); 是U外不可判定命题。 假设H上P(xP),P(xp)P(xp),则 推论9谓词演算系统K上的不动项命题 H卜P(xp),与系统H是一致的相矛盾,所以, P(xp),是U外不可判定命题。 H上P(xp); 推论10自然数系统N上的不动项命题 所以:P(xp),P(xp)在系统H均不可证, P(np),是U外不可判定命题。 P(xe)是系统H的不可判定命题; 2.3U外不可判定性与系统的完全性无关 当用一个性质P去划分一个系统时,在正集与 定理6对于U外不动项xp,U外的不可判定 反集的边缘都会产生不动项,这个不动项命题,无论 命题P(xp),与正集项(x:)命题P(x:)(i=1,2, 在任何系统中,都是不可判定的。 …),x≠xp,反项(x:)命题P(x)(i=1,2,…)的 对于任意关于谓词N的不动项X、,关于性质 判定无关,即与U内项命题的判定无关。 M命题M(Xx),若M≠N,则M(Xw)不是不动项 命题。若M=N,则M(Xx)是不动项命题,因此是 证明假设存在一个一致的公理系统∑,使 不可判定的。 得∑卜P(x),(i=1,2,…),即命题P(x)在公理 定义13U外不动项命题P(xp)的不可判定 系统∑中都可证; 性,叫做U外不可判定命题。 例15从整数到分数的发现:U为全体整数 由于命题P(xp)P(xp),若∑P(xp)则 集合,把这个集合,分成偶数集合与奇数集合, ∑一P(xp),与公理系统∑一致性相矛盾; +a={xIx=2n,n∈U)偶数集合: 所以,P(xp),P(xp)在公理系统∑中是不 -a={xlx=1-2n,n∈U)是奇数集合。 可判定命题。 正反集对应函数f(x)=1-x;,x=1-x,1/2为 不动项。 再假设公理系统∑,∑廿P(x),(i=1,2, 如果设P(x)表示命题:“x是偶数”;则有不动 …),即命题P(x)在公理系统∑中不可证; 项命题P(1/2),P(1/2)都是U外不可判定命题。 由于命题P(xp)P(xr),若∑卜P(xr)则 从有理数到无理数的发现:U为全体有理数集合。 +a={x|x2>2,x∈U仍 ∑卜P(x),与公理系统∑一致性相矛盾; -a={x1x22”;则有不动项 这个U外不动项命题P(x),是恒成立不可判 命题P(√2),P(√2)都是U外不可判定命题。 定命题,与U内项命题P(x)在公理系统∑中是 从实数到虚数的发现:U为不为0的全体实数 否可证没有关系。 集合。 如例15,从整数到分数的发现:U为全体整数 +={xIx>0,x∈U} 集合,把这个集合,分成偶数集合与奇数集合
原 员 相对于原来的集合 哉 都是变异项遥 按照以上定义袁 哉 外不动项 曾孕 相对于已经定义 集合 哉袁 都是未定义项曰所以袁悖论渊包括罗素悖 论冤 袁命题演算系统 蕴 上的不动项 孕藻 袁 谓词演算系统 运 上的不动项 曾孕 袁 自然数系统 晕 上的不动项 灶孕 袁 相 对于它们原始的已定义集合 哉袁 都是未定义项遥 圆援圆摇 哉 外不动项命题的不可判定性 定理 缘摇 哉 外不动项命题 孕渊曾孕 冤 或 劭 孕渊曾孕 冤 袁 相对于任何一致系统都是不可判定命题遥 证 明 假设存在某个一致系统 匀袁 若 匀诹孕渊曾孕 冤 袁孕渊曾孕 冤圮劭 孕渊曾孕 冤 袁 则 匀诹劭 孕渊曾孕 冤 袁 与 系统 匀 是一致的相矛盾袁所以袁 匀诹孕渊曾孕 冤 曰 假 设 匀诹劭 孕渊曾孕 冤 袁孕渊曾孕 冤圮劭 孕渊曾孕 冤 袁 则 匀诹孕渊曾孕 冤 袁 与系统 匀 是一致的相矛盾袁 所 以袁 匀诹劭 孕渊曾孕 冤 曰 所以院 孕渊曾孕 冤 袁劭 孕渊曾孕 冤 在系统 匀 均不可证袁 孕渊曾孕 冤 是系统 匀 的不可判定命题曰 当用一个性质 孕 去划分一个系统时袁在正集与 反集的边缘都会产生不动项袁这个不动项命题袁无论 在任何系统中袁都是不可判定的遥 对于任意关于谓词 晕 的不动项 载晕袁 关于性质 酝 命题 酝渊载晕冤 袁 若 酝 屹 晕袁 则 酝渊载晕冤 不是不动项 命题遥 若 酝 越 晕袁 则 酝渊载晕冤 是不动项命题袁因此是 不可判定的遥 定义 员猿摇 哉 外不动项命题 孕渊曾孕 冤 的不可判定 性袁叫做 哉 外不可判定命题遥 例 员缘 摇 从整数到分数的发现院 哉 为全体整数 集合袁把这个集合袁分成偶数集合与奇数集合袁 垣 琢 越 曾渣 曾 越 圆灶袁灶 沂 哉 偶数集合曰 原 琢 越 曾渣 曾 越 员 原 圆灶袁灶 沂 哉 是奇数集合遥 正反集对应函数 枣渊曾冤 越 员 原 曾 曰袁 曾 越 员 原 曾袁员 辕 圆 为 不动项遥 如果设 孕渊曾冤 表示命题院野 曾 是偶数冶曰则有不动 项命题 孕渊员辕 圆冤袁劭 孕渊员辕 圆冤 都是 哉 外不可判定命题遥 从有理数到无理数的发现院 哉 为全体有理数集合遥 垣 琢 越 曾渣 曾圆 跃 圆袁曾 沂 哉 原 琢 越 曾渣 曾圆 约 圆袁曾 沂 哉 摇 摇 正反集对应函数枣渊曾冤越 圆辕 曾袁曾 越 圆辕 曾袁 圆 为不动项遥 如果设 孕渊曾冤 表示命题院野 曾圆 跃 圆冶曰则有不动项 命题 孕渊 圆 冤 袁劭 孕渊 圆 冤 都是 哉 外不可判定命题遥 从实数到虚数的发现院 哉 为不为 园 的全体实数 集合遥 垣 琢 越 曾渣 曾 跃 园袁曾 沂 哉 原 琢 越 曾渣 曾 约 园袁曾 沂 哉 摇 摇 正反集对应函数 枣渊曾冤 越 原 员 辕 曾袁曾 越 原 员 辕 曾袁曾 越 原 员 越蚤 为不动项袁 如果设 孕渊曾冤 表示命题院野 曾 跃 园冶曰则有不动项 命题 孕渊蚤冤袁劭 孕渊蚤冤 都是 哉 外不可判定命题遥 按照定理 缘袁所有正尧反集合上的不动项命题袁 都是 哉 外不可判定命题遥 由这个定理袁很容易得到 以下推论院 推论 远 摇 任何悖论都是 哉 外不可判定命题遥 推论 苑 摇 罗素悖论是 哉 外不可判定命题遥 推论 愿摇 命题演算系统 蕴 上的不动项命题 孕藻 袁 是 哉 外不可判定命题遥 推论 怨 摇 谓词演算系统 运 上的不动项命题 孕渊曾孕 冤 袁 是 哉 外不可判定命题遥 推论 员园 摇 自然数系统 晕 上的不动项命题 孕渊灶孕 冤 袁 是 哉 外不可判定命题遥 圆援猿摇 哉 外不可判定性与系统的完全性无关 定理 远摇 对于 哉 外不动项 曾孕 袁哉 外的不可判定 命题 孕渊曾孕 冤 袁 与正集项渊 曾蚤 冤命题 孕渊曾蚤冤 渊蚤 越 员袁 圆袁 噎冤袁曾蚤 屹 曾孕 袁 反项渊 曾蚤 耀 冤命题 孕渊曾蚤 耀 冤 渊蚤 越 员袁圆袁噎冤 的 判定无关袁即与 哉 内项命题的判定无关遥 证明 假设存在一个一致的公理系统 移袁 使 得 移诹孕渊曾蚤冤袁渊蚤 越 员袁圆袁噎冤 袁 即命题 孕渊曾蚤冤 在公理 系统 移 中都可证曰 由于命题 孕渊曾孕 冤圮劭 孕渊曾孕 冤 袁 若 移诹孕渊曾孕 冤 则 移诹劭 孕渊曾孕 冤 袁 与公理系统 移 一致性相矛盾曰 所以袁 孕渊曾孕 冤 袁劭 孕渊曾孕 冤 在公理系统 移 中是不 可判定命题遥 再假设公理系统 移袁移 孕渊曾蚤冤袁渊蚤 越 员袁圆袁 噎冤袁 即命题 孕渊曾蚤冤 在公理系统 移 中不可证曰 由于命题 孕渊曾孕 冤圮劭 孕渊曾孕 冤 袁 若 移诹孕渊曾孕 冤 则 移诹劭 孕渊曾孕 冤 袁 与公理系统 移 一致性相矛盾曰 所以袁同样有 孕渊曾孕 冤 袁劭 孕渊曾孕 冤 在公理系统 移 中是不可判定命题遥 这个 哉 外不动项命题 孕渊曾孕 冤 袁是恒成立不可判 定命题袁与 哉 内项命题 孕渊曾蚤冤 在公理系统 移 中是 否可证没有关系遥 如例 员缘袁从整数到分数的发现院 哉 为全体整数 集合袁把这个集合袁分成偶数集合与奇数集合遥 窑缘园远窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷
第4期 张金成:逻辑及数学演算中的不动项与不可判定命题(【) ·507· +a={xlx=2n,n∈U}偶数集合 可判定的。 -a={xlx=1-2n,n∈U}奇数集合 另外,U外不动项命题P(xp)的不可判定性, 正反集对应函数f(x)=1-x:,x=1-x,1/2为 能作为系统Σ是否完全的标准,那么不动项命题 不动项,“1/2是偶数”:“1/2是奇数”:均不可证, P(x)的不可判定,∑相对U是不能完全的。我 都是不可判定命题。这个U外不动项命题,它与其 们可以找到这样一个实例,一个完全的系统中,同样 他整数x:是偶数还是奇数是否可证没有关系,是U 存在不动项。 外不可判定命题。 事实上,由于不动项存在是普遍的,很容易在整 由于一般的可判定集合外也存在不动项,所以, 数、自然数的任意一个有限子集上找到不动项。如 不动项命题的不可判定,是U外不可判定命题,并 果U外不动项命题P(x)的不可判定,可以作为系 不影响集合U内命题的可判定性。 统∑完全性、正反集合递归性的标准;那么将建立 由于不动项命题的不可判定,不影响集合的递 不起来真正完全的系统,也找不到真正的递归集合, 归性,所以,它也不影响系统的完全性。 这显然是错误的。 传统系统完全性的定义是:设全集U= 由于以前的逻辑研究中没有发现不动项,关于 {X,X2,…,X,…}是系统∑上的全部命题。 系统完全性的定义是有缺陷的,容易把U,外不动项 1)若HX:∈U3,(∑卜X)V(∑卜X),即: X。与U中的命题相混淆,把UΣ外不动项Xp与U 若HX∈U,X或一X,在∑中可证明,就称U相 中的命题区别开,系统完全性定义修改如下: 对Σ是完全的,简称系统∑是完全的: 定义14设全集U={X1,X2,…,X,…}是系 2)若3X,∈U,(∑HX)A(∑HX),即:若 统Σ上的全部命题。 3X∈U,X,并且一X,在∑中都不可证明,就称U相 1)若HX:∈U,(ΣX)V(∑上X),即若 对Σ是存在不可判定的命题,系统Σ是不完全的。 HX:∈U,X:或X,在∑中可证明,就称U相对Σ 注:系统Σ完全性的另一个等价定义是:若 是完全的,简称系统Σ是完全的: HX∈U,则MFX台∑FX,,称系统Σ是完全的 2)若3X,∈U,(∑HX)A(∑HX),即若 (Ms是系统Σ的模型)。 3X:∈U,X并且X,在Σ中都不可证明,就称U 定理7U外不动项命题P(xp)的不可判定 相对Σ是存在不可判定的命题,系统Σ是不完全的: 性,不能作为系统Σ是否完全的标准,即U外不动 3)若3X,且Xp是U关于性质P二项划分的 项命题的不可判定性与系统∑完全性无关。 不动项,(ΣHX)∧(HX),则Xp是U外不 证明设全集UΣ={X,X2,…,X,…}是系统 动项(XpUΣ),Xp是恒不可判定的命题,与系统∑ Σ上的全部命题,在系统Σ一致的假设下,用P(X) 是否完全无关。 表示Σ上X;一P(X)表示ΣHX。可证关系P把 2.4U外部矛盾的永恒性及其来源 U划分成正、反2个集合:+a={X1P(X)}; “不动项定理”说明只要有不动项存在,就会有 -a={XIP(X)}。建立双射关系F:+a~- 悖论存在,就会有矛盾存在。 a,F(X)=X,如果有不动项Xp存在, 推论11设全集0={x1x2,…,x,…)是一个 P(Xp)P(Xp),即:(∑X)(ΣHXp),那么 已经定义的集合,如果U可以二分为正反集合,并且 P(X),P(X)在系统∑中是不可判定命题,但 存在不动项,那么必然会形成不动项矛盾(即悖论)。 是,它们是U外不可判定命题,XpUΣ。 例16设U1为不包含0的整数集合,+α1= 根据“系统Σ完全性”的定义,“系统Σ完全 {x1x>0,x∈J},-a1={x1x0,正反集对应函数f(x)=-x; 有关系。 x=fx),x=-x,x=0,e1={0} 不动项X。不在+a中,也不在-α中,是U外 由于0是不动项,所以,P,(0)P(0): 不动项,系统的完全性只与U内的项判定有关。 P(0)AP(0),这里发现0是正负数外的一 即:P(X),P(X)不可判定,+a 个矛盾数。 {XIP(X)},-a={XIP(X)}中的命题仍然是 如果再把e1={0}加进原来集合U1,扩展到全
垣 琢 越 曾渣 曾 越 圆灶袁灶 沂 哉 偶数集合 原 琢 越 曾渣 曾 越 员 原 圆灶袁灶 沂 哉 奇数集合 摇 摇 正反集对应函数 枣渊曾冤 越 员 原 曾 曰袁 曾 越 员 原 曾袁员 辕 圆 为 不动项袁野 员 辕 圆 是偶数冶曰野 员 辕 圆 是奇数冶 曰均不可证袁 都是不可判定命题遥 这个 哉 外不动项命题袁它与其 他整数 曾蚤 是偶数还是奇数是否可证没有关系袁是 哉 外不可判定命题遥 由于一般的可判定集合外也存在不动项袁所以袁 不动项命题的不可判定袁是 哉 外不可判定命题袁并 不影响集合 哉 内命题的可判定性遥 由于不动项命题的不可判定袁不影响集合的递 归性袁所以袁它也不影响系统的完全性遥 传统系统 完 全 性 的 定 义 是院 设全集 哉撞 越 载员 袁载圆 袁噎袁载蚤袁噎 是系统 撞 上的全部命题遥 员冤若 坌载蚤 沂 哉撞袁渊撞诹载蚤冤 遗 渊撞诹劭 载蚤冤 袁 即院 若 坌载蚤 沂 哉撞袁载蚤 或 劭 载蚤 在 撞 中可证明袁就称 哉撞 相 对 撞 是完全的袁简称系统 撞 是完全的曰 圆冤若 埚载蚤 沂 哉撞袁渊撞 载蚤冤 夷 渊撞 劭 载蚤冤袁 即院若 埚载蚤 沂哉撞袁载蚤 并且劭 载蚤 在撞 中都不可证明袁就称哉撞 相 对 撞 是存在不可判定的命题袁系统 撞 是不完全的遥 注院系统 撞 完全性的另一个等价定义是院若 坌载蚤 沂 哉撞袁 则 酝撞莸载蚤圳撞诹载蚤 袁称系统 撞 是完全的 渊 酝撞 是系统 撞 的模型冤 遥 定理 苑摇 哉 外不动项命题 孕渊曾孕 冤 的不可判定 性袁不能作为系统 撞 是否完全的标准袁即 哉 外不动 项命题的不可判定性与系统 撞 完全性无关遥 证明 设全集 哉撞 越 载员 袁载圆 袁噎袁载蚤袁噎 是系统 撞 上的全部命题袁在系统 撞 一致的假设下袁用 孕渊载冤 表示 撞诹载 曰 劭 孕渊载冤 表示 撞 载 遥 可证关系 孕 把 哉撞 划分成正尧反 圆 个集合院 垣 琢 越 载渣 孕渊载冤 曰 原 琢 越 载渣 劭 孕渊载冤 遥 建立双射关系 云院 垣 琢 耀 原 琢袁 云渊载冤 越劭 载 袁 如果有不动项 载孕 存 在袁 孕渊载孕 冤圮劭 孕渊载孕 冤 袁即院 渊撞诹载孕 冤圮渊撞 载孕 冤 袁那么 孕渊载孕 冤 袁劭 孕渊载孕 冤 在系统 撞 中是不可判定命题袁但 是袁它们是 哉 外不可判定命题袁 载孕 埸 哉撞 遥 根据野系统 撞 完全性冶 的定义袁 野系统 撞 完全 性冶只跟 哉撞 内的命题 载 是否可证有关系袁因为 载孕 埸哉撞 袁所以袁野系统 撞 完全性冶根 载孕 是否可证袁没 有关系遥 不动项 载孕 不在 垣 琢 中袁也不在 原 琢 中袁是 哉 外 不动项袁系统的完全性只与 哉 内的项判定有关遥 即院 孕渊载孕 冤 袁劭 孕渊载孕 冤 不可判定袁 垣 琢 越 载渣 孕渊载冤 袁 原 琢 越 载渣 劭 孕渊载冤 中的命题仍然是 可判定的遥 另外袁 哉 外不动项命题 孕渊曾孕 冤 的不可判定性袁 能作为系统 撞 是否完全的标准袁那么不动项命题 孕渊曾孕 冤 的不可判定袁 移 相对 哉 是不能完全的遥 我 们可以找到这样一个实例袁一个完全的系统中袁同样 存在不动项遥 事实上袁由于不动项存在是普遍的袁很容易在整 数尧自然数的任意一个有限子集上找到不动项遥 如 果 哉 外不动项命题 孕渊曾孕 冤 的不可判定袁可以作为系 统 移 完全性尧正反集合递归性的标准曰那么将建立 不起来真正完全的系统袁也找不到真正的递归集合袁 这显然是错误的遥 由于以前的逻辑研究中没有发现不动项袁关于 系统完全性的定义是有缺陷的袁容易把 哉撞 外不动项 载孕 与 哉撞 中的命题相混淆袁把 哉撞 外不动项 载孕 与 哉撞 中的命题区别开袁系统完全性定义修改如下院 定义 员源摇 设全集 哉撞 越 载员 袁载圆 袁噎袁载蚤袁噎 是系 统 撞 上的全部命题遥 员冤若 坌载蚤 沂 哉撞袁渊撞诹载蚤冤 遗 渊撞诹 劭 载蚤冤 袁 即若 坌载蚤 沂哉撞袁载蚤 或 劭 载蚤 在 撞 中可证明袁就称 哉撞 相对 撞 是完全的袁简称系统 撞 是完全的曰 圆冤若 埚载蚤 沂 哉撞袁渊撞 载蚤冤 夷 渊撞 劭 载蚤冤袁 即若 埚载蚤 沂 哉撞袁载蚤 并且 劭 载蚤 在 撞 中都不可证明袁就称 哉撞 相对 撞 是存在不可判定的命题袁系统 撞 是不完全的曰 猿冤若 埚载孕 袁 且 载孕 是 哉撞 关于性质 孕 二项划分的 不动项袁 渊撞 载孕 冤 夷 渊撞 劭 载孕 冤 袁则 载孕 是 哉撞 外不 动项 渊载孕 埸哉撞冤 袁载孕 是恒不可判定的命题袁与系统 撞 是否完全无关遥 圆援源摇 哉 外部矛盾的永恒性及其来源 野不动项定理冶说明只要有不动项存在袁就会有 悖论存在袁就会有矛盾存在遥 推论 员员摇 设全集 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 是一个 已经定义的集合袁如果 哉 可以二分为正反集合袁并且 存在不动项袁那么必然会形成不动项矛盾渊即悖论冤遥 例 员远摇 设 哉员 为不包含 园 的整数集合袁 垣 琢员 越 曾渣 曾 跃 园袁曾 沂 允 袁 原 琢员 越 曾渣 曾 约 园袁曾 沂 允 袁 哉员 越 垣 琢员 胰原 琢员 遥 设 孕员渊曾冤 院曾 跃 园袁 正反集对应函数 枣渊曾冤 越 原 曾 曰 曾 越枣渊曾冤 袁曾 越 原 曾袁曾 越 园袁藻员 越 园 由于 园 是不动项袁所以袁 诹孕员渊园冤圮劭 孕员渊园冤 曰 诹孕员渊园冤 夷 劭 孕员渊园冤袁 这里发现 园 是正负数外的一 个矛盾数遥 如果再把 藻员 越 园 加进原来集合 哉员 袁 扩展到全 第 源 期摇摇摇摇摇摇摇摇摇摇摇摇摇 张金成院 逻辑及数学演算中的不动项与不可判定命题渊玉冤 窑缘园苑窑
·508 智能系统学报 第9卷 部的整数集合U2=J,再构造奇数、偶数正反集合。 en,重新命名不动项,扩展Un+1=+&Ue.U-a; 设+a2={x1x=2n,n∈J},-a2= {x1x=1-2n,n∈J},U2=+&2U-a2=J。设 以上分析发现经典逻辑是一个在相对已知集合 P,(x):x=2n,n∈J即:是偶数,正反集对应函数 上二分的封闭思维系统,在这个已知集合的外部可 f(x)=1-x;x=fx),x=1-x,x=1/2,由于1/2 以产生矛盾,产生悖论,而且这种矛盾是无法避免 是不动项,所以,上P2(1/2)P(1/2); 的。如果U,上的演算是一致的,矛盾只会产生在 P(1/2)AP,(1/2)。这里发现1/2是奇数、 U。的外部,经典逻辑在U。上的演算仍然成立,外部 偶数外的一个矛盾数。 矛盾不会导致系统崩遗。这说明,U。的外部矛盾是 同理,如果再把整数集合U,扩展的有理数集合 一种恒存在的矛盾,是正常的。 U,=Q,这里发现√万是有理数正反集合外的一个矛 3 Godel不完全定理证明不能成立 盾数,如例12。 如果再把有理数集合U3扩展到实数集合U,= 3.1Gdel不可判定命题 R,这里发现i=√一I是实数正反集合外的一个矛 简单回顾一下Gdl不完全定理的证明过程: 盾数,如:例13。 定义15一个自然数集上的k元关系R,称为在 矛盾数的出现相对于原来的已知集合U,是一 N中可表达的,如果存在一个有k个自由变元的公式 个未定义项,当把这个矛盾数重新定义,并且扩展的 (x1,x2,…,xn),使得对任何自然数n1,n2,…,n4, 原来的已知集合U,中去时得到U2,当以U2为整体 1)如果R(n1,n2,…,n)在N中成立,则 已知集合时,原来的矛盾就退化、消融了,但是,以 上(0a),0a),…,0a); U,为已知集合构造正反集合,在U,之外又有新的 2)如果R(n1,n2,…,nz)在N中不成立,则 矛盾数出现,再把这个矛盾数重新定义,并且扩展的 v7(0a,0a》,…,0)3]。 原来的已知集合U2中去时得到U,当以U3为整体 引进一个二元关系W:W={(m,n)},m是公 已知集合时,矛盾又退化、消融了,…,如此,数系在 式U(x)的Gdel数,n是公式U(m)从N证明的 矛盾的出现与消融中扩展,外部矛盾总是存在的,是 Gdel数。 永恒的。 可以证明:递归关系在N中都是可以表达的。 根据“U外不动项定理”:如果全集U= 可以证明:二元关系W是递归的,所以,W= {x1,2,…,x,…}是一个已经定义的集合,如果正 {(m,n)}在N中是可表达的: 集、反集上的演算是一致的,那么,不动项xp不属于 (m,n)∈W→Fwe(0m),0) 正集+,也不属于反集-α:即正、反集合上的不动 (m,n)生W→卜v7o(0m),0a) 项,是U外不动项。即xp生+a,xp生-a,xp年U。 U(x)=Hyw(x,y)--构造公式U(x); “U外不动项定理”说明不动项一定存在U外, m=g(U(x));m是公式U(x)的Gdel数: 即不动项矛盾(悖论)来源于正反集合之外。 用m去替换U(x)中所有自由出现的x得: 推论12设U={x1,x2,…,x,…},如果U上 U(m)=Hyw(0m),y)----y是U(m)证 的演算是一致的,那么,不动项矛盾 明的Gdel数; “上P(xp)P(xp)”,上P(xp)AP(x)在U Vyw(0m,y)的解释是“对任意y,y是 外,即xp生U(矛盾来源于已定义集合U的外部)。 U(m)证明的Gdel数不成立”或者: U,分成对立集合U1=+a1U-&1,产生矛盾集 “对任意y,y是Gdel数为m的公式(即: 合e1,重新命名不动项,扩展U2=+,Ue,U-a1; U(m))证明的Godel数不成立”; U2分成对立集合U2=+α2U-a2,产生矛盾集 或者Hy0(0m),y)3y(0m),y)“不 合e2,重新命名不动项,扩展U3=+a2Ue2U-a2; 存在y,y是U(m)证明的Gdel数”,即“U(m)是 U3分成对立集合U3=+a3U-a,产生矛盾集 不可证明的”[4: 合e3,重新命名不动项,扩展U4=+aUe3U-a3; 定理8U(m)在N中是一个不可判定命题。 证明 Un分成对立集合Un=+a。U-an,产生矛盾集合 1)(m,n)∈W→Fxw(0m),0a)
部的整数集合 哉圆 越 允袁 再构造奇数尧偶数正反集合遥 设 垣 琢圆 越 曾渣 曾 越 圆灶袁灶 沂 允 袁 原 琢圆 越 曾渣 曾 越 员 原 圆灶袁灶 沂 允 袁哉圆 越 垣 琢圆 胰原 琢圆 越 允 遥 设 孕圆渊曾冤 院曾 越 圆灶袁灶 沂 允 即院是偶数袁正反集对应函数 枣渊曾冤 越 员 原 曾 曰 曾 越 枣渊曾冤 袁曾 越 员 原 曾袁曾 越 员 辕 圆袁 由于 员 辕 圆 是不动项袁 所 以袁 诹孕圆渊员 辕 圆冤圮劭 孕圆渊员 辕 圆冤曰 诹孕圆渊员 辕 圆冤 夷 劭 孕圆渊员 辕 圆冤 遥 这里发现 员 辕 圆 是奇数尧 偶数外的一个矛盾数遥 同理袁如果再把整数集合 哉圆 扩展的有理数集合 哉猿 越 匝袁 这里发现 圆 是有理数正反集合外的一个矛 盾数袁如例 员圆 遥 如果再把有理数集合 哉猿 扩展到实数集合 哉源 越 砸袁 这里发现 蚤 越 原 员 是实数正反集合外的一个矛 盾数袁如院例 员猿遥 矛盾数的出现相对于原来的已知集合 哉员 是一 个未定义项袁当把这个矛盾数重新定义袁并且扩展的 原来的已知集合 哉员 中去时得到 哉圆 袁 当以 哉圆 为整体 已知集合时袁原来的矛盾就退化尧消融了袁但是袁以 哉圆 为已知集合构造正反集合袁在 哉圆 之外又有新的 矛盾数出现袁再把这个矛盾数重新定义袁并且扩展的 原来的已知集合 哉圆 中去时得到 哉猿 袁 当以 哉猿 为整体 已知集合时袁矛盾又退化尧消融了袁噎袁如此袁数系在 矛盾的出现与消融中扩展袁外部矛盾总是存在的袁是 永恒的遥 根据 野 哉 外不动项定理冶院 如果全集 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 是一个已经定义的集合袁如果正 集尧反集上的演算是一致的袁那么袁不动项 曾孕 不属于 正集 垣 琢袁 也不属于反集 原 琢 曰即正尧反集合上的不动 项袁是 哉 外不动项遥 即 曾孕 埸垣 琢袁曾孕 埸原 琢袁曾孕 埸 哉遥 野 哉 外不动项定理冶说明不动项一定存在 哉 外袁 即不动项矛盾渊悖论冤来源于正反集合之外遥 推论 员圆摇 设 哉 越 曾员 袁曾圆 袁噎袁曾 蚤袁噎 袁 如果 哉 上 的演算是一致的袁 那 么袁 不动项矛盾 野诹 孕渊曾孕 冤圮劭 孕渊曾孕 冤 冶袁诹 孕渊曾孕 冤 夷 劭 孕渊曾孕 冤 在 哉 外袁即 曾孕 埸 哉 渊矛盾来源于已定义集合 哉 的外部冤 遥 哉员 分成对立集合 哉员 越 垣 琢员 胰原 琢员 袁 产生矛盾集 合 藻员 袁 重新命名不动项袁扩展 哉圆 越 垣 琢员 胰 藻员 胰原 琢员 曰 哉圆 分成对立集合 哉圆 越 垣 琢圆 胰原 琢圆 袁 产生矛盾集 合 藻圆 袁 重新命名不动项袁扩展 哉猿 越 垣 琢圆 胰 藻圆 胰原 琢圆 曰 哉猿 分成对立集合 哉猿 越 垣 琢猿 胰原 琢猿 袁 产生矛盾集 合 藻猿 袁 重新命名不动项袁扩展 哉源 越 垣 琢猿 胰 藻猿 胰原 琢猿 曰 噎 哉灶 分成对立集合 哉灶 越 垣 琢灶 胰原 琢灶袁产生矛盾集合 藻灶袁 重新命名不动项袁扩展 哉灶垣员 越 垣 琢灶 胰 藻灶 胰原 琢灶曰 噎 以上分析发现经典逻辑是一个在相对已知集合 上二分的封闭思维系统袁在这个已知集合的外部可 以产生矛盾袁产生悖论袁而且这种矛盾是无法避免 的遥 如果 哉灶 上的演算是一致的袁矛盾只会产生在 哉灶 的外部袁经典逻辑在 哉灶 上的演算仍然成立袁外部 矛盾不会导致系统崩溃遥 这说明袁 哉灶 的外部矛盾是 一种恒存在的矛盾袁是正常的遥 猿摇 郧觟凿藻造 不完全定理证明不能成立 猿援员摇 郧觟凿藻造 不可判定命题 简单回顾一下 郧觟凿藻造 不完全定理的证明过程院 定义 员缘摇 一个自然数集上的 噪 元关系 砸袁 称为在 晕 中可表达的袁如果存在一个有 噪 个自由变元的公式 孜渊曾员袁曾圆袁噎袁曾灶 冤袁 使得对任何自然数 灶员袁灶圆袁噎袁灶噪袁 员 冤 如 果 砸渊灶员 袁灶圆 袁噎袁灶噪冤 在 晕 中成立袁 则 诹晕孜渊园渊灶员冤 袁园渊灶圆冤 袁噎袁园渊灶噪冤 冤 曰 圆冤 如 果 砸渊灶员 袁灶圆 袁噎袁灶噪冤 在 晕 中不成立袁 则 诹晕劭 孜渊园渊灶员冤 袁园渊灶圆冤 袁噎袁园渊灶噪冤 冤 咱猿暂 遥 引进一个二元关系 宰 院 宰 越 渊皂袁灶冤 袁皂 是公 式 哉渊曾冤 的 郧觟凿藻造 数袁 灶 是公式 哉渊皂冤 从 晕 证明的 郧觟凿藻造 数遥 可以证明院递归关系在 晕 中都是可以表达的遥 可以证明院二元关系 宰 是递归的袁所以袁 宰 越 渊皂袁灶冤 在 晕 中是可表达的院 渊皂袁灶冤 沂 宰圯诹晕憎渊园渊皂冤 袁园渊灶冤 冤 渊皂袁灶冤 埸 宰圯诹晕劭 憎渊园渊皂冤 袁园渊灶冤 冤 哉渊曾冤 越 坌赠劭 憎渊曾袁赠冤 原原原构造公式 哉渊曾冤 曰 皂 越 早渊哉渊曾冤冤 曰 皂 是公式 哉渊曾冤 的 郧觟凿藻造 数曰 用 皂 去替换 哉渊曾冤 中所有自由出现的 曾 得院 哉渊皂冤 越 坌赠劭 憎渊园渊皂冤 袁赠冤 原原原原原 赠 是 哉渊皂冤 证 明的 郧觟凿藻造 数曰 坌赠劭 憎渊园渊皂冤 袁赠冤 的解释是 野 对任意 赠袁赠 是 哉渊皂冤 证明的 郧觟凿藻造 数不成立冶或者曰 野对任意 赠袁赠 是 郧觟凿藻造 数 为 皂 的公式 渊 即院 哉渊皂冤 冤证明的 郧觟凿藻造 数不成立冶 曰 或者 坌赠劭 憎渊园渊皂冤 袁赠冤圮劭 埚赠诹憎渊园渊皂冤 袁赠冤 野不 存在 赠袁赠 是 哉渊皂冤 证明的 郧觟凿藻造 数冶 袁即野 哉渊皂冤 是 不可证明的冶咱源暂 曰 定理 愿摇 哉渊皂冤 在 晕 中是一个不可判定命题遥 证明 员冤 渊皂袁灶冤 沂 宰圯诹晕憎渊园渊皂冤 袁园渊灶冤 冤 袁 窑缘园愿窑 智 能 系 统 学 报摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇 第 怨 卷