Контактная схема — различия между версиями
Ilyal (обсуждение | вклад) |
(→Примеры некоторых контактных схем) |
||
| Строка 9: | Строка 9: | ||
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам. | Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 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 логических элементов. | ||
| + | |||
| + | * '''Конъюнкция''' | ||
| + | Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что | ||
| + | последовательное соединение элементов соответствует операции конъюнкции. | ||
| + | |||
| + | * '''Дизъюнкция''' | ||
| + | Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению элементов. | ||
| + | |||
| + | * '''Отрицание''' | ||
| + | Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над ребром графа знак отрицания. | ||
Версия 15:52, 8 декабря 2013
| Определение: |
| Контактная схема представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). |
Принцип работы
Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины и . Тогда контактная схема вычисляет некоторую функцию между вершинами и , равную 1 на тех наборах переменных, на которых между и есть путь по замкнутым ребрам.
Построение контактных схем
Любую контактную схему можно представить в виде комбинации 3 логических элементов.
- Конъюнкция
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что последовательное соединение элементов соответствует операции конъюнкции.
- Дизъюнкция
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению элементов.
- Отрицание
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над ребром графа знак отрицания.
