lec08
.pdfКлассом функций, сохраняющим 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
Свойства булевых функций с позиций функциональной полноты.
|
|
|
Принадлежность к классу |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
T0 |
|
T1 |
L |
M |
S |
|
||
|
|
|
|
||||||
≡0 |
+ |
|
|
+ |
+ |
|
|
|
|
≡1 |
|
|
+ |
+ |
+ |
|
|
|
|
|
x |
+ |
|
+ |
+ |
+ |
|
+ |
|
x |
|
|
|
+ |
|
|
+ |
|
|
x1 x2 |
+ |
|
+ |
|
+ |
|
|
|
|
|
|
|
|
|
|
|
|
||
x1 |
x2 |
+ |
|
+ |
|
+ |
|
|
|
x1 x2 |
+ |
|
|
+ |
|
|
|
|
|
x1 |
x2 |
|
|
+ |
+ |
|
|
|
|
x1 x2 |
|
|
+ |
|
|
|
|
|
|
(x1 |
x2) |
+ |
|
|
|
|
|
|
|
x1 |
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
x1 | x2 |
|
|
|
|
|
|
|
22 |