Схемы из функциональных элементов. Контактные схемы.

Функциональные элементы– некоторые абстрактные технические устройства, с помощью которых реализуются основные логические операции – конъюнкция, дизъюнкция, отрицание. Устройства изображаются следующим образом (рис. 5.11).

Элемент типа «и» Элемент типа «или» Элемент отрицания

Рис. 5.11

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

В элементе для отрицания имеется один вход для сигнала и один выход, на котором снимается инверсный сигнал.

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

Контактные Схемы.

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

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

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

Контакт (англ. contact) — ребро схемы, помеченное символом переменной или ее отрицанием. Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)

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

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

Замкнутый контакт (англ. closed contact) — контакт схемы, над которым написана $0$ или значение переменной равно $0$ .

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

Разомкнутый контакт (англ. open contact) — контакт схемы, над которым написана $1$ или значение переменной равно $1$ .

Пусть $u$ и $v$ — два полюса контактной схемы (из вершины $u$ ребра только выходят, в вершину $v$ ребра только входят), определяющую функцию $g(x_1, x_2 \dots, x_n)$ . Тогда $g(x_1, x_2 \dots, x_n)$ принимает значение $1$ при таком наборе значений переменных, если можно добраться из $u$ в $v$ только по разомкнутым контактам.

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

Представление одного из базисов в контактных схемах

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

Конъюнкция

Дизъюнкция

Отрицание

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

Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует. В качестве примера рассмотрим функцию, представленную в ДНФ: $f=(\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land z)$ . Каждой скобке ДНФ соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена ниже.

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

исключающее "или"		медиана
$x \oplus y = (\neg x \land y) \lor (x \land \neg y)$		$\langle x,y,z \rangle = (x \land y) \lor (x \land z) \lor (y \land z)$