RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2023 Volume 20, Issue 2, Pages 1499–1518 (Mi semr1656)

Discrete mathematics and mathematical cybernetics

On the structure of one class of perfect $\Pi$-partitions

K. L. Rychkov

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: The concept of $\Pi$-partition is an analogue of the concept of normalized formula (a formula in the basis $\{\vee,\wedge,^-\}$ in which negations are possible only over variables) and concept of $\Pi$-schema, just as these last two concepts are analogues of each other. At its core, a $\Pi$-partition is a kind of "imprint" of a formula in the Boolean function calculated by this formula and is considered as a representation of this formula. In order to describe the class of minimal normalized formulas that calculate linear Boolean functions, the structure of the $\Pi$-partitions representing these formulas has been clarified.

Keywords: boolean functions, $\pi$-schemes, normalized formulas, lower bounds on the complexity, formula representation.

UDC: 519.714

MSC: 03D15

Received November 26, 2023, published December 22, 2023

DOI: doi.org/10.33048/semi.2023.20.093



© Steklov Math. Inst. of RAS, 2024