Diskretka6

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

Пусть 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 C [C].

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

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

Свойства:

IC [C].

I[[C]] = [C].

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

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

Свойства:

IC [C].

I[[C]] = [C].

IC D =) [C] [D].

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

Примеры

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

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

Примеры

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

I[C].

Замкнутые классы функций Теорема Поста Доказательство теоремы Поста

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

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

Примеры

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

I[C].

IM = [f0; 1; _; &g].