Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.00008 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910898750226432 |
|---|---|
| author | Margaryan, Stepan |
| author_facet | Margaryan, Stepan |
| contents | We will study some important properties of Boolean functions based on newly introduced concepts called Special Decomposition of a Set and Special Covering of a Set. These concepts enable us to study important problems concerning Boolean functions represented in conjunctive normal form including the satisfiability problem. Studying the relationship between the Boolean satisfiability problem and the problem of existence of a special covering for set we show that these problems are polynomially equivalent. This means that the problem of existence of a special covering for a set is an NP complete problem. We prove an important theorem regarding the relationship between these problems. The Boolean function in conjunctive normal form is satisfiable if and only if there is a special covering for the set of clauses of this function. The purpose of the article is also to study some important properties of satisfiable Boolean functions using the concepts of special decomposition and special covering of a set. We introduce the concept of generation of satisfiable function by another satisfiable function by means of admissible changes in the clauses of the function. We will prove that 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 In addition, extending the rules of admissible changes we prove that arbitrary two satisfiable Boolean functions of n variables represented in conjunctive normal form with m clauses can be generated from each other. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00008 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Special Coverings of Sets and Boolean Functions Margaryan, Stepan Computational Complexity We will study some important properties of Boolean functions based on newly introduced concepts called Special Decomposition of a Set and Special Covering of a Set. These concepts enable us to study important problems concerning Boolean functions represented in conjunctive normal form including the satisfiability problem. Studying the relationship between the Boolean satisfiability problem and the problem of existence of a special covering for set we show that these problems are polynomially equivalent. This means that the problem of existence of a special covering for a set is an NP complete problem. We prove an important theorem regarding the relationship between these problems. The Boolean function in conjunctive normal form is satisfiable if and only if there is a special covering for the set of clauses of this function. The purpose of the article is also to study some important properties of satisfiable Boolean functions using the concepts of special decomposition and special covering of a set. We introduce the concept of generation of satisfiable function by another satisfiable function by means of admissible changes in the clauses of the function. We will prove that 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 In addition, extending the rules of admissible changes we prove that arbitrary two satisfiable Boolean functions of n variables represented in conjunctive normal form with m clauses can be generated from each other. |
| title | Special Coverings of Sets and Boolean Functions |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2501.00008 |