37 lines
2.2 KiB
Markdown
37 lines
2.2 KiB
Markdown
Базис. Теорема о размере базиса. * Базис замкнутого класса. Примеры базисов.
|
||
# Базис
|
||
- **Базис**
|
||
1. минимальная по включению полная система функций
|
||
2. полная система, которая перестаёт быть таковой после удаления любой функции
|
||
## Примеры
|
||
- [[1 курс/2 семестр/Дискретка/Билеты/15#^27f049|Шефферовы функции]]
|
||
- $\set{xy, \bar x}$
|
||
- $\set{x \vee y, \bar x}$
|
||
- $\set{xy, x \oplus y, 1}$
|
||
|
||
# Теорема о размере базиса
|
||
## Теорема
|
||
Каждый базис содержит не более четырех
|
||
функций.
|
||
|
||
## Доказательство
|
||
Покажем, что в каждой полной системе содержится полная подсистема не более чем из четырех функций. По [[1 курс/2 семестр/Дискретка/Билеты/15#Теорема|теореме Поста]] в любой полной системе имеются функции $f_1 \notin T_0, f_2 \notin T_1, f_3 \notin S, f_4 \notin M, f_5 \notin L$
|
||
|
||
Множество $\set{f_1, f_2, f_3, f_4, f_5}$ - полная система
|
||
Рассмотрим $f_1$. Т.к. $f_1 \notin T_0$, то $f_1(0, \dots, 0) = 1$
|
||
|
||
Если $f_1(1, \dots, 1) = 1$, то $f_1 \notin S$, тогда множество $\set{f_1, f_2, f_4, f_5}$ - полная система
|
||
Иначе $f_1 \notin T_1; f_1 \notin M$, тогда $\set{f_1, f_3, f_5}$ - полная система
|
||
|
||
# Базис замкнутого класса
|
||
- **Базис замкнутого класса** - минимальная по включению система функций Y такая, что $[Y] = X$
|
||
## Примеры
|
||
- $S = [\set{x \bar y \vee x \bar z \vee \bar y \bar z}] = [\set{\bar x, m(x, y, z)}]$
|
||
- $M = [\set{0, 1, xy, x \vee y}]$
|
||
- $L = [\set{x \oplus y, 1}]$
|
||
- $LS = [\set{\overline{x \oplus y \oplus z}}] = [\set{\bar x, l_3(x, y, z)}]$
|
||
- $T_0T_1M = [\set{xy, x \vee y}]$
|
||
|
||
# Задача
|
||
$\begin{equation*} if(x, y, z) = \begin{cases} y, x = 1\\ z, x = 0 \end{cases} \end{equation*}$
|
||
Доказать, что $T_0T_1 = [\{if\}]$ |