Изменения

{{Теорема|statement==Формулировка теоремы==Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <tex>~S,M,L,T_0,T_1</tex>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов <math>~S,M,L,T_0,T_1</math>, т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. |proof==Доказательство == ----

Рассмотрим функцию, несохраняющую 0 - <mathtex>f_0</mathtex>'''.''' <mathtex>f_0</mathtex>(0) = 1'''.''' <mathtex>f_0</mathtex>(1) может принимать два значения:

а) <mathtex>f_0</mathtex>(1) = 1, тогда <mathtex>f_0</mathtex>(x, x, x, ..., x) = <mathtex>~1</mathtex>'''.'''

б) <mathtex>f_0</mathtex>(1) = 0, тогда <mathtex>f_0</mathtex>(x, x, x, ..., x) = ¬x'''.'''

Возьмем функцию, несохраняющую 1 - <mathtex>f_1</mathtex>. <mathtex>f_1</mathtex>(1) = 0. <mathtex>f_1</mathtex>(0) может принимать два значения:

а) <mathtex>f_1</mathtex>(0) = 0, тогда <mathtex>f_1</mathtex>(x, x, x, ..., x) = <mathtex>~0</mathtex>'''.'''

б) <mathtex>f_1</mathtex>(0) = 1, тогда <mathtex>f_1</mathtex>(x, x, x, ..., x) = ¬x'''.'''

'''1''') Мы получили функцию '''НЕ'''. Используем несамодвойственную функцию <mathtex>f_s</mathtex>.

По определению найдется такой вектор <mathtex>x_0</mathtex>, что <mathtex>f_s</mathtex>(<mathtex>x_0</mathtex>) = <mathtex>f_s</mathtex>(¬<mathtex>x_0</mathtex>). <mathtex>x_0</mathtex> = (<mathtex>x_{01}, x_{02}, ..., x_{0k}</mathtex>)'''.'''

Возьмем <mathtex>f_s</mathtex>(<mathtex>x^{x_{01}}, x^{x_{02}}, ..., x^{x_{0k}}</mathtex>), где <mathtex>x^{x_{0i}}</mathtex> = x, при <mathtex>x_{0i}</mathtex> = 1 и <mathtex>x^{x_{0i}}</mathtex> = ¬x, при <mathtex>x_{0i}</mathtex> = 0'''.'''

Нетрудно заметить, что <mathtex>f_s</mathtex>(0) = <mathtex>f_s</mathtex>(1) => <mathtex>f_s</mathtex> = '''const.'''

'''2''')Мы получили '''НЕ''' и <mathtex>~0</mathtex>. '''¬'''<mathtex>~0</mathtex> = <mathtex>~1</mathtex>'''.'''

'''3''')Мы получили '''НЕ''' и <mathtex>~1</mathtex>. '''¬'''<mathtex>~1</mathtex> = <mathtex>~0</mathtex>'''.'''

'''4''')Мы получили <mathtex>~1</mathtex> и <mathtex>~0</mathtex>'''.'''

Рассмотрим немонотонную функцию <mathtex>f_m</mathtex>. Существуют такие <mathtex>x_1, x_2, ..., x_n</mathtex>, что <mathtex>f_m(x_1, x_2, ..., x_{i-1}, 0 , x_{i+1}, ..., x_n)</mathtex> = 1, <mathtex>f_m(x_1, x_2, ..., x_{i-1}, 1 , x_{i+1}, ..., x_n)</mathtex> = 0, зафиксируем все <mathtex>x_1, x_2, ..., x_n</mathtex>, тогда <mathtex>f_m(x_1, x_2, ..., x_{i-1}, x, x_{i+1}, ..., x_n)</mathtex> = ¬x'''.'''

В итоге мы имеем три функции: '''НЕ''', <mathtex>~0</mathtex>, <mathtex>~1</mathtex>'''.'''

Используем нелинейную функцию <mathtex>f_l</mathtex>'''.''' Среди нелинейных членов <mathtex>f_l</mathtex>, выберем тот, в котором минимальное количество элементов, все элементы, кроме двух, в этом члене, сделаем равными 1, оставшиеся 2 назавем <mathtex>x_1</mathtex> и <mathtex>x_2</mathtex>, а все элементы, не входящие в данный член, сделаем равными 0'''.''' Тогда <mathtex>f_l</mathtex> = <mathtex>x_1</mathtex>^<mathtex>x_2</mathtex> ⊕ [<mathtex>x_1</mathtex>] ⊕ [<mathtex>x_2</mathtex>] ⊕ [<mathtex>~1</mathtex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

1) Присутствует член <mathtex>~1</mathtex>. Возьмем отрицание от <mathtex>f_l</mathtex> и член <mathtex>~1</mathtex> уберется'''.'''

2) Присутствуют 3 члена, без <mathtex>~1</mathtex>: <mathtex>f_l</mathtex> = <mathtex>x_1</mathtex>^<mathtex>x_2</mathtex> ⊕ <mathtex>x_1</mathtex> ⊕ <mathtex>x_2</mathtex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''

3) Присутствуют 2 члена, без <mathtex>~1</mathtex>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <mathtex>f_l</mathtex>.

4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <mathtex>f_l</mathtex>.

Получается, что у нас есть функция В итоге получаем функцию '''НЕ''', а также либо функция функцию '''И''', либо функция функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' - полная система функций, что и требовалось доказать'''.'''}}