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

Материал из Викиконспекты
Версия от 15:52, 8 декабря 2013; 188.162.64.99 (обсуждение) (Примеры некоторых контактных схем)
Перейти к: навигация, поиск
Определение:
Контактная схема представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами).


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

Contact.png
Contactnot.png

Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 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. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению элементов.

  • Отрицание

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