Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Понятие о полноте системы БФ

Рассмотренные ранее простейшие логические операции И, ИЛИ, НЕ представляют собой элементарные функции алгебры логики. Совокупность простейших логических функций позволяет реализовать любую сколь угодно сложную БФ, представленную в аналитическом виде:

Такая совокупность функций получила название функционально полной системы (ФПС) или базиса.

Базис, включающий логические операции И, ИЛИ, НЕ, называют булевым базисом.

Удаление из ФПС хотя бы одной функции превращает эту систему в минимальный базис. Отметим, что булев базис является функционально полным, но не минимальным. Из него можно получить два минимальных базиса: И и НЕ либо ИЛИ и НЕ. Действительно, на основе теорем алгебры Буля из булева базиса можно исключить либо функцию ИЛИ, либо функцию И:

- для И, НЕ (исключается функция ИЛИ):

- для ИЛ И,НЕ (исключается функция И):

Из этого следует, что с помощью каждого из приведенных минимальных базисов можно реализовать любую элементарную функцию, т.е. они обладают функциональной полнотой. Одновременно отметим, что совокупность функций И, ИЛИ не является минимальным базисом. Кроме булева базиса, к числу элементарных относятся также функции:

ИЛИ-HE: F = XvY (функция Пирса);

И-НЕ: F = X Y (функция Шеффера).

Как показано ранее, эти функции реализуются комбинированными ЛЭ ИЛИ-HE и И-НЕ. Используя теоремы алгебры Буля, также можно показать, что эти элементарные функции составляют минимальный базис:

Вывод: минимальные базисы ИЛИ-HE, И-НЕ обладают функциональной полнотой, т.е., имея только комбинированные ЛЭ ИЛИ-HE, И-НЕ, можно построить логическую схему любой сложности.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>