Изменения

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

Используем нелинейную функцию <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</tex>^<tex>x_2</tex> ⊕ [<tex>x_1</tex>] ⊕ [<tex>x_2</tex>] ⊕ [<tex>~1</tex>], где в квадратных скобках указаны члены, которые могут и не присутствовать'''.'''

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

}}

== Источники ==

* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия]

* Образовательный сайт [http://mini-soft.ru/nstu/diskr/7_.php MiniSoft]