Page 38 - 4496

1) Визначаємо кількість членів полінома: для n=2 маємо
n
N g  2  . 4
2) x  x  k  k 1 x  k 2 x  k 3 x 1 x 2 .
2
2
1
0
1
Складемо таблицю значень функцій
x 1 x 2 f 1 f 2
0 0 0 k 0
0 1 1 k  k 2
0
1 0 1 k  k 1
0
1 1 1 k  k  k  k 3
2
1
0
Оскільки повинна виконуватись умова f = f , то маємо
2
1
k =0, k =1, k 1  1, k 1  k 2  k 3  1  k 3  1.(логічне
0
2
додавання)( k 1  k 2  k 3  1).
Отже ,
x 1  x 2  x 1  x 2  x 1 x 2 (x 1  x 2  x  x  (x  x 2 )) .
1
1
2
2.19 Теорема про повноту функцій(теорема Поста)
Означення1. Для двох наборів   ( 1 , 2 ,..., n ) і
  ( 1 , 2 ,..., n ) виконуються відношення передування
якщо   1 ;    2 ;....   ; n .
1
n
2
Скорочено цей факт будемо позначати так:   
Означення2. Функція f (x 1 , x 2 ,..., x n ) називається
монотонною, якщо для двох будь-яких наборів, що
знаходяться у відношенні передування, справджується
нерівність (f )  f ( ) .
Означення3. Перемикальна функція f (x 1 , x 2 ,..., x n )
називається лінійною, якщо вона може бути подана у вигляді
лінійного полінома:
x ( f x , ,..., x )  k  k x  k x ... k x .
1 2 n 0 1 1 2 2 n n
35