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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Xor)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Контактная схема''' (англ. ''contact sheme'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины {{---}} ''полюсами'').
+
'''Контактная схема''' (англ. ''contact sheme'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
'''Контакт''' (англ. ''contact'') ребро схемы, помеченное символом переменной или ее отрицанием
 
}}
 
}}
  
Строка 9: Строка 14:
 
[[Файл:contact.png||right||200px]]
 
[[Файл:contact.png||right||200px]]
 
[[Файл:contactnot.png |right|200px | Отрицание]]
 
[[Файл:contactnot.png |right|200px | Отрицание]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана <tex>1</tex>, ребра, на которых записан <tex>0</tex>, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную <tex>1</tex> на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.
+
Пусть <tex>u</tex> и <tex>v</tex> {{---}} 2 полюса контактной схемы <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>.
  
 
==Построение контактных схем==
 
==Построение контактных схем==
Строка 59: Строка 64:
 
Один из путей решения этой задачи состоит в следующем:
 
Один из путей решения этой задачи состоит в следующем:
 
* Осуществляем переход от контактной схемы <tex>S</tex> к её булевой функции <tex>F(S)</tex>.
 
* Осуществляем переход от контактной схемы <tex>S</tex> к её булевой функции <tex>F(S)</tex>.
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать [[Сокращенная_и_минимальная_ДНФ| карты Карно]].
+
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>, равносильную <tex>F(S)</tex> и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать [[Сокращенная_и_минимальная_ДНФ| карты Карно]].
 
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.
 
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.
  

Версия 17:03, 18 октября 2014

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


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


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


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

Contact.png
Отрицание

Пусть [math]u[/math] и [math]v[/math] — 2 полюса контактной схемы [math]S[/math], [math][u,v][/math] — некоторая цепь, соединяющая [math]u[/math] и [math]v[/math], [math]K(u,v)[/math] — конъюнкция букв прописанных на ребрах [math][u,v][/math]. Пусть функция [math]f(x^n)[/math] определяется формулой: [math]f(x^n)={\bigvee\limits_{[u,v]} (K(u,v))}[/math] в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса [math]u[/math] и [math]v[/math]. Говорят, что схема [math]S[/math] реализует функцию [math]g(x^n)[/math], если [math]f(x^n)=g(x^n)[/math].

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

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

Конъюнкция

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

Конъюнкция

Результат конъюнкции равен [math]1[/math] тогда и только тогда, когда оба операнда равны [math]1[/math]. В применении к контактным схемам это означает, что последовательное соединение полюсов соответствует операции конъюнкции.

Дизъюнкция

Дизъюнкция

Результат дизъюнкции равен [math]0[/math] только в случае, когда оба операнда равны [math]0[/math]. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.

Отрицание

Отрицание — это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.

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

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) \lor (x \land y \land z) = (x \land y) \lor (x \land z) \lor (y \land z)[/math]

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

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


Определение:
Сложностью контактной схемы — число ее контактов.


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


Задача минимизации контактных схем состоит в том, чтобы по данной схеме [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]
Доказательство:
[math]\triangleright[/math]

Построим дерево конъюнктов для n переменных и их отрицаний. Это дерево будет содержать [math]O(2^n)[/math] контактов. Внизу дерева получится [math]2^n[/math] вершин. Очевидно, что каждая вершина соответствует одному конъюнкту. Если соединить часть из этих вершин с вершиной [math]v[/math] ребрами, на которых написана [math]1[/math], то сложность полученной схемы не изменится.

Поэтому любую булевую функцию можно представить контактной схемой, сложностью [math]O(2^n)[/math]
[math]\triangleleft[/math]

См также

Построение функциональной схемы

Ссылки