Об одном свойстве минимальных формул, реализующих линейные булевы функции от 5, 6 и 7 переменных Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2025, Volume: 22, Number: 2, Pages: 1687–1716 Pages count : DOI: 10.33048/semi.2025.22.103 | ||
| Tags | boolean functions, π-circuits, normalized formulas, lower bounds on complexity, formula representations, Π-partitions. | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
Abstract:
We consider formulas in a basis consisting of disjunction, conjunction, and negation. It is established that in each minimal
(having the smallest possible number of occurrences of variables) formula that calculates a linear Boolean function depending on 5,
6 or 7 variables, at least one of the variables is included at least 8 times. The result focuses on the description of classes of minimal
formulas for these functions and is an important intermediate step in this description. But it also has an independent meaning, since
it actually represents another way (perhaps the most simple and transparent) to obtain accurate lower estimates of the formula complexity of the specified functions.
Cite:
Рычков К.Л.
Об одном свойстве минимальных формул, реализующих линейные булевы функции от 5, 6 и 7 переменных
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1687–1716. DOI: 10.33048/semi.2025.22.103 Scopus
Об одном свойстве минимальных формул, реализующих линейные булевы функции от 5, 6 и 7 переменных
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1687–1716. DOI: 10.33048/semi.2025.22.103 Scopus
Dates:
| Submitted: | Aug 1, 2025 |
| Published print: | Dec 31, 2025 |
| Published online: | Dec 31, 2025 |
Identifiers:
| Scopus: | 2-s2.0-105027540776 |
Citing:
Пока нет цитирований