Sciact
  • EN
  • RU

Representations of normalized formulas Full article

Journal Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797
Output data Year: 2022, Volume: 16, Number: 4, Pages: 760–775 Pages count : DOI: 10.1134/S1990478922040160
Tags Boolean function, normalized formula, minimal formula, representation of a formula, П-scheme, П-partition, lower bound for the complexity
Authors Rychkov K.L 1
Affiliations
1 Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia

Funding (1)

1 Sobolev Institute of Mathematics FWNF-2022-0017

Abstract: A class of objects called Π-partitions is defined. In a certain well-defined sense, these objects are the equivalents of formulas in a basis consisting of disjunction, conjunction, and negation in which negations are possible only over variables (normalized formulas). Π-partitions are viewed as representations of formulas, just as Π-schemes can be viewed as equivalents and graphical representations of the same formulas. Some theory of such representations is developed, which is essentially a mathematical apparatus focused on describing a class of minimal normalized formulas implementing linear Boolean functions. REMOVE— Π-scheme, Π-partition—REMOVE
Cite: Rychkov K.L.
Representations of normalized formulas
Journal of Applied and Industrial Mathematics. 2022. V.16. N4. P.760–775. DOI: 10.1134/S1990478922040160 Scopus РИНЦ OpenAlex
Original: Рычков К.Л.
Представления нормализованных формул
Дискретный анализ и исследование операций. 2022. Т.29. №4. С.77-103. DOI: 10.33048/daio.2022.29.751 РИНЦ
Dates:
Submitted: Aug 26, 2022
Accepted: Aug 31, 2022
Published print: Nov 22, 2022
Published online: Nov 22, 2022
Identifiers:
Scopus: 2-s2.0-85150184500
Elibrary: 59070346
OpenAlex: W4323344517
Citing: Пока нет цитирований
Altmetrics: