Раздел 7. Ограниченно-детерминированные (автоматные) функции

Предисловие

Мы познакомились с двумя функциональными системами с операциями:

(Р₂, C) – алгебра логики – система функций алгебры логики с операцией суперпозиции;

(Р_к, C) - k- значная логика – система функций k- значной логики с операцией суперпозиции.

Путем вариации функционального объекта и операции можно получать другие системы. Так, усложняя функциональные объекты, естественным образом получаем:

( ,С) – счетнозначную логику, т.е. систему, содержащую константы 0,1,...,k,... и функции f (x₁,...,x_n), переменные которых определены на расширенном натуральном ряде = {0, 1, 2,...}, а сами функции принимают значения на , с операцией суперпозиции.

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

Детерминированные функции

Определение. Пусть дан алфавит . Конечную последовательность символов этого алфавита будем называть словом в алфавите .

– длина слова ; , где – пустое слово.

Множество обозначает множество всех слов , которые имеют длину, равную :

.

- множество, которое состоит из пустого слова и объединения множеств , где :

.

Отметим, - счетное множество.

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

Определение. Функция называется детерминированной, если выполнены два условия:

1. Для его образ, т.е. , имеет длину такую же, что и .

2. Пусть даны два слова из :

, ;

и пусть , .

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

Множество всех детерминированных функций (д. функций) обозначим через .

Свойство детерминированной функции

Пусть . Тогда выходной символ в m-м разряде есть некоторая функция от входных символов от 1 до m.

Доказательство. , т.е. y=f(x) , где x – входное слово, а – выходное слово. Итак, любое слово отображается в слово , где

,

.

Тогда – некоторая функция алгебры логики, которая зависит от . Аналогично, , т.е. для есть функция .

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

Примеры детерминированных и недетерминированных функций

1. , которая осуществляет это отображение по следующему правилу:

, при этом , где .

Является ли детерминированной функцией?

► Детерминированность функции проверим по определению. Первое условие выполняется, т.к. . Проверим второе условие, оно доказывается идентично:

где

по условию, x(m ) =z(m), то , где

Функция f является детерминированной.

2. - , , . Является ли д. функцией?

► a)

2. ,

.

При этом , где . Тогда . По условию (или ). Отсюда , т.е. , где . Функция является детерминированной.

3. - , при этом:

для .

Является ли д.функцией?

► Да, т.к. в m-м разряде однозначно определяется по первым m разрядам .

Бывают и недетерминированные функции, которые отображают множество .

4. .

Пусть , , где ; .

5. - , причем , , . - недетерминированная функция. Для доказательства приведем пример двух последовательностей конечной длины: , , где . Тогда , , но . Получили противоречие с условием 2 определения д.функции, значит, .