Research Article
Special Coverings of Sets and Boolean Functions
Issue:
Volume 10, Issue 3, September 2025
Pages:
84-97
Received:
13 June 2025
Accepted:
30 June 2025
Published:
23 July 2025
Abstract: 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.
Abstract: 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 adde...
Show More
