Поліном Жегалкіна — довільна формула алгебри Жегалкіна, яка має вигляд суми кон'юнкцій булевих змінних. В зарубіжній літературі представлення полінома Жегалкіна зазвичай називається алгебраїчною нормальною формою (АНФ).
Теорема Жегалкіна — стверджує існування і унікальність будь-якої булевої функції у вигляді поліному Жегалкіна. Формально поліном Жегалкіна можна представити у вигляді:
![{\displaystyle P(X_{1}...X_{n})=a~\oplus ~a_{1}\wedge X_{1}~\oplus ~a_{2}\wedge X_{2}~\oplus ~...~\oplus ~a_{n}\wedge X_{n}~\oplus ~a_{12}\wedge X_{1}\wedge X_{2}~\oplus ~a_{13}\wedge X_{1}\wedge X_{3}~\oplus ~...~\oplus ~a_{1...n}\wedge X_{1}...\wedge X_{n},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f80422210d30a71be1d0007d31cbe07ce61b153)
![{\displaystyle a\ldots a_{1\ldots n}\in \{0,1\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df3a46b0c068278e9d6bc793e77850831bce0051)
Для трьох змінних поліном Жегалкіна має вигляд
![{\displaystyle f(x,y,z)=a_{0}~\oplus ~a_{1}\wedge x~\oplus ~a_{2}\wedge y~\oplus ~a_{3}\wedge z~\oplus ~a_{12}\wedge x\wedge y~\oplus ~a_{13}\wedge x\wedge z~\oplus ~a_{23}\wedge y\wedge z~\oplus ~a_{123}\wedge x\wedge y\wedge z.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4f1f9a638d9ac83e9678b97c563340e6908af9b)
Побудуємо поліном для функції
. Запишемо таблицю істинності функції і будемо послідовно знаходити коефіцієнти
підставляючи у функцію
замість
конкретні значення.
![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4) |
![{\displaystyle y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d) |
![{\displaystyle z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf368e72c009decd9b6686ee84a375632e11de98) |
![{\displaystyle f(x,y,z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5d48dce2c4341575269f1709237a2e18923237a) |
|
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 |
|
У першому рядку
Так як,
, то і
Для другого рядка
Так як,
, то і
отже
Послідовно підставляємо значення усіх рядків і знаходимо відповідні коефіцієнти.