Здравствуйте, Кусмарцев Андрей Валерьевич.

Теорема Поста:
Для того, чтобы система функций была полной, необходимо и достаточно, чтобы
1) она содержала хотя бы одну функцию, не сохраняющую 0
x→y не сохраняет 0, 0→0 равно 1
2) хотя бы одну функцию, , не сохраняющую 1
¬(xΘyΘz)=0 при x=y=z=1
3) хотя бы одну несамодвойственную функцию

самодвойственная функция - двойственная сама себе. Двойственная функция - эта та, которая получается заменой аргументов на их отрицание и последующим отрицанием результата.
у импликации, например значения 1 1 0 1. Через конъюнкцию и дизъюнкцию она выражается как ¬x∧y
Двойственная ей функция будет 0 1 0 0. x∨¬y.

x→y не самодвойственна, так как не совпадает с двойственной ей функцией.

4) хотя бы одну немонотонную функцию
Монотонной функцией называется та, которая при больших значениях аргументов принимает большее значение

T≤≡{f|α<β⇒ f(α)≤f(β)
где α=(а1, ..., an), β=(b1, ..., bn), ai,bi∈E2, α≤β≡∀i ai≤bi

x→y немонотонная, так как f(0,0)=1, а f(1,0)=0.

5) хотя бы одну нелинейную функцию
Класс линейных функций
TL≤≡{f|f=c0+c1x+c2y}
Из функций 2 переменных линейными является сумма по модулю два и ей обратная, а также x и y

x→y нелинейная
Следовательно, наша система полная.