Построение сокращенных УБДР по формулам - часть 2

Вначале создадим корень, помеченный x1, и рассмотрим остаточные функции, получающиеся при x1=0 и x1 =1. Имеем

$f_0( x_2, x_3, x_4)= ( x_2 \wedge \neg x_4)\vee (\neg x_2 \wedge x_3) \vee (\neg x_2 \wedge x_4),\\ f_1( x_2, x_3, x_4)= ( x_2 \wedge x_4)\vee (\neg x_2 \wedge x_3) \vee (\neg x_2 \wedge x_4).\\$

Они разные и обе существенно зависят от x2. Поэтому добавим для каждой из них вершину, помеченную x2. Затем для каждой из них определим остаточные функции, получающиеся при x2=0 и x2 =1. Получим

$f_{00}( x_3, x_4)= (x_3 \vee x_4),\\ f_{01}( x_3, x_4)= \neg x_4,\\ f_{10}( x_3, x_4)= (x_3 \vee x_4),\\ f_{11}( x_3, x_4)= x_4.$

Так как f00=f10, а f01 и f11 от x3 не зависят, то нам потребуется только одна вершина, помеченая x3. Она будет представлять функцию f00=f10=(x3

x4). При x3=0 она превращается в x4, а при x3=1 равна константе 1. В результате получается УБДР Df, показанная на рис.3.6.

Рис. 3.6.

Содержание Назад Вперед