Функционально-полные системы функций
Алгебры логики
Логические выражения, с помощью которых представляются дискретные устройства могут содержать любые функции одного и двух аргументов (2.1) и (2.2). В этом случае для построения электрических схем необходимо выполнить техническую реализацию всех функций алгебры логики, входящих в логические выражения. Задача технической реализации всех функций алгебры логики является достаточно сложной и дорогостоящей. Избавиться от этой сложной задачи позволяют функционально-полные системы функций алгебры логики.
Система функций алгебры логики называется функционально полной, если с помощью функций, входящих в эту систему можно представить любую из 16 функций алгебры логики двух аргументов. В пятом столбце таблицы 1.6. все функции двух аргументов представлены одной их стандартных форм, которая называется совершенной дизъюнктивной нормальной формой (СДНФ). СДНФ включает в себя три функции алгебры логики
- отрицание «НЕ»,
- конъюнкцию «И»,
- дизъюнкцию «ИЛИ».
Этот состав функций «И», «ИЛИ», «НЕ» является основным функционально-полным набором функций алгебры логики.
При построении электрических схем дискретных устройств достаточно широко используются еще два функционально-полных набора, каждый из которых содержит только одну функций «И-НЕ» либо «ИЛИ-НЕ».
Таким образом, в дальнейшем будем использовать следующие три функционально-полных набора:
1. «И», «ИЛИ», «НЕ»;
2. «И-НЕ»;
3. «ИЛИ-НЕ».
Существуют и другие функционально-полные системы функций алгебры логики, но они практически не используются.
Для представления любого логического выражения любым функционально-полным набором необходимо сначала это выражение представить функционально полным набором «И», «ИЛИ», «НЕ» используя таблицу 1.6., а затем используя закон двойного отрицания и закон инверсии заданное выражение можно представить функционально-полным набором «И-НЕ» либо «ИЛИ-НЕ». Функционально-полные наборы называют базисами.
Пример 2.5. Представить логическое выражение ~
базисом «И», «ИЛИ», «НЕ».
Для этого согласно таблице 1.6. сначала избавимся от операции неравнозначности, а затем от операции равнозначности. В результате получим:
~
.
Согласно закону инверсии опустим знаки отрицания непосредственно на аргументы, раскроем скобки и получим следующий окончательный вариант
Для представления этого логического выражения базисом «И-НЕ» необходимо избавиться от операции ИЛИ (логического сложения). Для этого воспользуется сначала законом двойного отрицания и получим:
~
.
По закону инверсии опустим нижнюю черту двойного отрицания на аргумент
~
.
Таким образом в базисе «И-НЕ» присутствуют только две операции «И» (логическое умножение) и отрицание, которые реализуются одним логическим элементом.
Аналогично выполняется представление данного логического выражения базисом «ИЛИ-НЕ». Для этого необходимо избавиться от операции логического умножения.
~