Page 37 - 4496

h  C ( C 1 ( g 1 g , 2 ,..., g s ( ), C 2 ( g 1 g , 2 ,..., g s ),..., C m ( g 1 g , 2 ,..., g s ))
 C ( g g , ,..., g ).
1 2 s

Отже, h  C (g 1 , g 2 ,..., g s ).
Теорему доведено: В належить до повних систем.
Приклад
Розглянемо систему  3   , xxx 1 1 2 . За систему (2.1)
візьмемо систему  2
У відповідності з теоремою де Моргана
x  x  x 1 x .Це означає , що функцію х 1+х 2 можна виразити
2
2
1
через функції системи  3 .Отже , система  3 є повною.
Якщо в повній системі допускаються константи 1 і 0 , то
таку систему називають ослабленою повною системою.
Функціонально повна система утворює базис у
логічному просторі .Система функцій називається мінімально
повним базисом , якщо вилучення з неї будь-якої функції
перетворює цю систему на неповну( система  3 ).

2.18 Теорема Жегалкіна
Поліном вигляду
f (x 1 , x 2 ,..., x n )  k  k 1 x  k 2 x  k 3 x 1 x  ... k n x 1 x 2 ...x n ,
2
2
1
0
(де k , k ,..., k - коефіцієнти , що набувають значення 0 або 1)
1
n
0
називається поліномом Жегалкіна.
Загальне число членів полінома N  2 .
n
g
Теорема Жегалкіна .Будь-яку перемикальна функцію
 f   P можна подати у вигляді полінома Жегалкіна. Теорема
Жегалкіна дає можливість подати логічну функцію у вигляді
полінома різного степеня. Степінь полінома визначається
максимальною кількістю співмножників x , x ,..., x .
j
2
1
Приклад. Подати функцію х 1+х 2 через поліном
Жегалкіна.
34