double arrow
Разложение булевой функции по переменным

Пусть s принимает значения 0 или 1, т.е. s {0, 1}.

Введем обозначение:

xs = Øx, если s = 0, xs = x, если s = 1.

Т.е. x0 = Øx, x1 = x.

Очевидно, что xs = 1, если x = s и xs = 0, если x s.

Теорема 4.5 (о разложении булевой функции по переменным).

Каждая булева функция f(x1, x2, ... , xn) может быть представлена в виде:

f(x1, x2, ... , xn) = f(x1, x2, ... , xm, xm+1, ... , xn) =

V x1s1&x2s2&...&xmsm& f(s1, s2, ... sm, xm+1, ... , xn), (4.1)

m n, где дизъюнкция берется по всем наборам (s1, s2, ... , sm) (их 2m).

Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2m = 22 =4) конъюнкции и имеет вид:

f(x1, x2, x3, x4) = x &x &f(0, 0, x3, x4) V x &x &f(0, 1, x3, x4) V x & x &f(1, 0, x3, x4) V x & x &f(1, 1, x3, x4) = Øx1x2&f(0, 0, x3, x4) V Øx1&x2&f(0, 1, x3, x4) V x1x2&f(1, 0, x3, x4) V x1&x2&f(1, 1, x3, x4).

Доказательство теоремы 4.5.

Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y1, y2, ... , ym, ym+1, ... , yn) .

Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).

В левой части получим f (y1, y2, ... , yn) .

Т. к. ys = 1 только, когда y = s, то среди 2m конъюнкций y1s1&y2s2&...&ymsm в правой части (4.1) только одна обратится в 1 – та, в которой y1 = s1,…, ym = sm. Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:

y1y1&y2y2&...&ymym&f(y1, y2, ... , ym, ym+1, ... , yn) = f(y1, y2, ... , yn) .

Теорема 4.5 доказана.

Теорема 4.6 (о представлении булевой функции формулой в СДНФ),

Всякая булева функция f(x1, x2, ... , xn),не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.




Доказательство.

При m = n получим важное следствие теоремы 4.5:

f(x1, x2, ... , xn) = V x1s1&x2s2&...&xnsn, (4.2)

f(s1, s2, ... , sn) = 1

где дизъюнкция берется по всем наборам (s1, s2, ... , sn), на которых f = 1.

Очевидно, что разложение (4.2) есть не что иное, как СДНФ формулы f, которая содержит столько конъюнкций, сколько единиц в таблице значений f. Следовательно, СДНФ для всякой булевой функции единственна с точностью до перестановки ее дизъюнктивных членов.

Очевидно также, что для булевой функции f(x1, x2, ... , xn), тождественно равной 0, разложение (2) не существует.

В силу изложенного для получения формулы булевой функции f(x1, x2, ... , xn) в СДНФ можно воспользоваться следующим алгоритмом.

Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).

Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f равно 1, т. е. f (s1, s2, ... , sn) = 1.



Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x1s1&x2s2&...&xnsn, где xisi = xi, если si = 1 и xisixi, если si = 0, i = 1, 2, ... ,n.

Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.

Пример 4.15.

Найдем формулу в СДНФ для функции f(x1, x2, x3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f(x1, x2, x3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.

2. Для каждой выбранной строки составляем конъюнкции по правилу, указанному в шаге 2. Получим соответственно для четырех выбранных строк:

x10&x21&x31 = Øx1 &x2&x3.

x11&x20&x30 = x1x2x3.

x11&x20&x31 = x1x2&x3 .

x11&x21&x31 = x1&x2&x3 .

3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:

f(x1, x2, x3) = Øx1&x2&x3V x1x2x3 V x1x2&x3 V x1&x2&x3.

Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.

Замечание. Если булева функция задана формулой в СДНФ, то, применяя алгоритм 4.3 в обратной последовательности, легко можем получить таблицу значений этой функции.

Теорема 4.7 (о представлении булевой функции формулой в СКНФ),

Всякая булева функция f(x1, x2, ... , xn),не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.

Доказательство.

Рассмотрим функцию Øf(x1, x2, ... , xn). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F1. Очевидно, условие, что функция Øf(x1, x2, ... , xn) не равна тождественно 0, равносильно условию, что функция f(x1, x2, ... , xn) не равна тождественно 1. Кроме того, по закону де Моргана формула F2 º ØF1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания

F2 º ØF1 º ØØf(x1, x2, ... , xn) º f(x1, x2, ... , xn),

что и доказывает теорему.

Для получения формулы булевой функции f(x1, x2, ... , xn) в СКНФ следует воспользоваться следующим алгоритмом.

Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)

Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f (s1, s2, ... , sn) = 0.

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию

x1 Øs1Vx2Øs2V...VxnØsn, где xi Øsi = xi, если si = 0 и xi Øsi = Øxi, если si = 1, i = 1, 2, ... , n.

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.

Пример 4.16.

Найдем формулу в СКНФ для функции f(x1, x2, x3), заданной таблицей 4.4.

1. Выберем в таблице строки, где f(x1, x2, x3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.

2. Для каждой выбранной строки составляем дизъюнкции по правилу, указанному в шаге 2. Получим соответственно для трех выбранных строк:

x11Vx21Vx31 = x1Vx2Vx3.

x11Vx21Vx30 = x1Vx2x3.

x11Vx20Vx31 = x1x2Vx3.

x10Vx20Vx31 = Øx1x2V x3.

3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ:

f(x1, x2, x3) = ( x1Vx2Vx3)&(x1Vx2x3)&(x1x2Vx3)&(Øx1x2Vx3).

Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.

Замечание. Т. к. всего строк в таблице функции 2n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p+q=2n.

Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 23.






Сейчас читают про: