Контактная схема
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются контактные схемы.
Определение: |
Контактная схема (англ. contact sheme) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). |
Содержание
Принцип работы
Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана
, ребра, на которых записан , называются разомкнутыми. Зафиксируем две вершины и . Тогда контактная схема вычисляет некоторую функцию между вершинами и , равную на тех наборах переменных, на которых между и есть путь по замкнутым ребрам.Построение контактных схем
Представление одного из базисов в контактных схемах
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:
Конъюнкция
Результат конъюнкции равен
тогда и только тогда, когда оба операнда равны . В применении к контактным схемам это означает, что последовательное соединение полюсов соответствует операции конъюнкции.Дизъюнкция
Результат дизъюнкции равен
только в случае, когда оба операнда равны . Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.Отрицание
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
Примеры построения некоторых функций
Xor
Медиана трех
Задача о минимизации контактной схемы
Определение: |
Две контактные схемы называются эквивалентными, если они реализуют одну и ту же булеву функцию. |
Определение: |
Сложностью контактной схемы — число ее контактов. |
Определение: |
Минимальная контактная схема — схема, имеющая наименьшую сложность среди эквивалентных ей схем. |
Задача минимизации контактных схем состоит в том, чтобы по данной схеме найти схему , эквивалентную и имеющую наименьшую сложность.
Один из путей решения этой задачи состоит в следующем:
- Осуществляем переход от контактной схемы к её булевой функции .
- Упрощаем карты Карно. , то есть отыскиваем функцию (на том же базисе, что и ), равносильную и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать
- Строим схему , реализующую функцию .
Теорема: |
Любой булеву функцию можно представить контактной схемой, сложностью |
Доказательство: |
Построим дерево конъюнктов для n переменных и их отрицаний. Это дерево будет содержать Поэтому любую булевую функцию можно представить контактной схемой, сложностью контактов. Внизу дерева получится вершин. Очевидно, что каждая вершина соответствует одному конъюнкту. Если соединить часть из этих вершин с вершиной ребрами, на которых написана , то сложность полученной схемы не изменится. |
См также
Построение функциональной схемы
Ссылки
- Контактные схемы
- Encyclopedia of Math — Contact sheme
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике