Что такое дизъюнктивная форма

Функция, представленная в DNF

y знак равно Икс 2 ¯ Икс 1 Икс 0 ¯ ∨ Икс 2 ¯ Икс 1 Икс 0 ∨ Икс 2 Икс 1 ¯ Икс 0 ∨ Икс 2 Икс 1 Икс 0 <\ displaystyle y = <\ bar >> x_ <1><\ bar >> \ vee <\ bar >> x_ <1>x_ <0>\ vee x_ ​​ <2><\ bar >> x_ <0>\ vee x_ ​​ <2>x_ <1>x_ <0>>

также может быть представлено как логическое выражение в квадратных скобках:

е знак равно ( ( Икс 2 ¯ ) ∧ Икс 1 ) ∨ ( Икс 2 ∧ Икс 0 ) <\ Displaystyle е = ((<\ бар >>) \ клин x_ <1>) \ vee (x_ <2>\ клин x_ <0>)>

е знак равно Икс 2 ¯ Икс 1 + Икс 2 Икс 0 <\ displaystyle e = <\ bar >> x_ <1>+ x_ <2>x_ <0>>

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

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

Каноническая дизъюнктивная нормальная форма

В KDNF те назначения переменных, для которых функция принимает значение 1, выражаются minter terms.

Ортогональная дизъюнктивная нормальная форма

Более нормальные формы

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

Источник

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

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

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

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

Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.

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

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой конъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

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

Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.

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

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой дизъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Алгоритм построения СДНФ по таблице истинности

Алгоритм построения СКНФ по таблице истинности

Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

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

Copyright © 2014-2021, Урок информатики
Все права защищены

Источник

Дизъюнктивные и конъюнктивные нормальные формы. Совершенные конъюнктивные и дизъюнктивные нормальные формы

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

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

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

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

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

=

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

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

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

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

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

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

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

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

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

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

.

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

2. .

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

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

Например:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Что такое дизъюнктивная форма

Пусть имеем множество переменных X=1, x₂, …, x_n>.

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

Определение. Число переменных, образующих элементарную конъюнкцию, назовем ее рангом.

Примеры. Ранги элементарных конъюнкций x₁ x ₃x₄ и 1 равны трем и нулю. •

Определение. Полной конъюнкцией назовем элементарную конъюнкцию, состоящую из всех n переменных множества X, то есть конъюнкцию ранга n.

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

Определение. Две конъюнкции называются смежными, если они ортогональны по одной и только одной переменной x_i (принято также говорить »смежны по переменной x_i»).

Пример. Конъюнкции x₁x₂ x ₃ и x₁x₃ x ₄ являются смежными по переменной x₃ (ортогональны только по x₃). •

Определение. Две конъюнкции называются соседними, если они ортогональны по одной и только одной переменной x_i и совпадают по остальным (принято также говорить »соседние по переменной x_i»).

Пример. Конъюнкции x₁x₂ x ₃ и x₁x₂ x₃ являются соседними по переменной x₃ (ортогональны только по x₃ и совпадают по x₁ и x₂). •

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

Примеры. Конъюнкции x₁x₂ x ₃ и x₁x₂ x₃ являются соседними по переменной x₃, следовательно, к ним применим закон склеивания соседних конъюнкций по x₃:

Конъюнкции x₁x₂ x ₃ и x₁x₃ x ₄ являются смежными по переменной x₃, следовательно, к ним применим закон обобщенного склеивания смежных конъюнкций по x₃:

Определение. Дизъюнктивной нормальной формой(ДНФ) булевой функции f(x₁, …, x_n) назовем дизъюнкцию различных элементарных конъюнкций, задающую функцию f(x₁, …, x_n).

Пример. x₁ x ₂ x₁ x ₂x₃ x₁ x ₃ x ₄ = ДНФ. •

Определение. Длиной ДНФ назовем число ее конъюнкций, а рангом ДНФ – сумму рангов конъюнкций.

Пример. Длина ДНФ из предыдущего примера равна трем, а ранг – восьми. •

Будем применять обозначение ДНФ_f, если захотим отметить, что ДНФ представляет булеву функцию f(x₁, …, x_n).

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

Источник