Изменения

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

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

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

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

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

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

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

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

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

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

Нетрудно заметить, что <tex>f_s</tex>(0) = <tex>f_s</tex>(1) \Rightarrow f_s => <tex>f_s\operatorname {const}</tex> = '''const.'''Таким образом мы получили одну из констант'''.'''

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

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

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

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

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

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

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

2) Присутствуют 3 члена, без <tex>~1</tex>: <tex>f_l</tex> = <tex>x_1 \wedge x_2 \oplus x_1 \oplus x_2</tex>'''.''' Составив таблицу истинности для этой функции, нетрудно заметить, что она эквивалентна функции '''ИЛИ.'''  3) Присутствуют 2 члена, без <tex>~1</tex>. Посторив две таблицы истинности, для двух различных вариантов, видим, что в обоих случаях функция истинна только в одной точке => СДНФ будет состоять только из одного члена, а если это так, то не составляет труда выразить '''И''', через '''НЕ''' и <tex>f_l</tex>.  4) Присутствует 1 член. Выразим '''И''', через '''НЕ''' и <tex>f_l</tex>. В итоге получаем функцию '''НЕ''', а также либо функцию '''И''', либо функцию '''ИЛИ''', но '''НЕ''' образует базис и с той и с другой функциями. Из того, что через функции '''F''' можно выразить базис, следует, что '''F''' {{- --}} полная система функций, что и требовалось доказать'''.'''