Эта публикация цитируется в
2 статьях
Представления нормализованных формул
К. Л. Рычков Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 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