|
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.
Received November 26, 2023, published December 22, 2023
Citation:
K. L. Rychkov, “On the structure of one class of perfect $\Pi$-partitions”, Sib. Èlektron. Mat. Izv., 20:2 (2023), 1499–1518
Linking options:
https://www.mathnet.ru/eng/semr1656 https://www.mathnet.ru/eng/semr/v20/i2/p1499
|
Statistics & downloads: |
Abstract page: | 32 | Full-text PDF : | 17 | References: | 11 |
|