Контактная схема

Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются контактные схемы.

Определение:

Контактная схема (англ. contact sheme) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами).

Принцип работы

Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины [math]u[/math] и [math]v[/math]. Тогда контактная схема вычисляет некоторую функцию [math]f[/math] между вершинами [math]u[/math] и [math]v[/math], равную 1 на тех наборах переменных, на которых между [math]u[/math] и [math]v[/math] есть путь по замкнутым ребрам.

Построение контактных схем

Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:

• Конъюнкция
  

Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что последовательное соединение полюсов соответствует операции конъюнкции.

• Дизъюнкция
  

Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.

• Отрицание

Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.

Примеры построения некоторых функций

• Xor
  

[math]x \oplus y = (\neg x \land y) \lor (x \land \neg y)[/math]

• Медиана трех
  

[math] \langle x,y,z \rangle = (x \land y) \lor (x \land z) \lor (y \land z) \lor (x \land y \land z) = (x \land y) \lor (x \land z) \lor (y \land z)[/math]

Задача о минимизации контактной схемы

Определение:

Две контактные схемы называются эквивалентными, если они реализуют одну и ту же булеву функцию.

Определение:

Сложностью контактной схемы называется число ее контактов.

Определение:

Минимальная контактная схема - схема, имеющая наименьшую сложность среди эквивалентных ей схем.

Задача минимизации контактных схем состоит в том, чтобы по данной схеме [math]S[/math] найти схему [math]T[/math] , эквивалентную [math]S[/math] и имеющую наименьшую сложность. Один из путей решения этой задачи состоит в следующем:

• Осуществляем переход от контактной схемы [math]S[/math] к её булевой функции [math]F(S)[/math].
• Упрощаем [math]F(S)[/math], то есть отыскиваем функцию [math]G[/math] (на том же базисе, что и [math]F(S)[/math]), равносильную [math]F(S)[/math] и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать карты Карно.
• Строим схему [math]T[/math], реализующую функцию [math]G[/math].

Теорема:

Любой булеву функцию можно представить контактной схемой, сложностью [math]O(2^n)[/math]

Доказательство:

[math]\triangleright[/math]

Построим дерево конъюнктов для n переменных и их отрицаний. Это дерево будет содержать [math]O(2^n)[/math] контактов. Внизу дерева получится [math]2^n[/math] вершин. Очевидно, что каждая вершина соответствует одному конъюнкту. Если соединить часть из этих вершин с вершиной [math]v[/math] ребрами, на которых написана [math]1[/math], то сложность полученной схемы не изменится. Поэтому любую булевую функцию можно представить контактной схемой, сложностью [math]O(2^n)[/math]

[math]\triangleleft[/math]

Ссылки

• Контактные схемы
• Encyclopedia of Math — Contact sheme
• Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике

Литература

• Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике — М.:"ФИЗМАТЛИД", 2009 — стр. 312