Временные булевы функции. Основные определения

Синтез и анализ схем, работа которых зависит от времени

Будем рассматривать все возможные наборы вида

(4.1)

В этих наборах величины х_i(i=1, 2, ..., п) могут принимать в качестве своих значений только 0 или 1, а величина t — любые целочисленные значения от 0 до s—1 включительно. Для таких наборов справедлива следующая теорема.

Теорема. Общее число различных наборов вида (4-1) при некотором фиксированном значении п равно s∙2ⁿ.

Действительно, общее число различных наборов вида <х₁, х₂, .... х_п> есть 2^п. Присоединяя к каждому из этих 2^п различных наборов всевозможные значения t, получим утверждение теоремы. Теперь введем основное определение.

Определение. Функция, определенная на наборах вида (4—1) и принимающая в качестве своих возможных значений 0 или 1, называется временной булевой функцией (сокращенно ВБФ).

Нетрудно понять, что если временная булева функция

зависит от времени (t) несущественно, то она превращается в обычную функцию алгебры логики.

Общее число различных ВБФ, зависящих от х₁, х₂, ..., х_п и t, определяется с помощью следующей теоремы.

Теорема. Общее число различных временных булевых функций вида

Доказательство этой теоремы полностью совпадает. с доказательством теоремы 1 для функции алгебры логики.

Сформулированные теоремы свидетельствуют о том, что любую временную булеву функцию можно полностью описать с помощью конечной таблицы.