完备布尔代数理论的计算复杂性

THE COMPUTATIONAL COMPLEXITY OF THE THEORY OF COMPLETE BOOLEAN ALGEBRAS

运用改进的Ehrenfeuchtgames理论，适当定义了范数和囿函数，给出了无原子布尔代数理论的一个判定过程．利用这个结果，直接构造出完备布尔代数的判定过程，并且分析了它们的复杂度．

After properly defining the norm and bound functions a decision procedure for the first order theory of atomless boolean algebras is explicitly constructed by making use of the improved Ehrenfeucht game procedure, which is essentially a kind of quantivier elimination procedure. Subsequently, a decision method is achieving for the theory of complete boolean algebras based on that procedure and a result by the author. The computational complexities of both procedures are analysized.