RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2018 Volume 9, Issue 1, Pages 5–26 (Mi mvk242)

This article is cited 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.

UDC: 519.716.5

Received 11.V.2017

DOI: 10.4213/mvk242



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024