Как привести к днф

2

Алгоритм преобразования формулы в КНФ и ДНФ

Пусть дана формула А, подлежащая преобразованию в КНФ. Если А — это пропозициональный символ /?, либо его отрицание -н/?, то ее КНФ состоит из единственного дизъюнкта, каковым является самор, либо р. Если же это не так, то надлежит выполнить следующие действия.

1. Исключение из Л связок -> и =, используя теоремы:

2. Внесение связки -> внутрь скобок везде, где это возможно, применяя законы де Моргана:

В результате этих действий связка будет расставлена в формуле А только перед пропозициональными символами или перед их отрицаниями. Вследствие этого могут появиться выражения вида —•—./?.

3. Удаление двойных отрицаний в соответствии с законом двойного отрицания

4. Применение закона дистрибутивности

необходимое число раз, пока не будет получена КНФ.

Для получения ДНФ этим же алгоритмом нужно на этапе 4 применять второй из законов дистрибутивности

необходимое число раз, пока не будет получена ДНФ.

Пример. Приведем к КНФ следующую формулу:

1. Исключение импликаций

2. Внесение связки внутрь скобок

3. Удаление двойных отрицаний

4. Применение закона дистрибутивности (av(bAC)) v ((avb)A(avc)) Следовательно, исходная формула эквивалентна КНФ D_]aD₂ aD₃, где

Приведение к ДНФ той же формулы выполняется точно также, и видно, что уже на этапе 3 искомая ДНФ построена, т. е. исходная формула эквивалентна ДНФ C₁vC₂vC₃vC₄, где

Конъюнктивная нормальная форма играет важную роль в обработке знаний на ЭВМ: дизъюнкты, входящие в КНФ, являются посылками в принципе резолюции, используемом в качестве единственного правила вывода в механизме вывода языков логического программирования. Например, синтаксической основой языка программирования PROLOG являются предложения Хорна, а его логической основой является принцип резолюции.

2.3 Дизъюнктивные и конъюнктивные нормальные формы

Базис =наиболее изучен и имеет самое широкое применение на практике.

Определение. Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) переменных или их отрицаний.

Пример 2.3.1 –

а) иэлементарные дизъюнкции;

б) иэлементарные конъюнкции;

в)одновременно является и элементарной дизъюнкцией и элементарной конъюнкцией.

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

Пример 2.3.2 –

а)ДНФ;

б) КНФ.

Теорема. Любая формула может быть приведена к ДНФ (КНФ) (т.е. любая формула эквивалентна некоторой ДНФ (КНФ)).

Правило приведения формулы к ДНФ:

а) все логические операции, присутствующие в формуле, выразить через , используя эквивалентности:

1);

2);

3);

4);

5);

б) перенести все отрицания к переменным по закону де Моргана:

;

в) используя закон дистрибутивности, преобразовать формулы так, чтобы все конъюнкции выполнялись раньше дизъюнкций: .

Пример 2.3.3 — Приведём к ДНФ формулу . Для этого

заменим на, затем применим закон де Моргана и закон двойного отрицания:=.

Заметим, что последняя формула в примере в некоторых учебниках уже считается ДНФ, в других же считают, что в элементарных конъюнкциях и дизъюнкциях каждая переменная должна встречаться не более одного раза. Для удаления лишних переменных применяют следующие эквивалентности:

а) (закон идемпотентности);

б) (закон исключённого третьего),(закон противоречия); в),— ( свойства констант).

Поэтому, используя закон идемпотентности, в последнем примере получим ДНФ: .

Приведение формулы к КНФ производится так же как к ДНФ, только вместо пункта в) применяется пункт в:

в) используя закон дистрибутивности, преобразовать формулы так, чтобы все дизъюнкции выполнялись раньше конъюнкций, т.е..

Пример 2.3.4 — Приведём к КНФ формулу .

Заменим операцию , используя формулу:

[закон де Моргана, двойное

отрицание] — КНФ.

ДНФ и КНФ имеют тот недостаток, что они не обладают свойством единственности, т.е. одна и та же формула имеет несколько ДНФ и КНФ. Этим недостатком не обладают совершенные нормальные формы.

Определение. Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой в каждую элементарную конъюнкцию каждая переменная входит ровно один раз, причём, входит либо сама переменная, либо её отрицание, и среди элементарных конъюнкций не должно быть одинаковых; совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой в каждую элементарную дизъюнкцию каждая переменная входит ровно один раз, причём, входит либо сама переменная, либо её отрицание, и среди элементарных дизъюнкций не должно быть одинаковых.

Пример 2.3.5 –

а) — СДНФ;

б) — СКНФ;

в) — не СДНФ, т.к. содержит две одинаковых элементарных конъюнкции;

г) — не СДНФ, т.к. в одной элементарной конъюнкции содержится и переменная и её отрицание:.

Теорема. (Существование и единственность СДНФ и СКНФ). Всякая логическая формула единственным образом (с точностью до порядка следования элементарных конъюнкций (дизъюнкций)) может быть представлена в СДНФ (СКНФ).

Для приведения формулы к СДНФ можно использовать один из двух методов:

І метод: приводим формулу к ДНФ; если какая-то элементарная конъюнкция не содержит некоторой переменной у, то добавляем её, используя закон расщепления: ; убираем одинаковые элементарные конъюнкции, используя закон идемпотентности .

Пример 2.3.6 — Получим СДНФ функции , заданной в ДНФ:

— СДНФ.

ІІ метод: для данной формулы строим таблицу истинности, потом применяем правило, основанное на теореме Шеннона: СДНФ функции содержит столько элементарных конъюнкций, сколько единиц в столбце значений; каждому единичному набору нулей и единицсоответствует элементарная конъюнкция всех переменных, в которойвзято с отрицанием, еслии без отрицания, если.

Пример 2.3.7 — Для функции , заданной в ДНФ, найти СДНФ. Построим таблицу истинности:

Т а б л и ц а 2.3.1

Функция принимает значение 1 при следующих значениях аргументов: — это её единичные наборы. По выше приведённому правилу,— СДНФ.

Приведение формулы к СКНФ аналогично приведению к СДНФ. Также существует два метода:

а) метод элементарных преобразований;

б) СКНФ находят по таблице истинности: СКНФ функции содержит столько элементарных дизъюнкций, сколько нулей в столбце значений; каждому нулевому набору нулей и единицсоответствует элементарная дизъюнкция всех переменных, в которойвзято с отрицанием, еслии без отрицания, если.

Пример 2.3.8 — Рассмотрим функцию из предыдущего примера . Приведём её к СКНФ двумя способами:

а)

б) из таблицы истинности выпишем нулевые наборы:, значит, по выше приведённому правилу,— СКНФ.

Минимизация булевых функций в классе ДНФ. Карты Карно

При решении практических задач часто возникает проблема минимизации логических формул, в смысле, например, найти формулу, содержащую наименьшее число переменных, или наименьшее число операций, или наименьшее количество подформул определённого вида и т.д. К настоящему времени наиболее изучена задача отыскания дизъюнктивных форм, минимальных по числу вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле.

Определение. Минимальной ДНФ (МДНФ) называется ДНФ с наименьшим числом вхождений переменных.

Существует много способов отыскания МДНФ (метод Квайна, неопределённых коэффициентов, с помощью гиперкубов и т.д.). Остановимся на наиболее простом – с использованием карт (диаграмм) Карно.

Карта Карно – это таблица, каждая клетка (ячейка) которой соответствует некоторой элементарной конъюнкции всех переменных. Для функции n переменных существуетвозможных комбинаций их значений, состоящих из 0 и 1. То есть, например, для n=2 имеемэлементарные конъюнкции, которым соответствуют следующие наборы 0 и 1: (1,1), (1,0), (0,1), (0,0); для n=3 ——— (1,1,1), (1,1,0),…,(0,0,0) и т.д. Карты Карно строятся в виде таблицы размеромтак, что её столбцы соответствуют значениям переменных, строки — (или наоборот); вообще, для одной и той же функции может быть построено несколько карт, важно, чтобы соседние ячейки (как по вертикали, так и по горизонтали) отличались только значением одной переменной.

Мы будем рассматривать в основном функции двух, трёх и четырёх переменных. Для них карты Карно имеют следующий вид:

а) для функции двух переменных х, у — рисунок 2.3.1;

б)для функции трёх переменных — рисунок 2.3.2;

