	Базис. Теорема о размере базиса. * Базис замкнутого класса. Примеры базисов.
# Базис
- **Базис** 
	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\}]$