3. Независимые системы. Базис замкнутого класса.

Система функций G называется независимой, если никакая функция fG не представима суперпозициями функций из G\f.

Примеры независимых систем:

{, -}, {V, -}.

Система {, V, -} не является независимой, т.к. удалив V или ,получим систему, суперпозициями функций которой можно представить любую из функций системы {, V, -}.

Независимая система функций G называется базисом замкнутого класса К, если всякая функция из К есть суперпозиция функций из G.

Например, системы {-, V}, {-, } являются базисом для класса Р₂, т.к. системы полные и независимые.

Система {+, v, 1,0} не является базисом для Р₂, т.к. хотя она полная, но не является независимой: можно удалить 0. значит базисом для Р₂ является система {+, v, 1}.

Функции, образующие базис во множестве всех булевых функций Р₂, называются шефферовыми функциями.

Например, функции x|y и ху – шефферовые, т.к. каждая из них образует полную систему (было доказано выше), причем, независимую.

Функция ху не является шефферовой, т. к. не образует полную систему: 11=1, т.е. хуТ₁.

Задачи для самостоятельного решения.

1. Выразить импликацию через функции системы {1, +, }.

2. Выразить дизъюнкцию и конъюнкцию через функции системы {-, }.

3. С помощью достаточного условия полноты проверить на полноту систему а) {0, v, }; б) {-, }; в) {0, +, }.

4. С помощью теоремы Поста проверить на полноту системы : {+, V, , -}, {, , -}, {, -}, {1, 0, -}.

5. Является ли система {1,0,+,} базисом множества всех булевых функций?

6. Являются ли функции ху, ху, xvy, шефферовыми функциями?

Контрольные вопросы

1. Что называется замыканием множества булевых функций?

2. Перечислить свойства замыкания.

3. Что такое суперпозиция? Какие суперпозиции относятся к элементарным?

4. Сформулировать два определения функционально замкнутого класса.

5. Сформулировать и доказать утверждение о принадлежности полной системы только к замкнутому классу Р₂ .

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

7. Сформулировать теорему Поста. Что собой представляет таблица Поста?

8. Какая система булевых функций называется независимой?

9. Что такое базис замкнутого класса?

10. Какие функции называются шефферовыми?