|
This article is cited in 2 scientific papers (total in 2 papers)
On the weights of Boolean functions representable by $2$-CNF or $3$-CNF
S. P. Gorshkova, A. V. Tarasovb a Academy of Cryptography of the Russian Federation, Moscow
b Moscow State University of Information Technologies, Radioengineering and Electronics,
Moscow
Abstract:
Sets of possible values of weights of bijunctive Boolean functions ($2$-CNF) are found. For Boolean functions having all variables as essential ones we describe: sets of bijunctive functions with weight close (but not equal) to the maximal value and sets of functions of maximal weight represented as $3$-CNF. A hypothesis on the maximal weight of functions representable as $k$-CNF ($k \geqslant 4$) and having all variables as essential ones is formulated. Some sets of balanced Boolean functions representable as $k$-CNF are described.
Key words:
weight of Boolean function, bijunctive Boolean functions, $k$-CNF.
Received 11.V.2017
Citation:
S. P. Gorshkov, A. V. Tarasov, “On the weights of Boolean functions representable by $2$-CNF or $3$-CNF”, Mat. Vopr. Kriptogr., 9:1 (2018), 5–26
Linking options:
https://www.mathnet.ru/eng/mvk242https://doi.org/10.4213/mvk242 https://www.mathnet.ru/eng/mvk/v9/i1/p5
|
|