О строении одного класса совершенных Π-разбиений Full article
Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
---|---|---|---|
Output data | Year: 2023, Volume: 20, Number: 2, Pages: 1499-1518 Pages count : 20 DOI: 10.33048/semi.2023.20.093 | ||
Tags | boolean functions, π-schemes, normalized formulas, lower bounds on the complexity, formula representation | ||
Authors |
|
||
Affiliations |
|
Funding (1)
1 | Sobolev Institute of Mathematics | FWNF-2022-0018 |
Abstract:
Theconcept of Π-partition is an analogue of the concept of normalized formula (a formula in the basis {∨,∧,− } in which negations are possible only over variables) and concept of Π-schema, just as these last two concepts are analogues of each other. At its core, a Π-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 Π-partitions representing these formulas has been clarified.
Cite:
Рычков К.Л.
О строении одного класса совершенных Π-разбиений
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2023. Т.20. №2. С.1499-1518. DOI: 10.33048/semi.2023.20.093 WOS Scopus РИНЦ
О строении одного класса совершенных Π-разбиений
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2023. Т.20. №2. С.1499-1518. DOI: 10.33048/semi.2023.20.093 WOS Scopus РИНЦ
Dates:
Submitted: | Nov 26, 2023 |
Published print: | Dec 22, 2023 |
Published online: | Dec 22, 2023 |
Identifiers:
Web of science: | WOS:001164415800015 |
Scopus: | 2-s2.0-85188425662 |
Elibrary: | 82134677 |