Контактная схема — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Принцип работы)
(Ссылки)
Строка 80: Строка 80:
 
* [[Реализация_булевой_функции_схемой_из_функциональных_элементов|Построение функциональной схемы]]
 
* [[Реализация_булевой_функции_схемой_из_функциональных_элементов|Построение функциональной схемы]]
  
==Ссылки==
+
==Источники информации==
 
* [http://pgap.chat.ru/zap/zap116.htm Контактные схемы]
 
* [http://pgap.chat.ru/zap/zap116.htm Контактные схемы]
 
* [http://www.encyclopediaofmath.org/index.php/Contact_scheme Encyclopedia of Math {{---}} Contact sheme]
 
* [http://www.encyclopediaofmath.org/index.php/Contact_scheme Encyclopedia of Math {{---}} Contact sheme]
 
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
 
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
 
* М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.
 
* М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.

Версия 17:19, 23 октября 2014

Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются контактные схемы. С помощью контактных схем можно представить любую булеву функцию.


Определение:
Контактная схема (англ. contact circuit) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание.


Определение:
Контакт (англ. contact) — ребро схемы, помеченное символом переменной или ее отрицанием


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

Определение:
Замкнутый контакт (англ. closed contact) — контакт схемы, над которым написана [math]0[/math] или значение переменной равно [math]0[/math].


Определение:
Разомкнутый контакт (англ. open contact) — контакт схемы, над которым написана [math]1[/math] или значение переменной равно [math]1[/math].


Пусть [math]u[/math] и [math]v[/math] — два полюса контактной схемы, определяющую функцию [math]g(x_1, x_2 \dots, x_n)[/math]. Тогда [math]g(x_1, x_2 \dots, x_n)[/math] принимает значение [math]1[/math] при таком наборе значений переменных, если можно добраться из [math]u[/math] в [math]v[/math] только по разомкнутым контактам.

Построение контактных схем

Представление одного из базисов в контактных схемах

Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации трех логических элементов:

Конъюнкция
Дизъюнкция
Отрицание
Конъюнкция Дизъюнкция Отрицание

Построение контактных схем

Example10.png

Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует. В качестве примера рассмотрим функцию, представленную в ДНФ: [math]f=(\neg x \land y \land \neg z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z)[/math]. Каждой скобке ДНФ соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена cправа.

Примеры построения некоторых функций

xor медиана
Исключающее "или" Медиана трех
[math]x \oplus y = (\neg x \land y) \lor (x \land \neg y)[/math] [math] \langle x,y,z \rangle = = (x \land y) \lor (x \land z) \lor (y \land z)[/math]

Задача о минимизации контактной схемы

Определение:
Две контактные схемы называются эквивалентными (англ. equivalent contact circuits), если они реализуют одну и ту же булеву функцию.


Определение:
Сложностью контактной схемы (англ. the complexity of the contact circuit) называется число ее контактов.


Определение:
Минимальная контактная схема (англ. minimal contact circuit) — схема, имеющая наименьшую сложность среди эквивалентных ей схем.


Задача минимизации контактных схем состоит в том, чтобы по данной схеме [math]S[/math] найти схему [math]T[/math] , эквивалентную [math]S[/math] и имеющую наименьшую сложность. Один из путей решения этой задачи состоит в следующем:

  • Осуществляем переход от контактной схемы [math]S[/math] к её булевой функции [math]F(S)[/math].
  • Упрощаем [math]F(S)[/math], то есть отыскиваем функцию [math]G[/math] (на том же базисе, что и [math]F(S)[/math], равносильную [math]F(S)[/math] и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать карты Карно.
  • Строим схему [math]T[/math], реализующую функцию [math]G[/math].
Теорема:
Любой булеву функцию можно представить контактной схемой, сложностью [math]O(2^n)[/math]

См также

Источники информации

  • Контактные схемы
  • Encyclopedia of Math — Contact sheme
  • Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
  • М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.