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

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

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

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

$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,$

$a\dots a_{1\dots n}\in \{0,1\}.$

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

$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.$

Побудуємо поліном для функції $f(x,y,z)=(11100010)$. Запишемо таблицю істинності функції і будемо послідовно знаходити коефіцієнти $a_i$ підставляючи у функцію $f(x,y,z)$ замість $x,y,z$ конкретні значення.

$x$	$y$	$z$	$f(x,y,z)$	$a_i$
0	0	0	1	$a_0$
0	0	1	1	$a_3$
0	1	0	1	$a_2$
0	1	1	0	$a_{23}$
1	0	0	0	$a_1$
1	0	1	0	$a_{13}$
1	1	0	1	$a_{12}$
1	1	1	0	$a_{123}$

У першому рядку $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.$ Так як, $f(0,0,0)=1$, то і $a_0=1.$

Для другого рядка $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.$ Так як, $f(0,0,1)=1$, то і $1\oplus a_3=1,$ отже $a_3=0.$

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