ГЛАВА ШЕСТАЯ. РЕКУРРЕНТНЫЕ БУЛЕВЫ ФУНКЦИИ

6-1. ОБЩИЕ ОПРЕДЕЛЕНИЯ

Будем рассматривать некоторую функцию зависящую от времени. Через будем обозначать значение этой функции в момент времени аналогично тому, как это делалось для ВБФ. Предположим, что может принимать значения 0 или 1.

Рассмотрим множество векторов

координаты которых принимают значения 0 или 1.

Набором будем называть фиксированный вектор из множества где

Произведем однозначное отображение векторов из на множество

Определение 6-1. Функция, дающая однозначное отображение множества на множество , называется рекуррентной булевой функцией первого рода (РБФ-1).

Рис. 6-1.

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

В этом соотношении может иметь значение от 1 до

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

где

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

Окончательно получим следующее соотношение, определяющее рекуррентную булеву функцию первого рода:

Физически эта собственная функция реализуется в виде схем с входами и линиями обратной связи (рис. 6-1,а).

Определение 6-2. Рекуррентная булева функция первого рода, не зависящая от аргументов называется вырожденной рекуррентной булевой функцией первого рода (ВРБФ-1).

ВРБФ-1 задается следующим соотношением:

Физически в схеме, соответствующей собственной функции (6-4), отсутствуют внешние входы (рис. 6-1, б).

Рассмотрим ряд примеров.

Пример 6-1.

Ясно, что данная ВРБФ-1 может быть определена соотношением

Пример 6-2.

Рассмотрим несколько первых значений этой функции:

Отсюда получаем Для любого

Пример 6-3. Имеем следующую схему задания функции:

Подсчитаем несколько первых значений функции

Напомним, что при любом совпадает с Тогда получим:

Рассмотрим теперь наборы следующего вида:

В этих наборах соответствует значению входного аргумента в момент времени При этом равно либо 0, либо 1.

Определение 6-3. Функция, дающая однозначное отображение множества О на множество называется рекуррентной булевой функцией второго рода (РБФ-2).

Пример 6-4.

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

Тогда

Пример 6-5.

Пусть входная последовательность имеет вид:

На выходе в соответствующие моменты времени будут появляться следующие значения функции:

Рассмотрим множество векторов

В конкретных наборах величины и могут принимать следующие значения:

Векторы из (6-6) представляют собой объединение векторов из Получим определение, обобщающее определения 6-2 и 6-3.

Определение 6-4. Функция, дающая однозначное отображение множества Т в множество называется рекуррентной булевой функцией (РБФ).

Пример 6-6.

Имеем:

Пример 6-7. Дана система рекуррентных булевых функций:

Вычислим несколько первых значений функций

Пусть

Тогда имеем для