в) для функции четырёх переменных — рисунок 2.3.3.

Рисунок 2.3.1 Рисунок 2.3.2 Рисунок 2.3.3

Для определения МДНФ булевой функции, сначала надо найти её СДНФ, затем каждую элементарную конъюнкцию СДНФ отметить единицей в соответствующей ячейке карты Карно.

Пример 2.3.9 — Функции изаданы в форме СДНФ. Карта Карно дляна рисунке 2.3.4; для— на рисунке 2.3.5.

Рисунок 2.3.4 Рисунок 2.3.5

Заметим, что, если в картах Карно две, четыре, восемь (для функции четырёх переменных) соседних ячеек по вертикали или по горизонтали содержат 1, то эти ячейки объединяют в блоки (на картах их отмечают овалами) и соответствующие этим блокам дизъюнкции элементарных конъюнкций можно упростить. Так, в примере 2.3.9 для функции имеем блок из двух ячеек, на рисунке он отмечен овалом. Этому блоку соответствует дизъюнкция, упрощая которую, получим:. Таким образом, блоку из двух ячеек функции двух переменных отвечает одна переменнаях, а именно та переменная, которая полностью «покрывает» этот блок. Формула упростилась .

Для функции также имеем один блок из двух ячеек, ему соответствует дизъюнкция элементарных конъюнкций, упрощая которую получим, т.е. блоку из двух ячеек функции трёх переменных соответствует конъюнкция двух переменных, «покрывающих» этот блок. Формула упростилась.

Рассмотрим ещё несколько примеров.

Пример 2.3.10 — — СДНФ функции. Её карта Карно на рисунке 2.3.6. Так какz находится на обоих концах карты, то её (карту) можно «скрутить» и считать, что 1 в углах карты образуют блок из четырёх ячеек. Эти четыре ячейки полностью «покрывает» переменная z, т.о., МДНФ функции будет .

Рисунок 2.3.6 Рисунок 2.3.7 Рисунок 2.3.8

Пример 2.3.11 — — СДНФ функции. Её карта Карно на рисунке 2.3.7. На карте есть блок из четырёх ячеек, который покрывают переменныеи, поэтому МДНФ функции будет:.

Пример 2.3.12 — Карта Карно для функции

заданной в СДНФ на рисунке 2.3.8.

На карте имеем: блок из 8 ячеек покрывает переменная y; двум блокам из 4 ячеек соответствуют элементарные конъюнкции и, поэтому МДНФ будет:.

2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования

Здесь рассказано о формах представления функций алгебры логики — о диъюнктивной (ДНФ) и конъюнктивной (КНФ) формах.

Раскрыто понятие совершенная ДНФ и КНФ. Приведены примеры преобразований

Просмотр содержимого документа
«2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования»

Логические функции, СДНФ СКНФ

1.4 Формы представления функций алгебры логики

Функции алгебры логики могут быть заданы различными способами:

— таблицей истинности — в аналитической форме- в числовой форме..

Если функция имеет значения на всех наборах, то она называется полностью определенной.

элементарная дизъюнкция — дизъюнктивный терм или макстерм — это дизъюнктивный терм или макстерм — это дизъюнкция произв числа попарно независимых перем Например,

элементарная конъюнкция — конъюнктивный терм или минтерм — конъюнкция произв числа попарно независимых перем. Напр, Х ₁Х ₂ Х₃ — минтерм 3-его ранг

– это не минтерм, так как перем и зависимы.

Для аналитической записи функций используют две формы:

1) Дизъюнктивную Нормальную Форму — ДНФ

2) Конъюнктивную Нормальную Форму – КНФ

ДНФ это дизъюнкция минтермов разл ранга

КНФ это конъюнкция макстермов различного ранга

Если все термы, входяшие в нормальную форму имеют одинаковый и максимальный ранг,= числу переменных функции — n, то такая форма называется совершенной. При этом, минтерм называют констинтуентой (составля) 1 (КЕ), а макстерм — конституентой 0 (КН).

— это СДНФ

— это СКНФ

Т е СДНФ есть дизъюнкция конституент 1, а СКНФ — есть конъюнкция конституент 0

Составление совершенных форм по табл истинности

