Розв'язник вправ по дискретній математиці/Булева алгебра/Поліном Жегалкіна

Матеріал з Вікіпідручника
Перейти до навігації Перейти до пошуку

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

Теорема Жегалкіна — стверджує існування і унікальність будь-якої булевої функції у вигляді поліному Жегалкіна. Формально поліном Жегалкіна можна представити у вигляді:

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

Побудуємо поліном для функції . Запишемо таблицю істинності функції і будемо послідовно знаходити коефіцієнти підставляючи у функцію замість конкретні значення.

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

У першому рядку Так як, , то і

Для другого рядка Так як, , то і отже

Послідовно підставляємо значення усіх рядків і знаходимо відповідні коефіцієнти.