Дискретная математика

Вычислим значение многочлена Жегалкина на этом наборе (подставляя x1 = 0):

f2(0, x2, x3) = x2x3 0 · x3 0 · x2 = x2x3.

Заменив переменную x2 на x, а x3 - на y в обеих частях полученного равенства, получим функцию двух переменных - конъюнкцию

φ1(x, y) = f2(0, x, y) = xy.

Очевидно, что для получения конъюнкции из функции f2 можно было взять конъюнкции K2 = x1x3 или K3 = x1x2.

Проделав аналогичные действия, получим

φ2(x, y) = f2(x, 0, y) = xy φ3(x, y) = f2(x, y, 0) = xy

Пример 7.15. Получить с помощью леммы L функцию xy или x y

из функции f3(xe) = (1101 1100).

Решение.

Так как количество единиц в векторе значений равно 5, а количество нулей - 3, то, согласно следствию 7.9.1 к необходимому признаку нелинейности функции (теорема 7.9), функция f3 нелинейна.

Представим данную функцию в виде многочлена Жегалкина:

f3(x1, x2, x3) = (1101 1100) = 1 x2 x2x3 x1x2x3.

Самой короткой конъюнкцией является K1 = x2x3.

141

Вычислим значение функции f3 на наборе γ = (0, x2, x3). Получим

f3(0, x2, x3) = 1 x2 x2x3 0 · x2x3 = 1 x2 x2x3.

Упростим полученное равенство, вынося за скобки одинаковые сомножители (в данном случае x2), применяя тождество

A 1 = A

и законы де Моргана:

f3(0, x2, x3) =

= 1 x2 x2x3 = 1 x2 ·(1 x3) = 1 x2x3 = x2x3 = x2 x3 = x2 x3.

Так как переменная x2 входит в полученную формулу отрицанием, заменим её на x, а переменную x3 - на y.

φ(x, y) = f3(0, x, y) = x y.

Из нелинейной функции f3 мы получили функцию "дизъюнкция".

Пример 7.16. Исследовать функцию ge = (0000 1111 0011 0011)}

на принадлежность классу L. В случае линейности выразить всеми возможными способами функции конъюнкцию и дизъюнкцию.

Решение.

Найдем многочлен Жегалкина для функции ge, используя 3 алгоритм.

142

g(x1, x2, x3, x4) = x2 x1x3 x1x2.

Задавая все возможные значения переменным x1, x2, x3 и x4 (всего 24 варианта), получим различные функции двух переменных.

1.g(0, 0, x3, x4) = 0 0 ·x3 0 ·0 = 0 - получили линейную функцию; лемма L не применима, функции xy или x y получить невозможно;

2.g(0, 1, x3, x4) = 1 0 · x3 0 · 0 = 1 L - аналогично;

3.g(1, 0, x3, x4) = 0 1 · x3 1 · 0 = x3 L

4.g(1, 1, x3, x4) = 1 1 · x3 1 · 1 = x3 L

5.g(0, x2, 0, x4) = x2 0 · 0 0 · x2 = x2 L

6.g(0, x2, 1, x4) = x2 0 · 1 0 · x2 = x2 L

7.g(1, x2, 0, x4) = x2 1 · 0 1 · x2 = 0 L

8.g(1, x2, 1, x4) = x2 1 · 1 1 · x2 = 1 L

143

Так как обе конъюнкции в многочлене Жегалкина содержат по две переменных, и в каждую входит переменная x1, то подстановка x1 = 0 даёт линейную функцию. Поскольку получить конъюнкцию или дизъюнкцию из линейной функции нельзя, больше такие подстановки не рассматриваем.

Так как многочлен Жегалкина не зависит от переменной x4 (такая переменная называется фиктивной), подстановки вида (x1, α1, α2, x4), αi {0, 1} дают нам формулу, содержащую только переменную x1. Опять получаем линейную функцию, лемму L применять не можем.

Рассмотрим оставшиеся варианты. Поскольку x4 - фиктивная переменная, то подстановки (x1, x2, x3, 0) и (x1, x2, x3, 1) дают одинаковый результат.

9. g(x1, x2, 0, 0) = g(x1, x2, 0, 1) = x2 x1 · 0 x1x2 = x2 x1x2 =

10. g(x1, x2, 1, 0) = g(x1, x2, 1, 1) = x2 x1 ·1 x1x2 = x2 x1 x1x2 =

= x2 x1(1 x2) = x2 1 1 x1x2 = x1 x2 1 = x1 x2 = x1 x2;

