Как привести формулу к кнф

ПДНФ и ПКНФ — Введение в математическую логику

В отличие от ученых из других научных сфер, математики часто не задумывается о практическом применении того или иного знания. Обычно они ставят теоретические вопросы и находят ответы на них.

Уже позже некоторые ответы оказываются полезными в других разделах математики или в науке в целом. Например, так появились векторы, без которых сложно представить всю современную науку. Сначала математики просто ради интереса занимались кубическими уравнениями и комплексными числами, а уже потом эти темы объединились и привели к векторам.

Как и математика, логика зачастую не имеет практического применения — например, сложно представить практическое применение форм в логике, которые мы изучим сегодня.

Тем не менее пропустить эту тему нельзя. Формы позволят решать задачи минимизации булевых функций и оптимизации на графах, которые мы будем рассматривать в других курсах по математике.

Формы в логике

Ранее в курсе мы научились определять истинность формул двумя способами:

Через таблицу истинности

Через доказательство с помощью modus ponens

Эти способы помогают нам доказать общезначимые формулы. Попробуем усложнить задачу и проверить, можно ли доказать общезначимую формулу из аксиом. Чтобы это сделать, нам нужно обратиться к нормальной форме.

В математической логике формулы могут иметь нормальную форму — это значит, что их можно приводить к простейшему виду с помощью эквивалентных преобразований. Другими словами, каждую формулу можно привести к нормальной форме — и тогда нам будет проще доказывать.

В этом уроке мы изучим четыре типа нормальных форм:

Дизъюнктивная нормальная форма (ДНФ)

Полная дизъюнктивная нормальная форма (ПДНФ)

Конъюнктивная нормальная форма (КНФ)

Полная конъюнктивная нормальная форма (ПКНФ)

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

Дизъюнктивная нормальная форма (ДНФ)

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

Другими словами, дизъюнктивная нормальная форма — это дизъюнкция нескольких элементарных конъюнкций. В дизъюнктивной нормальной форме используются операторы AND, OR и NOT.

Дизъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из суммы элементарных произведений. Например:

Логическая формула находится в дизъюнктивной нормальной форме только при таких условиях: если существует чередование одной или нескольких конъюнкций одного или нескольких литералов.

Есть еще несколько способов получить дизъюнктивную нормальную форму для логических формул:

Метод таблицы истинности

Метод деревьев истинности

Таблица логических эквивалентностей

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

Полная дизъюнктивная нормальная форма (ПДНФ)

У ДНФ есть еще и полная версия. Полная дизъюнктивная нормальная форма — это формула ДНФ, в которой все задействованные переменные представлены только один раз в каждом предложении.

Обратите внимание, что у функции может быть только одна ПДНФ. Это упрощает доказательство и снижает вероятность ошибок. Если есть всего один верный ответ, его намного легче проверить.

ПДНФ относится к сумме произведений. Например:

— пример выражения в ПДНФ

— основной оператор (сумма)

Чтобы не запутаться, рассмотрим основное отличие между ДНФ и ПДНФ:

ДНФ — длина всех переменных в выражении может быть разной

ПДНФ — длина всех переменных в выражении должна быть одинаковой

Посмотрим на еще двух примерах:

Выражение в ДНФ, которое не считается ПДНФ из-за разной длины переменных:

Выражение в ДНФ и ПДНФ одновременно:

Конъюнктивная нормальная форма (КНФ)

В логике есть термин клауза (или клаузула) — это формальная запись доказываемого предложения. Введем это понятие, чтобы отличать объектные высказывания от субъектных.

Для начала вспомним, что в булевой алгебре сложение и умножение — это симметричные операции. Это значит, что всегда можно интерпретировать сложение как умножение, а умножение как сложение. Потому и существует КНФ — форма, симметричная для ДНФ. Как и ДНФ, КНФ полезна для автоматизированного доказательства теорем.

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

