RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2022, том 29, выпуск 4, страницы 77–103 (Mi da1310)

Эта публикация цитируется в 1 статье

Представления нормализованных формул

К. Л. Рычков

Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

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

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

УДК: 519.714

Статья поступила: 26.08.2022
Переработанный вариант: 26.08.2022
Принята к публикации: 31.08.2022

DOI: 10.33048/daio.2022.29.751



Реферативные базы данных:


© МИАН, 2024