On the number of solutions of systems of Boolean equations consisting of rank $2$ clauses and arising in the method of consequences for solving Boolean equations systems
Abstract:
The class of bijunctive Boolean functions, that is, functions representable as 2-CNF, has been considered. An algorithm for reducing the problem of calculating the weight of an arbitrary function specified in 2-CNF form to the problem of calculating the weight of a monotone bijunctive function has been proposed. The weight of a monotone bijunctive function has been estimated through the number of vertices in a minimal vertex cover and through the number of vertices in a maximal complete subgraph (clique) of an undirected graph corresponding to the function. A series of results have been obtained for the spectrum of weights in the class of bijunctive Boolean functions.
Keywords:bijunctive function, 2-CNF, weight of Boolean function, resolution method for solving systems of Boolean equations, minimum vertex cover, complete subgraph, clique.
Fulltext:
PDF file (573 kB)