%\input amsppt.sty
%\documentstyle{amsppt}
%\nopagenumbers
\magnification=\magstep2
%\pagewidth{17 true cm}
%\vcorrection{-.5 true cm}
%\hcorrection{-.5 true cm}
\TagsOnRight
\pretitle{ \centerline{\bf { Научные труды ИвГУ. Математика. Вып.~2}}
\centerline{\bf {Иваново, 1999}}

\noindent --------------------------------------------------------------------------------------------------
\vskip .1 cm
УДК 512.8
\vskip .3 cm
\centerline {\bf Ю.~Н.~Евдокимов }
\vskip .3 cm
%\leftheadtext{\it Ю.~Н.~Евдокимов }
%\rightheadtext{\it ИНДУКТИВНЫЕ АЛГЕБРЫ ДЕ МОРГАНА }
\topmatter
%\author Ю.Н.Евдокимов
%\endauthor
%\vskip .3cm

\centerline{ИНДУКТИВНЫЕ АЛГЕБРЫ ДЕ МОРГАНА И}
\centerline{МОДЕЛИ УСЛОВНОЙ ЦЕЛЕВОЙ ДОСТИЖИМОСТИ}

\abstract \nofrills
\vskip .3 cm\noindent
Предлагается вариант абстрактно-алгебраической модели теории
систем, ориентированной как  на описание задач анализа работоспособности,
живучести и эффективности, так и на описание задач синтеза систем,
обладающих некоторыми из перечисленных качеств.

\endabstract
\endtopmatter
\document
\pageno=1
\vskip .5 cm

     Проблемы проектирования надёжных сетевых
информационно-вы\-числительных комплексов приводят к необходимости
разработки математических
моделей процессов исследования  и  создания  структурно-избыточных
систем, являющихся оптимальными относительно фиксированного набора
критериев сложности. В частном случае перечисленные
вопросы сводятся к постановке и решению задач  исследования  связей
во взвешенных графах при наличии в них  возможности  обрыва  цепей,
соединяющих между собой отдельные непересекающиеся  множества  вершин. Ниже
с опоpой на результаты Г.~Биркгофа  [2]  и  М.~И.~Нечепуренко [5],
относящиеся
к  вопросам  теоретико-решёточной  формализации задач анализа и синтеза систем,
наделённых  свойством  живучести, предлагается новое описание такого рода
задач,  представленное на более высоком уровне  абстракции  средствами  теории
квазиметрических алгебр де Моргана.

     Для сокращения записи отдельных выражений  воспользуемся  следующими
обозначениями.  Пусть $(S;\leqslant )$  --   частично   упорядоченное
множество и $R$  --  бинарное  отношение  между  его  элементами.  Для
произвольных $x,y \in S$  и $X,Y \subseteq S$  положим:  $min(X)$  --
 множество
минимальных  элементов   множества   $X$;
$$R^{-1} \rightleftharpoons \{ (b,a):R(a,b) \};
%\break
\ \ x^ {\nabla } \rightleftharpoons \{y \in S : y \leq x \};$$
$$R \langle x \rangle \rightleftharpoons \{y \in S : R(x,y) \};
%\break
\ \ X \vee Y \rightleftharpoons \{x \vee y :x \in X \and y \in Y \};$$
$$\square (X) \rightleftharpoons \{y \in S:(\exists x \in X)(x \leqslant y) \}.$$
Термин ``алгебра де  Моргана"   считается
общепринятым; его определение можно  найти,  например,  в  работе
[6]. В качестве языка неформального представления алгоритмов вместо
Упрощённого Алгола [1, с. 48 - 53] предполагается  использование
Упрощённого Паскаля (русскоязычный аналог -- алгоритмический  псевдокод
академика А.~П.~Ершова).  При  этом  устройство  ``исполнителя"
алгоритмов -- условной Паскаль-машины считается интуитивно очевидным
(Паскаль-машина -- Универсальный Исполнитель алгоритмов,  записанных
на Упрощённом Паскале).

     Алгебру де Моргана  $(S;\wedge ,\vee,',\bold O,\bold I)$  назовем
индуктивной,  если
относительно частичного порядка  $``a \leqslant b$, при $a \wedge b=a"$
она удовлетворяет
условию обрыва убывающих цепей ( индуктивности);  при  этом  высоту
$h(x)$  произвольного  элемента  $x$  индуктивной  алгебры  де  Моргана
определим по индукции: $h(\bold O)=0$, и если $h(y)=k \in \bold Z$ и $x$
 покрывает  $y$, то   $h(x) = k+1$.

     Пусть $x \in S$  и  $p$ - атом  индуктивной решётки $S$.  Положим
$x \rightleftharpoons p^k$ ,
если  $h(x)=k \in \bold N$  и  $x^{\nabla} \cap min(S \setminus \{\bold O \}) = \{p\}
\ \ (p^0 \rightleftharpoons \bold O)$.

     Типологическим классификатором нa индуктивной    алгебрe    де
Моргана $S$ назовём бинарное отношение $R$ между  элементами решётки $S$
и  её  атомами  из  $A \rightleftharpoons min(S \setminus \{ \bold O \})$,
если  оно
обладает   следующими свойствами:

1) $R \langle \bold O \rangle = \emptyset \text{ и } R\langle \bold I \rangle =A;$

2) для всех  $a \in A$ справедливо $R(a,a)$;

