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

Лемма M (лемма о немонотонной функции).Из немонотонной функции f(x1, . . . , xn) путем подстановки в неё вместо переменных x1, . . . , xn функций x, 0 и 1 можно получить немонотонную функцию одной переменной x.

Доказательство. Из немонотонности функции f(x1, . . . , xn) следует, что существует хотя бы одна пара двоичных наборов α и β таких, что

Получили функцию одной переменной

φ(x) = f(x, x, . . . , x, αk+1, . . . , αn).

131

x φ(x)

Так как таблица истинности 0 1

10

падает с таблицей истинности функции f(x) = x, то φ(x) = x.

Пример 7.12. Получить функцию x из немонотонных функций а) fe2 = (1010 1010); б) fe3 = (0101 1011).

Решение.

Немонотонность функций fe2 = (1010 1010) и fe3 = (0101 1011) установлена в примерах 7.10 и 7.11 ( п. б) и в) ).

1 способ (с использованием алгоритма 1)

а) Найдем хотя бы одну пару наборов, на которой нарушается монотонность. Такой парой являются наборы σe1 = (000) и αe1 = (001) : σe1 4 αe1, но f2(000) = 1 > 0 = f2(001) (см. пример 7.10, п. б) ).

Наборы σe1 и αe1 отличаются только в третьей координате, поэтому первые две координаты в наборе оставляем без изменений. Третью координату заменяем на функцию x. Получаем набор γ = (0, 0, x).

Найденная функция одной переменной φ(x) = f2(0, 0, x) - искомая функция "отрицание". Докажем это.

полученной функции φ(x) совпадает с таблицей истинности функции f(x) = x, то есть φ(x) = x.

б) fe3 = (0101 1011)

Наборы, на которых нарушается монотонность функции fe3, уже получены в примере 7.10, п. в) :

132

Наборы σe1 и αe1 различаются в первой координате; соответствующую этой координате переменную x1 заменяем на функцию x. Остальные координаты входят в набор γ = (x, 0, 1) без изменений.

φ(x) = f3(γ) = f3(x, 0, 1)

2 способ нахождения наборов, на которых нарушается монотонность (с использованием алгоритма 2).

а) В примере 7.11, п. б) мы получили, что αe000 = (1) 4̸ αe001 = (0). Индексы (000) и (001) при наборах αe единичной длины соответствуют двоичным наборам, на которых нарушается монотонность.

б) При установлении немонотонности функции f3 в примере 7.11, п. в) мы выяснили, что отношение предшествования нарушено для наборов (0101) и (1011) во второй координате.

Замечание 7.15. Несмотря на то, что с помощью алгоритма 2 проще устанавливать монотонность функции, чаще используют алгоритм 1, так как в процессе его работы не только определяется монотонность, но и сразу находятся наборы, на которых она нарушается. Данные наборы мы используем для выражения функции x. Это особенно важно, когда x нужно выразить из немонотонной функции всеми возможными способами.

133

Решение.

1.Сначала исследуем функцию g(xe) на монотонность, применяя алгоритм 1.

Найдем носитель функции

Ng = {(0110), (0111), (1100), (1111)}.

Каждому набору σe из носителя сопоставим класс монотонности.

σe1 = (0110) 7→M 1 = {(0110), (0111), (1110), (1111)}.

Набор αe1 = (1110) M 1 , но αe1 / Ng. Функция немонотонна, можно применять лемму М.

На паре наборов σe1 = (0110) и αe1 = (1110) нарушается монотонность. Получим функцию x на этой паре наборов.

γ1 = (x, 1, 1, 0); φ1(x) = g(x, 1, 1, 0) = x;

φ1(0) = g(0, 1, 1, 0) = 1 = 0φ1(1) = g(1, 1, 1, 0) = 0 = 1

2.σe2 = (0111) 7→M 2 = {(0111), (1111)} Ng.

3.σe3 = (1100) 7→M 3 = {(1100), (1101), (1110), (1111)}.

Значит, функцию x можно выразить ещё двумя способами:

σe3 = (1100)

а) e 7→γ2 = (1, 1, 0, x); φ2(x) = g(1, 1, 0, x) = x; β1 = (1101)

σe3 = (1100)

б) e 7→γ3 = (1, 1, 0, x); φ3(x) = g(1, 1, x, 0) = x. β2 = (1110)

Убедиться в том, что φ2(x) = φ3(x) = x можно также, как и в предыдущих примерах.

4. σe4 = (1111) 7→M 4 = {(1111)} Ng.

Больше наборов, на которых нарушается монотонность, нет. Значит, других способов получить x в данном примере не имеется.

134

7.5Класс L линейных функций

Определение 7.9. Функция f(xe) называется линейной, если её многочлен Жегалкина не содержит конъюнкций.

Например, функции f1(xe) = x1 x2 x4, f2(xe) = 1 x1 x3 являются линейными.

Функции f3(xe) = x1 · x2 x4 и f2(xe) = 1 x1 · x3 - нелинейные функции.

Напомним, что способы построения многочлена Жегалкина описаны в п. 3.5 на стр. 41.

Замечание 7.16. Все функции одной переменной

f1(x) = x, f2(x) = x = x 1, f3(x) ≡ 0, f4(x) ≡ 1

являются линейными функциями.

Множество всех линейных функций образует класс L.

Теорема 7.7. Класс L линейных функций замкнут:

[L] = L.

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

1.f(x) = x L (см. замечание 7.16).

2.Докажем, что любая суперпозиция F = f(f1, . . . , fm) линейных функций f, f1, . . . , fm также является линейной функцией. Докажем, что:

f, f1, . . . , fm L F = f(f1, . . . , fm) L.

По определению линейной функции

135

F= f(f1, . . . , fm) = a00 a01f1 a02f2 . . . a0mfm =

=a00 a01 · (a10 a11x1 a12x2 . . . a1nxn)

a02 · (a20 a21x1 a22x2 . . . a2nxn) . . .

a0m · (am0 am1x1 am2x2 . . . amnxn).

Приведем подобные слагаемые, вынося за скобки одинаковые переменные:

F = a00 a01a10 a02a20 . . . a0mam0

x1(a01a11 a02a21 . . . a0mam1) x2(a01a12 a02a22 . . . a0mam2)

.. . xn(a01a1n a02a2n . . . a0mamn) =

=α0 α1x1 α2x2 . . . αnxn,

αn = a01a1n a02a2n . . . a0mamn

Мы получили, что многочлен Жегалкина функции F не содержит конъюнкций, то есть F L.

Теорема 7.8. Число линейных функций, зависящих от n переменных, равно 2n+1, то есть

|L| = 2n+1.

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

f(xe) L f(xe) = α0 α1x1 α2x2 . . . αnxn.

Значит, любая линейная функция взаимнооднозначно определяется двоичным набором (α0, α1, . . . , αn) длины n + 1.

Число различных линейных функций равно количеству различных двоичных наборов длины n + 1, то есть 2n+1.

Получили:

|L| = 2n+1.

136

Теорема 7.9 (необходимое условие линейности функции). Если линейная функция f(x1, . . . , xn) отлична от константы, то количество единиц в её векторе значений равно числу нулей, то есть

|Nf | = 122n.

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

f(x1, . . . , xn) = α0 α1x1 α2x2 . . . αnxn L.

Так как f ̸≡const, то хотя бы один из коэффициентов α1, α2, . . . , αn не равен нулю. Без ограничения общности будем считать, что α1 ≠ 0, то есть

f(xe) = x1 α2x2 . . . αnxn α0.

Рассмотрим уравнение

x1 α2x2 . . . αnxn α0 = 1.

Очевидно, что множество решений этого уравнения совпадает с Nf . Это означает, что число различных решений равно количеству наборов в носителе функции.

