Для доказательства полноты системы {f1, f2} в классе конечно-автоматных функций относительно операций суперпозиции и введения обратной связи, нам нужно показать, что с помощью этих функций можно выразить любую конечно-автоматную функцию.

Шаг 1: Понимание функций f1 и f2

• f1: y(t) = 0 — это константная функция, которая всегда возвращает 0, независимо от входных данных.
• f2: y(t) = (x1(t) ∨ ¬x3(t))(¬x2(t) ∨ q(t-1)) — это более сложная функция, которая зависит от трех входных переменных и значения предыдущего состояния q(t-1).

Шаг 2: Определение функции q

Функция q(t) также представлена в задании: q(t) = (x1(t) ∨ ¬x2(t))(x3(t) ∨ q(t-1)), с начальным состоянием q(0) = 1. Это означает, что значение q зависит от входных переменных и предыдущего значения q.

Шаг 3: Использование операций суперпозиции и обратной связи

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

Шаг 4: Построение произвольной конечно-автоматной функции

Для доказательства полноты мы можем построить произвольную функцию, используя комбинации f1 и f2. Например, если мы хотим создать функцию, которая зависит от n входных переменных, мы можем использовать f2, чтобы комбинировать результаты от этих переменных и использовать q для хранения состояния.

Шаг 5: Пример построения

1. Предположим, что у нас есть 3 входные переменные x1, x2, x3.
2. Сначала мы можем задать начальное состояние q(0) = 1, как указано.
3. Далее, используя f2, мы можем вычислить y(t) на основе значений x1, x2, x3 и предыдущего состояния q.
4. Затем, используя q(t), мы можем обновить состояние для следующего времени, что позволяет нам создавать последовательные вычисления.

Шаг 6: Заключение

Таким образом, с помощью функций f1 и f2, используя суперпозицию и обратную связь, мы можем выразить любую конечно-автоматную функцию. Это и доказывает полноту системы {f1, f2} в классе конечно-автоматных функций.