Контактная схема
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются контактные схемы. С помощью контактных схем можно представить любую булеву функцию.
Определение: |
Контактная схема (англ. contact circuit) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание. |
Определение: |
Контакт (англ. contact) — ребро схемы, помеченное символом переменной или ее отрицанием |
Принцип работы
Пусть
и — два полюса контактной схемы , — некоторая цепь, соединяющая и , — конъюнкция букв прописанных на ребрах . Пусть функция определяется формулой: в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса и . Говорят, что схема реализует функцию , если .Построение контактных схем
Представление одного из базисов в контактных схемах
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации трех логических элементов:
![]() |
![]() |
![]() |
Конъюнкция | Дизъюнкция | Отрицание |
Построение контактных схем
Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует. В качестве примера рассмотрим функцию, представленную в ДНФ: . Каждой скобке ДНФ соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек.
Примеры построения некоторых функций
![]() |
![]() | |
Исключающее "или" | Медиана трех | |
Задача о минимизации контактной схемы
Определение: |
Две контактные схемы называются эквивалентными (англ. equivalent contact circuits), если они реализуют одну и ту же булеву функцию. |
Определение: |
Сложностью контактной схемы (англ. the complexity of the contact circuit) называется число ее контактов. |
Определение: |
Минимальная контактная схема (англ. minimal contact circuit) — схема, имеющая наименьшую сложность среди эквивалентных ей схем. |
Задача минимизации контактных схем состоит в том, чтобы по данной схеме найти схему , эквивалентную и имеющую наименьшую сложность.
Один из путей решения этой задачи состоит в следующем:
- Осуществляем переход от контактной схемы к её булевой функции .
- Упрощаем карты Карно. , то есть отыскиваем функцию (на том же базисе, что и , равносильную и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать
- Строим схему , реализующую функцию .
Теорема: |
Любой булеву функцию можно представить контактной схемой, сложностью |
См также
Ссылки
- Контактные схемы
- Encyclopedia of Math — Contact sheme
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике