61
правка
Изменения
→Полином Жегалкина
С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: <tex>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</tex>, который, в свою очередь, по [[Теорема Поста о полной системе функций|теореме Поста]] является полным.
'''Примеры:'''
<tex>f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 </tex>
<tex>f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 </tex>
<tex>f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 </tex>
=== Схемы из функциональных элементов ===
