Sciact
  • EN
  • RU

О строении одного класса совершенных Π-разбиений 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 Рычков К.Л. 1
Affiliations
1 Sobolev Institute of Mathematics

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 РИНЦ
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
Citing:
DB Citing
Web of science 1
Scopus 1
Altmetrics: