 |
Разложение булевой функции по переменным
|
|
|
|
Пусть s принимает значения 0 или 1, т.е. s 
{0, 1}.
Введем 
обозначение:
xs = Ø x, если s = 0, xs = x, если s = 1.
Т.е. x 0 = Ø x, x 1 = x.
Очевидно, что xs = 1, если x = s и xs = 0, если x 
s.
Теорема 4.5 (о разложении булевой функции по переменным).
Каждая булева функция f (x 1, x 2,..., xn) может быть представлена в виде:
f (x 1, x 2,..., xn) = f (x 1, x 2,..., xm, xm +1,..., xn) =
V x 1 s 1& x 2 s 2&...& xmsm & f (s 1, s 2,... sm, xm +1,..., xn), (4.1)
m 
n, где дизъюнкция берется по всем наборам (s 1, s 2,..., sm) (их 2 m).
Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2 m = 22 =4) конъюнкции и имеет вид:
f (x 1, x 2, x 3, x 4) = x 
& x 
& f (0, 0, x 3, x 4) V x & x 
& f (0, 1, x 3, x 4) V x 
& x & f (1, 0, x 3, x 4) V x & x & f (1, 1, x 3, x 4) = Ø x 1&Ø x 2& f (0, 0, x 3, x 4) V Ø x 1& x 2& f (0, 1, x 3, x 4) V x 1&Ø x 2& f (1, 0, x 3, x 4) V x 1& x 2& f (1, 1, x 3, x 4).
Доказательство теоремы 4.5.
Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y 1, y 2,..., ym, ym +1,..., yn).
Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).
В левой части получим f (y 1, y 2,..., yn).
Т. к. ys = 1 только, когда y = s, то среди 2 m конъюнкций y 1 s 1& y 2 s 2&...& ymsm в правой части (4.1) только одна обратится в 1 – та, в которой y 1 = s 1,…, ym = sm. Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:
y 1 y 1& y 2 y 2&...& ymym & f (y 1, y 2,..., ym, ym +1,..., yn) = f (y 1, y 2,..., yn).
Теорема 4.5 доказана.
Теорема 4.6 (о представлении булевой функции формулой в СДНФ),
Всякая булева функция f (x 1, x 2,..., xn),не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.
Доказательство.
При m = n получим важное следствие теоремы 4.5:
f (x 1, x 2,..., xn) = V x 1 s 1& x 2 s 2&...& xnsn, (4.2)
|
|
|
f (s 1, s 2,..., sn) = 1
где дизъюнкция берется по всем наборам (s 1, s 2,..., sn), на которых f = 1.
Очевидно, что разложение (4.2) есть не что иное, как СДНФ формулы f, которая содержит столько конъюнкций, сколько единиц в таблице значений f. Следовательно, СДНФ для всякой булевой функции единственна с точностью до перестановки ее дизъюнктивных членов.
Очевидно также, что для булевой функции f (x 1, x 2,..., xn), тождественно равной 0, разложение (2) не существует.
В силу изложенного для получения формулы булевой функции f (x 1, x 2,..., xn) в СДНФ можно воспользоваться следующим алгоритмом.
Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).
Шаг 1. Выбираем в таблице все наборы переменных s 1, s 2,..., sn, для которых значение f равно 1, т. е. f (s 1, s 2,..., sn) = 1.
Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x 1 s 1& x 2 s 2&...& xnsn, где xisi = xi, если si = 1 и xisi =Ø xi, если si = 0, i = 1, 2,..., n.
Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.
Пример 4.15.
Найдем формулу в СДНФ для функции f (x 1, x 2, x 3), заданной таблицей 4.4.
1. Выберем в таблице строки, где f (x 1, x 2, x 3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки.
2. Для каждой выбранной строки составляем конъюнкции по правилу, указанному в шаге 2. Получим соответственно для четырех выбранных строк:
x 10& x 21& x 31 = Ø x 1 & x 2& x 3.
x 11& x 20& x 30 = x 1&Ø x 2&Ø x 3.
x 11& x 20& x 31 = x 1&Ø x 2& x 3 .
x 11& x 21& x 31 = x 1& x 2& x 3 .
3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ:
f (x 1, x 2, x 3) = Ø x 1& x 2& x 3V x 1&Ø x 2&Ø x 3 V x 1&Ø x 2& x 3 V x 1& x 2& x 3.
Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ.
Замечание. Если булева функция задана формулой в СДНФ, то, применяя алгоритм 4.3 в обратной последовательности, легко можем получить таблицу значений этой функции.
|
|
|
Теорема 4.7 (о представлении булевой функции формулой в СКНФ),
Всякая булева функция f (x 1, x 2,..., xn),не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.
Доказательство.
Рассмотрим функцию Ø f (x 1, x 2,..., xn). В соответствии с теоремой 4.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F 1. Очевидно, условие, что функция Ø f (x 1, x 2,..., xn) не равна тождественно 0, равносильно условию, что функция f (x 1, x 2,..., xn) не равна тождественно 1. Кроме того, по закону де Моргана формула F 2 º Ø F 1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания
F 2 º Ø F 1 º ØØ f (x 1, x 2,..., xn) º f (x 1, x 2,..., xn),
что и доказывает теорему.
Для получения формулы булевой функции f (x 1, x 2,..., xn) в СКНФ следует воспользоваться следующим алгоритмом.
Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)
Шаг 1. Выбираем в таблице все наборы переменных s 1, s 2,..., sn, для которых значение f (s 1, s 2,..., sn) = 0.
Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию
x 1 Ø s 1V x 2Ø s 2V...V xn Ø sn, где xi Ø si = xi, если si = 0 и xi Ø si = Ø xi, если si = 1, i = 1, 2,..., n.
Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ.
Пример 4.16.
Найдем формулу в СКНФ для функции f (x 1, x 2, x 3), заданной таблицей 4.4.
1. Выберем в таблице строки, где f (x 1, x 2, x 3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки.
2. Для каждой выбранной строки составляем дизъюнкции по правилу, указанному в шаге 2. Получим соответственно для трех выбранных строк:
x 11V x 21V x 31 = x 1V x 2V x 3.
x 11V x 21V x 30 = x 1V x 2VØ x 3.
x 11V x 20V x 31 = x 1VØ x 2V x 3.
x 10V x 20V x 31 = Ø x 1VØ x 2V x 3.
3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ:
f (x 1, x 2, x 3) = (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1VØ x 2V x 3)&(Ø x 1VØ x 2V x 3).
Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ.
Замечание. Т. к. всего строк в таблице функции 2 n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p + q =2 n.
Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 23.
|
|
|
|
|
|
