Изменения
Опечатка
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''. С помощью ''контактных схем'' можно представить любую булеву функцию.
{{Определение
|definition =
'''Контактная схема''' (англ. ''contact circuit'') представляет собой [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание.
}}
{{Определение
|definition =
'''Контакт''' (англ. ''contact'') {{---}} ребро схемы, помеченное символом переменной или ее отрицанием. Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)
}}
==Принцип работы==
{{Определение
|definition =
'''КонтактЗамкнутый контакт''' (англ. ''closed contact'') {{---}} ребро контакт схемы, помеченное символом над которым написана <tex>1</tex> или значение переменной или ее отрицаниемравно <tex>1</tex>.
}}
==Построение контактных схем==
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к [[ДНФ|ДНФ]] или [[КНФ|КНФ]], а затем построить, используя комбинации трех логических элементов:
{| cellpadding="0"
| [[Файл:multiply.png | 250px | thumb | Конъюнкция]] || [[Файл:disjunction.png | 250 px | thumb | Дизъюнкция]] || [[Файл:contactnot.png |right200px |200px thumb | Отрицание]]|-| Конъюнкция || Дизъюнкция || Отрицание
|}
===Построение контактных схем===
Пусть задана произвольная булева функция. Требуется построить для нее контактную схему, которая ее реализует.
В качестве примера рассмотрим функцию, представленную в [[ДНФ|ДНФ]]: <tex>f=(\neg x \land y \land \neg z) \lor (x \land \neg y \land \neg z) \lor (x \land y \land z)</tex>. Каждой скобке [[ДНФ|ДНФ]] соответствует цепочка из последовательных соединенных контактов, определяемых переменными содержащимися в скобке. При этом, вся схема состоит из параллельных соединений указанных цепочек. Для приведенного примера соответствует схема приведена cправаниже. [[Файл:example10.png|320px]]
=== Примеры построения некоторых функций ===
{| cellpadding="0"
| [[Файл:xor.png |200 px| xorthumb | исключающее "или"]] || || [[Файл:median.png |200 px|thumb | медиана]]
|-
|}
{{Определение
|definition='''Минимальная контактная схема''' (англ. ''minimal contact circuit'') {{---}} схема, имеющая наименьшую сложность среди эквивалентных ей схем.
}}
{{Определение
|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 = Пусть дана функция <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://www.encyclopediaofmath.org/index.php/Contact_scheme Encyclopedia of Math {{---}} Contact sheme]
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике
* М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
