Многие, наверное, знают о полиномах Жегалкина, это известный способ задания функции алгебры логики. Выглядят они примерно так:

G(x,y,z) = xy ⊕ yz ⊕ x

Разумеется, длина каждой конъюнкции может быть произвольной, как и их количество. Порядок их не имеет значение, и конъюнкции не должны повторяться (от повторов можно избавляться, уничтожая “дубли” парами). Также возможна конъюнкция длины 0, обозначаемая “1”.

У полиномов Жегалкина есть одно замечательное и простое свойство: каждая функция представима ровно одним полиномом Жегалкина.

Доказывается это так. Сначала заметим, что сумма (сложение по модулю 2) произвольных двух полиномов Жегалкина равна 0 тогда и только тогда, когда они совпадают (иначе бы нашлось бы два разных значения, и он где-то равнялся бы 1). Теперь возьмём два разных полинома Жегалкина (“разных” здесь - разных по записи), и сложим их попарно. У нас получится некоторый новый полином Жегалкина.

Теперь посмотрим, чему он равен: 0 он не может равняться, т.к. полиномы разные, значит, в нём есть конъюнкции. Тогда возьмём какую-то конъюнкцию минимальной длины, и сделаем все её переменные единицами, а остальные - нулями. На этих переменных полином будет отличаться от значения на “всех нулях”, и тогда у нас найдётся значение 1 среди этих двух, либо же полином “разности” изначально равнялся 1.

Мы доказали, что все полиномы Жегалкина дают разные функции. Осталось заметить только, что, так как конъюнкций n переменных существует 2^n, полиномов будет 2^(2^n), что совпадает с числом булевых функций от n переменных.

Наверное, самое красивое среди булевой логики первого курса. Нет, ещё теорема Поста о 5 предполных классах. И автоматы с задержкой.