Глава 22. Полнота

Выделяются следующие классы булевых функций:

1. Класс функций, сохраняющих 0:

T0 = {F | F (0, … ,0) = 0}.

2. Класс функций, сохраняющих 1:

T1 = {F | F (1, … ,1) = 1}.

3. Класс самодвойственных функций:

T* = {F | F = F*}.

4. Класс монотонных функций:

T< = {F | A £ B Þ F(A) £ F(B)},

Где A = (А1, ... ,аN), B = (B1, … ,Bn), АI, Bi Î Е2, A < B = " I Ai £ Bi.

5. Класс линейных функций:

TL = {F | F = C0 Å C1X1 Å … Å Cnxn}.

Где + обозначает сложение по модулю 2, а знак конъюнкции опущен.

Множество функций F Образует Полную систему, если любая функция реализуема в виде формулы над F.

ТЕОРЕМА (Пост) Система булевых функций F полна тогда и только тогда, ко­гда она содержит хотя бы одну функцию, не сохраняющую нуль, хотя бы одну функцию, не сохраняющую единицу, хотя бы одну несамодвойственную функцию, хотя бы одну немонотонную функцию и хотя бы одну нелинейную функцию.

Пример

Системы {Ú, Ø}, {Ù, Ø} являются полными.

< Предыдущая		Следующая >