ГЛАВА III. ОБЩИЕ ПОНЯТИЯ О КОНЕЧНЫХ АВТОМАТАХ И ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИНАХ

§ 3.1. Дискретное время и такты

Пусть — алфавиты, содержащие некоторое конечное число символов.

Тогда функциональная зависимость

ставит в соответствие любой совокупности символов, взятых по одному из алфавитов , символ из алфавита .

Рассмотрим теперь воображаемое идеальное устройство, реализующее функциональную зависимость (3.1). Это устройство имеет входов и один выход. К входам строго одновременно подводятся символы из алфавитов соответственно. В это же мгновение на выходе появляется символ из алфавита в соответствии с равенством (3.1). Такое мгновенно действующее идеальное устройство назовем функциональным преобразователем. В частном случае, когда каждый из алфавитов содержит только по два символа, т. е. когда и у — логические переменные, a f — логическая функция, устройство будет называться логическим преобразователем.

Однотактные релейно-контактные схемы и другие технические средства, реализующие операции исчисления высказываний и описанные в гл. II, если считать их мгновенно действующими, являются техническими примерами реализации абстрактного понятия «логический преобразователь».

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

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

В отличие от этого привычного рассмотрения времени, при изучении устройств дискретного действия удобно вводить в рассмотрение воображаемое дискретное время. Представим себе, что непрерывная числовая полуось времени разбита каким-либо образом на бесконечное число конечных интервалов, не обязательно равных между собой (рис. 3.1). Двигаясь вдоль оси от , обозначим точки, разделяющие интервалы, буквами . Эти точки образуют счетное множество.

Условимся далее вместо . писать просто ряд неотрицательных целых чисел . и называть дискретным временем t воображаемое время, которое принимает последовательно лишь эти целочисленные значения.

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

Текущий такт, т. е. такт, соответствующий настоящему моменту, обозначим буквой .

Рис. 3.1.

Тогда символы t делятся тактом на предыдущие и последующие ) (рис. 3.2).

Рис. 3.2.

До сих пор, говоря о равенстве (3.1), мы считали, что переменные фиксированы. Предположим теперь, что символы, соответствующие переменным , меняются в дискретном времени. Иначе говоря, в каждый такт . заданы определенные значения переменных и тем самым определены функции , заданные на натуральном ряде чисел . и принимающие значения из алфавитов . Согласно (3.1) им тогда ставится в соответствие функция

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

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

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

Рассмотрим в качестве примера случай, когда — логическая переменная и значения ее в любой момент определяются как отрицание значения у в предыдущий момент

Хотя соотношение

противоречиво, равенство (3.4) не приводит к противоречиям и определяет функцию , которая принимает последовательно значения 1 и 0, несмотря на то, что отсутствуют какие-либо входные (внешние) воздействия.

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

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