Special Coverings of Sets and Boolean Functions

We will study some properties of Boolean functions based on newly introduced concepts called “Special Decomposition of a Set’’ and “Special Covering of a Set’’. The introduced concepts easily solve the question of how changes in clauses affect the resulting value of a function. They easily determine a clause as well as the literals that can be added to or removed from the clause so that the satisfiability of the function is preserved. The concept of generating a satisfiable function by another satisfiable function through admissible changes in the function's clauses is also introduced. If the generation of a function by another function is defined as a binary relation, then the set of satisfiable functions of n variables, represented in conjunctive normal form with m clauses is partitioned to equivalence classes. Moreover, we prove that any two satisfiable Boolean functions of n variables, represented in conjunctive normal form with m clauses, can be generated from each other in polynomial time.