748
правок
Изменения
Нет описания правки
==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right|200px |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> есть путь по замкнутым ребрам.
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:
* '''Конъюнкция''' [[Файл:multiply.png | 200px | right | Конъюнкция]]
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
последовательное соединение полюсов соответствует операции конъюнкции.
* '''Дизъюнкция''' [[Файл:disjunction.png | 200 px | right| Дизъюнкция]]
Результат дизъюнкции равен 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>
==Задача о минимизации контактной схемы==
ее контактов.
}}
{{Определение
|definition='''Минимальная контактная схема''' - схема, имеющая наименьшую сложность среди эквивалентных ей схем.
}}
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
Один из путей решения этой задачи состоит в следующем:
* Упрощаем <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>.
{{Теорема
|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>
}}
==Ссылки==
