Abstract It is an important subject to find all possible reductions of a proposition set in the two-valued propositional logic. The current algorithms find single reduction one by one, and collect them to get all the possible reductions. In this paper, an algorithm for finding all the reductions at a time with the help of the formal concept theory is proposed, and the notions of intent waned values and waned values hypergraph are put forward. The proposed algorithm greatly decreases the operation times of finding all reductions.
[1] Yu Peng, Hou Zaien. Proposition Reduction Based on the Truth Degree of Proposition. Fuzzy Systems and Mathematics, 2010, 24(1): 66-70 (in Chinese) (于 鹏,候再恩.基于公式真度的公式集约简.模糊系统与数学, 2010, 24(1): 66-70) [2] Liberatore P. Redundancy in Logic II: 2CNF and Horn Propositional Formulae. Artificial Intelligence, 2008, 172(2/3): 265-299 [3] Liberatore P. Redundancy in Logic III: Non-Monotonic Reasoning. Artificial Intelligence, 2008, 172(11): 1317-1359 [4] Li Lifeng. Consistency and Reduction of Finite Proposition Set in n-Valued Propositional Logic L*n. Computer Engineering and Applications, 2009, 45(13): 59-61 (in Chinese) (李立峰.n值命题逻辑系统L*n中的有限命题集的相容性及约简.计算机工程与应用, 2009, 45 (13): 59-61) [5] Liberatore P. Redundancy in Logic I: CNF Prepositional Formulae. Artificial Intelligence, 2005, 163(2): 203-232 [6] Ren Yan, Ma Xiaojue, Wang Hongtao. Reduction of a Propositional Set and Its Roots in (ξ)*System. Fuzzy Systems and Mathematics, 2006, 20(2): 23-27 (in Chinese) (任 燕,马晓珏,王洪涛.(ξ)*命题集的约简及命题集的根.模糊系统与数学, 2006, 20(2): 23-27) [7] Li Lifeng, Zhang Dongxiao. The Application of Concept Lattice Theory in the Reduction of the Proposition Set in Two-Valued Propositional Logic. Acta Electronica Sinica, 2007, 35(8): 1538-1542 (in Chinese) (李立峰,张东晓.概念格在二值命题逻辑命题集约简中的应用.电子学报, 2007, 35(8): 1538-1542) [8] Li Lifeng, Zhang Jianke, Feng Feng. Reduction Theory of Finite Proposition Set in Lukasiewicz Propositional Logic. Computer Engineering and Applications, 2009, 45(7): 44-45, 51 (in Chinese) (李立峰,张建科,冯 锋.Lukasiewicz命题逻辑系统中有限命题集的约简理论.计算机工程与应用, 2009, 45(7): 44-45, 51) [9] Ganter B, Wille R. Formal Concept Analysis Mathematical Foundations. Secaucus, USA: Springer-Verlag, 1999 [10] Eiter T, Gottlob G. Identifying the Minimal Transversals of a Hypergraph and Related Problems. SIAM Journal on Computing, 1995, 24(6): 1278-1304 [11] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, USA: Freeman, 1990
2013, Vol. 26 
