Обоснование транзитивных операций дизъюнкции и конъюнкции

При построении транзитивных связей необходимо произвести анализ значений типов связей между этими вершинами и определить, какую связь между вершинами i и k выбрать: непосредственную или через вершину j. (для построения матрицы следования с транзитивными связями)

Первое, что влияет на этот выбор - это наличие транзитивной связи из вершины i в вершину k через вершину j. Обозначим эту связь S_T. Для существования такой связи, как было замечено выше, необходимо, чтобы обе связи S_ij и S_jk были отличны от нуля. Для проверки этой связи введем операцию «Ä», которая аналогична операции конъюнкции в булевой алгебре. Таблица истинности операции «Ä» применительно к информационно-логическим графам представлена в таблице:

Здесь L₁, L₂, L обозначают некоторые кортежи [5] из логических связей S’_ab, где S’_ab либо некоторая логическая связь из вершины a в вершину b, либо ранее вычисленная транзитивная связь. Символ “_” – оператор конкатенации [5]. Как нетрудно убедиться операция «Ä» коммутативна, поэтому в таблице приведены значения без учета перестановки операндов. Рассмотрим построение этой таблицы более подробно. Очевидно, что транзитивная связь есть, если обе связи S_ij и S_jk отличны от нуля. Соответственно результат операции на наборах, где хотя бы одна из связей S_ij или S_jk равна нулю, будет нулевым, т.е. транзитивная связь отсутствует. Далее, в связи с тем, что ход решения алгоритма отражается последовательностью выполненных логических операторов, то в ситуации, когда один операнд равен единице, а второй содержит логический тип связи, необходимо, чтобы результат операции отражал логическую связь. Поэтому на наборе (1,L) результатом выполнения операции «Ä» будет L. Исходя из тех же рассуждений, можно сказать, что в случае, когда обе связи содержат логический тип связи необходимо их объединить, и результатом операции на наборе (L₁, L₂) будет выражение L₁_ L₂. Таким образом, данная операция дает нам транзитивную связь S_T=S_­ijÄS_jk. Следующим шагом будет определение, какая связь нам более важна: непосредственная из вершины i в k (S_ik­) или новая, вычисленная S_T. Первое, на что следует обратить внимание, как уже говорилось, это на типы связей. Более важной связью будем по-прежнему считать логическую. Такой выбор делается из тех же соображений, что и раньше. Второе, что определяет результат операции – это непосредственно наличие хотя бы одной из связей между вершинами i и k: транзитивной или задающей [1]. Т.е. необходимо выбрать ненулевую связь, если она есть, при нулевом значении другой связи. Обозначим операцию, осуществляющую такой выбор, «Å». Из изложенного выше можно сказать, что ее характер подобен операции ИЛИ булевой алгебры. Таблица истинности для операции «Å»:

Таким образом, для трех рассматриваемых вершин можно определить новую связь, используя две введенные операции, т.е. связь S_ik можно вычислить по следующей формуле: S_ik=S_ikÅ(S_ijÄS_jk) (2)

или применительно к матрице следования: (k,i)=(k,i) Å ((j,i) Ä(k,j)) (3)

После последовательного преобразования всей S мы получим матрицу ST.