3) для произвольных $x$ и $y$, если $x \leq y$, то
$R\langle x \rangle \subseteq R\langle y \rangle.$

\noindent
Упорядоченную тройку $(S;A;R)$ назовём типологическим пространст\-вом.

Для произвольного типологического пространства $(S;A;R)$  положим:
$\Lambda = P(A) \rightleftharpoons   \{X : X \subseteq A \},
 T = \{\tau \in \bold Z : 0 \leqslant \tau \leqslant h(\bold I) \},
V$  -  множество
оценок на решётке $S$ [2, с.301] и $\Omega = P(V)$.   Элементы   множества
 $ \bold F  =  \Lambda \cup (\Lambda \times T) \cup
 (\Lambda \times T \times \Omega)$
назовём   типами   условной   целевой
достижимости типологического пространства $(S;A;R)$.

     Пусть $\lambda \in \Lambda , \tau \in T, \omega \in \Omega$ и
$x,y \in S$.
Введём новые обозначения:
$$ S_{\lambda} \rightleftharpoons  \cap \{ R^{-1} \langle a \rangle :
a \in \lambda \},$$
$$S_{\langle \lambda,\tau \rangle} \rightleftharpoons
\{s \in S_{\lambda}:(\forall x)(x \leqslant s \and h(s)-h(x)=
\tau \to x \in S_{ \lambda })\},$$
$$
x \prec y (mod( \omega )) \text{, если } (\forall v \in \omega)(v(x)
\leqslant v(y))
\and (\exists v \in \omega)(v(x) \neq v(y)),
$$
$$x \sim y (mod(\omega )) \text{, если } (\forall v \in \omega )
(v(x)=v(y)),
$$
$$x \preceq y (mod(\omega )) \text{, если } (x \prec y (mod(\omega ))) \text
{ или }
(x \sim y (mod(\omega ))),$$
$$S_{\langle \lambda ,\tau, \omega \rangle} \rightleftharpoons
min_{\omega }(S_{\langle \lambda ,\tau \rangle }) \equiv
 \{ s \in S_{\langle \lambda ,\tau \rangle }):
(\forall x \in S_{\langle \lambda,\tau \rangle }) \neg (x \prec s(mod(w)))\}.$$

     Пусть $f \in \bold F$ и $s \in S$. Будем говорить, что элемент $s$
 типологического
пространства $(S;A;R)$ обеспечивает тип целевой достижимости $f$,  если
$s \in S_f$. При этом с теоретико-системных позиций различные виды  типов
 целевой достижимости будем интерпретировать так:

1) если $f= \lambda \in \Lambda $, то $f$ назовём типом ``работоспособности"
($s$  обеспечивает тип работоспособности $\lambda $, если $s \in S_{\lambda});

2) если $f= \langle \lambda ,\tau \rangle \in \Lambda \times T$, то $f$ назовём типом
``живучести" ($s$ обеспечивает
тип живучести $\langle \lambda ,\tau \rangle$, если
$s \in S_{\langle \lambda,\tau \rangle }$, т.е.  $s$  сохраняет
работоспособность типа $\lambda $ при отказах типа $\tau $);

3) если $f=\langle \lambda ,\tau ,\omega \rangle \in \Lambda \times T \times \Omega$,
то  $f$  назовём  типом  ``эффективности"  ($s$
обеспечивает эффективность типа $\langle \lambda ,\tau,\omega \rangle$, если
$s \in S_{\langle \lambda ,\tau, \omega \rangle}$, т.е. $s$
 является оптимальным элементом относительно  множества  оценок
