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


Для трьох змінних поліном Жегалкіна має вигляд

Побудуємо поліном для функції
. Запишемо таблицю істинності функції і будемо послідовно знаходити коефіцієнти
підставляючи у функцію
замість
конкретні значення.
 |
 |
 |
 |
|
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 |
|
У першому рядку
Так як,
, то і
Для другого рядка
Так як,
, то і
отже
Послідовно підставляємо значення усіх рядків і знаходимо відповідні коефіцієнти.