Совершенные формы составляют по табл истинности функции. СДНФ : для каждого набора переменных на которых функция=1, записывают минтерм ранга n , в которых с отрицанием берутся переменные = 0 на данном наборе. Все минтермы объединены дизъюнктивно.

СКНФ =для каждого набора переменных, на которых функция=0, записывают макстерм ранга n, в кот с отрицанием берутся переменные, имеющие значение=1 на данном наборе. Все макстермы объединены конъюнктивно

Для компактной записи функций исп числовую форму, в которой заданы только номера наборов. Числовая форма для СДНФ:

Числовая форма для СКНФ:

Алгоритм преобразованияя в ДНФ

1) Сначала избавляемся от операций импликации, эквивалентности и неравнозначности, выразив их через логические связки ¬, & и ∨ по законам:

2) Доводят знаки отрицания до независимых переменных, используя законы де Моргана:

3) Применяя з-н дистрибутивности

преобразуют формулу к дизъюнкции элементарных конъюнкций

4) 4) Постоянно избавляются от двойных отрицаний:
ДНФ A наз совершенной и обозн СДНФ, если каждая переменная формулы A входит с отрицанием или без отрицания в каждый конъюнкт точно 1 раз.

Алгебраическая форма представления булевых функций используется для минимизации (упрощения формулл) и для построения логических схем. Существукт 2 формы алгебраических функций – дизъюнктивная и конъюнктивн. Дизъюнктивная нормальная форма представляет сумму элементарных произведения аргументов, например

Если кажд слаг содер все арг или их отриц, то получ соверш дизъюнкт норм форму (СДФН), напр

Для перехода от табл истинн к СДНФ учит только те сост, для кот функц= 1. Для каждого такого сост запис элем произв всех ар. Если арг имеет зн "0", то запис его отриц. Для привед примера СДНФ имеет вид (17.4)

Совершенная конъюнктивная нормальная форма (СКНФ) представляет логическое произведение элементарных логических сумм, причем каждая сумма содержит все аргументы или их отрицания, например

ДНФ, но не СДНФ от 3 перем

-представл импликации в виде ДНФ.

-СДНФ для импликации

-СДНФ для оп эквивалентности

-СДНФ для оп неравнозначности

Прим.1 Привести к ДНФ формулу

2. Привести ту же формулу к СДНФ. Начав преобразования с ДНФ

Нахождение СДНФ по табл истинности функции

Нахождение СКНФ по табл истинности функции

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.

2)Выписать для каждой отмеченной строки конъюнкцию всех переменных так: если значение некоторой переменной в данной строке — 1, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание.

3)Все полученные конъюнкции связать в дизъюнкцию.

1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 0.

2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных так: если значение некоторой переменной в данной строке= 1, то в дизъюнкцию включать саму эту переменную, если равно 0, то ее отрицание.

Как привести к днф и кнф

Простой конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание).

Например, является простой конъюнкцией,

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание).Например, выражение – простая дизъюнкция,

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций (например выражение – КНФ).

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одинаковом порядке.

Например, выражение является СКНФ.

Приведем алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы:

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К₂. Проделываем эту операцию несколько раз (можно последовательно, можно одновременно) для всех возможных пар слагаемых, а затем, применяем обычное поглощение;

— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

г) переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной (например, z, то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона):

Таким образом, из КНФ получена СКНФ.

Заметим, что минимальную или сокращенную КНФ обычно получают из соответствующей ДНФ.

4. Представление логических функций
в виде СДНФ (СКНФ)

Будем использовать логическую функцию “эквивалентность”, записанную в виде х у . Напомним, что 0 0 = 1; 0 1 =0; 1 0 = 0; 1 1 = 1.Таким образом, х у = 1 тогда и только тогда, когда х = у.

Лемма. Любая логическая функция f(x₁, x₂, …, x_n) может быть представлена в виде дизъюнкции 2 п дизъюнктных слагаемых, причем дизъюнкция берется по всевозможным наборам из E n . Этот факт будем записывать следующим образом:

где дизъюнкция проводится по всевозможным наборам (s₁, s₂, …, s_п) из Е п .

