Изменения

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

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а значит, и замыкание набора входило бы в этот класс и набор К не мог быть полным===== Необходимость.=====

Докажем достаточность Заметим, что необходимость этого утвержденияочевидна, так как если бы все функции из набора К входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор К не мог бы быть полным.

===== Достаточность. =====# Рассмотрим функцию, не сохраняющую ноль {{---}} <tex>f_0</tex>. (<tex>f_0(0) = 1</tex>) <tex>f_0(1)</tex> может принимать два значения:## <tex>f_0(1) = 1</tex>, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex>. ## <tex>f_0(1) = 0</tex>, тогда <tex>f_0(x, x, x, \dots, x) = \neg x</tex>.# Рассмотрим функцию, не сохраняющую один {{---}} <tex>f_1</tex>. (<tex>f_1(1) = 0</tex) <tex>f_1(0)</tex> может принимать два значения:## <tex>f_1(0) = 0</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = 0</tex>.## <tex>f_1(0) = 1</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</tex>.

а) <tex>f_0(1) = 1</tex>''Таким образом, тогда <tex>f_0(x, x, x, \ldots, x) = 1</tex>.возможны четыре варианта:''

б) <tex>f_0(1) = 0</tex>, тогда * Мы получили функцию <tex>f_0(x, x, x, \dots, x) = \neg x</tex>. Рассмотрим функцию, не сохраняющую один {{---}} <tex>f_1</tex>. <tex>f_1(1) = 0</tex>. <tex>f_1(0)</tex> может принимать два значения: а) <tex>f_1(0) = 0</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = 0</tex>. б) <tex>f_1(0) = 1</tex>, тогда <tex>f_1(x, x, x, \ldots, x) = \lnot x</tex>. Возможны четыре варианта: 1) Мы получили функцию НЕ. Используем несамодвойственную функцию <tex>f_s</tex>. По определению , найдется такой вектор <tex>x_0</tex>, что <tex>f_s(x_0) = f_s(\lnot x_0)</tex>. Где <tex>x_0 = (x_{01}, x_{02}, ..., x_{0k})</tex>. Возьмем <tex>f_s(x^{x_{01}}, x^{x_{02}}, \ldots, x^{x_{0k}})</tex>, где <tex>x^{x_{0i}} = x</tex>, при <tex>x_{0i} = 1</tex> и <tex>x^{x_{0i}} = \lnot x</tex>, при <tex>x_{0i} = 0 </tex>.

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

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

4) Мы получили ''В итоге имеем три функции:'' <tex>1\neg </tex> и , <tex>0</tex>, <tex>1</tex>.

Рассмотрим немонотонную Используем нелинейную функцию <tex>f_mf_l</tex>. Существуют такие Среди нелинейных членов <tex>x_1, x_2, \ldots, x_nf_l</tex>(ее представления в виде [[Полином Жегалкина|полинома Жегалкина]]), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, что оставшиеся два назовем <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 0 , x_{i+1}, \ldots, x_n) = 1</tex>, и <tex>f_m(x_1, x_2, \ldots, x_{i-1}, 1 , x_{i+1}, \ldots, x_n) = 0</tex>. Все элементы, зафиксируем все не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде <tex>g_l = x_1, \land x_2 [ \oplus x_1] [\oplus x_2, ][ \ldots, x_noplus ~1]</tex>, тогда <tex>f_mгде в квадратных скобках указаны члены, которые могут и не присутствовать (x_1, x_2остальные слагаемые будут равны нулю, \ldotsпоскольку в них есть как минимум один аргумент, x_{i-1}не входящий в выбранный член, x, x_{i+1}, \ldots, x_nтак как в выбранном члене минимальное число элементов)= \lnot x</tex>.

В итоге имеем три функции''Рассмотрим несколько вариантов: НЕ, <tex>0</tex>, <tex>1</tex>.''

Используем нелинейную функцию # Присутствует член <tex>f_l\oplus ~1</tex>. Среди нелинейных членов Возьмем отрицание от <tex>f_lg_l</tex> (ее представления в виде [[Полином Жегалкина|полинома Жегалкина]])и член <tex>\oplus ~1</tex> исчезнет.# Присутствуют три члена, выберем тотбез <tex>\oplus ~1</tex>: <tex>g_l= x_1 \land x_2 \oplus x_1 \oplus x_2</tex>. Составив таблицу истинности для этой функции нетрудно заметить, в котором минимальное количество элементовчто она эквивалентна функции <tex> \vee </tex>. Все аргументы# Присутствуют два члена, кроме без <tex>\oplus ~1</tex>. Построив две таблицы истинности для двухразличных вариантов, заметим, что в обоих случаях функция истинна только в этом членеодной точке, приравняем единицеследовательно, оставшиеся два назовем СДНФ функции <tex>g_l</tex> будет состоять только из одного члена. Если это так, то не составляет труда выразить <tex> \wedge </tex> через <tex>x_1\neg </tex> и <tex>g_l</tex>. Например, если функция <tex>g_l(x_1, x_2, ..., x_n)</tex>принимает истинное значение, когда аргументы c номерами <tex>i_1, i_2, ..., i_m</tex> ложны, а все элементыостальные истины, не входящие в данный член, сделаем равными нулю. Тогда эта функция будет представима в виде то функцию <tex> \wedge </tex> можно выразить как <tex>g_l = x_1 \land x_2 ([ \oplus lnot]x_1] , [\oplus lnot]x_2], ..., [ \oplus ~1lnot]x_n)</tex>, где в квадратных скобках указаны члены<tex>\lnot</tex> ставится перед аргументами с номерами <tex>i_1, i_2, которые могут и не присутствовать (остальные слагаемые будут равны нулю..., поскольку в них есть как минимум i_m</tex>.# Присутствует один аргумент не входящие в выбранный член, т. к. мы выбрали член, в котором минимальное число элементов)Выразим <tex> \wedge </tex> через <tex> \neg </tex> и <tex>g_l</tex> аналогично пункту 3.

В итоге получаем функцию НЕ, а также либо функцию И, либо функцию ИЛИ. Поскольку функцию И можно выразить через ИЛИ и НЕ, а функцию ИЛИ через И и НЕ, то мы получили базис И, ИЛИ, НЕ. Любую булеву функцию, не равную тождественному нулю, можно представить в форме [[СДНФ]], т. е. с помощью данного базиса. Если же функция равна тождественному нулю, то ее можно представить в виде <tex>x \land \lnot x</tex>. ''Значит, полученные функции образуют полную систему, т. к. поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K {{---}} полная система функций, что и требовалось доказать.''