- 528 -
Произведение булевых матриц определяется, как и для обычных матриц, правилом «строка на столбец», но операциям сложения и умножения действительных чисел соответствуют дизъюнкция и конъюнкция логических переменных и функций. Элементы матрицы C = AB, где А и В - булевые матрицы, выражаются соотношением cij = ai1b1j ∨ ai2b2j ∨ ... ∨ ainbnj. Произведения матрицы самой на себя выражается как ее степени AA = A2, A2A = A3, ..., An-1A = An.
Можно показать, что для любой контактной схемы с k узлами существует такое r ≤ k - 1, что Pr = Pr+s = Q, где s - произвольное целое положительное число. Это значит, что матрицу полных связей можно получить умножением матрицы непосредственных связей Р на саму себя до тех пор, пока результат не начнет повторяться, причем число таких умножений не превышает k - 1. Так, для рассматриваемого примера имеем:
Следует отметить, что элементы матрицы Рi представляют собой функции всех связей между узлами посредством не более чем i-1 узлов. В частности, каждый элемент матрицы P2 учитывает непосредственные связи между парой узлов и связи между ними посредством еще одного узла. Например, p23 = p32 = x4 ∨ x2x3 соответствует непосредственной связи между узлами 2 и 3 через контакт x4, а также связи посредством узла 4 (член х2х3).
7. . Исключение узлов (анализ). При анализе контактной схемы с помощью булевых матриц сначала записывается матрица непосредственных связей Р, а затем путем возведения ее в соответствующую степень получается матрица полных связей Q. Элементы qij матрицы Q и представляют собой булевы функции данной контактной схемы между парами узлов с соответствующими номерами.
Однако такой способ в большинстве случаев не является рациональным, так как обычно представляют интерес только некоторые из функций qij между внешними узлами (полюсами) схемы. Поэтому имеет смысл предварительно исключить внутренние узлы и таким образом уменьшить порядок матрицы Р,прежде чем возводить ее в требуемую степень. При исключении s-гo узла в матрице непосредственных связей вычерчиваются s-я строка и s-й столбец и каждый ее элемент pij заменяется элементом pij ∨ pispsj . Член pispsj учитывает путь между узлами iи j через узел s, который действует параллельно с непосредственной связью pij. В результате исключения узла матрица Р преобразуется к матрице Ps на единицу
- 529 -
меньшего порядка, которая представляет собой матрицу непосредственных связей относительно неисключенной совокупности узлов.
Пусть, например, в схеме рис. 201 требуется определить булевы функции между узлами 1, 2 и 3. Матрицы Р и Р4 имеют вид:
, 
Определив P24 после преобразований, получим матрицу полных связей относительно узлов 1, 2 и 3,называемую матрицей выходов:
Элементы этой матрицы являются функциями выходов:
f12 = x1 ∨ (x2 ∨ x̅3) (x̅2 ∨ x̅1x2);
f13 = x̅2 ∨ x̅1x3 ∨ x1(x2 ∨ x̅3);
f23 = x1x̅2 ∨ x2 ∨ x3.
8. Введение узлов (синтез). При синтезе контактных схем задаются функции для внешних узлов (полюсов), которые определяют матрицу выходов. Необходимое и достаточное условие непротиворечивости этих функций состоит в том, что матрица выходов должна быть устойчивой, т. е. удовлетворять равенству F = F2.
Рис. 201. Контактная схема к примеру.
Структуру контактной схемы, реализующей заданную непротиворечивую совокупность функций, можно получить из матрицы F путем ее последовательного расширения, соответствующего операции введения узла. Эта операция обратна исключению узла и приводит к матрице Fs, порядок которой на единицу выше, а элементы таковы, что при исключении узла s снова получим матрицу F. Последовательным применением операции введения узла исходная матрица расширяется и преобразуется к виду, при котором элементы представляют собой константы 0 или 1, переменные, их отрицания или элементарные конъюнкции переменных. Тогда полученную матрицу можно рассматривать как матрицу непосредственных связей, на основе которой легко построить соответствующую контактную схему. При этом элементарные конъюнкции реализуются последовательными соединениями соответствующих контактов.