Контактная схема — различия между версиями
(→Ссылки) |
(→Принцип работы) |
||
Строка 12: | Строка 12: | ||
==Принцип работы== | ==Принцип работы== | ||
+ | |||
+ | |||
+ | |||
+ | Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы, определяющую функцию <tex>g(x^n)</tex>. Тогда <tex>g(x^n)</tex> принимает значение <tex>1</tex> при таком наборе значений переменных, если можно добраться из <tex>u</tex> в <tex>v</tex> по замкнутым контактам. | ||
+ | |||
+ | |||
Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы <tex>S</tex>, <tex>[u,v]</tex> {{---}} некоторая цепь, соединяющая <tex>u</tex> и <tex>v</tex>, <tex>K(u,v)</tex> {{---}} конъюнкция букв прописанных на ребрах <tex>[u,v]</tex>. Пусть функция <tex>f(x^n)</tex> определяется формулой: <tex>f(x^n)={\bigvee\limits_{[u,v]} (K(u,v))}</tex> в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса <tex>u</tex> и <tex>v</tex>. Говорят, что схема <tex>S</tex> реализует функцию <tex>g(x^n)</tex>, если <tex>f(x^n)=g(x^n)</tex>. | Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы <tex>S</tex>, <tex>[u,v]</tex> {{---}} некоторая цепь, соединяющая <tex>u</tex> и <tex>v</tex>, <tex>K(u,v)</tex> {{---}} конъюнкция букв прописанных на ребрах <tex>[u,v]</tex>. Пусть функция <tex>f(x^n)</tex> определяется формулой: <tex>f(x^n)={\bigvee\limits_{[u,v]} (K(u,v))}</tex> в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса <tex>u</tex> и <tex>v</tex>. Говорят, что схема <tex>S</tex> реализует функцию <tex>g(x^n)</tex>, если <tex>f(x^n)=g(x^n)</tex>. | ||
Версия 16:59, 23 октября 2014
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются контактные схемы. С помощью контактных схем можно представить любую булеву функцию.
Определение: |
Контактная схема (англ. contact circuit) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание. |
Определение: |
Контакт (англ. contact) — ребро схемы, помеченное символом переменной или ее отрицанием |
Содержание
Принцип работы
Пусть
и — два полюса контактной схемы, определяющую функцию . Тогда принимает значение при таком наборе значений переменных, если можно добраться из в по замкнутым контактам.
Пусть и — два полюса контактной схемы , — некоторая цепь, соединяющая и , — конъюнкция букв прописанных на ребрах . Пусть функция определяется формулой: в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса и . Говорят, что схема реализует функцию , если .
Построение контактных схем
Представление одного из базисов в контактных схемах
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации трех логических элементов:
Конъюнкция | Дизъюнкция | Отрицание |
Построение контактных схем
Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует. В качестве примера рассмотрим функцию, представленную в ДНФ: . Каждой скобке ДНФ соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена cправа.
Примеры построения некоторых функций
Исключающее "или" | Медиана трех | |
Задача о минимизации контактной схемы
Определение: |
Две контактные схемы называются эквивалентными (англ. equivalent contact circuits), если они реализуют одну и ту же булеву функцию. |
Определение: |
Сложностью контактной схемы (англ. the complexity of the contact circuit) называется число ее контактов. |
Определение: |
Минимальная контактная схема (англ. minimal contact circuit) — схема, имеющая наименьшую сложность среди эквивалентных ей схем. |
Задача минимизации контактных схем состоит в том, чтобы по данной схеме найти схему , эквивалентную и имеющую наименьшую сложность.
Один из путей решения этой задачи состоит в следующем:
- Осуществляем переход от контактной схемы к её булевой функции .
- Упрощаем карты Карно. , то есть отыскиваем функцию (на том же базисе, что и , равносильную и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать
- Строим схему , реализующую функцию .
Теорема: |
Любой булеву функцию можно представить контактной схемой, сложностью |
См также
Ссылки
- Контактные схемы
- Encyclopedia of Math — Contact sheme
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
- М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.