Контактная схема — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача о минимизации контактной схемы)
Строка 1: Строка 1:
 +
Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''.
 +
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Контактная схема''' (''англ.'' boolean curcuit) представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
+
'''Контактная схема''' (''англ.'' contact sheme) представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
 
}}
 
}}
  
Строка 41: Строка 43:
 
==Ссылки==
 
==Ссылки==
 
* [http://pgap.chat.ru/zap/zap116.htm Контактные схемы]
 
* [http://pgap.chat.ru/zap/zap116.htm Контактные схемы]
* [http://en.wikipedia.org/wiki/Boolean_circuit Wikipedia {{---}} Boolean curcuit]
+
* [http://www.encyclopediaofmath.org/index.php/Contact_scheme Encyclopedia of Math {{---}} Contact sheme]
  
 
==Литература==
 
==Литература==
 
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике {{---}} М.:"ФИЗМАТЛИД", 2009 {{---}} стр. 312
 
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике {{---}} М.:"ФИЗМАТЛИД", 2009 {{---}} стр. 312

Версия 16:01, 6 января 2014

Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются контактные схемы.


Определение:
Контактная схема (англ. contact sheme) представляет собой ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами).


Принцип работы

Contact.png
Contactnot.png

Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины [math]u[/math] и [math]v[/math]. Тогда контактная схема вычисляет некоторую функцию [math]f[/math] между вершинами [math]u[/math] и [math]v[/math], равную 1 на тех наборах переменных, на которых между [math]u[/math] и [math]v[/math] есть путь по замкнутым ребрам.

Построение контактных схем

Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:

  • Конъюнкция
    Multiply.png

Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что последовательное соединение полюсов соответствует операции конъюнкции.

  • Дизъюнкция
    Disjunction.png

Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.

  • Отрицание

Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.

Задача о минимизации контактной схемы

Определение:
Две контактные схемы называются эквивалентными, если они реализуют одну и ту же булеву функцию.


Определение:
Сложностью контактной схемы называется число ее контактов.

Задача минимизации контактных схем состоит в том, чтобы по данной схеме [math]S[/math] найти схему [math]T[/math] , эквивалентную [math]S[/math] и имеющую наименьшую сложность. Один из путей решения этой задачи состоит в следующем:

  • Осуществляем переход от контактной схемы [math]S[/math] к её булевой функции [math]F(S)[/math].
  • Упрощаем [math]F(S)[/math], то есть отыскиваем функцию [math]G[/math] (на том же базисе, что и [math]F(S)[/math]), равносильную [math]F(S)[/math] и содержащую меньше вхождений атомарных формул.
  • Строим схему [math]T[/math], реализующую функцию [math]G[/math].

Ссылки

Литература

  • Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике — М.:"ФИЗМАТЛИД", 2009 — стр. 312