This article is cited in 4 papers

Computational Methods in Discrete Mathematics

A method for bi-decomposition of partial Boolean functions

Yu. V. Pottosin

United Institute of Informatics Problems National Academy of Sciences of Belarus, Minsk, Belarus

Abstract: A method for bi-decomposition of incompletely specified (partial) Boolean functions is suggested. The problem of bi-decomposition is reduced to the problem of two-block weighted covering a set of edges of a graph of rows orthogonality of a ternary or binary matrix that specify a given function, by complete bipartite subgraphs (bicliques). Each biclique is assigned in a certain way with a set of arguments of the given function, and the weight of a biclique is the cardinality of this set. According to each of bicliques, a Boolean function is constructed whose arguments are the variables from the set, which is assigned to the biclique. The obtained functions form a solution of the bi-decomposition problem.

Keywords: partial Boolean function, bi-decomposition, cover problem, complete bipartite subgraph.

UDC: 519.7

Language: English

DOI: 10.17223/20710410/47/9

Bibliographic databases:

•