Как и в случае БДР, УБДР реализует булеву функцию f(x1, …, xn), если для каждого набора значений переменных ?1, ?2, …, ?n путь в диаграмме, начинающийся в корне и соответствующий этому набору (из вершины xi идем по ребру, помеченному ?i), завершается стоком с меткой f(?1, ?2, …, ?n).
Из этого определения непосредственно следует, что каждая внутренняя вершина диаграммы v, помеченная переменной x
Пример 3.2. Реализуем с помощью УБДР функцию f1(x,y,z), представленную выше в примере 3.1, с помощью БДР T1 и таблицы 3.1.
Вначале зафиксируем порядок переменных: x < y < z. Объединив листья с одинаковыми метками и две z- вершины с одинаковыми потомками, получим УБДР D1, приведенную на рис.3.2.
Ясно, что реализация функции f1(x,y,z) с помощью УБДР D1 намного компактнее, чем с помощью БДР T1.
Под сложностью L(D) УБДР D будем понимать число внутренних вершин в D. Например, L(D1)=4. Может ли сложность диаграммы для некоторой функции зависеть от порядка переменных? Да! Рассмотрим порядок переменных y < x < z. Как показывает следующий рисунок, относительно этого порядка функцию f(x,y,z) можно реализовать УБДР D2 со сложностью L(D2)=3.