6-

Замкнутые классы функций

Замкнутые классы

Определение. Класс функций C F называется замкнутым, если [C] = C,то есть каждая формула над C принадлежит C.

Примеры

IКласс всех функций F замкнутый.

IВ силу Предложения 4 любое замыкание [C] является замкнутым классом.

IM = [f0; 1; _; &g] класс монотонных функций.

IL = [f0; 1; +g] класс линейных функций, состоящих

из многочленов Жегалкина вида a0 + a1x1 + + anxn; где ai 2 B:

Замкнутые классы функций

Замкнутые классы

Предложение 5. Для того чтобы класс C был замкнутым необходимо и достаточно, чтобы тождественная функция (то есть сама переменная) принадлежала C, и

g = f (A1; : : : ; An) 2 C для всех f ; A1; : : : ; An 2 C:

Замкнутые классы функций

Замкнутые классы

Предложение 5. Для того чтобы класс C был замкнутым необходимо и достаточно, чтобы тождественная функция (то есть сама переменная) принадлежала C, и

g = f (A1; : : : ; An) 2 C для всех f ; A1; : : : ; An 2 C:

Доказательство. Необходимость очевидна. Докажем достаточность индукцией по индуктивному определению.

Замкнутые классы функций

Замкнутые классы

Предложение 5. Для того чтобы класс C был замкнутым необходимо и достаточно, чтобы тождественная функция (то есть сама переменная) принадлежала C, и

g = f (A1; : : : ; An) 2 C для всех f ; A1; : : : ; An 2 C:

Доказательство. Необходимость очевидна. Докажем достаточность индукцией по индуктивному определению.

I Каждая переменная есть Imn 2 C.

Замкнутые классы функций

Замкнутые классы

Предложение 5. Для того чтобы класс C был замкнутым необходимо и достаточно, чтобы тождественная функция (то есть сама переменная) принадлежала C, и

g = f (A1; : : : ; An) 2 C для всех f ; A1; : : : ; An 2 C:

Доказательство. Необходимость очевидна. Докажем достаточность индукцией по индуктивному определению.

IКаждая переменная есть Imn 2 C.

IПусть f 2 C и A1; A2; : : : ; An формулы над C. Делаем индукционное предположение о том, что

A1; A2; : : : ; An 2 C.

Замкнутые классы функций

Замкнутые классы

Предложение 5. Для того чтобы класс C был замкнутым необходимо и достаточно, чтобы тождественная функция (то есть сама переменная) принадлежала C, и

g = f (A1; : : : ; An) 2 C для всех f ; A1; : : : ; An 2 C:

Доказательство. Необходимость очевидна. Докажем достаточность индукцией по индуктивному определению.

IКаждая переменная есть Imn 2 C.

IПусть f 2 C и A1; A2; : : : ; An формулы над C. Делаем индукционное предположение о том, что

A1; A2; : : : ; An 2 C. Так как f формула над C, то по нашим условиям новая формула f (A1; A2; : : : ; An) над C будет принадлежать C.

Замкнутые классы функций

Замкнутые классы

Предложение 5. Для того чтобы класс C был замкнутым необходимо и достаточно, чтобы тождественная функция (то есть сама переменная) принадлежала C, и

g = f (A1; : : : ; An) 2 C для всех f ; A1; : : : ; An 2 C:

Доказательство. Необходимость очевидна. Докажем достаточность индукцией по индуктивному определению.

IКаждая переменная есть Imn 2 C.

IПусть f 2 C и A1; A2; : : : ; An формулы над C. Делаем индукционное предположение о том, что

A1; A2; : : : ; An 2 C. Так как f формула над C, то по нашим условиям новая формула f (A1; A2; : : : ; An) над C будет принадлежать C.

IТак как других формул над C нет, каждая формула над C принадлежит C, то есть [C] = C.

Замкнутые классы функций

Класс T0

Теорема. Класс T0, состоящий из всех f 2 F, для которых f (0; : : : ; 0) = 0, является замкнутым.

Замкнутые классы функций

Класс T0

Теорема. Класс T0, состоящий из всех f 2 F, для которых f (0; : : : ; 0) = 0, является замкнутым.

Доказательство. Пусть f ; A1; : : : ; An 2 T0 и g = f (A1; : : : ; An).

Замкнутые классы функций

Класс T0

Теорема. Класс T0, состоящий из всех f 2 F, для которых f (0; : : : ; 0) = 0, является замкнутым.

Доказательство. Пусть f ; A1; : : : ; An 2 T0 и g = f (A1; : : : ; An). Тогда

g(0; : : : ; 0) = f (A1(0; : : : ; 0); : : : ; An(0; : : : ; 0)) = f (0; : : : ; 0) = 0;

так что g 2 T0: