RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2020 Number 4, Pages 51–53 (Mi vmumm4341)

Short notes

On irreduceability of Boolean functions with respect to commutative associative operation

G. V. Safonov, G. V. Bokov, V. B. Kudryavtsev

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The paper is focused on decomposition of Boolean functions on the form $f_1\circ\ldots\circ f_m$, where $\circ$ is a commutative associative operation and $f_1,\ldots,f_m$ are Boolean functions with fewer arguments. For each commutative associative operation, we define necessary and sufficient conditions for the absence of such a decomposition and find the related complexity class.

Key words: Boolean functions, commutative associative operations, decomposition, complexity.

UDC: 510.52

Received: 11.09.2019


 English version:
Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2020, 75:4, 169–171

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025