logo search
Лекции ДМ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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