Изменения

'''Контактная схема''' (англ. ''англ.contact circuit'' boolean curcuit) представляет собой ориентированный ациклический [[Основные определения теории графов|ориентированный ациклический граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют .}}{{Определение|definition ='''Контакт'контактами'', а вершины - (англ. ''полюсамиcontact''){{---}} ребро схемы, помеченное символом переменной или ее отрицанием.Каждому ребру в схеме сопоставляется какая то переменная (не обязательно каждой переменной сопоставляется ребро)

[[Файл:contact.png||right||200px]][[Файл:contactnot.png||right{{Определение||200px]]definition =Зафиксируем некоторые значения переменным. Тогда '''замкнутымиЗамкнутый контакт''' (англ. ''closed contact' называются ребра') {{---}} контакт схемы, на которых записана над которым написана <tex>1</tex> или значение переменной равно <tex>1, ребра, на которых записан 0, называются </tex>.}} {{Определение|definition ='''Разомкнутый контакт'''(англ. 'разомкнутыми'open contact'') {{---}} контакт схемы, над которым написан <tex>0</tex> или значение переменной равно <tex>0</tex>. Зафиксируем две вершины }} Пусть <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию {{---}} два полюса контактной схемы (из вершины <tex>fu</tex> между вершинами ребра только выходят, в вершину <tex>uv</tex> и ребра только входят), определяющую функцию <tex>vg(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 логических элементов: контактных схемах===

* '''Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к [[ДНФ|ДНФ]] или [[КНФ|КНФ]], а затем построить, используя комбинации трех логических элементов:{| cellpadding="0"| [[Файл:multiply.png | 250px | thumb | Конъюнкция''' ]] || [[Файл:multiplydisjunction.png | 250 px | thumb | Дизъюнкция]] || [[Файл:contactnot.png | 200px | right thumb | Отрицание]]Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, чтопоследовательное соединение полюсов соответствует операции конъюнкции.|}

* '''Дизъюнкция''' [[Файл: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 =Две контактные схемы называются '''эквивалентными''' (англ. ''equivalent contact circuits)'', если они реализуют одну и ту же булеву функцию. }} {{Определение|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>F(S)</tex>.* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>, равносильную <tex>F(S)</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://enwww.wikipediaencyclopediaofmath.org/wikiindex.php/Boolean_circuit Wikipedia Contact_scheme Encyclopedia of Math {{---}} Boolean curcuitContact sheme]* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике* М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы. [[Категория: Дискретная математика и алгоритмы]]