Логическое и функциональное программирование (стр. 5 из 16)
Дизъюнкция любого числа первичных термов равна либо 1, либо элементарной дизъюнкции. Произведение любого числа первичных термов равно либо 0, либо элементарному произведению.
Нормальной дизъюнктивной формой (ДНФ) называется дизъюнкция любого конечного множества попарно различных произведений.
Конъюнктивной нормальной формой (КНФ) называется произведение любого конечного множества попарно различных дизъюнкций.
Алгоритм приведения к ДНФ и КНФ заключается в следующем.
1. Преобразовать выражение в соответствии с операциями отрицания.
2. Использовать первый (ДНФ) или второй (КНФ) законы дистрибутивности.
Пример: Привести к ДНФ и КНФ выражение.
На первом этапе обрабатываем знаки отрицания:
Раскрывая скобки, приведем к ДНФ:
При приведении к КНФ последовательно применяем второй закон к первой скобке выражения
Рассмотрим некоторое множество М булевых переменных. В качестве такого множества будем выбирать множество аргументов той или иной булевой функции.
Элементарные дизъюнкции называются конституантами 0 для данного множества М булевых переменных, если они содержат в прямом либо инверсном виде все переменные множества М.
Элементарные конъюнкции называются конституантами 1 для данного множества М булевых переменных, если они содержат в прямом либо инверсном виде все переменные множества М.
Для переменных
произвольную конституанту нуля можно представить в виде 
а произвольную конституанту 0 в виде 
где 
означает либо 
, либо 
. Условимся нумеровать конституанты нуля и единицы с помощью тех же номеров, что и соответствующие им наборы переменных.ДНФ/КНФ называется совершенной (СДНФ/СКНФ), если все составляющие ее элементарные произведения/дизъюнкции являются конституантами единицы/нуля для одного и того же множества М переменных. СДНФ/СКНФ называется СДНФ/СКНФ булевой функции f, если она равна этой функции и если множество, составляющих ее переменных, совпадает с множеством аргументов функции f.
Справедливо следующее: Любая булева функция имеет одну и только одну СДНФ/СКНФ.
Рассмотри процесс приведения к СДНФ/СКНФ.
Рассмотрим произвольную ДНФ j от переменных x1, . . ., xn. Пусть некоторые элементарные произведения p, входящие в эту форму, не содержат какой либо переменной xj. Тогда эти произведения можно заменить равными им выражениями
Продолжая этот процесс относительно других переменных множества аргументов функции, не входящих в то или иное элементарное произведение, после повторения этой процедуры некоторое конечное число раз получим СДНФ выражения j, поскольку в каждое составляющее ее элементарное произведение будут входить все переменные из множества аргументов функции.
Назовем этот процесс приведением ДНФ к совершенному виду.
Аналогичным образом можно построить процесс приведения КНФ к совершенному виду. Для этой цели к входящей в КНФ произвольной элементарной дизъюнкции q, не содержащей, например, переменной
, добавляется равный нулю элемент 
. Затем к полученному выражению применяется второй дистрибутивный закон: 
Продолжая по аналогии, мы сможем в каждую элементарную дизъюнкцию ввести все недостающие в ней переменные, после чего форма превратится в совершенную.
Пример: Выражение
привести к СДНФ и СКНФ.1.
2.
Синтез логических выражений.
Используя таблицу истинности любой логической формулы, можно определить ее в СДНФ или СКНФ. Для построения СДНФ в таблице истинности необходимо выбрать строки, в которых функция принимает значение 1 и сформировать конституанту 0. Переменная будет находиться в этой конституанте без знака отрицания, если она принимает значение 1 в этой строке и с отрицанием в противном случае. Соединить полученные конституанты знаком дизъюнкции.
Для получения СКНФ ищутся строки, в которых функция принимает значение 0. Строятся конституанты 1. Переменная берется со знаком отрицания, если она равна 1 и наоборот. Конституанты соединяются знаком конъюнкции.
Пример: Дана таблица истинности. Построить СДНФ и СКНФ.
| x | y | z | f |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
СДНФ:
СКНФ:
Минимизация булевых функции
Под минимизацией булевых функций понимается нахождение наиболее простого представления этой функции в виде суперпозиции функций, составляющих какую-нибудь фиксированную функционально полую систему S булевых функций. Наиболее простым обычно считается представление, содержащее наименьшее возможное число суперпозиций. При решении задачи минимизации важную роль играет понятие импликанты.
Булева функция
называется импликантой функции 
, если на любом значении переменных 
, на котором значение g равно 1, значение f также равно 1.Простой импликантой функции f называется элементарное произведение
, являющееся импликантой f и такое, что никакая его собственная часть (то есть произведение, получаемое из gотбрасыванием одного или нескольких компонент) уже не является импликантой функции f.Дизъюнкция любого множества импликант одной и той же функции является импликантой этой функции.
Дизъюнкция всех простых импликант булевой функции совпадает с этой функцией и называется сокращенной дизъюнктивной нормальной формой.
Сокращенная нормальная форма является более экономной, чем СДНФ. Однако часто допускает дальнейшее упрощение за счет того, что некоторые из простых импликант могут поглощаться дизъюнкцией других простых импликант. Например, в сокращенной ДНФ
простая импликанта yz поглощается дизъюнкцией остальных элементов формы: 
.Однако справедливо следующее утверждение для сокращенной дизъюнктивной формы. Если сокращенная ДНФ не содержит никакой переменной, входящей в нее одновременно с отрицанием и без него, то эта форма является минимальной дизъюнктивной формой.
Приведение к минимальной нормальной форме от сокращенной ДНФ можно осуществит с помощью импликантной таблицы. Импликантная таблица представляет собой прямоугольную таблицу, строки которой обозначаются различными простыми импликантами, а столбцы конституантами единицы, на которых функция обращается в единицу.
На пересечении p-й строки k-го столбца импликантной таблицы ставится * тогда и только тогда, когда импликанта составляет некоторую часть конституанты k. Для примера:
 |  |  |  |  |
 | * | * | ||
 | * | * | ||
 | * | * | ||
 | * | * |
Система S простых импликант булевых функций f называется приведенной, если эта система полна и никакая ее часть не является полной системой импликант функции f. Дизъюнкция всех простых импликант, составляющих S, называется приведенной или тупиковой дизъюнктивной нормальной формой. Всякая минимальная ДНФ является тупиковой ДНФ.