Добавим к обеим частям уравнения выражение α2x2 . . . αnxn α0 и упростим левую часть, используя тождество

A A = 0.

Получим:

x1 = α2x2 . . . αnxn α0 1.

Так как значение переменной x1 однозначно определяется из данного уравнения коэффициентами α2, . . . , αn, число различных решений равно количеству двоичных наборов (α2, . . . , αn) длины n − 1. Всего таких наборов 2n−1, то есть

|Nf | = 2n−1 = 122n.

Замечание 7.17. Условия теоремы являются необходимыми, но не достаточными. То есть, из того, что вектор значений функции содержит поровну нулей и единиц, не следует, что функция линейна.

137

fe1 = (1010 1010) = 1 x3 L

Например, fe2 = (0001 0111) = x2x3 x1x3 x1x2 / L , хотя число нулей и единиц в векторе значений обеих функций совпадает

(|Nf1 | = 4 = 22 = 23−1 = |Nf2 |).

Для получения многочлена Жегалкина булевых функций fe1 и fe2 мы использовали алгоритм 3 - метод треугольника (см. п. 3.5.3 на стр. 44). Выделенная в таблице колонка соответствует коэффициентам многочлена:

В дальнейшем мы будем пользоваться следующим следствием:

Следствие 7.9.1. Если количество нулей и единиц в векторе значений функции, отличной от константы, различно, то функция нелинейна.

138

Лемма L (лемма о нелинейной функции).Из нелинейной функции f(x1, . . . , xn) путем подстановки в неё вместо переменных x1, . . . , xn функций одной переменной x, y, 0, 1, x и y можно получить одну из нелинейных функций: конъюнкцию или дизъюнкцию. Точнее, существует представление конъюнкции или дизъюнкции в виде суперпозиции констант, отрицаний и функции f.

Доказательство. Пусть f(x1, . . . , xn) / L. Это означает, что её многочлен Жегалкина содержит хотя бы одну конъюнкцию. Согласно теореме Жегалкина (см. теорему 3.6) любую булеву функцию можно представить в виде

f(xe) =

= a0 a1x1 a2x2 . . . anxn a12x1x2 a13x1x3 . . . a12:::nx1x2 · · · xn.

ставления функции в виде многочлена Жегалкина.

Рассмотрим функцию двух переменных φ(x, y), полученную из f(xe) подстановкой:

вместо переменной xi1 - функции x, вместо переменной xi2 - функции y,

вместо переменных xi3 , xi4 , . . . , xik - константы 1, вместо остальных переменных - константы 0.

Тогда

φ(x, y) = xi1 xi2 αxi1 βxi2 γ = xy αx βy γ,

где α, β, γ {0, 1} - коэффициенты, зависящие от конкретной функции f.

Все возможные функции φ(x, y) (в зависимости от значений коэффициентов α, β, γ) перечислены в следующей таблице:

139

При выводе формул в таблице использовались законы де Моргана, двойного отрицания и логическое тождество A 1 = A (см. основные эквивалентности алгебры логики в п. 2.3.6 на стр. 23).

Для каждого набора значений (α, β, γ) получили выражение функции f либо в виде конъюнкции, либо в виде дизъюнкции.

Пример 7.14. Выразить конъюнкцию или дизъюнкцию из функции

f2(xe) = (0001 0111).

Решение.

Так как

f2(x1, x2, x3) = (0001 0111) = x2x3 x1x3 x1x2 / L,

то к функции f2(xe) можно применить лемму L.

Многочлен Жегалкина функции f2 содержит 3 конъюнкции ранга 2. Поэтому можно брать любую из них, например, K1 = x2x3. В неё входят переменные x2 и x3.

Рассмотрим набор γ = (0, x2, x3), в который переменные x2 и x3 входят без изменений, а переменная x1, не вошедшая в K1, заменена на 0.

140