Diskretka6
.pdfЗамкнутые классы функций Теорема Поста Доказательство теоремы Поста
Замыкание класса
Пусть 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].