Теория контроля контактных схем, страница 2

Т а б л и ц а   3.2

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Таким образом, задача построения ЭНФ по МС сводится к известной задаче нахождения всех максимальных совместимых подмножеств (МАКСОПОД). Каждой конъюнкции ЭНФ в МС соответствует максимальная полная (заполненная единицами) подматрица. Например, конъюнкции  в табл. 3.1 соответствует максимальная полная подматрица, показанная в табл. 3.3.

                                                               Т а б л и ц а   3.3

1

1

1

1

1

1

1

1

1

          Чтобы найти такую подматрицу надо включить в множество М строку  и затем последовательно включать в это множество строки, которые совместимы со всеми строками, уже включенными в М. Процесс нахождения конъюнкции ЭНФ завершается, когда число строк в множестве М окажется равным числу столбцов в этих строках, заполненных единицами. В табл. 3.4 отражен процесс нахождения конъюнкции .

Т а б л и ц а   3.4

1

1

1

1

1

1

1

1

1

1

1

1

          Для построения ЭНФ по МС может быть использован любой из известных алгоритмов МАКСОПОД, которые упорядочивают процесс формирования конъюнкций [13].

          Обозначим через А и В – множества букв ЭНФ, совместимых соответственно с буквами a и b. Введем четыре вида отношений между буквами ЭНФ (контактами):

          1) эквивалентности a = b, если А = В;

          2) замены a « b, если A \ a = B \ b;

          3) включения по эквивалентности a Ì b,  если А Ì В;

          4) включения по замене a ® b, если A \ aÌ B \ b.

          Указанные отношения определяются по МС путем сравнения строк  a  и  b.  Для  табл.  3.1  имеем:  =  « b «  Ì ,  Ì ,  ® ,  ®.

          Если а = b, то буквы a и b совместимы и всегда входят вместе в одну и ту же конъюнкцию ЭНФ, а контакты a и b включены последовательно и всегда вместе входят в один и тот же путь проводимости схемы. Если а « b, то буквы a и b несовместимы и для всякой конъюнкции ЭНФ, содержащей букву а, найдется конъюнкция, которую можно получить из первой путем замены а на b,а контакты a и b включены параллельно и всегда вместе входят в одно и то же сечение схемы. Если a  b, то буквы a и b совместимы и во всех конъюнкциях, которые содержат букву b, присутствует и буква a. Если a ®b, то буквы a и b несовместимы и для всякой конъюнкции ЭНФ, содержащей букву a, найдется конъюнкция, содержащая букву b и все буквы, составляющие первую конъюнкцию (кроме а), а также некоторое множество других букв.