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

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

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

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

Т.е. x ⁰ = Ø x, x ¹ = x.

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

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

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

f (x ₁, x ₂,..., x_n) = f (x ₁, x ₂,..., x_m, x_{m +1},..., x_n) =

V x ₁ ^{s 1}& x ₂ ^{s 2}&...& x_m^sm & f (s ₁, s ₂,... s_m, x_{m +1},..., x_n), (4.1)

 

m n, где дизъюнкция берется по всем наборам (s ₁, s ₂,..., s_m) (их 2 ^m).

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

f (x ₁, x ₂, x ₃, x ₄) = x & x & f (0, 0, x ₃, x ₄) V x & x & f (0, 1, x ₃, x ₄) V x & x & f (1, 0, x ₃, x ₄) V x & x & f (1, 1, x ₃, x ₄) = Ø x ₁&Ø x ₂& f (0, 0, x ₃, x ₄) V Ø x ₁& x ₂& f (0, 1, x ₃, x ₄) V x ₁&Ø x ₂& f (1, 0, x ₃, x ₄) V x ₁& x ₂& f (1, 1, x ₃, x ₄).

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

Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y _1, y ₂,..., y_m, y_{m +1},..., y_n).

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

В левой части получим f (y _1, y ₂,..., y_n).

Т. к. y^s = 1 только, когда y = s, то среди 2 ^m конъюнкций y ₁ ^{s 1}& y ₂ ^{s 2}&...& y_m^sm в правой части (4.1) только одна обратится в 1 – та, в которой y ₁ = s ₁,…, y_m = s_m. Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:

y ₁ ^{y 1}& y ₂ ^{y 2}&...& y_m^ym & f (y _1, y ₂,..., y_m, y_{m +1},..., y_n) = f (y _1, y ₂,..., y_n).

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

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

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

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

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

f (x ₁, x ₂,..., x_n) = V x ₁ ^{s 1}& x ₂ ^{s 2}&...& x_n^sn, (4.2)

f (s ₁, s ₂,..., s_n) = 1

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

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

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

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

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

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

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x ₁ ^{s 1}& x ₂ ^{s 2}&...& x_n^sn, где x_i^si = x_i, если s_i = 1 и x_i^si =Ø x_i, если s_i = 0, i = 1, 2,..., n.

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

Пример 4.15.

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

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

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

x ₁⁰& x ₂¹& x ₃¹ = Ø x ₁ & x ₂& x ₃.

x ₁¹& x ₂⁰& x ₃⁰ = x ₁&Ø x ₂&Ø x ₃.

x ₁¹& x ₂⁰& x ₃¹ = x ₁&Ø x ₂& x ₃ .

x ₁¹& x ₂¹& x ₃¹ = x ₁& x ₂& x ₃ .

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

f (x ₁, x ₂, x ₃) = Ø x ₁& x ₂& x ₃V x ₁&Ø x ₂&Ø x ₃ V x ₁&Ø x ₂& x ₃ V x ₁& x ₂& x ₃.

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

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

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

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

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

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

F ₂ º Ø F ₁ º ØØ f (x ₁, x ₂,..., x_n) º f (x ₁, x ₂,..., x_n),

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

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

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

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

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

x ₁ ^{Ø s 1}V x ₂^{Ø s 2}V...V x_n ^{Ø sn}, где x_i ^{Ø si} = x_i, если s_i = 0 и x_i ^{Ø si} = Ø x_i, если s_i = 1, i = 1, 2,..., n.

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

Пример 4.16.

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

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

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

x ₁¹V x ₂¹V x ₃¹ = x ₁V x ₂V x ₃.

x ₁¹V x ₂¹V x ₃⁰ = x ₁V x ₂VØ x ₃.

x ₁¹V x ₂⁰V x ₃¹ = x ₁VØ x ₂V x ₃.

x ₁⁰V x ₂⁰V x ₃¹ = Ø x ₁VØ x ₂V x ₃.

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

f (x ₁, x ₂, x ₃) = (x ₁V x ₂V x ₃)&(x ₁V x ₂VØ x ₃)&(x ₁VØ x ₂V x ₃)&(Ø x ₁VØ x ₂V x ₃).

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

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

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