Discrete mathematics and mathematical cybernetics

On the characteristic property of one class of normalized formulas calculating linear Boolean functions

K. L. Rychkov

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

Abstract: By means of a modification of the method proposed by S. V. Yablonsky for constructing an economical (hypothetically minimal) normalized formula ($\Pi$-circuit) that calculates a given linear Boolean function, a whole class of similar formulas was constructed – the class of so-called optimal perfect normalized formulas. Presumably it is the class of all minimal normalized formulas that compute this function. To prove this conjecture, we consider extending this class to the class of perfect normalized formulas that also compute the same function. It is established that a normalized formula is perfect if and only if it has a perfect representation on the own rectangle of the specified function.

Keywords: Boolean functions, $\pi$-circuits, normalized formulas, lower bounds on complexity, formula representations, $\Pi$-partitions.

UDC: 519.714

MSC: 03D15

Received August 27, 2024, published December 31, 2024

DOI: 10.33048/semi.2024.20.097