6-

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

Примеры:

I F = [f_; &; g]

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

Примеры:

I F = [f_; &; g] = [f_; g]

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

Примеры:

I F = [f_; &; g] = [f_; g] = [f&; g].

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

Примеры:

I F = [f_; &; g] = [f_; g] = [f&; g].

I [f1; +; g] = F.

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

Примеры:

I F = [f_; &; g] = [f_; g] = [f&; g].

I[f1; +; g] = F.

I[fjg] = [f#g] = F.

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

Замыкание класса

Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.

Определение. Пусть дан класс функций C F. Замыканием класса C называется класс [C], состоящий из всех функций, являющихся формулами над C.

Примеры:

I F = [f_; &; g] = [f_; g] = [f&; g].

I[f1; +; g] = F.

I[fjg] = [f#g] = F.

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

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

Свойства замыкания

Предложение 2. Для каждого C F имеет место C [C]:

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

Свойства замыкания

Предложение 2. Для каждого C F имеет место C [C]:

Доказательство. Пусть f (x1; x2; : : : ; xn) 2 C.