Докажите, что система функций является полной ⊕,+,~. Подробно обоснуйте решение, показав принадлежность функции из

Докажите, что система функций является полной ⊕,+,~. Подробно обоснуйте решение, показав принадлежность функции из набора к тому или иному классу эквивалентности функций, или приведите пример, опровергающий эту принадлежность.

Докажем, что система ⊕,+,~ функционально полна.
Функция f=A⊕B) сложения по модулю 2:
* сохраняет константу 0, так как f(0,0)=0;
* не сохраняет константу 1, т.к. f(1,1)=0;
* не монотонная, так как f(0,1)>f(1,1);
* не самодвойственная;
* линейная.
Функция g(A,B)=A+B (дизъюнкция):
* сохраняет константу 0, т.к . g(0,0)=0;
* сохраняет константу 1, т.к. g(1,1)=1;
* монотонна (в любой паре возрастающих наборов функция не уменьшается);
* не самодвойственная;
* не линейная, т.к. g(A,B)=A⊕B⊕AB;
Наконец, функция h(A,B)=A~B (эквивалентность):
* не сохраняет константу 0;
* сохраняет константу 1;
* не монотонна;
* не самодвойственна;
* линейная, т.к h(A,B)=1⊕A⊕B.
Составляем таблицу принадлежности функций системы основным классам булевых функций.
T0 T1 M S L
f + ─ ─ ─ +
g + + + ─ ─
h ─ + ─ ─ +
Как следует из построенной таблицы, для каждого из пяти основных классов булевых функций найдется функция, не принадлежащая этому классу

. g(0,0)=0;
* сохраняет константу 1, т.к. g(1,1)=1;
* монотонна (в любой паре возрастающих наборов функция не уменьшается);
* не самодвойственная;
* не линейная, т.к. g(A,B)=A⊕B⊕AB;
Наконец, функция h(A,B)=A~B (эквивалентность):
* не сохраняет константу 0;
* сохраняет константу 1;
* не монотонна;
* не самодвойственна;
* линейная, т.к h(A,B)=1⊕A⊕B.
Составляем таблицу принадлежности функций системы основным классам булевых функций.
T0 T1 M S L
f + ─ ─ ─ +
g + + + ─ ─
h ─ + ─ ─ +
Как следует из построенной таблицы, для каждого из пяти основных классов булевых функций найдется функция, не принадлежащая этому классу