Общие понятия

Cхема из функциональных элементов (CФЭ) является математической моделью дискретных преобразователей без памяти. Дискретные преобразователи – устройства с некоторым количеством входов:  и выходов: . Наборы сигналов на входах и выходах принадлежат известным множествам. Cигналы , подаваемые на входы, принадлежат , выходные сигналы  принадлежат , где .

Длительность сигнала существенно больше, чем время его обработки, поэтому временем выработки выходного сигнала можно пренебречь, т. е. можно считать, что после поступления входного сигнала мгновенно появился выходной сигнал. CФЭ моделирует именно такие дискретные преобразователи.

Базисом схемы называется набор некоторых объектов , называемых элементами. В схемах из функциональных элементов  – функции алгебры логики (отсюда и название: схемы из функциональных элементов). Каждое  зависит от  переменных, которые называются входами элемента. Базис  называется стандартным.

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

1) в графе нет ориентированных циклов;

2) любой вершине  графа приписана переменная, причем разным вершинам графа приписаны разные переменные;

3) каждой вершине , в которую входит  дуг, сопоставлен элемент из базиса , зависящий от  переменных, которые взаимно однозначно соответствуют дугам, входящим в ;

4) в множестве вершин графа выделено некоторое подмножество вершин, которые называются выходными.

Переменные, соответствующие выходным вершинам, также называются выходными.

В любом орграфе без орциклов существует хотя бы одна вершина, куда не входит ни одна дуга (см. «Теорию графов»). Вершины CФЭ, куда не входит ни одна дуга, называются входами схемы, а соответствующие им переменные – входными переменными.

Пример 1. .

а

Здесь стрелками отмечены выходные вершины. CФЭ принято рисовать так, как показано на рис. 6.1, б.   Рис. 6.1

б

Подсхемой схемы из функциональных элементов называется любой подграф, обладающий свойством:

если  – вершина, вошедшая в подсхему, то дуги, входящие в эту вершину в графе, либо все входят в подсхему, либо все не входят в нее. Те вершины подсхемы, куда не входит ни одна дуга, называются входами подсхемы.

Пример 2.

а                               б Рис. 6.2

а – подсхема схемы из примера 1;

б – не является подсхемой, так как в вершину  в схеме входило 2 дуги, а здесь только одна.

Набор значений всех переменных, сопоставленных вершинам, называется допустимым для данной CФЭ, если для любой вершины  с функциональным элементом , куда входят  дуг , выходящих из вершин , и каждой вершине  соответствует значение переменной , то вершине  должно соответствовать значение переменной .

Так, для схемы, приведенной в примере 1, допустимым набором значений переменных будет, например, такой:

 или такой:

.

Множество дуг, входящих в вершину , называется пучком с центром в (рис. 6.3).

Рис. 6.3

Cложностью схемы называется число пучков, которое равно числу вершин, исключая входные, сложность схемы будем обозначать буквой .