Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний. Для каждой функции логики высказываний можно составить таблицу истинности. Обратная задача тоже всегда разрешима. Введем несколько определений.
Элементарными конъюнкциями (конъюнктами) называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более
одного раза.
Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Элементарными дизъюнкциями (дизъюнктами) называются дизъюнкции переменных с отрицаниями или без них.
Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций.
Для каждой функции алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм.
Алгоритм построения ДНФ:
1. Перейти к булевым операциям, используя формулы эквивалентных преобразований.
2. Перейти к формулам с тесными отрицаниями, то есть к формуле, в которой отрицания располагаются не выше, чем над переменными – применить законы де Моргана.
3. Раскрыть скобки – применить законы дистрибутивности.
4. Повторяющиеся слагаемые взять по одному разу – закон идемпотентности.
5. Применить законы поглощения и полупоглощения.
Пример 6. Найти ДНФ формулы: .
В алгебре Буля справедлив принцип двойственности . Он заключается в следующем.
Функция называется двойственной к функции , если . Т.е. для нахождения функции, двойственной к заданной, необходимо построить отрицание функции от отрицаний аргументов.
Пример 7. Найти функцию, двойственную к .
Среди элементарных функций алгебры логики 1 двойственна 0 и наоборот, х двойственна х, двойственна , двойственна и наоборот.
Если в формуле F 1 представляющей функцию все конъюнкции заменить
на дизъюнкции, дизъюнкции на конъюнкции, 1 на 0, 0 на 1, то получим формулу F * , представляющую функцию * , двойственную .
Конъюнктивная нормальная форма (КНФ) – двойственное для ДНФ понятие, поэтому ее легко построить по схеме:
Пример 8. Найти КНФ формулы: .
Воспользовавшись результатом примера 6, имеем
Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы. В каждом из типов нормальных форм (дизъюнктивных и конъюнктивных) можно выделить класс совершенных форм СДНФ и СКНФ.
Совершенной элементарной конъюнкцией называется логическое произведение всех переменных с отрицанием или без них, причем, каждая переменная входит в произведение только один раз.
Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, т.е. добавлением для отсутствующей переменной x i множится с применением закона дистрибутивности
Пример 9. Найти СДНФ для ДНФ примера 6
Совершенной элементарной дизъюнкцией называется логическая сумма всех переменных с отрицаниями или без них, причем, каждая переменная входит в сумму только один раз.
Всякую КНФ можно привести к СКНФ, добавляя член конъюнкции, не содержащий какой – либо переменной X i конъюнкцией и применяя дистрибутивный закон
Пример 10 . Привести КНФ к СКНФ:
Для построения СКНФ можно воспользоваться схемой
Пример 11. Найти СКНФ для формулы примера 6.
Всякая функция имеет СДНФ и, притом, единственную . Каждая функция имеет СКНФ и, притом, единственную .
Т.к. СДНФ и СКНФ определены формулами однозначно, их можно строить по таблице истинности формулы.
Для построения СДНФ необходимо выделить строки, в которых F принимает значение 1 и записать для них совершенные элементарные конъюнкции. Если значение переменной в нужной строке таблицы истинности равно единице, то в совершенном конъюнкте она берется без отрицания, если нулю – то с отрицанием. Затем совершенные конъюнкты (их число равно числу единиц в таблице) соединяются знаками дизъюнкции.
Для построения СКНФ по таблице истинности необходимо выделить в ней строки, где F=0, и записать совершенные элементарные дизъюнкции, после чего соединить их знаками конъюнкции. Если в требуемой строке таблицы истинности (F=0) значение переменной соответствует нулю, то в совершенном дизъюнкте она берется без отрицания, если единице – то с отрицанием.
Пример 12. Найти СДНФ и СКНФ по таблице истинности для формулы примера 6.
В таблице 14 приведено лишь конечное значение F=10101101. В справедливости этого утверждения следует убедиться самостоятельно, построив развернутую таблицу истинности.
Таблица 14
| x | y | z | ||
Нормальная форма логической формулы не содержит знаков импликации, эквивалентности и отрицания неэлементарных формул.
Нормальная форма существует в двух видах:
конъюнктивная нормальная форма (КНФ) -- конъюнкция нескольких дизъюнкций, например, $\left(A\vee \overline{B}\vee C\right)\wedge \left(A\vee C\right)$;
дизъюнктивная нормальная форма (ДНФ) -- дизъюнкция нескольких конъюнкций, например, $\left(A\wedge \overline{B}\wedge C\right)\vee \left(B\wedge C\right)$.
СКНФ
Совершенная конъюнктивная нормальная форма (СКНФ) -- это КНФ, удовлетворяющая трем условиям:
не содержит одинаковых элементарных дизъюнкций;
ни одна из дизъюнкций не содержит одинаковых переменных;
каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.
Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.
Правила построения СКНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.
СДНФ
Совершенная дизъюнктивная нормальная форма (СДНФ) -- это ДНФ, удовлетворяющая трем условиям:
не содержит одинаковых элементарных конъюнкций;
ни одна из конъюнкций не содержит одинаковых переменных;
каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.
Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.
Правила построения СДНФ по таблице истинности
Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные, которые имеют значение 0 берут с отрицанием.
Примеры нахождения СКНФ и СДНФ
Пример 1
Записать логическую функцию по ее таблице истинности:
Рисунок 1.
Решение:
Воспользуемся правилом построения СДНФ:
Рисунок 2.
Получим СДНФ:
Воспользуемся правилом построения СКНФ.
Нормальные формы логических функций Представление булевой функции в форме дизъюнкции конъюнктивных термов конституент единицы Ki 2.7 называется дизъюнктивной нормальной формой ДНФ этой функции. содержат в точности по одной все логические переменные взятые с отрицаниями или без них то такая форма представления функции называется совершенной дизъюнктивной нормальной формой СДНФ этой функции. Как видно при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов при которых функция принимает значение 1.
Поделитесь работой в социальных сетях
Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск
Лекция 1.хх
Нормальные формы логических функций
Представление булевой функции в форме дизъюнкции конъюнктивных термов (конституент единицы) K i
, (2.7)
называется дизъюнктивной нормальной формой (ДНФ ) этой функции.
Если все конъюнктивные термы в ДНФ являются минтермами , т. е. содержат в точности по одной все логические переменные, взятые с отрицаниями или без них, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ ) этой функции. СДНФ называется совершенной , потому что каждый терм в дизъюнкции включает все переменные; дизъюнктивной , потому что главная операция в формуле дизъюнкция. Понятие “ нормальной формы ” означает однозначный способ записи формулы, реализующей заданную функцию.
С учётом сказанного выше из теоремы 2.1 вытекает следующая теорема.
Теорема 2. Любая булева функция (не равная тождественно 0 ) может быть представлена в СДНФ , .
Пример 3. Пусть имеем таблично заданную функцию f (x 1 , x 2 , x 3 ) (табл. 10).
Таблица 10
|
f (x 1 , x 2 , x 3 ) |
|||
На основании формулы (2.6) получаем:
Как видно, при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов, при которых функция принимает значение 1.
Представление булевой функции в форме конъюнкции дизъюнктивных термов (конституент нуля) D i
, (2.8)
называется конъюнктивной нормальной формой (КНФ ) этой функции.
Если все дизъюнктивные термы КНФ являются макстермами , т. е. содержат в точности по одной все логические переменные функции, взятые с отрицаниями или без них, то такая КНФ называется совершенной конъюнктивной нормальной формой (СКНФ ) этой функции.
Теорема 3. Любая булева функция (не равная тождественно 1 ) может быть представлена в СКНФ , причём такое представление единственно .
Доказательство теоремы может быть проведено аналогично доказательству теоремы 2.1 на основании следующей леммы Шеннона о конъюнктивном разложении.
Лемма Шеннона . Любая булева функция f (x 1 , x 2 , …, x m ) от m переменных может быть представлена так :
. (2.9)
Нужно отметить, что обе формы представления логической функции (ДНФ и КНФ) теоретически являются равными по своим возможностям: любую логическую формулу можно представить как в ДНФ (кроме тождественного нуля), так и в КНФ (кроме тождественной единицы). В зависимости от ситуации представление функции в той или иной форме может быть короче.
На практике же чаще всего используется ДНФ , т. к. эта форма является для человека более привычной: с детства ему привычнее складывать произведения, чем умножать суммы (в последнем случае у него интуитивно появляется желание раскрыть скобки и перейти тем самым к ДНФ).
Пример 4. Для функции f (x 1 , x 2 , x 3 ), заданной табл. 10, написать её СКНФ.
В отличие от СДНФ, при составлении СКНФ в таблице истинности логической функции нужно смотреть комбинации переменных, при которых функция принимает значение 0, и составить конъюнкцию соответствующих макстермов, но переменные нужно брать с обратной инверсией :
Нужно отметить, что непосредственно перейти от СДНФ функции к её СКНФ или наоборот невозможно. При попытке таких преобразований получаются функции, обратные по отношению к желаемым. Выражения для СДНФ и СКНФ функции непосредственно можно получить только из её таблицы истинности.
Пример 5. Для функции f (x 1 , x 2 , x 3 ), заданной табл. 10, попробовать перейти от СДНФ к СКНФ.
Используя результат примера 2.3 получим:
Как видно, под общей инверсией получилась СКНФ логической функции, которая является обратной по отношению к функции, полученной в примере 2.4:
т. к. содержит все макстермы, которых нет в выражении для СКНФ рассматриваемой функции.
1. Используя свойства операций (см. табл. 9) тождественность (), сумма по модулю 2 (), импликация (), переходим к операциям И, ИЛИ, НЕ (в базис Буля).
2. Используя свойства отрицания и законы де Моргана (см. табл. 9) добиваемся, чтобы операции отрицания относились только к отдельным переменным, а не к целым выражениям.
3. Используя свойства логических операций И и ИЛИ (см. табл. 9), получаем нормальную форму (ДНФ или КНФ).
4. При необходимости переходим к совершенным формам (СДНФ или СКНФ). Например, для получения СКНФ часто нужно использовать свойство: .
Пример 6. Преобразовать в СКНФ логическую функцию
Выполняя по порядку шаги приведённого выше алгоритма, получим:
Используя свойство поглощения, получим:
Таким образом, мы получили КНФ функции f (x 1 , x 2 , x 3 ). Чтобы получить её СКНФ, нужно каждую дизъюнкцию, в которой не хватает какой-либо переменной, повторить дважды с этой переменной и с её отрицанием:
2.2.6. Минимизация логических функций
Поскольку одну и ту же логическую функцию можно представить ра з личными формулами, то нахождение наиболее простой фо р мулы, задающей булеву функцию, упрощает логическую схему, реализующую булеву фун к цию. Минимальной формой л о гической функции в некотором базисе можно считать такую, которая содержит минимальное число суперпозиций фун к ций базиса, допуская и скобки. Однако трудно построить эффективный а л горитм такой минимизации с получением минимальной скобочной фо р мы.
Рассмотрим более простую задачу минимизации при синтезе комбинационных схем, при которой ищется не минимальная скобочная форма функции, а её минимальная ДНФ. Для этой задачи существуют простые эффективные алгоритмы.
Метод Квайна
Минимизируемая функция представляется в СДНФ, и к ней применяются все возможные операции неполного склеивания
, (2.10)
а затем поглощения
, (2.11)
и эта пара этапов применяется многократно. Таким образом, удаётся снизить ранг термов. Это процедура повторяется до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом.
Заметим, что левую часть уравнения (2.10) сразу можно было минимизировать более простым и очевидным способом:
Этот способ плох тем, что при такой непосредственной минимизации конъюнктивные термы или исчезают, хотя возможны ещё случаи их использования для склеивания и поглощения с оставшимися термами.
Нужно отметить, что метод Квайна является достаточно трудоёмким, поэтому вероятность допущения ошибок во время преобразований достаточно велик. Но его преимуществом является то, что теоретически его можно использовать для любого числа аргументов и при увеличении количества переменных преобразования усложняются не так сильно.
Метод карт Карно
Метод карт (таблиц) Карно является более наглядным, менее трудоёмким и надёжным способом минимизации логических функций, но его использование практически ограничено функциями 3-4 переменных, максимум 5-6 переменных.
Карта Карно это двумерная табличная форма представления таблицы истинности булевой функции, позволяющая в графической наглядной форме легко отыскать минимальные ДНФ логических функций. Каждой клетке таблицы сопоставляется минтерм СДНФ минимизируемой функции, причём так, что любым осям симметрии таблицы соответствуют зоны, взаимно инверсные по какой-либо переменной. Такое расположение клеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично.
Таблицы истинности и карты Карно для функций И и ИЛИ двух пер е менных представлены на рис. 8. В каждую клетку карты записывается зн а чение функции на соответствующем этой клетке наборе значений аргуме н тов.
А ) И б ) ИЛИ
Рис. 8. Пример карт Карно для функций двух переменных
В карте Карно для функции И только одна 1, поэтому её ни с чем невозможно склеить. В выражении для минимальной функции будет только терм, соответствующий этой 1:
f = x y .
В карте Карно для функции ИЛИ уже три 1 и можно составить две склеивающиеся пары, при этом 1, соответствующая терму xy , используется дважды. В выражении для минимальной функции нужно записать термы для склеиваемых пар, оставляя в них все переменные, которые для этой пары не меняются, и убирая переменные, которые меняют своё значение. Для горизонтальной склейки получим x , а для вертикальной y , в итоге получим выражение
f = x + y .
На рис. 9 приведены таблицы истинности двух функций трёх переменных (а ) и их карты Карно (б и в ). Функция f 2 отличается от первой тем, что на трёх наборах переменных она не определена (в таблице это обозначено прочерком).
При определении минимальной ДНФ функции используются следующие правила. Все клетки, содержащие 1, объединяются в замкнутые прямоугольные области, которые называются k -кубами , где k = log 2 K , K количество 1 в прямоугольной области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2 k , где k = 0, 1, 2, 3, … . Для k = 1 прямоугольник называется один-куб и содержит 2 1 = 2 единицы; для k = 2 прямоугольник содержит 2 2 = 4 единицы и называется два-куб ; при k = 3 область из 2 3 = 8 единиц называется три-куб ; и т. д. Единицы, которые невозможно объединить в прямоугольники, можно назвать ноль-кубами , которые содержат только одну единицу (2 0 = 1). Как видно, при чётном k области могут иметь форму квадрата (но не обязательно), а при нечётном k только прямоугольников.
|
б в |
||||||
Рис. 9. Пример карт Карно для функций трёх переменных
Эти области могут пересекаться, т. е. одни и те же клетки могут входить в разные области. Затем записывается минимальная ДНФ функции как дизъюнкция всех конъюнктивных термов, соответствующих k - кубам.
Каждая из указанных областей на карте Карно представляется в минимальной ДНФ конъюнкцией, число аргументов в которой на k меньше общего числа аргументов функции m , т. е. это число равно m k . Каждая конъюнкция минимальной ДНФ составляется лишь из тех аргументов, которые для соответствующей области карты имеют значения либо без инверсий, либо только с инверсией, т. е. не меняют своего значения.
Таким образом, при охвате клеток карты замкнутыми областями следует стремиться к тому, чтобы число областей было минимальным, а каждая область содержала возможно большее число клеток, так как при этом будет минимальным число членов в минимальной ДНФ и число аргументов в соответствующей конъюнкции будет минимальным.
Для функции по карте Карно на рис. 9, б находим
поскольку для верхней замкнутой области переменные x 1 и x 2 имеют значения без инверсий, для нижней x 1 имеет значение с инверсией, а x 3 без инверсии.
Неопредёленные значения в карте на рис. 9, в можно доопределить, заменив нулём или единицей. Для данной функции видно, что оба неопределённых значения выгоднее заменить 1. При этом образуются две области, являющиеся различными видами 2-кубов. Тогда выражение для минимальной ДНФ функции будет следующим:
При построении замкнутых областей допускается сворачивание карты Карно в цилиндр как по горизонтальной, так и по ве р тикальной осям с объединением противоположных граней ка р ты, т. е. единицы, расположенные по краям карты Карно симметри ч но, также могут быть объединены.
Карты Карно можно рисовать разными способами (рис. 10).
|
x 2 x 3 |
||||||||||
а б
Рис. 10.
Разные способы изображения карт Карно
для функции 3 переменных
Но самыми удобными вариантами карт Карно для функций 2-4 переменных являются показанные на рис. 11 таблицы, т. к. в них для каждой ячейки показ а ны все переменные в прямом или инверсном виде.
а б
Рис. 11.
Наиболее удобное изображение карт Карно
для функций 3 (а
) и 4 (б
) переменных
Для функций 5 и 6 переменных больше подходит способ, показанный на рис. 10, в .
Рис. 12. Изображение карты Карно для функции 5 переменных
Рис. 13. Изображение карты Карно для функции 6 переменных
Другие похожие работы, которые могут вас заинтересовать.вшм> |
|||
| 9020. | ПРИНЦИП ДВОЙСТВЕННОСТИ. РАЗЛОЖЕНИЕ БУЛЕВЫХ ФУНКЦИЙ ПО ПЕРЕМЕННЫМ. СОВЕРШЕННЫЕ ДИЗЪЮНКТИВНАЯ И КОНЪЮНКТИВНАЯ НОРМАЛЬНЫЕ ФОРМЫ | 96.34 KB | |
| Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу в виде совершенной д. н. ф. Для этого в таблице истинности для каждой для функции отмечаем все строки, в которых | |||
| 6490. | Описание и минимизация логических функций | 187.21 KB | |
| В словесной форме выражается взаимосвязь между аргументами функции и ее значениями. Пример: функция трех аргументов принимает значение когда любые два или более аргументов функции равны. Состоит в построении таблицы истинности содержащей значения функции для всех наборов значений аргументов. В данном примере по таблице истинности получаем такую запись в виде ДНФ... | |||
| 6707. | Проектирование реляционных баз данных. Проблемы проектирования в классическом подходе. Принципы нормализации, нормальные формы | 70.48 KB | |
| Что такое проект реляционной базы данных Это набор взаимосвязанных отношений в которых определены все атрибуты заданы первичные ключи отношений и заданы еще некоторые дополнительные свойства отношений которые относятся к принципам поддержки целостности. Поэтому проект базы данных должен быть очень точен и выверен. Фактически проект базы данных это фундамент будущего программного комплекса который будет использоваться достаточно долго и многими пользователями. | |||
| 4849. | Формы и методы осуществления функций государства | 197.3 KB | |
| Термин «функция» имеет в отечественной и зарубежной научной литературе далеко не одинаковое значение. В философском и общесоциологическом плане, он рассматривается, как «внешнее проявление свойств какого-либо объекта в данной системе отношений»; как совокупность обычных или же специфических действий отдельных лиц или органов | |||
| 17873. | Формирование логических УУД у учащихся 3 класса | 846.71 KB | |
| Психолого-педагогические аспекты проблемы формирования логических универсальных действий у младших школьников Методики оценки сформированности логических УУД. Разработка концепции развития универсальных учебных действий в системе общего образования отвечает новым социальным запросам. Важнейшей задачей современной системы образования является формирование универсальных учебных действий УУД. Сформированность универсальных учебных действий является залогом профилактики школьных трудностей. | |||
| 2638. | Техническая реализация логических связей в системах автоблокировки | 1.04 MB | |
| Техническая реализация логических связей в системах автоблокировки Техническая реализация алгоритмов управления трехзначной и четырехзначной АБ может быть достигнута при помощи релейных контактных и бесконтактных дискретных и интегральных логических элементов... | |||
| 10203. | ПРИМЕНЕНИЕ КОНЦЕПЦИИ РИСК ОРИЕНТИРОВАННОГО ПОДХОДА ДЛЯ ПОСТРОЕНИЯ СТРУКТУРНО-ЛОГИЧЕСКИХ МОДЕЛЕЙ ВОЗНИКНОВЕНИЯ И РАЗВИТИЯ ЧС | 70.8 KB | |
| Общий анализ риска Производственная среда насыщается мощными технологическими системами и технологиями которые делают труд человека производительным и менее тяжелым физически однако более опасным. Для риска характерны неожиданность и внезапность наступления опасной ситуации. Ежедневно мы сталкиваемся с многочисленными рисками но большая часть из них остается потенциальными т. Теория риска предусматривает количественную оценку негативного воздействия на человека а также нанесения ущерба его здоровью и жизни. | |||
| 11576. | Понятие, виды и формы сделок. Последствия несоблюдения требуемой формы сделок | 49.82 KB | |
| Признание сделки недействительной виды недействительной сделки. Прикладная ценность курсовой работы заключается в упрощении понятия сделки то есть публичного его представления в более доступной форме. | |||
| 6213. | Приближение функций | 3.08 MB | |
| Первая состоит в замене некоторой функции заданный аналитически или таблично другой функцией близкой к исходной но более простой и удобной для вычислений. Например замена функции многочленом позволяет получать простые формулы численного интегрирования и дифференцирования; замена таблицы приближающей функцией позволяет получать значения в ее промежуточных точках. Возникает также и вторая задача восстановление функции на некотором отрезке по заданным на этом отрезке значениям функции в дискретном множестве точек. Ответ на такой вопрос... | |||
| 14058. | Эволюция функций государства | 29.99 KB | |
| Российское государство как правовое явление прежде всего должно обеспечивать реализацию назначения государства а также его основных конституционных характеристик как демократического федеративного правового социального светского государства с республиканской формой правления. Главное назначение государства определяется ст. | |||
Простой конъюнкцией называется конъюнкция одной или нескольких переменных , при этом каждая переменная встречается не более одного раза (либо сама , либо ее отрицание ).
Например, является простой конъюнкцией,
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций .
Например, выражение является ДНФ.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма , у которой в каждую конъюнкцию входят все переменные данного списка (либо сами , либо их отрицания ), причем в одном и том же порядке .
Например, выражение является ДНФ, но не СДНФ. Выражение 
является СДНФ.
Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.
Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных , при этом каждая переменная входит не более одного раза (либо сама , либо ее отрицание ).Например, выражение - простая дизъюнкция,
Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение - КНФ).
Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.
Например, выражение 
является СКНФ.
Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:
а) переход от ДНФ к КНФ
Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:
Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;
б) переход от КНФ к ДНФ
Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)
Таким образом, получили ДНФ.
Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;
в) сокращение ДНФ (или СДНФ) по правилу Блейка
Применение этого правила состоит из двух частей:
Если среди дизъюнктных слагаемых в ДНФ имеются слагаемые 
, то ко всей дизъюнкции добавляем слагаемое К
1 К
2 . Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;
Если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,
или
Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ 
, после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):
в) переход от ДНФ к СДНФ
Если в какой-то простой конъюнкции недостает переменной, например, z , вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:
г) переход от КНФ к СКНФ
Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z , то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):
Таким образом, из КНФ получена СКНФ.
Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.
Стандартный базис. Элементарные формулы - литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.
Стандартный базис - это набор из трех исходных операций булевой алгебры: сложения (объединения), умножения (пересечения) и отрицания.
Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ 1 xˆ 2 . . . xˆ л, называется элементарной конъюнкцией . Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x 1 x 1 = x 1). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.
Дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой , или ДНФ . Например,
x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .
Если состав переменных в каждой элементарной конъюнкции данной ДНФ один и тот же, то ДНФ называется совершенной . Приведенный пример - это ДНФ, не являющаяся совершен- ной. Напротив, формула
x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4
есть совершенная форма.
Поскольку в булевой алгебре сложение и умножение - симметричные операции и всегда можно интерпретировать сложение как умножение, а умножение как сложение, существует и двойственное понятие - конъюнктивная нормальная форма (КНФ ), представляющая собой конъюнкцию элементарных дизъюнкций, и совершенная конъюнктивная форма (СКНФ ). Из принципа двойственности для симметричных полуколец вытекает, что любому утверждению относительно ДНФ отвечает двойственное утверждение относительно КНФ, которое получается заменой сложения (дизъюнкции) умножением, умножения (конъюнкции) сложением, константы 0 константой 1, константы 1 константой 0, отношения порядка двойственным (обратным) порядком. Поэтому далее мы остановимся на изучении только ДНФ.
Теорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.
◀Условимся под x σ понимать формулу x, если σ = 1, и формулу x , если σ = 0. Пусть функция f(y 1 , . . . , y n) принимает значение 1 на векторе (t 1 , . . . , t n) (такой вектор называют конституэнтой единицы ). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу
в которой сумма (объединение) распространяется на все те наборы (t 1 , . . . , t n) значений аргументов, на которых заданная функция принимает значение 1. Отметим, что множество таких наборов не пусто, так что в сумме есть по крайней мере одно слагаемое.
Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f.
Следствие 1.1. Стандартный базис является полным.
◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x 1 , x 2 , . . . , x n) = x 1 x 1 .
Пример 1.2. Рассмотрим функцию трех переменных m(x 1 , x 2 , x 3) (табл. 1.4), называемую мажоритарной функциеи ̆. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.
Полнота стандартного базиса позволяет подбирать и другие полные системы функций. Полнота множества F может быть установлена из следующих соображений. Предположим, каждая из трех функций стандартного бузиса представима формулой над F . Тогда в силу теоремы 1.3 иножество F будет полным.
Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина . Сложение по модулю 2 и умножение - базовые операции кольца Z2, выражения, составленные с их помощью - это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:
xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.
Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина - это многочлен над кольцом Z2.
Нетрудно сконструировать формулы над базисом Жегалкина, представляющие операции сложения и отрицания стандартного базиса (умножение у двух базисов общее):
x+y=x⊕y⊕xy, x =x⊕1.
Поэтому базис Жегалкина - полное множество.
Можно показать, что для любой булевой функции полином Жегалкина определен однозначно
(точнее, с точностью до порядка слагаемых). Коэффициенты полинома Жегалкина при небольшом количестве переменных можно найти методом неопределенных коэффициентов.
Пример 1.4. Рассмотрим множество из единственной функции - штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:
x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).
Пример 1.5. Базис, состоящий из единственной функции - стрелки Пирса, также является полным. Проверка этого аналогична случаю штриха Шеффера. Впрочем, это заключение можно сделать и на основании принципа двойственности для симметричных полуколец.
*Штрих Шеффера - бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формы следует быть внимательным: результат зависит от порядка выполнения операций. В этом случае рекомендуется явно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формы равнозначны.