Based on the common properties of logic formulas:equivalence and satisfiability,the concept of variable minimal formulas with property preservation is introduced.A formula is variable minimal if the resulting sub-form...Based on the common properties of logic formulas:equivalence and satisfiability,the concept of variable minimal formulas with property preservation is introduced.A formula is variable minimal if the resulting sub-formulas with any variable omission will change the given property.Some theoretical results of two classes:variable minimal equivalence(VME) and variable minimal satisfiability(VMS) are studied.We prove that VME is NP-complete,and VMS is in DP and coNP-hard.展开更多
基金Supported by the National Natural Science Foundation of China (60803007, 90818027, 10871091 and 60721002)the National High Technology Re-search and Development Program of China (2009AA01Z147)the National Basic Research Program of China (2008CB320703)
文摘Based on the common properties of logic formulas:equivalence and satisfiability,the concept of variable minimal formulas with property preservation is introduced.A formula is variable minimal if the resulting sub-formulas with any variable omission will change the given property.Some theoretical results of two classes:variable minimal equivalence(VME) and variable minimal satisfiability(VMS) are studied.We prove that VME is NP-complete,and VMS is in DP and coNP-hard.