Diskretka5

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

Формулы над классом функций

Пусть 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 формула.

...