а) Пусть f(x₁, x₂, …, x_n)= 1. Тогда слева в формуле (* ) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s₁, s₂, …, s_п) имеется набор s₁ = х₁, s₂ = х₂, …, s_п = х_п. Очевидно, что для этого набора слагаемое равно 1 (так как и .

б) Пусть f(x₁, x₂, …, x_n) = 0. Предположим, что справа стоит не ноль, а единица, тогда какое-то слагаемое тоже должно равняться 1, т. е. для некоторого набора

Это означает (по свойствам конъюнкции), что , откуда следует, что х₁=s₁, х₂=s₂ ,…, х_п=s_n, но в этом случае f ( s₁, s₂, . s_n) f(x_1,x₂, …,x_n) = 0 и, значит, справа нет слагаемого, равного 1, т. е. в этом случае и справа и слева в формуле (* ) стоит 0. Лемма доказана.

Теорема. Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х₁,х_2, …,х_n), для которых f(х₁,х₂, …,х_n) =1, и составляем простую конъюнкцию для этого набора так: если х_i = 0, то берем в этой конъюнкции , если х_i = 1, то берем х_i. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ.

Доказательство. Пусть f(x_1,x₂,…,x_n) не равна тождественному нулю, тогда в дизъюнкции можно не записывать слагаемые, равные нулю, а из формулы (* ) следует следующее представление для данной функции

Запись означает, что дизъюнкция берется по всем наборам ( s₁, s₂, . s_n) , для которых f ( s₁, s₂, . s_n) = 1. Так как (если s₁=0), из формулы (**) следует утверждение теоремы.

Следствие. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание.

Из предыдущей теоремы видно, что следствие верно для любой функции, не равной тождественному нулю. Однако если f(x₁, x₂,…, x_{n) =}0, то ее также можно выразить через конъюнкцию, дизъюнкцию и отрицание, например, так: f(x₁, x₂,…, x_{n) = x1} ,и, несмотря на то, что последнее выражение не является простой конъюнкцией (и, значит, не является СДНФ), тем не менее тождественный ноль также выражен через нужные три функции.

Набор функций, через которые можно выразить любые другие функции, называется полным набором (более точные формулировки даны в разд. 7). Таким образом, конъюнкция, дизъюнкция и отрицание являются полным набором.

По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х₁, х₂, …, х_п), для которых f(x₁, x₂,…, x_n) = 0, причем если х_i = 1, то в этой дизъюнкции берем _, если же х_i = 0, то берем х_i.

Пример. Составить для импликации и сложения по модулю 2 СДНФ и СКНФ.

Тогда СДНФ для этих функций:

СКНФ для этих функций:

5. Нахождение сокращенной ДНФ
по таблице истинности (карты Карно)

Доказано, что любую функцию (кроме тождественного нуля) можно представить в виде СДНФ. На практике часто бывает удобно получить (вместо СДНФ) как можно более “короткую” ДНФ. Словам “короткая ДНФ” можно придать разный смысл, а именно:

ДНФ называется минимальной, если она содержит наименьшее число букв (разумеется, среди всех ДНФ ей равносильных); ДНФ называется кратчайшей, если она содержит минимальное число знаков дизъюнкции Ú ; тупиковой, если уничтожение одной или нескольких букв в ней приводит к неравной ДНФ и сокращенной ДНФ, если ее упрощение проведено с помощью правила Блейка.

На практике наиболее важной представляется нахождение минимальной ДНФ, но алгоритм ее нахождения по существу является вариантом перебора всех равносильных ДНФ. Алгоритмически проще всего находить сокращенную ДНФ (эти алгоритмы были даны в разд. 3). Заметим, что если функция п переменныхзаданасвоейтаблицей истинности, топравило Блейка имеет простой геометрический смысл. Именно, если все возможные наборы переменных представить себе как вершины п-мерного куба со стороной равной 1 (всего вершин будет 2 п ) в декартовой системе координат, то надо отметить те вершины, на которых значение функции равно 1, и если какие-то из этих единиц лежат на “прямой”, “плоскости” или “гиперплоскости” в п-мерном пространстве, то в сокращенную ДНФ будут входить “уравнения” этих прямых или гиперплоскостей по известному правилу: если в это уравнение входило составной частью х = 0,то в сокращенную ДНФ входит , если х = 1, то просто х.Разумеется, геометрически все это изобразить можно только при п = 2, 3.

