Все полные системы для классов t0, t1, s, m, l в утверждениях выше являются базисами для этих систем.

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

1. - эта система полна в Т₀ . Покажем, что любая собственная подсистема полной в Т₀ не является. Рассмотрим . Т.к. ,тогда , но функция не является полной в классе Т₀ .

Рассмотрим в силу того, что не является полной в классе Т₀ . Таким образом все собственные подсистемы не полны в классе Т₀, поэтому - базис в Т₀ .

2) - эта система полна в Т₁ . Покажем, что все собственные подсистемы не полны в Т₁. Покажем, что не полна в Т₁ , а именно . Для этого рассмотрим класс К следующих функций: , если и только если для любых 2-х наборов значений переменных, на которых значение функции равно 0 существует переменная равная 0 в обоих наборах, причем наборы не обязательно различные:

Например

0 0 1 1 0 0

0 1 1 1 0 0

1 0 0

1 1 1 в обоих наборах.

Из определения следует, что на единичном наборе функция из К равна единице.

0 0 0

0 1 1

1 0 1 0 0 в обоих наборах

1 1 1 0 0

0 0 0

0 1 0 0 1

1 0 0 1 0

1 1 1

Утверждение:

Класс К замкнут относительно суперпозиции функций.

Доказательство: Пусть

Образуем их суперпозицию:

Пусть верно противное - суперпозиция , тогда существует пара наборов значений переменных

:

для любого и для любого

Обозначим

.

Тогда на обоих наборах значение равно 0. В силу того, что , и т.к. в наборах нет переменной, равной нулю, такой переменной должна быть последняя переменная , т. е. . Но для наборов нет переменной, равной нулю в обоих наборах, следовательно получаем противоречие с тем, что . Утверждение доказано.

В силу того, что . Но .

Рассмотрим в силу того, что , имеем, . Таким образом все собственные подсистемы системы полными в Т₁ не являются, и тогда является базисом в Т₁ .

2. есть базис в S. Эта система полна в классе S. Покажем, что все собственные подсистемы данной системы в классе S полными не являются - эта функции у которых ровно одна существенная переменная, а функция имеет три существенные переменные. Поэтому .

3. Рассмотрим функцию

, поэтому система - базис в S .

4) Покажем, что - базис в М. Во-первых эта система полна в классе М . Покажем, что все собственные подсистемы не полные.

а функции дизъюнкции в замыкании нет поэтому система не полна в классе М.

, а функции в замыкании нет, следовательно система не полна в классе М следовательно начальная система есть базис в классе монотонных функций.

5) Система полна в классе L . Покажем, что все собственные подсистемы в классе линейных полными не являются:

следовательно начальная система является базисом в классе линейных функций.

Замечание

Вопросы о представлении функций в монотонном базисе потребуются в следующем разделе минимизации двоичных фукций.

Замечание

Пост нашел все замкнутые классы в классе двоичных функций и описал структуру их взаимных вложений.