lec08

Классом функций, сохраняющим 0, называются все БФ (x1, x2, … xn), для которых: (0, 0, …,0) = 0. Обозначение: T0.

Классом функций, сохраняющим 1, называются все БФ (x1, x2, … xn), для которых выполняется (1, 1, …, 1) = 1. Обозначение: T1.

Теорема 8.3. Классы функций, сохраняющих const, являются замкнутыми:

[T1] = T1; [T0] = T0.

Доказательство.

Пусть 1(x1, x2, … xn), 2(x1, x2, … xn), … S(x1, x2, … xn) T0

Рассмотрим их суперпозицию.

T0 (x1, x2, … xn) = i( 1(x1, x2, … xn), 2(x1, x2, … xn), … S(x1, x2, … xn)).

Проверим это, вычислив:

(0,0, … 0) = i( 1(0,0, … 0), 2(0,0, … 0), … S(0,0, … 0)) = i(0,0, … 0) = 0.

Таким образом [T0] = T0.

Вторая часть теоремы для T1 доказывается аналогично.

!!! Итог: Замкнутыми являются классы L, M, S, T0, T1. Эти классы называются основными замкнутыми классами функций.

21

Свойства булевых функций с позиций функциональной полноты.