Карты Карно позволяют эти геометрические идеи использовать при п = 3, 4, 5, для функций, заданных своей таблицей истинности. При больших п картыКарнопрактическинеиспользуются. Рассмотрим отдельно (и более подробно) случаи п = 3, 4.

Составляем таблицу истинности для данной конкретной функции п = 3 в виде таблицы, приведенной в примере 5.1. (Заметим, что для х₁и х₂естественный порядок набора переменных здесь нарушен. Это сделано для того, чтобы при переходе от данного к следующему набору переменных в этом наборе менялась только одна цифра). Прямая содержит 2 вершины, плоскость – 4, гиперплоскости – 8, 16 и т. д. вершин, поэтому объединять можно 2 рядом стоящие единицы или 4, 8, 16 и т. д. Карты Карно соединяются “по кругу”, т. е. наборы (10) и (00) считаются рядом стоящими.

Пример 5.1. Пусть задана функция:

Видно, ее СДНФ содержит (по числу 1) 6 дизъюнктных слагаемых, но ее сокращенная ДНФ содержит (после объединения единиц) всего 2 буквы

Пример 5.2. Следующий пример показывает, “как соединять единицы по кругу”.

Здесь сокращенная ДНФ содержит 2 слагаемых (СДНФ содержала бы 5):

Пример 5.3. Пример показывает использование карт Карно при п = 4.

Здесь сокращенная ДНФ содержит 4 слагаемых (СДНФ содержит 8):

При п = 5 использование карт Карно является несколько более сложным и здесь не приводится.

Пусть дана формула А, подлежащая преобразованию в КНФ. Если А — это пропозициональный символ /?, либо его отрицание -н/?, то ее КНФ состоит из единственного дизъюнкта, каковым является самор, либо р. Если же это не так, то надлежит выполнить следующие действия.

1. Исключение из Л связок -> и =, используя теоремы:

2. Внесение связки -> внутрь скобок везде, где это возможно, применяя законы де Моргана:

В результате этих действий связка будет расставлена в формуле А только перед пропозициональными символами или перед их отрицаниями. Вследствие этого могут появиться выражения вида —•—./?.

3. Удаление двойных отрицаний в соответствии с законом двойного отрицания

4. Применение закона дистрибутивности

необходимое число раз, пока не будет получена КНФ.

Для получения ДНФ этим же алгоритмом нужно на этапе 4 применять второй из законов дистрибутивности

необходимое число раз, пока не будет получена ДНФ.

Пример. Приведем к КНФ следующую формулу:

1. Исключение импликаций

2. Внесение связки внутрь скобок

3. Удаление двойных отрицаний

4. Применение закона дистрибутивности (av(bAC)) v ((avb)A(avc)) Следовательно, исходная формула эквивалентна КНФ D_]aD₂ aD₃, где

Приведение к ДНФ той же формулы выполняется точно также, и видно, что уже на этапе 3 искомая ДНФ построена, т. е. исходная формула эквивалентна ДНФ C₁vC₂vC₃vC₄, где

Конъюнктивная нормальная форма играет важную роль в обработке знаний на ЭВМ: дизъюнкты, входящие в КНФ, являются посылками в принципе резолюции, используемом в качестве единственного правила вывода в механизме вывода языков логического программирования. Например, синтаксической основой языка программирования PROLOG являются предложения Хорна, а его логической основой является принцип резолюции.

Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. [1] Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.

Содержание

Примеры и контрпримеры [ править | править код ]

¬ A ∧ ( B ∨ C ) , <displaystyle
eg Awedge (Bvee C),> ( A ∨ B ) ∧ ( ¬ B ∨ C ∨ ¬ D ) ∧ ( D ∨ ¬ E ) , <displaystyle (Avee B)wedge (
eg Bvee Cvee
eg D)wedge (Dvee
eg E),> A ∧ B . <displaystyle Awedge B.>

Формулы не в КНФ:

Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:

¬ B ∧ ¬ C , <displaystyle
eg Bwedge
eg C,> ( A ∨ C ) ∧ ( B ∨ C ) , <displaystyle (Avee C)wedge (Bvee C),> A ∧ ( B ∨ D ) ∧ ( B ∨ E ) . <displaystyle Awedge (Bvee D)wedge (Bvee E).>

