Об одном свойстве минимальных формул, реализующих линейные булевы функции от 5, 6 и 7 переменных | Sciact - Система учета научной деятельности ИМ СО РАН

Об одном свойстве минимальных формул, реализующих линейные булевы функции от 5, 6 и 7 переменных Научная публикация

Журнал

Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304

Вых. Данные

Год: 2025, Том: 22, Номер: 2, Страницы: 1687–1716 Страниц : DOI: 10.33048/semi.2025.22.103

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

boolean functions, π-circuits, normalized formulas, lower bounds on complexity, formula representations, Π-partitions.

Авторы

Рычков К.Л. ¹

Организации

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

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

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

FWNF-2022-0017

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.

Рычков К.Л.
Об одном свойстве минимальных формул, реализующих линейные булевы функции от 5, 6 и 7 переменных
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1687–1716. DOI: 10.33048/semi.2025.22.103 Scopus

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

Scopus:

2-s2.0-105027540776

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