Предполные классы. Базисы

Класс называется предполным, если он не является полным в P₂ и добавление к нему любой функции, не принадлежащей этому классу, приводит к полной системе.

Лемма 15.Любой замкнутый класс, не совпадающий с P₂, содержится в одном из классов T₀,T₁,L,S,M.

Лемма 16.Любой предполный класс является замкнутым.

Лемма 17.В P₂существует только пять предполных классов, а именно: T₀,T₁,L,S,M.

Система функций называется базисом в P₂, если она полна, а любая ее собственная подсистема не полна.

Теорема 6.Любой базис в P₂ содержит не более четырех функций.

Критериальная таблица может быть полезной для нахождения базисов, содержащихся в системе A.

Пример 15. Проверить, является ли система A={xy, xÚz, Øx} базисом в P₂.

Критериальная таблица имеет вид

Система является полной, и ее подсистемы {xy, Øx} и {xÚz, Øx} также полны. Следовательно, A не является базисом в P₂.

Задачи

31.Выяснить, полны ли системы функций A и B:

31.1. , B={(0101), (11101000), (01101001)};

31.2. , B={(1001), (11101000)};

31.3. , B={(11),(00), (00110101)};

31.4. , B={(0111), (10010110)};

31.5. , B={(10), (00110111)};

31.6. , B={(11),(0111), (00110111)};

31.7. , B={(1011), (10010110)};

31.8. , B={(01011010), (00100001)};

31.9. , B={(1101), (10101001)};

31.10. , B={(1001),(0111), (01100110)}.

32.Проверить, является ли система функций A базисом в P₂:

32.1. ;

32.2. ;

32.3. ;

32.4. ;

32.5. ;

32.6. ;

32.7. ;

32.8. ;

32.9. ;

32.10. .