{

11. g(x1, 0, x3, 0) = g(x1, 0, x3, 1) = 0 x1 · x3 x1 · 0 = x1x3;

{

12. g(x1, 1, x3, 0) = g(x1, 1, x3, 1) = 1 x1 ·x3 x1 ·1 = 1 x1 ·x3 x1 =

= 1 x1(1 x3) = 1 x1x3 = x1x3 = x1 x3;

{

144

7.6Задачи для самостоятельного решения

1.Проверить принадлежность функций основным замкнутым классам T0, T1, S, M, L. Применить, где это возможно, леммы S, M, L.

1.fe1 = ( 0110 0001 );

2.fe2 = ( 1101 0001 );

3.fe3 = ( 1001 0110 );

4.fe4 = ( 0101 0111 );

5.fe5 = ( 0110 1111 );

6.fe6 = ( 0110 1110 );

7.fe7 = ( 1001 1100 );

8.fe8 = ( 1011 0101 );

9.fe9 = ( 1111 1100 );

10.ff10 = ( 0101 1111 ).

2.Найти среди функций f1 и f2 несамодвойственную и по лемме S (о несамодвойственной функции) выразить всеми возможными способами все константы.

3. Найти среди функций f1 и f2 немонотонную и по лемме M (о немонотонной функции) выразить всеми возможными способами x.

145

ной функции) выразить всеми возможными способами конъюнкцию и дизъюнкцию.

Ответы к задачам для самостоятельного решения

1.1. fe1 T0; fe1 T1; fe1 / S; fe1 / M; fe1 / L;

2.fe2 / T0; fe2 T1; fe2 / S; fe2 / M; fe2 / L;

3.fe3 / T0; fe3 / T1; fe3 S; fe3 / M; fe3 L;

4.fe4 T0; fe4 T1; fe4 / S; fe4 M; fe4 / L;

5.fe5 T0; fe5 T1; fe5 / S; fe5 / M; fe5 / L;

6.fe6 T0; fe6 / T1; fe6 / S; fe6 / M; fe6 / L;

7.fe7 / T0; fe7 / T1; fe7 / S; fe7 / M; fe7 / L;

146

8.fe8 / T0; fe8 T1; fe8 / S; fe8 / M; fe8 / L;

9.fe9 / T0; fe9 / T1; fe9 / S; fe9 / M; fe9 / L;

10.ff10 T0; ff10 T1; ff10 / S; ff10 M; ff10 / L.

147

Глава 8

Полнота систем функций

8.1Примеры полных систем

Мы знаем, что любую функцию алгебры логики можно представить в виде формулы через элементарные функции x, x y, x&y, например, в виде СДНФ или СКНФ (см. главу 3).

любую булеву функцию можно выразить в виде формулы через функции этой системы, то есть [ ] = P2.

Теорема 8.1. Пусть даны две системы функций из P2 :1 = {f1, f2, . . .} и 2 = {g1, g2, . . .}.

Если система 1 полна и каждая её функция выражается в виде формул через функции системы 2, то система функций 2 также полна.

Рассмотрим примеры полных систем.

1.Система P2 (множество всех булевых функций) является полной системой.

2.Система 1 = {x, x y, x&y} представляет собой полную систему, так как, согласно теореме 3.4, любую булеву функцию можно представить формулой, являющейся суперпозицией дизъюнкции, конъюнкции и отрицания.

148

функции системы 4.

5.Полнота системы 5 = {x ↓ y}, согласно теореме 8.1, следует из полноты системы 3 и тождеств

x ↓ x = x, (x ↓ y) ↓ (x ↓ y) = x ↓ y = x y.

6.Система 6 = {1, x y, x&y} является полной, так как по теореме Жегалкина любую булеву функцию можно представить в виде многочлена Жегалкина, то есть формулы, выраженной через функции системы 6.

8.2Критерий Поста функциональной полноты

целиком не содержится ни в одном из основных замкнутых классов

T0, T1, S, M и L. Доказательство.

Необходимость. Требуется доказать, что, если система функций полна ([ ] = P2), то она целиком не содержится ни в одном из классов K {T0, T1, S, M, L}.

Ранее мы доказали, что каждый из классов K замкнут ([K] = K). При этом [K] ≠ P2, K {T0, T1, S, M, L}.

Рассмотрим таблицу принадлежности функций одной переменной основным замкнутым классам. Если функция содержится в классе, соответствующий элемент таблицы равен "+ \; "- \- в противоположном случае.

149

Так как все столбцы различны, то и классы попарно различны.

Докажем необходимость от противного.

Пусть = {f1, f2, . . . , fk, . . .} K, где K {T0, T1, S, M, L}. Тогда по свойству замыкания (см. стр. 111) [ ] [K]. Получили, что P2 = [ ] [K] ≠ P2, то есть P2 ≠ P2 - противоречие. Необходимость доказана.

Достаточность. Так как система функций = {f1, f2, . . . , fk, . . .} не содержится целиком ни в одном из классов T0, T1, S, M и L, то из этой системы можно выделить не более 5 функций, при этом

fi1 / T0, fi2 / T1, fi3 / S, fi4 / M, fi5 / L.

Доказательство достаточности теоремы - это

8.2.1Алгоритм получения функций 0, 1, x, x y, x&y из системы функций

1.Получение функций 0, 1, x.

Так как леммы L и М используют константы, сначала выразим функции 0 и 1 через систему функций .

fi1 (xe) / T0 fi1 (0, 0, . . . , 0) = 1.

Возможны 2 случая:

а) fi1 (1, 1, . . . , 1) = 1

Так как fi1 (0, 0, . . . , 0) = fi1 (0, 0, . . . , 0) = 1, то fi1 (x) / S и по лемме S можно получить константу 1:

функцию fi1 (xe) .

В этом случае константа 0 получается из функции fi2 (xe) / T1:

fi2 (xe) / T1 fi2 (1, 1, . . . , 1) = 0

150