Булевы функции: полнота и базис системы

[Joker_vD]

Sverest в сообщении #454878 писал(а):

Полная система функций, та которая достаточна, чтобы представить любую булеву функцию,

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

[Sverest]

и так как $\{x \vee y, \overline{x} \oplus y\}$$\{x \vee y, \overline{x} \oplus y\}$ сохраняет единицу, то такой системой можно выразить любую булеву функцию, значит система полная

[Joker_vD]

Sverest
Слушайте, это уже не смешно. Я только что написал, что раз они сохраняют единицу, то не всякую булеву функцию можно через них выразить, значит, система неполная. А, да ну вас...

[blondinko]

Sverest в сообщении #455386 писал(а):

такой системой можно выразить любую булеву функцию

А вот и нет!
Тождественный нуль Вы из этой системы ну никак не выразите.

А всё почему.
Обе Ваши функции сохраняют единицу (т.е. при наборе параметров $\{x_i : x_i = 1 \,\, \forall i\}, f(x_1, x_2, … x_n) = 1$), а это значит что нуль при таком наборе Вы на суперпозиции этих функций получить не сможете.
Допустим, у Вас есть два параметра, скажем, x и y, оба равны 1. Есть также суперпозиция: $f_0(f_1(f_3(…), f_4(…)), f_2(f_5(…), f_6(…)))$ (функции могут повторяться, конечно же), и все функции сохраняют 1. Подставим во все функции с «максимальным уровнем вложенности» наши параметры. Все вернут 1.
Это будет эквивалентно подстановке единиц во все функции «предпоследнего» уровня.
И так мы раскручиваем всю цепочку вплоть до $f_0(u, v)$. Как думаете, чему будут равны u и v? Правильно, 1.
А тогда что вернёт $f_0$? Тоже 1. Она ведь сохраняет 1. Но нам-то нужен 0! Везде, даже на наборе $(1, 1)$!

Вот Вам готовый контрпример на утверждение о полноте Вашей системы.