Представление формул деревьями и оптимизация формул по глубине

Дерево формулы — упорядоченное ориентированное корневое дерево, которое точно отражает синтаксическую структуру формулы. Листья помечаются входными переменными, внутренние вершины — функциональными символами базиса, а корень соответствует всей формуле. Число листьев равно рангу R(F), число внутренних вершин равно сложности L(F), а глубина корня равна D(F).1

Оптимизация по глубине выполняется среди подобных формул, получаемых перестановкой аргументов и изменением порядка выполнения однотипных операций ∧ и ∨. Для формулы над Б₀ с поднятыми отрицаниями существует подобная формула F̌ с \(D(\check F)\le \lceil \log_{2}(L(F)+1)\rceil+\operatorname{Alt}(F)\), где Alt(F) — максимальное число чередований ∧ и ∨ вдоль пути дерева. Для одной конъюнкции или дизъюнкции достигается минимальная глубина ⌈log₂(L+1)⌉.1

Что важно запомнить
  • Листья дерева формулы соответствуют вхождениям переменных, внутренние вершины — операциям базиса.
  • R(F) — число листьев, L(F) — число внутренних вершин, D(F) — глубина корня.
  • Для формул базиса {∧,∨,¬} выполняется нижняя оценка \(D(F)\ge \lceil \log_{2}(L(F)+1)\rceil\).1
  • Подобные формулы реализуют одну функцию и отличаются только перестановкой аргументов и расстановкой скобок в цепочках ∧/∨.
  • Балансировка дерева уменьшает глубину и моделирует распараллеливание вычисления.1

Как формула задаётся деревом

Формуле над базисом Б индуктивно сопоставляют упорядоченное ориентированное корневое дерево. Если формула состоит из одной переменной, дерево имеет одну вершину. Для \(F=\varphi(F_{1},\ldots,F_k)\) берут деревья подформул \(F_{1},\ldots,F_k\), добавляют новый корень с меткой φ и соединяют его с корнями поддеревьев в порядке аргументов. Глубина построенного дерева совпадает с глубиной формулы.1

Это представление сохраняет всю позиционную структуру: каждой позиционной подформуле соответствует определённое корневое поддерево и наоборот. Поэтому дерево удобно для анализа сложности и эквивалентных перестроений формулы.

Функционалы через дерево

Для формул курса R(F) равно числу листьев дерева, L(F) — числу остальных, то есть внутренних, вершин, а D(F) — глубине корня. Для базиса Б₀={∧,∨,¬} из структурных соотношений следует важная нижняя граница \(D(F)\ge \lceil \log_{2}(L(F)+1)\rceil\). Она показывает, что при фиксированном числе операций глубину нельзя уменьшать произвольно.1

Подобные формулы и оптимизация глубины

Формулы называют подобными, если одну можно получить из другой применением коммутативности и ассоциативности ∧ и ∨. Такие преобразования не меняют число операций и переменных, но меняют форму дерева и потому могут менять глубину. В лекциях подчёркивается вычислительный смысл: L связано с объёмом последовательной работы, а D — с временем параллельного вычисления при неограниченном числе процессоров. Поэтому балансировка дерева является частным случаем распараллеливания.1

Для формулы F над Б₀ с поднятыми отрицаниями вводится Alt(F) — максимальное число смен операций ∧ и ∨ вдоль пути дерева. Теорема курса гарантирует существование подобной формулы F̌ такой, что \(D(\check F)\le \lceil \log_{2}(L(F)+1)\rceil+\operatorname{Alt}(F)\). Для элементарной конъюнкции или дизъюнкции, где чередований нет, существует подобная формула глубины ровно ⌈log₂(L+1)⌉, и эта глубина минимальна. Для любой ДНФ или КНФ можно получить подобную формулу с глубиной не больше ⌈log₂(L(A)+1)⌉+1.1

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

Пусть нужно вычислить конъюнкцию восьми переменных. Запись (((((((x₁∧x₂)∧x₃)∧x₄)∧x₅)∧x₆)∧x₇)∧x₈) имеет глубину 7. Если сгруппировать переменные попарно, затем объединять результаты попарно, получится сбалансированное дерево глубины 3. Функция и число операций не изменятся, но критический путь станет намного короче.

Частые ошибки
  • Путать дерево формулы с произвольной СФЭ. У дерева каждая внутренняя вершина, кроме корня, используется ровно одним родителем, а в СФЭ результат может разветвляться.
  • Считать, что подобные формулы могут отличаться функцией. Подобие строится на эквивалентных перестановках и ассоциативных перегруппировках.
  • Отождествлять L(F) и D(F). Большая формула может иметь малую глубину после балансировки.

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

Источники

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