Page 36 - 4496

2.17 Набори повних систем

Розглянемо систему булевих функцій , які утворюють
множину .
Означення. Система функцій f (x 1 , x 2 ,..., x n )  f   P
називається функціонально повною , якщо будь-яка булева
функція може бути записана у вигляді формули через функції
цієї системи.
Приклади:
1 Система Р- множина всіх булевих функцій від двох
змінних (16) є повною.
2 Система  2   , xx 1 1  x 2 , xx 1 2  є повною (на основі
попередньої теореми)

Теорема про набори повних систем
Нехай задано дві системи функцій
A   f , f ,..., f m  (2.1)
2
1
B  g , g ,..., g s  (2.2)
1
2
відносно яких відомо, що система (2.1) повна і кожна її
функція виражається у вигляді формули через функції
системи (2.2). Тоді система (2.2) також є повною
Доведення
Нехай h -довільна система функцій, h P . З
врахуванням системи функцій (2.1) h можна виразити через
f  P :
h  C ( f 1 , f 2 ,..., f m ).
За умовою теореми
f  C 1 (g 1 , g 2 ,..., g s );
1
f  C 2 (g 1 , g 2 ,..., g s );
2
..................................
f  C m (g 1 , g 2 ,..., g s );
m
f , f ,..., f
У формулу (2.3) замість 1 2 m підставимо їх
значення. Тоді

33