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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача о минимизации контактной схемы)
Строка 8: Строка 8:
 
==Принцип работы==
 
==Принцип работы==
 
[[Файл:contact.png||right||200px]]
 
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
+
[[Файл:contactnot.png |right|200px | Отрицание]]
 
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.
 
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.
  
Строка 14: Строка 14:
 
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:  
 
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:  
  
* '''Конъюнкция''' [[Файл:multiply.png | 200px | right ]]
+
* '''Конъюнкция''' [[Файл:multiply.png | 200px | right | Конъюнкция]]
 
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
 
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
 
последовательное соединение полюсов соответствует операции конъюнкции.
 
последовательное соединение полюсов соответствует операции конъюнкции.
  
* '''Дизъюнкция''' [[Файл:disjunction.png | 200 px | right]]
+
* '''Дизъюнкция''' [[Файл:disjunction.png | 200 px | right | Дизъюнкция]]
 
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.
 
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.
  
* '''Отрицание'''
+
* '''Отрицание'''  
 
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
 
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
 +
 +
=== Примеры построения некоторых функций ===
 +
* '''Xor''' [[Файл:xor.png |200 px| right| xor]]
 +
<tex>x \oplus y = (\neg x \land y) \lor (x \land \neg y)</tex>
 +
 +
 +
* '''Медиана трех''' [[Файл:median.png |200 px| right| медиана]]
 +
<tex> <xyz> = (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)</tex>
 +
  
 
==Задача о минимизации контактной схемы==
 
==Задача о минимизации контактной схемы==
Строка 35: Строка 44:
 
ее контактов.   
 
ее контактов.   
 
}}
 
}}
 +
 +
{{Определение
 +
|definition='''Минимальная контактная схема''' - схема, имеющая наименьшую сложность среди эквивалентных ей схем.
 +
}}
 +
 
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
 
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
 
Один из путей решения этой задачи состоит в следующем:
 
Один из путей решения этой задачи состоит в следующем:
Строка 40: Строка 54:
 
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать [http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE карты Карно].
 
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать [http://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%80%D1%82%D0%B0_%D0%9A%D0%B0%D1%80%D0%BD%D0%BE карты Карно].
 
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.
 
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.
 +
 +
{{Теорема
 +
|statement = Любой булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
 +
|proof=Построим дерево конъюнктов для n переменных и их отрицаний. Это дерево будет содержать <tex>O(2^n)</tex> контактов. Внизу дерева получится <tex>2^n</tex> вершин. Очевидно, что каждая вершина соответствует одному конъюнкту. Если соединить часть из этих вершин с вершиной <tex>v</tex> ребрами, на которых написана <tex>1</tex>, то сложность полученной схемы не изменится.
 +
 +
Поэтому любую булевую функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
 +
}}
 +
  
 
==Ссылки==
 
==Ссылки==

Версия 20:28, 15 октября 2014

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


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


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

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

Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины [math]u[/math] и [math]v[/math]. Тогда контактная схема вычисляет некоторую функцию [math]f[/math] между вершинами [math]u[/math] и [math]v[/math], равную 1 на тех наборах переменных, на которых между [math]u[/math] и [math]v[/math] есть путь по замкнутым ребрам.

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

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

  • Конъюнкция
    Конъюнкция

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

  • Дизъюнкция
    Дизъюнкция

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

  • Отрицание

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

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

  • Xor
    xor
[math]x \oplus y = (\neg x \land y) \lor (x \land \neg y)[/math]


  • Медиана трех
    медиана
[math] \lt xyz\gt  = (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]


Ссылки

Литература

  • Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике — М.:"ФИЗМАТЛИД", 2009 — стр. 312