http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.118.78.117&*Викиконспекты - Вклад участника [ru]2026-05-07T15:54:12ZВклад участника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=35018Контактная схема2014-01-04T10:27:44Z<p>217.118.78.117: /* Построение контактных схем */</p>
<hr />
<div>{{Определение<br />
|definition =<br />
'''Контактная схема''' представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').<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 />
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.</div>217.118.78.117