Representations of normalized formulas | Sciact - Система учета научной деятельности ИМ СО РАН

Representations of normalized formulas Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2022, Том: 16, Номер: 4, Страницы: 760–775 Страниц : DOI: 10.1134/S1990478922040160

Ключевые слова

Boolean function, normalized formula, minimal formula, representation of a formula, П-scheme, П-partition, lower bound for the complexity

Авторы

Rychkov K.L ¹

Организации

1	Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0017

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

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

Рычков К.Л.
Представления нормализованных формул
Дискретный анализ и исследование операций. 2022. Т.29. №4. С.77-103. DOI: 10.33048/daio.2022.29.751 РИНЦ

Поступила в редакцию:	26 авг. 2022 г.
Принята к публикации:	31 авг. 2022 г.
Опубликована в печати:	22 нояб. 2022 г.
Опубликована online:	22 нояб. 2022 г.

Scopus:	2-s2.0-85150184500
РИНЦ:	59070346
OpenAlex:	W4323344517

Пока нет цитирований