Том 29, номер 4, 2022 г., Стр. 77-103

УДК 519.714
Рычков К. Л.
Представления нормализованных формул

Аннотация:
Определён класс названных $\Pi$-разбиениями объектов, которые в некотором вполне определённом смысле являются эквивалентами формул в базисе, состоящем из дизъюнкции, конъюнкции и отрицания, в которых отрицания возможны только над переменными (нормализованные формулы). $\Pi$-разбиения рассматриваются в качестве представлений этих формул подобно тому, как эквивалентами и графическими изображениями тех же самых формул можно считать $\Pi$-схемы. Разработана некоторая теория таких представлений, которая по сути является математическим аппаратом, ориентированным на описание класса реализующих линейные булевы функции минимальных нормализованных формул.
Библиогр. 18.

Ключевые слова: булева функция, нормализованная формула, минимальная формула, представление формулы, $\Pi$-схема, $\Pi$-разбиение, нижняя оценка сложности.

DOI: 10.33048/daio.2022.29.751

Рычков Константин Леонидович ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: rychkov@math.nsc.ru

Статья поступила 26 августа 2022 г.
После доработки — 26 августа 2022 г.
Принята к публикации 31 августа 2022 г.

Литература

[1] Храпченко В. М. О сложности реализации линейной функции в классе $\Pi$-схем // Мат. заметки. 1971. Т. 9, № 1. С. 35–40.

[2] Яблонский С. В. Реализация линейной функции в классе $\Pi$-схем // Докл. АН СССР. 1954. Т. 94, № 5. С. 805–806.

[3] Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сиб. журн. исслед. операций. 1994. Т. 1, № 4. С. 33–52.

[4] Черухин Д. Ю. К вопросу о логическом представлении счётчика чётности // Неформальная наука. 2009. № 2. С. 14–23.

[5] Рычков К. Л. О нижних оценках формульной сложности линейной булевой функции // Сиб. электрон. мат. изв. 2014. Т. 11. С. 165–184.

[6] Рычков К. Л. О сложности реализации линейной булевой функции в классе $\pi$-схем // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 3. С. 36–94.

[7] Рычков К. Л. О минимальных $\pi$-схемах для линейных булевых функций // Методы дискретного анализа в синтезе схем булевых функций. Вып. 51. Новосибирск: Изд-во Ин-та математики, 1991. С. 84–104.

[8] Рычков К. Л. Достаточные условия локальной бесповторности минимальных $\pi$-схем, реализующих линейные булевы функции // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 5. С. 71–85.

[9] Рычков К. Л. О совершенности минимальных правильных разбиений множества рёбер $n$-мерного куба // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 4. С. 74–107.

[10] Храпченко В. М. Об одном методе получения нижних оценок сложности $\Pi$-схем // Мат. заметки. 1971. Т. 10, № 1. С. 83–92.

[11] Субботовская Б. А. О реализации линейных функций формулами в базисе $\lor , \land , -$ // Докл. АН СССР. 1961. Т. 136, № 3. С. 553–555.

[12] Храпченко В. М. Упрощённое доказательство одной нижней оценки сложности // Дискрет. математика. 2013. Т. 25, № 2. С. 82–84.

[13] Августинович С. В., Васильев Ю. Л., Рычков К. Л. Формульная сложность тернарной линейной функции // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 3. С. 3–12.

[14] Васильев Ю. Л., Рычков К. Л. Нижняя оценка формульной сложности тернарной линейной функции // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 4. С. 15–26.

[15] Сергеев И. С. Формульная сложность линейной функции в $k$-арном базисе // Мат. заметки. 2021. Т. 109, № 3. С. 419–435.

[16] Razborov A. Applications of matrix methods to the theory of lower bounds in computational complexity // Combinatorica. 1990. V. 10, No. 1. P. 81–93.

[17] Karchmer M., Wigderson A. Monotone circuits for connectivity require super-logarithmics depth // SIAM J. Discrete Math. 1990. V. 3, No. 2. P. 255–265.

[18] Håstad J. The shrinkage exponent is 2 // SIAM J. Comput. 1998. V. 27. P. 48–64.