Раздел 4 синтез управляющих систем

4.1. Схемы из функциональных элементов

Одним из интересных примеров приложения алгебры логики является теория управляющих систем. Основными классами «дискретных» управляющих систем являются контактные схемы, формулы, схемы из функциональных элементов (СФЭ).

В данном разделе остановимся на синтезе СФЭ. Рассмотрим такие дискретные преобразователи, т.е. устройства, которые обладают некоторым числом входов и выходов. Наборы сигналов, поступающие на входы и возникающие на выходах, принадлежат известным конечным множествам.

Устройства осуществляют преобразования входных сигналов в выходные. Выделим такой класс устройств, в которых время преобразования существенно мало по сравнению с длительностью сигналов (другими словами, временем преобразования в которых можно пренебречь). Математической моделью таких устройств и являются так называемые схемы из функциональных элементов.

Задача синтеза управляющих систем является одной из основных задач кибернетики. В общих чертах эта задача может быть сформулирована следующим образом. Пусть задан запас элементарных средств. Заданы правила построения из них более сложных образований – схем. Задан способ нахождения по схеме реализуемой ею функции. Задача синтеза состоит в получении для каждой функции наилучшей схемы, реализующей эту функцию.

Обозначения, используемые в дальнейшем в данном разделе:

–знак сложения по модулю 2;

log a – двоичный логарифм a;

[a] – наибольшее целое число, не превосходящее a;

< – неравенство, справедливое при достаточно больших n;





(асимптотически равно) –;

(и– величины одного порядка) –.

4.2. Определение схем из функциональных элементов

Определение схемы из функциональных элементов распадается на две части. Вначале определяется один вспомогательный объект – сеть, а уже потом с его помощью определяется схема. Понятие сеть играет чисто вспомогательную роль и используется только для определения схемы из функциональных элементов. Сеть строится из полюсов и элементов.

○ – полюс (полюсы будем изображать маленькими кружочками)

1…n

–элемент (каждый элемент имеет несколько входов, занумерованных числами 1, 2, …, и один выход; элементы будем изображать в виде треугольников с отростками, отростки сверху соответствуют входам элемента, а отросток снизу – его выходу).

Определение логической сети:

1. Полюс есть логическая сеть, при этом он является ее единственной вершиной.

2. Если S₁ и S₂ – логические сети без общих вершин, то их объединение есть логическая сеть , вершинами которой являются вершины исходных логических сетейи.

3. Если S – логическая сеть и E – элемент (входы и выход которого не являются вершинами S), то результат присоединения всех входов элемента E к некоторым вершинамS есть снова логическая сеть. При этом к одной вершине S могут присоединяться различные входы элемента Е, но каждый вход присоединяется только к одной вершине. Вершинами новой логической сети являются вершины S

и выход элемента E.

Определение схемы. Схемой из функциональных элементов (СФЭ) называется логическая сеть, в которой:

1) Каждому полюсу приписана одна из переменных x₁, …, x_n, …, причем, разным полюсам – разные переменные, полюсы называются входами схемы;

2) Каждому элементу E с r входами поставлена в соответствие некоторая функция алгебры логики φ_Е (y₁,…,y_r), существенно зависящая от r аргументов (при r=0 функция φ_Е есть константа) и называемая функцией элемента E; элемент E с сопоставленной ему функцией φ_Е называется функциональным элементом;

3) Вершины, которым приписано хотя бы одно из чисел, отмечены символом *. Эти вершины называются выходами схемы; l-м выходом из системы будем называть единственный выход, которому приписано число l.