Логический базис

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

Логический базис называют минимальным, если удаление хотя бы одной из входящих в него функций превращает его в функционально неполный. Логический базис И, ИЛИ, НЕ не является минимальным, так как с помощью закона дуальности (правил Де Моргана) можно исключить из логических выражений либо функцию И, либо функцию ИЛИ:

. (1.2.)

В результате получим минимальные базисы: И, НЕ и ИЛИ, НЕ.

Пример 1.1. Упростить выражение

( ) ( ) ( ).

Решение.Используя тождества 1б, 2а и 3б, получим

(( ) ( )) ( ) ( ).

Откуда на основании 1а, 4а, 4г, 3а, 4а, 1б имеем

( ) ( ( ) ( (

( ( ( .

Пример 1.2. Упростить выражение