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

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

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

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

$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\ldots a_{1\ldots 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.$

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