No Image

Чем отличается днф от сднф

СОДЕРЖАНИЕ
2 просмотров
11 марта 2020

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

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

Любая булева формула, не являющаяся тождественно ложной, может быть приведена к СДНФ, причём единственным образом [1] , то есть для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная.

Пример нахождения СДНФ [ править | править код ]

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

В ячейках результата f ( x 1 , x 2 , x 3 ) <displaystyle f(x_<1>,x_<2>,x_<3>)> отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:

  • x 1 = 0 <displaystyle x_<1>=0>
  • x 2 = 0 <displaystyle x_<2>=0>
  • x 3 = 0 <displaystyle x_<3>=0>

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: x 1 ¯ ⋅ x 2 ¯ ⋅ x 3 ¯ <displaystyle <overline <1>>>cdot <overline <2>>>cdot <overline <3>>>>

Переменные второго члена:

  • x 1 = 0 <displaystyle x_<1>=0>
  • x 2 = 0 <displaystyle x_<2>=0>
  • x 3 = 1 <displaystyle x_<3>=1>

Таким образом анализируются все ячейки f ( x 1 , x 2 , x 3 ) <displaystyle f(x_<1>,x_<2>,x_<3>)> . Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).

Совершенная ДНФ этой функции:

f ( x 1 , x 2 , x 3 ) = ( x 1 ¯ ∧ x 2 ¯ ∧ x 3 ¯ ) ∨ ( x 1 ¯ ∧ x 2 ¯ ∧ x 3 ) ∨ ( x 1 ¯ ∧ x 2 ∧ x 3 ¯ ) ∨ ( x 1 ∧ x 2 ∧ x 3 ¯ ) <displaystyle f(x_<1>,x_<2>,x_<3>)=(<overline <1>>>land <overline <2>>>land <overline <3>>>)vee (<overline <1>>>land <overline <2>>>land x_<3>)vee (<overline <1>>>land x_<2>land <overline <3>>>)vee (x_<1>land x_<2>land <overline <3>>>)>

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

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

Если учесть, что нулевые конъюнкции можно опустить, а А*А=А, то приведенная ДНФ сведется к более простому виду: .

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

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

=

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

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

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

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

1. . Этот трехчлен содержит два раза , два раза , но один раз и один раз . Значит,, симметрия нарушена по .

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

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

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

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

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

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

.

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

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

2. .

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

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

Читайте также:  Почему не сбиваются сливки

Например:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мы получили тот же ответ.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась – это был конец пары: "Что-то тут концом пахнет". 8526 – | 8113 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

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

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

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

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

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

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

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

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

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

Читайте также:  C users сергей appdata local temp

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(*)

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

а) Пусть f(x1, x2, , xn)= 1. Тогда слева в формуле (* ) стоит 1. Докажем, что и справа в этом случае стоит 1, для чего достаточно указать одно дизъюнктное слагаемое, равное 1. Но среди всех наборов (s1, s2, , sп) имеется набор s1 = х1, s2 = х2, , sп = хп. Очевидно, что для этого набора слагаемое равно 1 (так как и .

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

Это означает (по свойствам конъюнкции), что , откуда следует, что х1=s1, х2=s2 ,, хп=sn, но в этом случае f ( s1, s2, . sn) f(x1,x2, ,xn) = 0 и, значит, справа нет слагаемого, равного 1, т. е. в этом случае и справа и слева в формуле (* ) стоит 0. Лемма доказана.

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

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

Читайте также:  Как перевести с англ на русский

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

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

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

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

По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1, х2, , хп), для которых f(x1, x2,, xn) = 0, причем если хi = 1, то в этой дизъюнкции берем , если же хi = 0, то берем хi.

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

х у х® у х + у

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

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

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

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

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

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

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

Составляем таблицу истинности для данной конкретной функции п = 3 в виде таблицы, приведенной в примере 5.1. (Заметим, что для х1и х2естественный порядок набора переменных здесь нарушен. Это сделано для того, чтобы при переходе от данного к следующему набору переменных в этом наборе менялась только одна цифра). Прямая содержит 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 использование карт Карно является несколько более сложным и здесь не приводится.

Дата добавления: 2016-05-25 ; просмотров: 6805 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Комментировать
2 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector