论文部分内容阅读
由于计算机应用方面的推进,置换群的布尔函数的可表示问题是近十几年才成为人们关注的热点。布尔函数的自同构群主要应用于研究形式语言的并行计算复杂度中(为了获得进一步的信息,可以参阅参考文献1)。但是,现在公认的难点是:这类问题的研究必需应用一些新的方法。因为可表示或者k-可表示是在置换同构意义下保持其性质不变的,而并非是在一般的抽象群同构意义下。这样就使得有关有限置换群最前沿的理论,如O’Nan-Scott定理(参阅参考文献2),基本没有办法应用。而大量的关于抽象群的完美理论在此也是无能为力的。 人们研究此类问题的基本思路还是由简单的置换群开始得到一些结论,再通过各种运算来合成其它复杂的群,并加以讨论。本文所讨论的置换群的圈积就是在由本原群向非本原群的扩展中所应用的运算。关于圈积的布尔函数的可表示性问题,参考文献1和参考文献4已经有了一些结论,但很不完备。为了使本文能自成体系,我会将其作为单独的一部分加以介绍。 由一个很基本的定理(参阅本文的定理 3)建立起了图可表示和布尔函数可表示之间的关系,也使我有了从另一个角度来入手研究的想法。1999年“Discrete Mathematics”上的一篇关于直积的图可表示性的论文(参阅参考文献 3)给了我很大的启示。又在图论中已有的关于图的合成方面一篇论文(参阅参考文献 5)的启发下,我终于得到了本文的一个主要结论:如果圈积的两个运算因子均图可表示,则此圈积一定可图表示。 得到此结论的主要难点在于构造圈积的表示图上。为了解决此难点,我主要将轨道的思想引入到证明中,定义了图与图的一种新运算——图的轨道合成。分了四种情况,用了三种构造方法加以讨论,最终达到了目的。 本文关于圈积GlH的图可表示方面的必要条件是定理5,它只得出了H也应图可表示的结论,有关G的限制有待近一步的探讨。