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

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

ред.

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

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

 
 

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

 

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

 
 
 
 
 
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  

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

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

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