自由分配格的一种矩阵表示及其阶的计算

自由分配格的一种矩阵表示及其阶的计算 A KIND OF MATRIX REPRESENTATION OF THE FREE DISrRIBUTIVE LATTICE AND EVALUATION OF ITS ORDER 戴大为 Dai Dawei first-author 借计算机进行公式推演是定理的自动证明研究中一个有意义的课题。文献[1][2] 对此作了一些探讨,并把这种思想用于Dedekind问题的研究,获得了新的结果。本文是这一工作的继续。狭义的Dedekind问题是:n个元素生成的自由分配格D n 应有多少元素?以D（n）表示D n 元素的个数。我们知道,在阈逻辑中,D（n）恰是变量数目不超过n的正伪阀门函数的个数[3]。因此,Dedekind问题本身有它的实际意义。虽然Dedekind提出这一问题已有80多年的历史[4] ,但至今仍未求得计算D（n）的公式。本文给出了计算D（n）的一种算法。广义的Dedekind问题是,求r个链条生成的自由分配格的元素的个数[l 1 ,l 2 ,…,l r ].文献[2] 解决了三个链条的情形,得到了计算[l,m,n]的公式为: [l,m,n] =（l+m+n+2）!! l!! m!! n!!/（1+m+1）!!（m+n+1）!!（n+l+1）!!式中l!!=l!（l-1）!…3!2!1!,0!!=1.本文对广义的Dedekind问题的一些特例提供了一种算法。 Let D n be the free distributive lattice generated by n elements. Up to isomorphism, D n is none other than the partial ordered set A n defined recursively as the following. 1) A o ={0, 1}, 0≤1. 2) A k+1 ={（w 1 , w 2 ）|（w 1 , w 2 ）∈ A k ×A k , w 1 ≤w 2 }; k=0, 1, 2, …. The partial ordering in A k+1 is that （w 1 , w 2 ）≤（w 1 ′ , w 2 ′ ） if and only if w 1 ≤w 1 ′ , and w 2 ≤w 2 ′ . Corresponding to the enumeration of A n , we get an enumeration of members in D n . It is in this enumeration of D n that we speak of the ith member of D n . Then we have proved the following. Theorem I. Let T n =(α ij ′ ) and T n-1 =（α（ij））. Then α ij ′ =α p（i）p（j） ·α q（i）q（j） . Further we define the characteristic submatrix A ij of an element α（ij） of T n-1 as this: suppose that the elements α ii1 , α jj2 , …, α iir in the ith row of T n-1 and the elements α（jj1）, α jj2 , …, α jjs in the jth row of T n-1 are 0. Then A ij is the submatrix of T n-1 formed by deleting the i 1 , i 2 , …, i r rows and the j 1 , j 2 , …, j 8 , columns from T n-1 . Thus we obtain. Theorem 2. Let T n-1 =(α ij ). Thenin which A ij is the characteristic submatrix of α ij . The theorems express an easy algorithm for evaluating the order of D n . For making it more efficient, we have improved the algorithm and given a practicable BASIC program as well. 1980-03-01 2021-04-01 3