ДНФ
Версия от 09:04, 15 октября 2011; Permenko (обсуждение | вклад)
Определение: |
ДНФ (Дизъюнктивная Нормальная Форма) — нормальная форма, в которой булева функция имеет вид дизъюнкции нескольких конъюнктов. |
Пример ДНФ:
Определение: |
СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет условиям:
|
Пример СДНФ:
Теорема: |
Для любой булевой функции , не равной тождественному нулю, существует СДНФ, ее задающая. |
Доказательство: |
Для любой булевой функции выполняется следующее соотношение, называемое разложением Шеннона.
Данное соотношение легко проверить подстановкой всевозможных значений ( и ). Эта формула позволяет выносить за знак функции. Последовательно вынося , ,.., за знак , получаем следующую формулу :
Т.к применение данного соотношения к каждой из переменных увеличивает количество дизъюнктивных членов в два раза, то для функции от переменных мы имеем дизъюнктивных членов. Каждый из них соответствует значению функции на одном из возможных наборов значений n переменных. Если на некотором наборе , то весь соответствующий дизъюнктивный член также равен нулю и из представления данной функции его можно исключить. Если же , то в соответствующем дизъюннктивном члене само значение функции можно опустить. В результате для произвольной функции была построена СДНФ. |
Алгоритм построения СДНФ по таблице истинности
- В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 1.
- Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть 1, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
- Все полученные конъюнкции связываем операциями дизъюнкции.
Примеры СДНФ для некоторых функций
Стрелка Пирса:
Медиана трёх: