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

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

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

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

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

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

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

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

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

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

~

~

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

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