|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Представления нормализованных формул
К. Л. Рычков Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Определён класс названных $\Pi$-разбиениями объектов, которые в некотором вполне определённом смысле являются эквивалентами формул в базисе, состоящем из дизъюнкции, конъюнкции и отрицания, в которых отрицания возможны только над переменными (нормализованные формулы). $\Pi$-разбиения рассматриваются в качестве представлений этих формул подобно тому, как эквивалентами и графическими изображениями тех же самых формул можно считать $\Pi$-схемы. Разработана некоторая теория таких представлений, которая по сути является математическим аппаратом, ориентированным на описание класса реализующих линейные булевы функции минимальных нормализованных формул. Библиогр. 18.
Ключевые слова:
булева функция, нормализованная формула, минимальная формула, представление формулы, $\Pi$-схема, $\Pi$-разбиение, нижняя оценка сложности.
Статья поступила: 26.08.2022 Переработанный вариант: 26.08.2022 Принята к публикации: 31.08.2022
Образец цитирования:
К. Л. Рычков, “Представления нормализованных формул”, Дискретн. анализ и исслед. опер., 29:4 (2022), 77–103
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1310 https://www.mathnet.ru/rus/da/v29/i4/p77
|
Статистика просмотров: |
Страница аннотации: | 82 | PDF полного текста: | 18 | Список литературы: | 23 | Первая страница: | 4 |
|