Поліном Жегалкіна — довільна формула алгебри Жегалкіна, яка має вигляд суми кон'юнкцій булевих змінних. В зарубіжній літературі представлення полінома Жегалкіна зазвичай називається алгебраїчною нормальною формою (АНФ).
Теорема Жегалкіна — стверджує існування і унікальність будь-якої булевої функції у вигляді поліному Жегалкіна. Формально поліном Жегалкіна можна представити у вигляді:
Для трьох змінних поліном Жегалкіна має вигляд
Побудуємо поліном для функції . Запишемо таблицю істинності функції і будемо послідовно знаходити коефіцієнти підставляючи у функцію замість конкретні значення.
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
У першому рядку Так як, , то і
Для другого рядка Так як, , то і отже
Послідовно підставляємо значення усіх рядків і знаходимо відповідні коефіцієнти.