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

Задача синтеза состоит в том, чтобы по заданной системе ФАЛ F построить реализующую её схему из выбранного полного класса U и минимизировать заданный монотонный функционал сложности Ψ. Сложность функции или системы функций определяется как минимум Ψ(Σ) по всем схемам Σ∈U, реализующим F. Схема, на которой этот минимум достигается, называется минимальной.1

Для оценки наихудшего случая вводится функция Шеннона \(\Psi(n)=\max_{f\in P_{2}(n)}\Psi(f)\). Значение сложности всегда зависит от выбранной модели схем и функционала: одна и та же ФАЛ может иметь разную сложность в формулах, СФЭ и контактных схемах.1

Что важно запомнить
  • Синтез задаётся тройкой: требуемое функционирование, класс схем U, функционал Ψ.
  • Ψ(F)=min Ψ(Σ) по всем Σ, реализующим F.1
  • Минимальная схема реализует F и достигает этого минимума.
  • Функция Шеннона Ψ(n) — максимальная сложность среди n-местных ФАЛ.
  • При расширении класса схем минимальная сложность не увеличивается.
  • Для системы \(F=(f_{1},\ldots,f_m)\): \(\max_i L(f_i)\le L(F)\le \sum_i L(f_i)\).1

Формальная постановка задачи синтеза

Пусть U — полный класс схем: любую систему ФАЛ можно реализовать некоторой схемой из U. Пусть \(\Psi:U\to\mathbb{R}_{+}\) — функционал сложности. В курсе предполагается его монотонность: удаление вершин или рёбер не увеличивает Ψ. Тогда

\(\Psi(F)=\min\{\Psi(\Sigma):\Sigma\in U,\ \Sigma\text{ реализует }F\}\). 1

Схема Σ, для которой \(\Psi(\Sigma)=\Psi(F)\), называется минимальной относительно U и Ψ. Благодаря монотонности минимум достаточно искать среди приведённых схем: бесполезные элементы можно удалить без ухудшения функционирования и без роста сложности.

Почему сложность не является свойством функции «сама по себе»

Нужно всегда указывать модель. Например, класс СФЭ шире класса формул, а класс контактных схем шире π-схем. Поэтому при одном и том же функционале выполняются неравенства вида \(\Psi^C(F)\le\Psi^\Phi(F)\) и \(\Psi^K(F)\le\Psi^\pi(F)\). Более богатая модель может использовать структурные возможности, которых нет в её подклассе.1

Функция Шеннона

Чтобы характеризовать трудность всего множества n-местных функций, вводят

\(\Psi (n)=\max_{f\in P_{2}(n)} \Psi (f)\).

Это сложность самой трудной функции от n переменных в выбранном классе схем. Асимптотическое исследование Ψ(n) — центральная задача теории сложности управляющих систем.

Системы функций

Для \(F=(f_{1},\ldots,f_m)\) при функционале L очевидны границы

\(\max_i L(f_i)\le L(F)\le \sum_i L(f_i)\). 1

Нижняя оценка следует из того, что схема должна реализовать каждую компоненту. Верхняя получается объединением отдельных схем для \(f_i\). Реальная оптимальная система может быть меньше суммы, если компоненты совместно используют промежуточные вычисления.

Пример простыми словами

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

Частые ошибки
  • Говорить о «сложности функции» без указания класса схем и функционала.
  • Считать любой алгоритм построения схемы решением задачи минимального синтеза. Он даёт реализацию, но минимальность нужно отдельно доказать.
  • Путать функцию Шеннона со средней сложностью. Это максимум по всем функциям от n переменных.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 3, §1, постановка задачи синтеза и функция Шеннона, МГУ, факультет ВМК