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

Дискрет. матем., 1998, том 10, выпуск 1, страницы 28–45 (Mi dm417)

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

Операторы над отношениями, сохраняющие транзитивность

Л. А. Шоломов


Аннотация: Пусть $\mathcal{T}=\mathcal{T}(A)$ — класс всех транзитивных отношений на конечном множестве $A$. Оператор $r=F(r_1,\ldots,r_n)$ на множестве отношений сохраняет транзитивность, если
$$ r_1,\ldots,r_n\in\mathcal T\Rightarrow r\in\mathcal{T}. $$
Введем операторы $\tau_n^{(u)}(r_1,\ldots,r_n)$, $u=0,1$, $n\geq0$, положив $\tau_0^{(0)}=\emptyset$, $\tau_0^{(1)}=A^2$,
$$ \tau_n^{(u)}=r_1\cap(\overline{(r_1^{-1})}\cup\tau_{n-1}^{(u)}(r_2,\ldots,r_n)),\qquad n\geq 1. $$
Назовем $\tau$-оператором всякий оператор, полученный из $\tau_n^{(u)}$ заменой некоторых $r_i$, $1\leq i\leq n$, на $r_i^{-1}$. Показано, что оператор $F$, выразимый через теоретико-множественные операции и обращение отношений, сохраняет транзитивность тогда и только тогда, когда оператор $F$ представим в виде пересечения $\tau$-операторов.

УДК: 519.816

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

DOI: 10.4213/dm417


 Англоязычная версия: Discrete Mathematics and Applications, 1998, 8:2, 183–200

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


© МИАН, 2024