Построение КНФ [ править | править код ]

Алгоритм построения КНФ [ править | править код ]

1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:

A → B = ¬ A ∨ B , <displaystyle A
ightarrow B=
eg Avee B,> A ↔ B = ( ¬ A ∨ B ) ∧ ( A ∨ ¬ B ) . <displaystyle Aleftrightarrow B=(
eg Avee B)wedge (Avee
eg B).>

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

¬ ( A ∨ B ) = ¬ A ∧ ¬ B , <displaystyle
eg (Avee B)=
eg Awedge
eg B,> ¬ ( A ∧ B ) = ¬ A ∨ ¬ B . <displaystyle
eg (Awedge B)=
eg Avee
eg B.>

3) Избавиться от знаков двойного отрицания.

4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.

Пример построения КНФ [ править | править код ]

Приведем к КНФ формулу

F = ( X → Y ) ∧ ( ( ¬ Y → Z ) → ¬ X ) . <displaystyle F=(X
ightarrow Y)wedge ((
eg Y
ightarrow Z)
ightarrow
eg X).>

Преобразуем формулу F <displaystyle F> к формуле, не содержащей → <displaystyle
ightarrow > :

F = ( ¬ X ∨ Y ) ∧ ( ¬ ( ¬ Y → Z ) ∨ ¬ X ) = ( ¬ X ∨ Y ) ∧ ( ¬ ( ¬ ¬ Y ∨ Z ) ∨ ¬ X ) . <displaystyle F=(
eg Xvee Y)wedge (
eg (
eg Y
ightarrow Z)vee
eg X)=(
eg Xvee Y)wedge (
eg (
eg
eg Yvee Z)vee
eg X).>

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

F = ( ¬ X ∨ Y ) ∧ ( ( ¬ Y ∧ ¬ Z ) ∨ ¬ X ) . <displaystyle F=(
eg Xvee Y)wedge ((
eg Ywedge
eg Z)vee
eg X).>

По закону дистрибутивности получим КНФ:

F = ( ¬ X ∨ Y ) ∧ ( ¬ X ∨ ¬ Y ) ∧ ( ¬ X ∨ ¬ Z ) . <displaystyle F=(
eg Xvee Y)wedge (
eg Xvee
eg Y)wedge (
eg Xvee
eg Z).>

k-конъюнктивная нормальная форма [ править | править код ]

k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.

Например, следующая формула записана в 2-КНФ:

( A ∨ B ) ∧ ( ¬ B ∨ C ) ∧ ( B ∨ ¬ C ) . <displaystyle (Alor B)land (
eg Blor C)land (Blor
eg C).>

Переход от КНФ к СКНФ [ править | править код ]

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в неё выражение : Z ∧ ¬ Z = 0 <displaystyle Zwedge
eg Z=0> (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

( X ∨ Y ) ∧ ( X ∨ ¬ Y ∨ ¬ Z ) = ( X ∨ Y ∨ ( Z ∧ ¬ Z ) ) ∧ ( X ∨ ¬ Y ∨ ¬ Z ) = ( X ∨ Y ∨ Z ) ∧ ( X ∨ Y ∨ ¬ Z ) ∧ ( X ∨ ¬ Y ∨ ¬ Z ) . <displaystyle (Xvee Y)wedge (Xvee
eg Yvee
eg Z)=(Xvee Yvee (Zwedge
eg Z))wedge (Xvee
eg Yvee
eg Z)=(Xvee Yvee Z)wedge (Xvee Yvee
eg Z)wedge (Xvee
eg Yvee
eg Z).>

Таким образом, из КНФ получена СКНФ.

Формальная грамматика, описывающая КНФ [ править | править код ]

Следующая формальная грамматика описывает все формулы, приведенные к КНФ:

где обозначает произвольную булеву переменную.

Задача выполнимости формулы в КНФ [ править | править код ]

В теории вычислительной сложности важную роль играет задача выполнимости булевых формул в конъюнктивной нормальной форме. Согласно теореме Кука, эта задача NP-полна, и она сводится к задаче о выполнимости формул в 3-КНФ, которая сводится и к которой в свою очередь сводятся другие NP-полные задачи.