RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2022 Volume 34, Issue 2, Pages 32–42 (Mi dm1701)

Propagation criterion for monotone Boolean functions with least vector support set of 1 or 2 elements

G. A. Isaev

Lomonosov Moscow State University

Abstract: The propagation criterion for monotone Boolean functions with least vector support sets consisting of one or two vectors is studied. We obtain necessary and sufficient conditions for the validity of the propagation criterion for a vector in terms of the Hamming weights of vectors in least vector support set depending on whether these vectors share some nonzero components with the given vector. We find the cardinality of the set of vectors satisfying the propagation criterion for such functions.

Keywords: Boolean function, propagation criterion, monotone Boolean function, the least vector support set of a monotone Boolean function, Walsh spectrum.

UDC: 519.716.322+519.719.2

Received: 03.03.2022

DOI: 10.4213/dm1701


 English version:
Discrete Mathematics and Applications, 2024, 34:2, 61–69


© Steklov Math. Inst. of RAS, 2024