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

== [[Розв'язник вправ по дискретній математиці]]. Булева алгебра. Поліном Жегалкіна ==
'''Поліном Жегалкіна'''&nbsp;— довільна формула [[:w:Алгебра Жегалкіна|алгебри Жегалкіна]], яка має вигляд суми [[:w:кон'юнкція|кон'юнкцій]] булевих змінних. В зарубіжній літературі представлення полінома Жегалкіна зазвичай називається алгебраїчною нормальною формою (АНФ).

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

: <math> 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, </math>

: <math> a \ldots a_{1 \ldots n} \in \{0,1\} .</math>
Для трьох змінних поліном Жегалкіна має вигляд
: <math> 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. </math>

Побудуємо поліном  для функції <math>f(x,y,z)=(1110 0010)</math>. Запишемо [[:w:таблиця істинності|таблицю істинності]] функції і будемо послідовно знаходити коефіцієнти <math>a_i</math> підставляючи у функцію <math>f(x,y,z)</math> замість <math>x,y,z</math> конкретні значення.

{| class="wikitable"
|-
!<center><math>x</math></center>!!<center><math>y</math></center>!!<center><math>z</math></center>!!<center><math>f(x,y,z)</math></center>!!<center><math>a_i</math></center>
|-
| 0 || 0 || 0 || 1   || <math>a_0</math>
|-                        
| 0 || 0 || 1 || 1   || <math>a_3</math> 
|-                        
| 0 || 1 || 0 || 1   || <math>a_2</math> 
|-                        
| 0 || 1 || 1 || 0   || <math>a_{23}</math> 
|-                        
| 1 || 0 || 0 || 0   || <math>a_1</math> 
|-                        
| 1 || 0 || 1 || 0   || <math>a_{13}</math> 
|-                        
| 1 || 1 || 0 || 1   || <math>a_{12}</math> 
|-                        
| 1 || 1 || 1 || 0   || <math>a_{123}</math> 
|}

У першому рядку <math>f(0,0,0)=a_0~\oplus~a_1\wedge 0~\oplus~ a_2\wedge 0 ~\oplus~a_3\wedge 0 ~\oplus~ a_{12}\wedge 0\wedge 0 ~\oplus~ a_{13}\wedge 0\wedge 0 ~\oplus~ a_{23}\wedge 0\wedge 0 ~\oplus~ a_{123}\wedge 0\wedge 0\wedge 0=a_0. </math> Так як, <math>f(0,0,0)=1</math>, то і <math>a_0=1. </math>

Для другого рядка <math>f(0,0,1)=a_0~\oplus~a_1\wedge 0~\oplus~ a_2\wedge 0 ~\oplus~a_3\wedge 1 ~\oplus~ a_{12}\wedge 0\wedge 0 ~\oplus~ a_{13}\wedge 0\wedge 1 ~\oplus~ a_{23}\wedge 0\wedge 0 ~\oplus~ a_{123}\wedge 0\wedge 0\wedge 1=a_0~\oplus~a_3=1~\oplus~a_3. </math> Так як, <math>f(0,0,1)=1</math>, то і <math>1~\oplus~a_3=1,</math> отже <math>a_3=0.</math> 

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