$\omega \in \Omega $
среди всех элементов из $S_{\langle \lambda ,\tau \rangle}$, обладающих
свойством живучести типа ${\langle \lambda ,\tau \rangle}$) .

При  этом  отношение  квазипорядка $\preceq (mod(\omega ))$  будем называть
отношением  предпочтения,   отношение   строгого   частичного   порядка
\break
$\prec(mod(\omega ))$  - отношением строгого предпочтения, а отношение
эквивалентности  $\sim (mod(\omega ))$ - отношением безразличия.

В  рамках  предложенного   формализма   практический   интерес
представляет формальная запись и решение следующих задач.

    {\bf Задача анализа.} Построить алгоритм, который для заданных $s \in S$ и
$f \in \bold F$ эффективно распознаёт, обладает ли  элемент  $s$
типологического
пространства $(S;A;R)$ типом целевой достижимости $f$ или нет.

    {\bf Задача синтеза.} Построить алгоритм, который по заданному  типу
целевой  достижимости  $f \in \bold F$  эффективно  перечисляет  все
элементы множества $S_f$.

Теоретической   основой    разработок    алгоритмов    решения
перечисленных задач являются следующие теоремы.

{\bf Теорема 1} Пусть
$A=\{ a_1 ,a_2 ,\,\dots,\,a_q \}$ - множество
атомов индуктивной алгебры де Моргана
$(S;\wedge ,\vee,',\bold O,\bold I ,\leqslant),
i \in \bold N$ и
$1 \leqslant i \leqslant q, x \in S$  и \break
$k_{x,i} \rightleftharpoons max \{ t \in \bold Z : a^t_i \leqslant x \}$.
Тогда
$$x = sup \{ a^{k_{x,i}}_i : (i \in \bold N) \and (1 \leqslant i \leqslant q)\}.$$

{\bf Теорема 2}  Для  любых  двух  атомов  $a$  и  $b$  типологического
    пространства  $(S;A;R)$  имеет  место  равенство:
$$R^{-1} \langle a \rangle \cap R^{-1} \langle b \rangle =
\square (min(R^{-1}\langle a \rangle) \vee min(R^{-1} \langle b \rangle )).$$

     Конкретными моделями предложенной абстрактной теории являются,
например, алгебра суграфов обыкновенного полного графа, взвешенного
неотрицательными целыми числами (графическая модель), и её матричное
представление (числовая  модель).  Описание  конкретных  моделей  и
решение задач анализа и синтеза в рамках этих  моделей,  записанное
на Упрощённом Паскале, представлено в pаботах [3, 4].

\vskip .5 cm
\centerline{\bf Список использованной литеpатуpы}
\vskip .3 cm
\noindent
1. {\it Ахо А.,Хопкрофт Дж., Ульман Дж.} Построение и анализ
вычисли-
\break
\phantom{ны}
тельных алгоритмов. М., 1979. 536~с.

\noindent
2. {\it Биркгоф Г.} Теория решёток. М., 1984. 566~с.

\noindent
3. {\it Евдокимов Ю.~Н.} Анализ эффективности и задача структурного син-
\break
\phantom{ны}
теза: [Ч.] 1. М., 1987. 47~с. Деп. в ВИНИТИ 12.08.87, $\No$~5894-В87.

\noindent
4. {\it Евдокимов Ю.~Н.} Анализ эффективности и задача структурного син-
\break
\phantom{ны}
теза. [Ч.] 2. М., 1988. 42~с. Деп. в ВИНИТИ 09.08.88, $\No$~6410-В88.

\noindent
5. {\it Нечепуренко М.~И.} Формализация понятия живучести //
Имитаци-
\break
\phantom{ны}
онное моделирование систем. Новосибирск, 1981.
%\break
%\phantom{ны}
C.~57 -- 86.

\noindent
6. {\it Трияльс Э.,Альсина К., Вальверде Л.} Нужны ли в теории нечётких
\break
\phantom{ны}
множеств иперации max,min и 1-j ? //Нечёткие множества и те-
\break
\phantom{ны}
ория  возможностей: (Последние достижения). М., 1986. C.~199 -- 
\break
\phantom{ны}
228.
\end
