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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача о минимизации контактной схемы)
м (rollbackEdits.php mass rollback)
 
(не показаны 63 промежуточные версии 9 участников)
Строка 1: Строка 1:
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''.
+
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.
 
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Контактная схема''' (''англ.'' contact sheme) представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
+
'''Контактная схема''' (англ. ''contact circuit'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание.
 +
}}
 +
{{Определение
 +
|definition =
 +
'''Контакт''' (англ. ''contact'') {{---}} ребро схемы, помеченное символом переменной или ее отрицанием. Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)
 
}}
 
}}
  
 
==Принцип работы==
 
==Принцип работы==
[[Файл:contact.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> есть путь по замкнутым ребрам.
+
|definition =
 +
'''Замкнутый контакт''' (англ. ''closed contact'') {{---}} контакт схемы, над которым написана <tex>1</tex> или значение переменной равно <tex>1</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition =
 +
'''Разомкнутый контакт''' (англ. ''open contact'') {{---}} контакт схемы, над которым написан <tex>0</tex> или значение переменной равно <tex>0</tex>.
 +
}}
 +
 
 +
Пусть <tex>u</tex> и <tex>v</tex> {{---}} два полюса контактной схемы (из вершины <tex>u</tex> ребра только выходят, в вершину <tex>v</tex> ребра только входят), определяющую функцию <tex>g(x_1, x_2 \dots, x_n)</tex>. Тогда <tex>g(x_1, x_2 \dots, x_n)</tex> принимает значение <tex>1</tex> при таком наборе значений переменных, если можно добраться из <tex>u</tex> в <tex>v</tex> только по замкнутым контактам.
  
 
==Построение контактных схем==
 
==Построение контактных схем==
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:
+
===Представление одного из базисов в контактных схемах===
  
* '''Конъюнкция''' [[Файл:multiply.png | 200px | right ]]
+
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к [[ДНФ|ДНФ]] или [[КНФ|КНФ]], а затем построить, используя комбинации трех логических элементов:
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
+
{| cellpadding="0"
последовательное соединение полюсов соответствует операции конъюнкции.
+
| [[Файл:multiply.png | 250px | thumb | Конъюнкция]] || [[Файл:disjunction.png | 250 px | thumb | Дизъюнкция]] || [[Файл:contactnot.png |200px | thumb | Отрицание]]
 +
|}
  
* '''Дизъюнкция''' [[Файл:disjunction.png | 200 px | right]]
+
===Построение контактных схем===
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.
 
  
* '''Отрицание'''
+
Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует.
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
+
В качестве примера рассмотрим функцию, представленную в [[ДНФ|ДНФ]]: <tex>f=(\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land z)</tex>. Каждой скобке [[ДНФ|ДНФ]] соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена ниже.
 +
 
 +
[[Файл:example10.png|320px]]
 +
 
 +
=== Примеры построения некоторых функций ===
 +
 
 +
{| cellpadding="0"
 +
| [[Файл:xor.png |200 px| thumb | исключающее "или"]] ||  || [[Файл:median.png |200 px|thumb | медиана]]
 +
|-
 +
| <tex>x \oplus y = (\neg x \land y) \lor (x \land \neg y)</tex> ||  || <tex> \langle x,y,z \rangle = (x \land y) \lor (x \land z) \lor (y \land z)</tex>
 +
|}
  
 
==Задача о минимизации контактной схемы==
 
==Задача о минимизации контактной схемы==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Две контактные схемы называются '''эквивалентными''', если они реализуют одну и ту же булеву функцию.  
+
Две контактные схемы называются '''эквивалентными''' (англ. ''equivalent contact circuits)'', если они реализуют одну и ту же булеву функцию.  
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Сложностью''' контактной схемы называется число  
+
'''Сложностью контактной схемы''' (англ. ''the complexity of the contact circuit'') называется число  
 
ее контактов.   
 
ее контактов.   
 
}}
 
}}
 +
 +
{{Определение
 +
|definition='''Минимальная контактная схема''' (англ. ''minimal contact circuit'') {{---}} схема, имеющая наименьшую сложность среди эквивалентных ей схем.
 +
}}
 +
 +
{{Определение
 +
|definition =
 +
'''Дерево конъюнктов для <tex>n</tex> переменных''' {{---}} двоичное ориентированное дерево глубиной <tex>n</tex>, такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной <tex>x_k (k \leqslant n)</tex>, а правое помечено символом отрицания переменной <tex>x_k</tex>.
 +
}}
 +
 
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
 
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
 
Один из путей решения этой задачи состоит в следующем:
 
Один из путей решения этой задачи состоит в следующем:
 
* Осуществляем переход от контактной схемы <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>.
  
==Ссылки==
+
{{Теорема
 +
|statement = Любую булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>
 +
|proof =  
 +
Пусть дана функция <tex>f(x_1,x_2 \dots, x_n)</tex> и она представлена в [[ДНФ|ДНФ]]
 +
[[Файл:tree_for_two.png | 250px | thumb | Дерево конъюнктов для 2-х переменных]]
 +
 
 +
Возьмем дерево конъюнктов для <tex>n</tex> переменных (см. картинку). Очевидно, что от вершины <tex>u</tex> до "нижних" вершин дерево можно добраться за <tex>O(n)</tex>, а ребер у такого дерева <tex>O(2^n)</tex>
 +
 
 +
Соединим нижние вершины, которые соответствуют конъюнктам функции, с вершиной <tex>v</tex> контактами, над которыми написана <tex>1</tex>. От этого в схему добавится не более, чем <tex>2^n</tex> ребер и тогда сложность останется <tex>O(2^n)</tex>.
 +
 
 +
В результате можно построить контактную схему для любой функции со сложностью <tex>O(2^n)</tex>
 +
}}
 +
 
 +
==См также==
 +
* [[Реализация_булевой_функции_схемой_из_функциональных_элементов|Построение функциональной схемы]]
 +
 
 +
==Источники информации==
 
* [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]
 +
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
 +
* М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
  
==Литература==
+
[[Категория: Схемы из функциональных элементов ]]
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике {{---}} М.:"ФИЗМАТЛИД", 2009 {{---}} стр. 312
 

Текущая версия на 19:21, 4 сентября 2022

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

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


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


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

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


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


Пусть [math]u[/math] и [math]v[/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] только по замкнутым контактам.

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

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

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

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

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

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

Example10.png

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

исключающее "или"
медиана
[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]n[/math] переменных — двоичное ориентированное дерево глубиной [math]n[/math], такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной [math]x_k (k \leqslant n)[/math], а правое помечено символом отрицания переменной [math]x_k[/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]

Пусть дана функция [math]f(x_1,x_2 \dots, x_n)[/math] и она представлена в ДНФ

Дерево конъюнктов для 2-х переменных

Возьмем дерево конъюнктов для [math]n[/math] переменных (см. картинку). Очевидно, что от вершины [math]u[/math] до "нижних" вершин дерево можно добраться за [math]O(n)[/math], а ребер у такого дерева [math]O(2^n)[/math]

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

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

См также

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

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