Контактная схема
| Определение: |
| Контактная схема (англ. boolean curcuit) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). |
Принцип работы
Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины и . Тогда контактная схема вычисляет некоторую функцию между вершинами и , равную 1 на тех наборах переменных, на которых между и есть путь по замкнутым ребрам.
Построение контактных схем
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:
- Конъюнкция
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что последовательное соединение полюсов соответствует операции конъюнкции.
- Дизъюнкция
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.
- Отрицание
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
Ссылки
Литература
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике — М.:"ФИЗМАТЛИД", 2009 — стр. 312