Другими словами, конъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из произведения элементарных произведений. Например:

Приведение формул алгебры высказываний к КНФ виду

11. 1. Приведение формул алгебры высказываний к ДНФ и СДНФ виду.

11. 2. Приведение формул алгебры высказываний к КНФ виду.

Приведение формул алгебры высказываний к ДНФ и СДНФ виду.

Элементарной конъюнкцией называется конъюнкция, состоящая только из переменных или их отрицаний. Например: .

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

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

Покажем, что это действительно так:

=

(по закону поглощения ).

Мы доказали следующее правило поглощения:

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

Проиллюстрируем это правило еще на двух примерах.

1. . Этот трехчлен содержит два раза , два раза , но один раз и один раз . Значит,, симметрия нарушена по . Поэтому, согласно нашему правилу, пропадает член, не содержащий букву (т. е. не содержащий ни , ни ). Значит, надо вычеркнуть .

2. . Этот трехчлен содержит два раза , два раза , но один раз и один раз . Симметрия нарушена по . Значит, вычеркиваем член, не содержащий , т. е. вычеркиваем .

Минимальной мы назовем ту ДНФ , которая имеет самую ко­роткую запись.

Существует еще одно правило поглощения, которое тоже основано на соображениях симметрии:

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

Например: . Покажем, что это действительно так:

.

Рассмотрим еще несколько примеров, иллюстрирующих это правило.

1. . Этот трехчлен содержит два раза , но содержит по одному разу и , и по одному разу и . Значит, симметрия нарушена дважды: по и по . Симметрия не нарушена только по . Поэтому, применяя наше правило, получим дизъюнкцию, одним членов которой будет , адругим — тот член трехчлена, | который_ не содержит . Значит, получим .

2. . В этом трехчлене симметрия нарушена по и по . Симметрия не нарушена только по . Значит, = .

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

Например:

Среди всех этих ДНФ есть одна, которая отличаете однородностью и «совершенством» своей формы. Mы имеем в виду формулу: Она так и называется: «совершенная дизъюнктивно-нормальная форма» (СДНФ).

Дадим точное определение:

СДНФ — это такая ДНФ, которая удовлетворяет следующим условиям:

1. Все элементарные конъюнкции различны.

2. Нет нулевых конъюнкций.

3. Ни одна из элементарных конъюнкций не содержит одинаковых членов.

4. Каждая элементарная конъюнкция содержит все переменные.

Чтобы получить СДНФ, надо сначала найти минимальную ДНФ. Тогда будут выполнены условия 1, 2, 3. Посли этого надо преобразовать эту минимальную ДНФ таким образом, чтобы было выполнено условие 4. Это делается следующим образом:

Приведение формул алгебры высказываний к КНФ виду

Элементарной дизъюнкцией называется дизъюнкция, состоящая только из переменных или их отрицаний. Например: .

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций. Например: . Если воспользоваться равносильностью , то можно заменить через . Кроме того, известно, что, . А если один член дизъюнкции равен 1, то и вся дизъюнкция равна 1. Значит: . Но . Значит, единичный член конъюнкции мож­но просто опустить. Таким образом, первоначальная КНФ| сводится к более простой форме: .

Но эта формула не является еще минимальной. Для КНФ тоже существуют правила поглощения, основанные на соображениях симметрии. Эти правила можно полу­чить по закону двойственности из аналогичных правил, установленных для ДНФ.

Мы знаем, например, что: (симметрия нарушена по переменной . Поглотилось вы­ражение, не содержащее эту переменную). Запишем теперь двойственную равносильность: . В левой части стоит ранее полученная КНФ. Значит, эту КНФ действительно можно свести к более простой форме.

В то же время мы установили новое правило погло­щения:

Если КНФ зависит от трех переменных и представляет собой конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена только по одной из пере­менных, то поглощается та элементарная дизъюнкция, которая эту переменную не содержит.

