Введение в схемы, автоматы и алгоритмы
Основные определения
Одним из предшественников УБДР являются бинарные деревья решений.
Определение 3.1.
Бинарное дерево решений (БДР) - это бинарное дерево T=(V,E), все внутренние вершины которого помечены переменными, а листья - значениями 0 или 1. Из каждой внутренней вершины v выходят 2 ребра, одно помечено 0, другое - 1; вершина w0, в которую ведет ребро, помеченное 0, называется 0-сыном v, а вершина w1, в которую ведет ребро, помеченное 1, называется 1-сыном v.
Такое дерево, вершины которого помечены переменными x1, …, xn реализует булеву функцию f(x1, …, xn), если для каждого набора значений переменных ?1, ?2, …, ?n ветвь в дереве, соответствующая этому набору (из вершины xi идем по ребру, помеченному ?i), завершается листом с меткой f(?1, ?2, …, ?n).
Пример 3.1. Например, рассмотрим изображенное ниже БДР T1 (на всех рисунках предполагается, что ребра направлены сверху вниз).
Рис. 3.1.
По определению T1 реализует функцию f1(x,y,z), представленную в таблице 3.1.
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1. | 1 | 0 |
Нетрудно построить ДНФ этой функции: f(x, y, z) = (¬ x
УБДР являются модификацией БДР, в которой все листья с одной меткой представлены одной вершиной, в каждую вершину может входить несколько ребер, возможен выбор порядка появления переменных на ветвях.
Определение 3.2. Пусть зафиксирован некоторый порядок n переменных
Упорядоченная бинарная диаграмма решений относительно порядка переменных
- существует лишь две вершины, из которых не выходят ребра; они помечены константами 0 и 1 и называются стоками;
- остальные (внутренние) вершины помечены переменными и из каждой из них выходят два ребра, одно помечено 0, другое - 1;
- порядок, в котором переменные встречаются на любом пути из корня в сток, совместим с , т.е. если из вершины, помеченной x(i), есть путь в вершину, помеченную x(j), то i < j.
