Базис (функционально полный набор) – это множество логических функций, суперпозицией которых можно представить любую логическую формулу, т. е. полная система логических функций.
Базисы могут быть избыточными и минимальными. Например, система функций И, Или, НЕ (булев базис, базис Буля) – избыточный базис, так как при удалении из него некоторых функций (функции ИЛИ или функции И) система остаётся полной.
Минимальными базисами являются системы: 1) И, НЕ; 2) ИЛИ, НЕ; 3) И-НЕ (базис Шеффера); 4) ИЛИ-НЕ (базис Пирса). При удалении из таких базисов любой операции они перестают быть полными системами функций.
Одни и те же преобразования логических переменных можно задать в различных формах (базисах). Выбор базиса зависит от простоты реализации той или иной функции с помощью логических операций данной системы функций. Чаще всего используются базисы Шеффера и Пирса, т. к. они содержат только одну операцию, и для реализации сложной схемы нужен только один тип ЛЭ. В развитых сериях стандартных интегральных схем (ИС) наряду с базовыми ЛЭ обычно имеется и ряд других, выполняющих другие логические операции.
|
|
В табл. 2.9 приведено несколько полезных свойств булевых функций НЕ, И, ИЛИ, формулы перехода между базисами И-НЕ и ИЛИ-НЕ (законы де Моргана), а также формулы перехода от операций импликация, тождественность и сумма по модулю 2 в базис Буля. Все приведённые соотношения можно легко проверить с помощью их таблиц истинности.
Таблица 2.9
№ | Формулы булевой алгебры | Формулы в упрощённой записи | Название свойства |
Коммутативность (перемена мест операндов) | |||
Ассоциативность (последовательность выполнения операций) | |||
Дистрибутивность (раскрытие скобок) | |||
Законы исключённого третьего | |||
Законы тождественных операндов | |||
Законы поглощения | |||
Свойства нуля | |||
Свойства единицы | |||
Свойство двойного отрицания | |||
Законы (формулы) де Моргана | |||
Свойство импликации | |||
Свойства эквивалентности | |||
Свойства сложения по модулю два |
Далее по возможности будем пользоваться упрощёнными обозначениями логических операций.
Докажем некоторые из приведённых свойств:
7. ;
;
12. ; ;
13. ; .
Введём понятие терма.
Терм – это дизъюнкция или конъюнкция любого числа переменных, взятых с отрицанием или без него. В терм в общем случае не обязательно должны входить все переменные, он даже может состоять только из одной переменной.
Термы, состоящие только из одной переменной, взятой с отрицанием или без него, называются первичными термами.
Ранг терма определяется количеством переменных, входящих в данный терм.
|
|
Терм в виде конъюнкции переменных, взятых с отрицанием или без него, называется конъюнктивным термом, конституентой единицы (любой такой терм, принимающий значение 1, автоматически приводит к единичному значению функции) или минтермом (для принятия функцией значения 1 требуется минимальное количество единичных термов, а точнее только один). Под минтермом обычно понимается конъюнктивный терм, содержащий все переменные логической функции.
Терм, являющийся дизъюнкцией логических переменных в прямом или инверсном виде, называется дизъюнктивным термом, конституентой нуля (любой такой терм, принимающий значение 0, автоматически приводит к нулевому значению функции) или макстермом (для принятия функцией значения 1 требуется максимальное количество единичных термов, а точнее всех термов). Под макстермом обычно понимается дизъюнктивный терм, содержащий все переменные логической функции.
Теорема 2.1. Любая логическая функция может быть представлена как суперпозиция только трёх функций: И, ИЛИ и НЕ.
Доказательство данной теоремы основано на лемме о дизъюнктивном разложении.
Лемма. Любая булева функция f (x 1 , x 2 , …, xm) от m переменных может быть представлена так:
. (2.4)
Действительно, при xi = 0 правая часть этой формулы принимает значение
;
аналогично при xi = 1 правая часть
.
Итак, правая часть формулы (2.4) при всех наборах аргументов совпадает с левой, что доказывает справедливость формулы (2.4).
Разложим функцию f (x 1 , x 2 , …, xm) последовательно по переменным x 1 , x 2 , …, xm :
Таким образом, любую булеву функцию можно представить как дизъюнкцию термов, каждый из которых представляет собой конъюнкцию всех переменных (с отрицаниями или без них) и значения этой функции на соответствующем конкретном наборе значений переменных.
Примем для σ {0, 1} x σ= при σ = 0 и x σ= x при σ = 1. Тогда окончательная форма представления любой булевой функции будет иметь вид:
. (2.5)
Поскольку значения функции на каждом конкретном наборе равны либо 0, либо 1, то в формуле (2.5) останутся только такие термы, которые соответствуют наборам переменных, на которых функция равна единице:
. (2.6)
Представление булевой функции в форме дизъюнкции конъюнктивных термов (конституент единицы) Ki
, , (2.7)
называется дизъюнктивной нормальной формой (ДНФ) этой функции.
Если все конъюнктивные термы в ДНФ являются минтермами, т. е. содержат в точности по одной все логические переменные, взятые с отрицаниями или без них, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ) этой функции. СДНФ называется совершенной, потому что каждый терм в дизъюнкции включает все переменные; дизъюнктивной, потому что главная операция в формуле – дизъюнкция. Понятие “ нормальной формы ” означает однозначный способ записи формулы, реализующей заданную функцию.
С учётом сказанного выше из теоремы 2.1 вытекает следующая теорема.
Теорема 2.2. Любая булева функция (не равная тождественно 0) может быть представлена в СДНФ, причём такое представление единственно.
Пример 2.3. Пусть имеем таблично заданную функцию f (x 1 , x 2 , x 3) (табл. 2.10).
Таблица 2.10
x 1 | x 2 | x 3 | f (x 1 , x 2 , x 3) |
На основании формулы (2.6) получаем:
.
Как видно, при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов, при которых функция принимает значение 1.
Представление булевой функции в форме конъюнкции дизъюнктивных термов (конституент нуля) Di
, , (2.8)
называется конъюнктивной нормальной формой (КНФ) этой функции.
Если все дизъюнктивные термы КНФ являются макстермами, т. е. содержат в точности по одной все логические переменные функции, взятые с отрицаниями или без них, то такая КНФ называется совершенной конъюнктивной нормальной формой (СКНФ) этой функции.
|
|
Теорема 2.3. Любая булева функция (не равная тождественно 1) может быть представлена в СКНФ, причём такое представление единственно.
Доказательство теоремы может быть проведено аналогично доказательству теоремы 2.1 на основании следующей леммы Шеннона о конъюнктивном разложении.
Лемма Шеннона. Любая булева функция f (x 1 , x 2 , …, xm) от m переменных может быть представлена так:
. (2.9)
Нужно отметить, что обе формы представления логической функции (ДНФ и КНФ) теоретически являются равными по своим возможностям: любую логическую формулу можно представить как в ДНФ (кроме тождественного нуля), так и в КНФ (кроме тождественной единицы). В зависимости от ситуации представление функции в той или иной форме может быть короче.
На практике же чаще всего используется ДНФ, т. к. эта форма является для человека более привычной: с детства ему привычнее складывать произведения, чем умножать суммы (в последнем случае у него интуитивно появляется желание раскрыть скобки и перейти тем самым к ДНФ).
Пример 2.4. Для функции f (x 1 , x 2 , x 3), заданной табл. 2.10, написать её СКНФ.
В отличие от СДНФ, при составлении СКНФ в таблице истинности логической функции нужно смотреть комбинации переменных, при которых функция принимает значение 0, и составить конъюнкцию соответствующих макстермов, но переменные нужно брать с обратной инверсией:
.
Нужно отметить, что непосредственно перейти от СДНФ функции к её СКНФ или наоборот невозможно. При попытке таких преобразований получаются функции, обратные по отношению к желаемым. Выражения для СДНФ и СКНФ функции непосредственно можно получить только из её таблицы истинности.
Пример 2.5. Для функции f (x 1 , x 2 , x 3), заданной табл. 2.10, попробовать перейти от СДНФ к СКНФ.
Используя результат примера 2.3 получим:
Как видно, под общей инверсией получилась СКНФ логической функции, которая является обратной по отношению к функции, полученной в примере 2.4:
|
|
,
т. к. содержит все макстермы, которых нет в выражении для СКНФ рассматриваемой функции.
Далее приведём систематическую процедуру (алгоритм) преобразования аналитической записи функции в нормальную форму с использованием свойств булевых функций.
1. Используя свойства операций (см. табл. 2.9) тождественность (), сумма по модулю 2 (), импликация (), переходим к операциям И, ИЛИ, НЕ (в базис Буля).
2. Используя свойства отрицания и законы де Моргана (см. табл. 2.9) добиваемся, чтобы операции отрицания относились только к отдельным переменным, а не к целым выражениям.
3. Используя свойства логических операций И и ИЛИ (см. табл. 2.9), получаем нормальную форму (ДНФ или КНФ).
4. При необходимости переходим к совершенным формам (СДНФ или СКНФ). Например, для получения СКНФ часто нужно использовать свойство: .
Пример 2.6. Преобразовать в СКНФ логическую функцию
.
Выполняя по порядку шаги приведённого выше алгоритма, получим:
Используя свойство поглощения, получим:
.
Таким образом, мы получили КНФ функции f (x 1 , x 2 , x 3). Чтобы получить её СКНФ, нужно каждую дизъюнкцию, в которой не хватает какой-либо переменной, повторить дважды – с этой переменной и с её отрицанием:
.