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

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

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

(x ₁, x ₂, …, x _n, t) (7.1)

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

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

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

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

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

y = φ(x ₁, x ₂, …, x_n, t)

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

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

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

y = φ(x ₁, x ₂, …, x _n, t),

где

0 ≤ t ≤ s – 1

равно 2^{s ·2 п}

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

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