Maximal contractions in Boolean algebras  

作　　者：SHI HuiXian WANG GuoJun 

机构地区：[1]Institute of Mathematics,Shaanxi Normal University,Xi'an 710062,China

出　　处：《Science China(Information Sciences)》2012年第9期2044-2055,共12页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 11171200,61005046,61103133);Fundamental Research Funds for the Central Universities (Grant No. GK201004006)

摘　　要：In the present paper, the concepts of deductive element and maximal contraction are introduced in Boolean algebras, and corresponding theories of consistency and maximal contractions are studied. An algorithm principle is proposed to compute all maximal contractions for a consistent set with respect to its refutation in Boolean algebras. It is pointed out that the quotient algebra of the first-order language with respect to its provable equivalence relation constitutes a Boolean algebra, and hence the computation of R-contractions for closed formulas in first-order languages can be converted into the one in Boolean algebras proposed in this paper. Furthermore, the concept of basic element is introduced in Boolean algebras, which contributes to the definitions of clause and Horn clause transplanted from logic to a special type of Boolean algebras generated by basic elements. It is also pointed out that the computation of R-contractions for clauses in the classical propositional logic can be converted into the one in Boolean algebras generated by basic elements proposed in this paper.In the present paper, the concepts of deductive element and maximal contraction are introduced in Boolean algebras, and corresponding theories of consistency and maximal contractions are studied. An algorithm principle is proposed to compute all maximal contractions for a consistent set with respect to its refutation in Boolean algebras. It is pointed out that the quotient algebra of the first-order language with respect to its provable equivalence relation constitutes a Boolean algebra, and hence the computation of R-contractions for closed formulas in first-order languages can be converted into the one in Boolean algebras proposed in this paper. Furthermore, the concept of basic element is introduced in Boolean algebras, which contributes to the definitions of clause and Horn clause transplanted from logic to a special type of Boolean algebras generated by basic elements. It is also pointed out that the computation of R-contractions for clauses in the classical propositional logic can be converted into the one in Boolean algebras generated by basic elements proposed in this paper.

关 键 词：deductive element consistency maximal contraction minimal subtraction basic element CLAUSE 

分 类 号：O153.2[理学—数学] TU528.01[理学—基础数学]