Множества. Комбинаторика. Отношения (стр. 12 )

ТЕОРЕМА (лемма о немонотонной булевой функции). Из любой немонотонной булевой функции с помощью подстановки в нее вместо переменных констант 0 и 1 и тождественной функции можно получить функцию отрицания.

Доказательство. Пусть f Ï M Þ $ a =<a1, …, an>, b = <b1,…, bn>, a µ b, но f(a) > f(b), т. е. f(a)=1, f(b) =0. Неравенство ai < bi, означает, что ai =0, bi=1. Если ai при ai = bi,ji = íx при ai < bi,то ji(0) = ai, ji(1) = bi и для функции j(х) = f(j1(x),…,jn(x)) имеем j(0) = f(a) =1, j(b) =0 Þ j(x) = x. <

ТЕОРЕМА (лемма о нелинейной булевой функции). Из любой нелинейной булевой функции с помощью подстановки в нее вместо переменных констант 0 и 1, тождественной функции, функции отрицания можно получить конъюнкцию или отрицание конъюнкции.

Доказательство. Представление нелинейной булевой функции f в виде полинома Жегалкина содержит слагаемое, в котором обязательно присутствуют конъюнкция каких-либо двух переменных. Изменение нумерации переменных не ослабит общности доказательства теоремы и мы изменим нумерацию переменных таким образом, чтобы в полиноме Жегалкина присутствовало слагаемое к конъюнкцией х1х2. Тогда, собрав в одну скобку все слагаемые, содержание х1х2, в другую все слагаемые, содержание х1, но не содержащие х2, в третью содержащие х2, но не содержащие х1, получим f(x1,…, xn) = x1x2 f1(x3,…, xn) Å x1 f2(x3, …, xn) Å x2 f3(x3, …, xn) Å f4(x3,…,xn), где в силу единственности представления булевой функции в виде полинома Жегалкина f1 ¹ 0, т. е. существует набор значений переменных, для которого f1(a3,…, an) =1. Пусть f2(a3,…, an) = a, f3(a3,…, an) = b, f4(a3,…, an) = g Þ j(х1, х2) = f(х1, х2, а 3,…, an) = х1х2 Å a х1Å b х2 Å g Þ y(х, у) = j(хÅb, уÅ a) = хуÅabÅg Þ y(х, у) = ху, если abÅg =0, или y(х, у) = Ø(ху), если abÅg =1. <

Упражнения

1) Взять произвольно функцию, проверить является ли она несамодвойственной. Если функция несамодвойственная, то с помощью алгоритма, описанного в доказательстве леммы о несамодвойственной функции построить константу.

2) Взять произвольно функцию, проверить является ли она немонотонной. Если функция немонотонная, то с помощью алгоритма, описанного в доказательстве леммы о немонотонной функции построить отрицание.

3) Взять произвольно функцию, проверить является ли она нелинейной. Если функция нелинейная, то с помощью алгоритма, описанного в доказательстве леммы о нелинейной функции построить конъюнкцию или отрицание конъюнкции.

2.2.7. Теорема Поста о функциональной полноте

ТЕОРЕМА (критерий полноты функциональной системы). Для полноты функциональной системы необходимо и достаточно, что для каждого из пяти важнейших замкнутых классов в ней нашлась функция ему не принадлежащая.

Доказательство. ÞПусть N – полный класс и N Í Т0 Þ [N] Í [Т0] Þ Р2 Í Т0 Þ Р2 = Т0. Противоречие. Следовательно, в классе N найдется функция, не сохраняющая константу 0. Аналогично приходим к противоречию, предположив, что полный класс N принадлежит классам Т1, L, M, S.

Предположим, что в классе N найдутся функции f0 Ï N0 , f1Ï T1, f2 Ï S, f3 Ï M, f4 Ï L. Так как f0(0,…, 0) =1, то j(x) = f0(x,…,x) =`x, если f0(1,…,1) = 0, и j(x)= 1, если f0(1,…,1) =1. Для функции y(х)= f1(x,…,x) имеем y(х) =`х, если f1 0,…,0) = 0, и y(х) =1, если f1 0,…,0) =1. С помощью f0 и f1 в [N] можно получить 0; 1 или`х. При наличии отрицания с помощью несамодвойственной функции в [N] можно построить константу, а, следовательно, и вторую константу, т. е. можно построить 0 и 1. При наличии обеих констант с помощью немонотонной функции можно построить отрицание. При наличии обеих констант и отрицания с помощью нелинейной функции можно построить конъюнкцию. При наличии конъюнкции и отрицания с помощью законов де Моргана можно построить дизъюнкцию. Таким образом, в [N] построен полный класс { Ù, Ú, Ø} Þ [N] = Р2 Þ N – полный класс. <

Следствие. Из любой полной системы можно выделить полную подсистему, содержащую не более четырех функций.

Доказательство. Так как самодвойственная функция на противоположных наборах значений переменных принимает противоположные значения, то f0(1,…,1) =1 означает, что f0 Ï S. Если же f0(0,…,0) =1Þ f0 Ï M. Отсюда вместо пяти разных функций в доказательстве достаточной теоремы можно брать только четыре, которые образуют полную систему. <

Замечание. Число 4 в следствии не может быть понижено. Из следующей таблицы видно, что четыре функции по теореме Поста образуют полную систему, но после удаления любой из них система перестает быть полной.

	0	1	х1х2	X1Åх2Åх3
Т0	1	0	1	1
Т1	0	1	1	1
L	1	1	0	1
M	1	1	1	0
S	0	0	0	1

Упражнения

1) Полны ли системы булевых функций?

а) {Ø, Ù, Ú};

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

Построим таблицы истинности данных функций:

x	y	Øx	xÙy	xÚy
0	0	1	0	1
0	1	1	0	1
1	0	0	0	1
1	1	0	1	0

Операция отрицание не сохраняет 0, 1, не является монотонной, самодвойственна (так как на противоположных наборах оно принимает противоположные значения) и линейна (так как ее полином Жегалкина x+1).

Операция конъюнкция – сохраняет 0, 1, монотонна, не самодвойственна, не линейна.

Операция дизъюнкция – сохраняет 0, 1, не монотонна, несамодвойственна, не линейна (так как ее полином Жегалкина xy+x+y+1).

Составим таблицу:

	Ø	Ù	Ú
Т0	0	1	1
T1	0	1	1
L	1	0	0
M	0	1	0
S	1	0	0

Следовательно, данная система полна, так как она полностью не содержится ни в одном из этих классов. (Отрицание не сохраняет 0 и 1, значит, в классах Т0 и Т1 система не содержится, конъюнкция и дизъюнкция нелинейны, следовательно, в классе L система тоже не содержится, и т. д.).

б) { Ù, Ú}; Ответ: не полна

в) {Þ, Ù, Ú}; Ответ: полна