Изменения

Перейти к: навигация, поиск

Контактная схема

1819 байт добавлено, 01:11, 10 октября 2019
Опечатка
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.
{{Определение
|definition =
'''Контактная схема''' (англ. ''contact shemecircuit'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание.
}}
{{Определение
|definition =
'''Контакт''' (англ. ''contact'') {{---}} ребро схемы, помеченное символом переменной или ее отрицанием. Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)
}}
 
==Принцип работы==
{{Определение
|definition =
'''КонтактЗамкнутый контакт''' (англ. ''closed contact'') ребро {{---}} контакт схемы, помеченное символом над которым написана <tex>1</tex> или значение переменной или ее отрицаниемравно <tex>1</tex>.
}}
==Принцип работы=={{Определение[[Файл:contact.png||right||200px]]definition =[[Файл:contactnot'''Разомкнутый контакт''' (англ.png |right|200px | Отрицание]]Пусть <tex>u</tex> и <tex>v</tex> ''open contact'') {{---}} 2 полюса контактной контакт схемы , над которым написан <tex>S0</tex>, или значение переменной равно <tex>[u,v]0</tex> {{---.}} некоторая цепь, соединяющая  Пусть <tex>u</tex> и <tex>v</tex>, <tex>K(u,v)</tex> {{---}} конъюнкция букв прописанных на ребрах два полюса контактной схемы (из вершины <tex>[u,v]</tex>. Пусть функция ребра только выходят, в вершину <tex>f(x^n)v</tex> определяется формулой: ребра только входят), определяющую функцию <tex>fg(x^n)={x_1, x_2 \bigvee\limits_{[udots,v]} (K(u,v)x_n)}</tex> в которой дизъюнкция берется по всем простым цепям схемы, соединяющие полюса . Тогда <tex>ug(x_1, x_2 \dots, x_n)</tex> и принимает значение <tex>v1</tex>. Говорятпри таком наборе значений переменных, что схема если можно добраться из <tex>Su</tex> реализует функцию в <tex>g(x^n)</tex>, если <tex>f(x^n)=g(x^n)v</tex>только по замкнутым контактам.
==Построение контактных схем==
===Представление одного из базисов в контактных схемах===
[[Файл:multiply.png | 200px | right | Конъюнкция]]
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к [[ДНФ|ДНФ]] или [[КНФ|КНФ]], а затем построить, используя комбинации 3 логических элементов:
====Конъюнкция====
Результат конъюнкции равен <tex>1</tex> тогда и только тогда, когда оба операнда равны <tex>1</tex>. В применении к контактным схемам это означает, что
последовательное соединение полюсов соответствует операции конъюнкции.
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к [[ДНФ|ДНФ]] или [[КНФ|КНФ]], а затем построить, используя комбинации трех логических элементов:{| cellpadding="0"| [[Файл:multiply.png | 250px | thumb | Конъюнкция]] || [[Файл:disjunction.png | 200 250 px | right thumb | Дизъюнкция]] || [[Файл:contactnot.png |200px | thumb | Отрицание]]====Дизъюнкция==== Результат дизъюнкции равен <tex>0</tex> только в случае, когда оба операнда равны <tex>0</tex>. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.|}
===Построение контактных схем=Отрицание==== Отрицание {{---}} это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует. В качестве примера рассмотрим функцию, представленную в [[ДНФ|ДНФ]]: <tex>f=== Примеры построения некоторых функций ===(\neg x \land y \land z) \lor (x \land \neg y \land z) \lor (x \land y \land z)</tex>. Каждой скобке [[ДНФ|ДНФ]] соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена ниже.
[[Файл:xorexample10.png |200 px| right| xor320px]]====Исключающее "или"====
<tex>x \oplus y = (\neg x \land y) \lor (x \land \neg y)</tex>== Примеры построения некоторых функций ===
{| cellpadding="0"| [[Файл:xor.png |200 px| thumb | исключающее "или"]] || || [[Файл:median.png |200 px| rightthumb | медиана]]|-====Медиана трех====  | <tex> x \langle x,oplus y,z \rangle = (\neg x \land y) \lor (x \land z) \lor (neg y \land z) </tex> || || <tex> \lor (langle x \land ,y ,z \land z) rangle = (x \land y) \lor (x \land z) \lor (y \land z)</tex>|}
==Задача о минимизации контактной схемы==
{{Определение
|definition =
Две контактные схемы называются '''эквивалентными''' (англ. ''equivalent contact circuits)'', если они реализуют одну и ту же булеву функцию.
}}
{{Определение
|definition =
'''Сложностью контактной схемы''' {{---}} (англ. ''the complexity of the contact schemecircuit'') называется число
ее контактов.
}}
{{Определение
|definition='''Минимальная контактная схема''' {{---}} (англ. ''Minimal minimal contact schemecircuit'') {{---}} схема, имеющая наименьшую сложность среди эквивалентных ей схем.}} {{Определение|definition = '''Дерево конъюнктов для <tex>n</tex> переменных''' {{---}} двоичное ориентированное дерево глубиной <tex>n</tex>, такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной <tex>x_k (k \leqslant n)</tex>, а правое помечено символом отрицания переменной <tex>x_k</tex>.
}}
{{Теорема
|statement = Любой Любую булеву функцию можно представить контактной схемой, сложностью <tex>O(2^n)</tex>|proof=Построим дерево конъюнктов для n переменных и их отрицаний. Это дерево будет содержать Пусть дана функция <tex>Of(2^nx_1,x_2 \dots, x_n)</tex> контактови она представлена в [[ДНФ|ДНФ]][[Файл:tree_for_two. Внизу дерева получится <tex>png | 250px | thumb | Дерево конъюнктов для 2^n</tex> вершин. Очевидно, что каждая вершина соответствует одному конъюнкту. Если соединить часть из этих вершин с вершиной <tex>v</tex> ребрами, на которых написана <tex>1</tex>, то сложность полученной схемы не изменится.-х переменных]]
Поэтому любую булевую функцию Возьмем дерево конъюнктов для <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://www.encyclopediaofmath.org/index.php/Contact_scheme Encyclopedia of Math {{---}} Contact sheme]
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
* М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Схемы из функциональных элементов ]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/40435...71851»

Навигация