A heuristic method for bi-decomposition of partial Boolean functions
The problem of decomposition of a Boolean function is to represent a given Boolean function in the form of a superposition of some Boolean functions whose number of arguments are less than the number of given function. The bi-decomposition represents a given function as a logic algebra operation, wh...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2020-09-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1072 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849240260130635776 |
|---|---|
| author | Yu. V. Pottosin |
| author_facet | Yu. V. Pottosin |
| author_sort | Yu. V. Pottosin |
| collection | DOAJ |
| description | The problem of decomposition of a Boolean function is to represent a given Boolean function in the form of a superposition of some Boolean functions whose number of arguments are less than the number of given function. The bi-decomposition represents a given function as a logic algebra operation, which is also given, over two Boolean functions. The task is reduced to specification of those two functions. A method for bi-decomposition of incompletely specified (partial) Boolean function is suggested. The given Boolean function is specified by two sets, one of which is the part of the Boolean space of the arguments of the function where its value is 1, and the other set is the part of the space where the function has the value 0. The complete graph of orthogonality of Boolean vectors that constitute the definitional domain of the given function is considered. In the graph, the edges are picked out, any of which has its ends corresponding the elements of Boolean space where the given function has different values. The problem of bi-decomposition is reduced to the problem of a weighted two-block covering the set of picked out edges of considered graph by its complete bipartite subgraphs (bicliques). Every biclique is assigned with a disjunctive normal form (DNF) in definite way. The weight of a biclique is a pair of certain parameters of assigned DNF. According to each biclique of obtained cover, a Boolean function is constructed whose arguments are the variables from the term of minimal rank on the DNF. A technique for constructing the mentioned cover for two kinds of output function is described. |
| format | Article |
| id | doaj-art-df4452c32e144e329de5a0a19ff3f6c0 |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2020-09-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-df4452c32e144e329de5a0a19ff3f6c02025-08-20T04:00:40ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012020-09-01173445310.37661/1816-0301-2020-17-3-44-53933A heuristic method for bi-decomposition of partial Boolean functionsYu. V. Pottosin0The United Institute of Informatics Problems of the National Academy of Sciences of BelarusThe problem of decomposition of a Boolean function is to represent a given Boolean function in the form of a superposition of some Boolean functions whose number of arguments are less than the number of given function. The bi-decomposition represents a given function as a logic algebra operation, which is also given, over two Boolean functions. The task is reduced to specification of those two functions. A method for bi-decomposition of incompletely specified (partial) Boolean function is suggested. The given Boolean function is specified by two sets, one of which is the part of the Boolean space of the arguments of the function where its value is 1, and the other set is the part of the space where the function has the value 0. The complete graph of orthogonality of Boolean vectors that constitute the definitional domain of the given function is considered. In the graph, the edges are picked out, any of which has its ends corresponding the elements of Boolean space where the given function has different values. The problem of bi-decomposition is reduced to the problem of a weighted two-block covering the set of picked out edges of considered graph by its complete bipartite subgraphs (bicliques). Every biclique is assigned with a disjunctive normal form (DNF) in definite way. The weight of a biclique is a pair of certain parameters of assigned DNF. According to each biclique of obtained cover, a Boolean function is constructed whose arguments are the variables from the term of minimal rank on the DNF. A technique for constructing the mentioned cover for two kinds of output function is described.https://inf.grid.by/jour/article/view/1072partial boolean functionboolean function bi-decompositionsuperposition of functionslogic algebra operationscovering problemcomplete bipartite subgraphheuristic method |
| spellingShingle | Yu. V. Pottosin A heuristic method for bi-decomposition of partial Boolean functions Informatika partial boolean function boolean function bi-decomposition superposition of functions logic algebra operations covering problem complete bipartite subgraph heuristic method |
| title | A heuristic method for bi-decomposition of partial Boolean functions |
| title_full | A heuristic method for bi-decomposition of partial Boolean functions |
| title_fullStr | A heuristic method for bi-decomposition of partial Boolean functions |
| title_full_unstemmed | A heuristic method for bi-decomposition of partial Boolean functions |
| title_short | A heuristic method for bi-decomposition of partial Boolean functions |
| title_sort | heuristic method for bi decomposition of partial boolean functions |
| topic | partial boolean function boolean function bi-decomposition superposition of functions logic algebra operations covering problem complete bipartite subgraph heuristic method |
| url | https://inf.grid.by/jour/article/view/1072 |
| work_keys_str_mv | AT yuvpottosin aheuristicmethodforbidecompositionofpartialbooleanfunctions AT yuvpottosin heuristicmethodforbidecompositionofpartialbooleanfunctions |