RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2010, том 22, выпуск 4, страницы 83–103 (Mi dm1121)

Проблема выразимости в решетке с замыканием

Н. Г. Парватов


Аннотация: В статье рассматривается проблема выразимости элемента полной решетки с операцией замыкания. Устанавливаются условия, при которых данная проблема имеет решение в виде конечной нижней окрестности. Отдельно рассматривается наиболее важный для приложения случай полной решетки $\mathscr B(P)$ упорядоченных включением подмножеств множества $P$. Показывается, что существование конечной нижней окрестности для каждого порожденного замкнутого элемента этой решетки влечет финитарность операции замыкания в ней. В случае решетки $\mathscr B(P)$ с финитарным замыканием устанавливаются конструктивные достаточные условия существования для ее элемента конечной нижней окрестности. Тем самым обобщается теорема А. В. Кузнецова о функциональной полноте. Отдельно рассматривается случай замыкания Галуа, индуцированного некоторым соответствием Галуа между решетками подмножеств. В этом случае устанавливаются необходимые и достаточные условия существования конечной нижней окрестности элемента решетки. Этим наряду с теоремой А. В. Кузнецова обобщается и теорема С. В. Яблонского о предикатно описываемых классах функций конечнозначной логики. Попутно с проблемами выразимости в статье рассматривается возможность задания замкнутых элементов решетки $\mathscr B(P)$, в частности, элементов нижних окрестностей, конечными запрещающими множествами при некотором предупорядочении множества $P$, а в случае замыкания Галуа – конечными описаниями. Доказанные теоремы сопровождаются примерами их использования.

УДК: 519.7

Статья поступила: 18.11.2008

DOI: 10.4213/dm1121


 Англоязычная версия: Discrete Mathematics and Applications, 2010, 20:5-6, 567–589

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


© МИАН, 2024