§7. Замыкание множества булевых функций.

Пример 7.1.Рассмотрим функцию четырех переменных

f(a, b, с, d) = _:

1. f (0, 0, 0, 0) = =1 0=1, f (a, b, с, d) ,

2. f (1, 1, 1, 1) = =0 0=0, f (a, b, с, d) .

3.Функция f (a, b, с, d) не является самодвойственной:

f (0,1,1,1)= f (1,0,0,0).

4.Рассматриваемая булева функция f (a, b, с, d) немонотонная :

(1, 0, 0, 0) ≥ (0, 0, 0, 0), f (1, 0, 0, 0) ≥ f (0, 0, 0, 0).

5.Установим, является ли булева функция f (a, b, с, d) линейной.

Предположим, что она линейная и, следовательно, представима в виде (a, b, с, d) = с₀ с_аа с_bb с_сс c_dd.

Найдем неизвестные коэффициенты с₀, с_a, с_b, с_c, с_d, исходя из предположения о линейности этой функции. Зафиксируем набор

(0, 0, 0, 0) : f (0, 0, 0, 0).= 1, с₀ с_а0 с_b0 с_c0 c_d0=с₀, с₀=1.

Аналогично определим коэффициенты с_a, с_b, с_c, с_d, фиксируя соответственно наборы 1000, 0100, 0010, 0001. Имеем:

f (1, 0, 0, 0) = =0 0=0,1 с_а1 с_b0 с_c0 c_d0=1 с_a,1 с_a=1, с_a=1;

f (0, 1, 0, 0) = =1 1=1, 1 1∙0 0∙0 с_с0 c_d0=1 с_b, 1 с_b=1, с_b=0;

f (0, 0, 1, 0) = =1 0=1, 1 1∙0 0∙0 с_c∙1 c_d0=1 c_c, 1 с_c=1, с_a=0;

f (0, 0, 0, 1) = =0 0=0, 1 1∙0 0∙0 0∙0 c_d∙1=0 с_a, 1 с_d=0, с_d=1.

Окончательно получаем

f(a, b, с, d) = 1 а d.

Это равенство в каждой из остальных 11 строк таблицы истинности не сохраняется (проверте!). Действительно, например, f (1, 1, 1, 1) = =0 0=0, 1 1 1=1, 0 ≠ 1.

Следовательно, сделанное предположение является неверным. Функция f (a, b, с, d) – нелинейная:

f (a, b, с, d) .

ТЕОРЕМА Поста. Система булевых функций F полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую нуль, хотя бы одну функцию, не сохраняющую единицу, хотя бы одну несамодвойственную функцию, хотя бы одну немонотонную функцию и хотя бы одну нелинейную функцию.

Система булевых функций {+, &, 1} – полна, более того, она является базисом, называемым базисом Жегалкина; Тогда любую булеву функцию можно представить в виде многочлена от своих переменных и такой многочлен называется многочленом Жегалкина.

Многочленом Жегалкина называется многочлен, являющийся сум­мой константы и различных одночленов, в которые каждая из переменных входит не выше, чем в первой степени.

Многочлен Жегалкина константы равен самой же константе;

мно­гочлен Жегалкина булевой функции одной переменной

многочлен Жегалкина булевой функции двух переменных

многочлен Жегалкина булевой функции трех переменных

и т.д.

Коэффициенты a_1,...i, и свободный член а_о принимают значения 0 или 1, а число слагаемых в формуле равно 2ⁿ, где n — число переменных. Знак — сумма по модулю два.

Теорема (Жегалкина). Каждая булева функция f(x₁,… , х_n) может быть представлена в виде многочлена Жегалкина и притом единственным образом, с точностью до порядка слагаемых.

Первый алгоритм построения многочлена Жегалкина.

Выше было указано, что любую функцию, отличную от константы 0, можно представить в виде СДНФ. Если сравним таблицы истинности дизъюнкции и суммы по модулю два, видим, что они отличаются только последней строкой, т. е. на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю два. Кроме того, известно, что . На этом и основан первый алгоритм построения многочлена Жегалкина:

1. Составляем СДНФ.

2. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегалкина.

3. Упрощаем, если можно, полученное выражение, используя тождество

4. В полученной формуле каждое отрицание заменяем на .

5. Раскрываем скобки в полученной формуле, содержащей только функции +, &, 1.

6. Приводим подобные члены, используя тождество .

Используя метод неопределенных коэффициентов, получаем

Второй алгоритм определения многочлена Жегалкина:

1. Составляем систему линейных уравнений относительно 2ⁿ неиз­вестных коэффициентов, содержащую 2ⁿ уравнений, решением которой являются коэффициенты многочлена Жегалкина.

Многочлен Жегалкина называется нелинейным, если он содержит конъюнкции переменных, а если он не содержит конъюнкции перемен­ных, то он называется линейным.

Функция f(x₁,… , х_n) называется линейной, если ее многочлен Же­галкина имеет вид и нелинейной в противном случае.

Из определения многочлена Жегалкина следует, что для любой буле­вой функции коэффициенты при переменных x₁,… , х_n и свободный член вычисляются по формулам:

На этом основан алгоритм определения линейности (или нелинейно­сти) булевой функции.

1. По таблицам истинности булевой функции f(x₁,… , х_n) и выше указанным формулам находим коэффициенты: (а₀, а₁, ...,а_n).

2. Выписываем многочлен и про­веряем, задает ли он эту функцию. Для этого строим таблицу истинности многочлена Ф(x₁,… , х_n) и сравниваем ее с таблицей истинности функ­ции f(x₁,… , х_n).

Если таблицы истинности совпадают, то функция f(x₁,… , х_n) ли­нейная и Ф(x₁,… , х_n) — ее многочлен Жегалкина, В противном случае функция нелинейная.