Аналогичным образом можно получить и второе пра­вило поглощения, основанное на соображениях симмет­рии. Мы уже знаем, что: .

Запишем двойственную равносильность:

Сформулируем соответствующее правило поглощения:

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

Чтобы найти минимальную КНФ, равносильную данной формуле, надо эту формулу сначала привести к виду ДНФ, затем надо разложить ее на «множители» и применить законы погло­щения.

Рассмотрим конкретный пример.

Можно поступить и по-другому. Новый подход начнет­ся с того момента, когда была получена формула . В этой формуле симметрия нарушена только по одной переменной . Мы применяли соответ­ствующий закон поглощения. А сейчас мы этого делать не будем. Вместо этого мы добавим к нашей формуле нулевую конъюнкцию, составленную из той переменной, по которой была нарушена симметрия, т. е. добавим и произведем группировку:

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, то ее отрицание.

15. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.

Если х – логическая переменная, , то выражение: называется литерой. Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.

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

Алгоритм приведения формулы к ДНФ:

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

закон де Моргана, сокращаем двойные отрицания.

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

Алгоритм приведения формулы к КНФ:

1) Выразить все логические операции, через дизъюнкции, конъюнкции и отрицания: , .

2) закон де Моргана, сокращаем двойные отрицания.

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

Способы построения СДНФ и СКНФ.

СДНФ – дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. СКНФ – конъюнкция некоторых коституент нуля, среди которых нет одинаковых.

Первая теорема Шеннона: Любая булева функция f(x₁,…,x_n) представима в виде разложения Шеннона:

Вторая теорема Шеннона: Любая булева функция f(x₁,…,x_n) представима в виде разложения Шеннона:

Теорема о функциональной полноте: Для любой булевой функции f найдется формула φ, представляющая функцию f. Если f≠0, то φ однозначно представима в виде СДНФ: . Если f≠1, то φ однозначно представима в виде СКНФ: .

Приведение КНФ к СКНФ:

Данную формулу приводим к КНФ

Если в дизъюнкт одна и та же литера x δ входит несколько раз, то мы удаляем их все кроме одной

Если в некоторый дизъюнкт не входит переменная y, то заменяем его на эквивалентную формулу и применяем закон дистрибутивности

Если в полученном КНФ имеется несколько одинаковых конституент нуля, то оставляем только одну из них. В результате получается СКНФ.

16. Минимизация днф. Сокращенная, тупиковая, минимальная днф.

Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза.

Формула φ(x₁,…,x_n) называется импликантой формулы ψ(x₁,…,x_n), если φ – элементарное произведение и , т.е для соответствующих формулам φ и ψ функций f_φ и f_ψ справедливо неравенство f_φ ≤f_ψ. Формула φ(x₁,…,x_n) называется импликантой функции f, если φ – импликанта СДНФ, представляющей f. Импликанта формулы ψ называется простой, если после отбрасывания любой литеры из φ не получается формула, являющаяся импликантой формулы ψ.

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

Если из СкДНФ удалить все лишние импликанты, то получается Тупиковая ДНФ. Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает МинимальнуюДНФ

Способы построения СДНФ и СКНФ.

СДНФ – дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. СКНФ – конъюнкция некоторых коституент нуля, среди которых нет одинаковых.

Метод Квайна для нахождения МДНФ,представляющей данную булеву функцию. Определим следующие три операции:

Операцию полного склеивания

Операцию неполного склеивания

Операция элементарного поглащения

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

Приведение КНФ к СКНФ:

Данную формулу приводим к КНФ

Если в дизъюнкт одна и та же литера x δ входит несколько раз, то мы удаляем их все кроме одной

Если в некоторый дизъюнкт не входит переменная y, то заменяем его на эквивалентную формулу и применяем закон дистрибутивности

Если в полученном КНФ имеется несколько одинаковых конституент нуля, то оставляем только одну из них. В результате получается СКНФ.