代德景问题的机械算法

代德景问题的机械算法 THE MECHANICAL ALGORITHM FOR SOLVING DEDEKIND’S PROBLEM. 刘初长 Liu Chuchang first-author <正> 数学定理的证明是人类演绎能力的最集中表现,能否使数学定理证明机械化,是人工智能中的一个重要课题。六十年代以来,定理的机械证明引起了人们极大的兴趣[2]。由于电子计算机的计算速度快,许多需要通过大量计算才能获得结论的问题,就可以利用计算机求出部分结果,猜出部分结论,然后编好程序,让机器进行自动证明。文献[1]就是利用这种方法,得到了关于代德景问题的重要定理,而使三个变量的代德景问题完全解决。但四个变量或更多个变量的代德景问题,还在摸索之中。为了最后解决这个问题,我们还需要做大量的计算。本文是作者在利用手算和计算机考虑一些特例时,提出的一种机械算法。根据这种方法,利用计算机可以较迅速地获得许多育用的公式。如果不考虑时空的限制,理论上可以得出计算任意多个练条生成的自由分配格所含元素总数的公式。 In this paper a mechanical algorithm for solving Dedekind’s problem is given, and some special results of this problem for 4, 5, 6 variables have been obtained[1,2]. Using thes algorithm we have verified that[1,1,1,1,1,1] =7828854 which is agree with the ward’s result[3]in 1946, In addition we have obtained a new result:[1,1,1,1,1,2] =3352343220. First in this paper we have generalized the concept about the pile—numbers, and defined the recursive functionon the set G M （r 1 ,…,r k ）of the pile--numbers as following: （1） f（0,1）=0; （2） for u≠0, f（u,1）=1; （3） for s > 1 f（u,s）=f（u’,s-1）. where u’, uε G m （r 1 ,…,r k ） and N be the set of natural numbers. Second, we use the following formulas: （1） for s > {u}, f（u, s）=0; （2） f（u, s）=f（u i , s）+f（u i , s-1）+f i （u, s）; （3） f（u, s）=f（u i , s）+f（u i , s-1）+f（u j , s-1）+f i （u j , s）+f ij （u,s） to compute the value of f（u, s）, and we hove abtained: Theorem: Let[n ,m, r 1 ,…, r k ]be the order of the free distributive lattice generated by k+2 chains with lengths n, m, r 1 ,…,r k respectively, then we have:where f（u, s）is the reeursive function on G m+1 （r 1 ,…, k ）and p=（m+1）（r i +1）. 1980-03-01 2021-04-01 3