3.4 Базисные логические функции
Любую логическую функцию можно представить совокупностью элементарных логических функций: дизъюнкцией, конъюнкцией, инверсией или их суперпозицией. Набор элементарных функций ИЛИ, И, НЕ называют функционально полным или базисным (базисом). Кроме того существуют еще два базиса: И-НЕ; ИЛИ-НЕ.
3.5 Принцип двойственности булевой алгебры
Если
в выражении F8=А
В
конъюнкцию заменить на дизъюнкцию и
проинвертировать обе переменные, то
результат окажется инверсией прежнего
значения функции
.
Аналогично, если в выражении F14=А
В
дизъюнкцию заменить на конъюнкцию и
проинвертировать обе переменные, то
результат окажется инверсией прежнего
значения функции
.
Указанные свойства логических функций отражают принцип двойственности булевой алгебры.
3.6 Основные тождества булевой алгебры
А+0=А;А+1=1;
А+А=А;А+
=1;
А*0=0;А*1=А;
А*А=А;А*
=0;
=А.
3.7 Основные законы и теоремы булевой алгебры
3.7.1 Законы
Переместительный (свойство коммутативности): А+В=В+А; А*В=В*А.
Сочетательный (свойство ассоциативности): (А+В)+С=А+(В+С); (А*В)*С=А*(В*С).
Распределительный (свойство дистрибутивности): А*(В+С)=А*В+А*С; А+В*С=(А+В)*(А+С).
3.7.2 Теоремы
Поглощения: А+А*В=А; А*(А+В)=А.
Склеивания:
Де Моргана. Существует две формы записи теоремы де Моргана:
Форма
1:
(3.1.1)
Форма
2:
(3.1.2)
Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).
Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:
(3.1.3)
Два полезных соотношения:
(3.1.4)
3.8 Совершенная дизъюнктивная нормальная форма (сднф) записи булевых выражений
СДНФ является одной из аналитических форм представления переключательных функций. Булевы выражения простых логических функций можно записать по их словесному описанию. В общем случае для получения аналитической формы (булевого выражения) используют таблицы истинности.
Предположим, логическая функция трех переменных задана таблицей истинности (таблица 3.4).
Таблица 3.4
-
№набора
С
В
А
F
0
0
0
0
0
1
0
0
1
1
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
1
7
1
1
1
0
Эта
функция имеет четыре конституенты
единицы К1,
К4, К5 и К6
(коституента единицы – это единичное
значение ПФ на одном конкретном наборе.
Всего для ПФ трех переменных может быть
восемь конституент единицы, если функция
принимает единичное значение на всех
наборах). Конституента единицы записывается
в виде конъюнкции. Для нашего примера
;
.
Булево выражение ПФ в СДНФ представляет сумму конституент единицы:
.(3.2)
Поскольку конституенты единицы записываются в виде конъюнкций, то СДНФ представляет сумму конъюнкций, каждая из которых содержит все переменные в прямом или инверсном виде не более одного раза. Очевидно, что логическая функция имеет единственное булево выражение в СДНФ, что следует из методики его получения.
СДНФ называется дизъюнктивной (состоит из суммы конъюнкций), совершенной (все конъюнкции содержат по одному разу каждую переменную в прямом или инверсном виде) и нормальной (двухуровневой) – для ее реализации требуются логические элементы двух видов: конъюнкторы и дизъюнкторы, при этом предполагается, что исходные переменные поступают в прямом и инверсном виде.