Одним из предшественников УБДР являются бинарные деревья решений.
Определение 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 (на всех рисунках предполагается, что ребра направлены сверху вниз).
По определению 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 переменных
Упорядоченная бинарная диаграмма решений относительно порядка переменных