http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=46.23.68.180&*Викиконспекты - Вклад участника [ru]2026-05-22T00:31:51ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D0%BE%D0%BD%D1%82%D0%B0%D0%BA%D1%82%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0&diff=35129Контактная схема2014-01-05T13:13:09Z<p>46.23.68.180: /* Задача о минимизации контактной схемы */</p>
<hr />
<div>{{Определение<br />
|definition =<br />
'''Контактная схема''' (''англ.'' boolean curcuit) представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').<br />
}}<br />
<br />
==Принцип работы==<br />
[[Файл:contact.png||right||200px]]<br />
[[Файл:contactnot.png||right||200px]]<br />
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.<br />
<br />
==Построение контактных схем==<br />
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов: <br />
<br />
* '''Конъюнкция''' [[Файл:multiply.png | 200px | right ]]<br />
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что<br />
последовательное соединение полюсов соответствует операции конъюнкции.<br />
<br />
* '''Дизъюнкция''' [[Файл:disjunction.png | 200 px | right]]<br />
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.<br />
<br />
* '''Отрицание'''<br />
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.<br />
<br />
==Задача о минимизации контактной схемы==<br />
{{Определение<br />
|definition =<br />
Две контактные схемы называются '''эквивалентными''', если они реализуют одну и ту же булеву функцию. <br />
}}<br />
<br />
{{Определение<br />
|definition =<br />
'''Сложностью''' контактной схемы называется число <br />
ее контактов. <br />
}}<br />
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.<br />
Один из путей решения этой задачи состоит в следующем:<br />
* Осуществляем переход от контактной схемы <tex>S</tex> к её булевой функции <tex>F(S)</tex>.<br />
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений атомарных формул.<br />
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.<br />
<br />
==Ссылки==<br />
* [http://pgap.chat.ru/zap/zap116.htm Контактные схемы]<br />
* [http://en.wikipedia.org/wiki/Boolean_circuit Wikipedia {{---}} Boolean curcuit]<br />
<br />
==Литература==<br />
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике {{---}} М.:"ФИЗМАТЛИД", 2009 {{---}} стр. 312</div>46.23.68.180