Diskretka5
.pdfЗамкнутые классы функций
Формулы над классом функций
Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.
Замкнутые классы функций
Формулы над классом функций
Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.
Определение. Пусть дан класс функций C F. Понятие формулы над классом C определяется по индукции:
Замкнутые классы функций
Формулы над классом функций
Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.
Определение. Пусть дан класс функций C F. Понятие формулы над классом C определяется по индукции:
I Каждая переменная есть формула над C.
Замкнутые классы функций
Формулы над классом функций
Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.
Определение. Пусть дан класс функций C F. Понятие формулы над классом C определяется по индукции:
IКаждая переменная есть формула над C.
IЕсли f 2 C, f : Bn ! B, и A1; A2; : : : ; An формулы над C, то выражение f (A1; A2; : : : ; An) тоже является формулой над C.
Замкнутые классы функций
Формулы над классом функций
Пусть F класс всех булевых функций f : Bn ! B, n 2 N [ f0g.
Определение. Пусть дан класс функций C F. Понятие формулы над классом C определяется по индукции:
IКаждая переменная есть формула над C.
IЕсли f 2 C, f : Bn ! B, и A1; A2; : : : ; An формулы над C, то выражение f (A1; A2; : : : ; An) тоже является формулой над C.
IДругих формул над C нет.
Замкнутые классы функций
Примеры
Пусть C = f g = f:g.
Замкнутые классы функций
Примеры
Пусть C = f g = f:g.
1. x формула.
Замкнутые классы функций
Примеры
Пусть C = f g = f:g.
1.x формула.
2.x формула.
Замкнутые классы функций
Примеры
Пусть C = f g = f:g.
1.x формула.
2.x формула.
3.x формула.
Замкнутые классы функций
Примеры
Пусть C = f g = f:g.
1.x формула.
2.x формула.
3.x формула.
4.x формула.
...