|
|||||
|
|
| 完备布尔代数理论的计算复杂性 | |
| 引用本文： | 薛锐. 完备布尔代数理论的计算复杂性[J]. 北京师范大学学报(自然科学版), 1999, 35(3): 303-309 |
| 作者姓名： | 薛锐 |
| 作者单位： | 北京师范大学数学系 |
| 摘 要： | 运用改进的Ｅｈｅｒｎｆｅｕｃｈｔ ｇａｍｅｓ理论，适当定义了范数和囿函数，给出了无原子布尔代数理论的一个判定过程，利用这个结果，直接构造出完备布尔代数的判定过程，并且分析了它们的复杂度。 |
| 关 键 词： | 完备布尔代数 可判定性 计算复杂性 数理逻辑 |
THE COMPUTATIONAL COMPLEXITY OF THE THEORY OF COMPLETE BOOLEAN ALGEBRAS |
|
| Xue Rui. THE COMPUTATIONAL COMPLEXITY OF THE THEORY OF COMPLETE BOOLEAN ALGEBRAS[J]. Journal of Beijing Normal University(Natural Science), 1999, 35(3): 303-309 | |
| Authors: | Xue Rui |
| Abstract: | 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. |
| Keywords: | complete boolean algebra Decidability elementary equivalence Ehrenfeuct game computational complexity |
| 本文献已被 CNKI 维普 等数据库收录！ | |