Diskretka5

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

Примеры

Пусть C = f0; 1; _; &g.

1.x; y; z; t формулы.

2.x & y; y & z; x & z формулы.

3.x & y & t; y & z & t формулы.

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

Примеры

Пусть C = f0; 1; _; &g.

1.x; y; z; t формулы.

2.x & y; y & z; x & z формулы.

3.x & y & t; y & z & t формулы.

4.x & y & t _ y & z & t формула.

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

Примеры

Пусть C = f0; 1; _; &g.

1.x; y; z; t формулы.

2.x & y; y & z; x & z формулы.

3.x & y & t; y & z & t формулы.

4.x & y & t _ y & z & t формула.

5.x & y & t _ y & z & t _ x & z формула.

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

Примеры

Пусть C = f0; 1; _; &g.

1.x; y; z; t формулы.

2.x & y; y & z; x & z формулы.

3.x & y & t; y & z & t формулы.

4.x & y & t _ y & z & t формула.

5.x & y & t _ y & z & t _ x & z формула.

Любой монотонная функция (ДНФ без отрицаний) есть формула над C = f0; 1; _; &g.

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

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

Предложение 1. Если D : Bn ! B формула над C, и E1; E2; : : : ; En формулы над C, то выражение

D(E1; E2; : : : ; En) также является формулой над C.

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

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

Предложение 1. Если D : Bn ! B формула над C, и E1; E2; : : : ; En формулы над C, то выражение

D(E1; E2; : : : ; En) также является формулой над C.

Доказательство. Индукция по индуктивному определению

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

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

Предложение 1. Если D : Bn ! B формула над C, и E1; E2; : : : ; En формулы над C, то выражение

D(E1; E2; : : : ; En) также является формулой над C.

Доказательство. Индукция по индуктивному определению

IЕсли D(x1; : : : ; xm; : : : xn) = xm; m < n, переменная, то D(E1; E2; : : : ; En) = Em формула над C.

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

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

Предложение 1. Если D : Bn ! B формула над C, и E1; E2; : : : ; En формулы над C, то выражение

D(E1; E2; : : : ; En) также является формулой над C.

Доказательство. Индукция по индуктивному определению

IЕсли D(x1; : : : ; xm; : : : xn) = xm; m < n, переменная, то D(E1; E2; : : : ; En) = Em формула над C.

IЕсли D = f (A1; A2; : : : ; Ak ), где f 2 C и A1; A2; : : : ; An

формулы над C, то делаем индукционное предположение

о том, что A1(E1; : : : ; En); : : : ; Ak (E1; : : : ; En) формулы над C.

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

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

Предложение 1. Если D : Bn ! B формула над C, и E1; E2; : : : ; En формулы над C, то выражение

D(E1; E2; : : : ; En) также является формулой над C.

Доказательство. Индукция по индуктивному определению

IЕсли D(x1; : : : ; xm; : : : xn) = xm; m < n, переменная, то D(E1; E2; : : : ; En) = Em формула над C.

IЕсли D = f (A1; A2; : : : ; Ak ), где f 2 C и A1; A2; : : : ; An

формулы над C, то делаем индукционное предположение

о том, что A1(E1; : : : ; En); : : : ; Ak (E1; : : : ; En) формулы над C.Тогда

D(E1; E2; : : : ; En) = f (A1(E1; : : : ; En); : : : ; Ak (E1; : : : ; En))

снова формула над C.

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

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

Предложение 1. Если D : Bn ! B формула над C, и E1; E2; : : : ; En формулы над C, то выражение

D(E1; E2; : : : ; En) также является формулой над C.

Доказательство. Индукция по индуктивному определению

IЕсли D(x1; : : : ; xm; : : : xn) = xm; m < n, переменная, то D(E1; E2; : : : ; En) = Em формула над C.

IЕсли D = f (A1; A2; : : : ; Ak ), где f 2 C и A1; A2; : : : ; An

формулы над C, то делаем индукционное предположение

о том, что A1(E1; : : : ; En); : : : ; Ak (E1; : : : ; En) формулы над C.Тогда

D(E1; E2; : : : ; En) = f (A1(E1; : : : ; En); : : : ; Ak (E1; : : : ; En))

снова формула над C.

IТак как других формул D над C нет, предложение доказано.