Конъюнкция и дизъюнкция

Содержание 

Конъюнкция и  дизъюнкция…………………………………………………………. 2 стр.

ДНФ и КНФ…………………………………………………………………………... 2 стр.

Построение минимальных  ДНФ…………………………………………………….. 2 стр.

Нахождение сокращенной  ДНФ методом Квайна…………………………………. 5 стр. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Конъюнкция  и дизъюнкция 
 

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

     Определение 2: Дизъюнкцией (логическое сложение) двух булевых переменных называется следующая функция.  

 

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

     Определение 3: Переменная или называется литералом (или буквой). 

     Определение 4: Конъюкция литералов, встречающихся не более чем по одному разу, называется элементарной конъюнкцией. Число букв входящих в неё называется её рангом. Элементарная конъюнкция называется полной относительно рассматриваемой булевой функции, если её ранг равен числу переменных данной функции. 

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

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

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

     Определение 7: Конъюнкция конечного множества элементарных дизъюнкций называется конъюнктивной нормальной формой(или сокращенно КНФ). Число элементарных дизъюнкций образующих КНФ называется длинной. КНФ состоящая только из полных элементарных дизъюнкций называется СКНФ. Произвольную формулу B vможно представить в виде КНФ, а затем КНФ в виде СКНФ. 

     Построение  минимальных ДНФ. 

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

 
 

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

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

 

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

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

     Назовем число букв, образующих конъюнкцию, рангом конъюнкции. Для обозначения ранга конъюнкции K условимся использовать выражение r(K). Отметим, что склеиваться могут только конъюнкции одинакового ранга. Между конъюнкциями различных рангов может существовать отношение покрытия. Если r(Ki) < r(Kj) и если Ki ^Kj = Ki, то говорят, что конъюнкция Ki покрывает конъюнкцию Kj. Например, всякая конъюнкция, получающаяся в результате склеивания, покрывает все элементарные конъюнкции, используемые для ее построения.

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

 

где ri - ранг конъюнкции с порядковым номером i. Прежде чем перейти к дальнейшему  изложению, рассмотрим следующий пример.  

Пример 3.1. 

Пусть переключательная функция φ(x1, x2,x3, x4) задана совокупностью своих элементарных конъюнкций:

 

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

 

     Отыскивая склеивающиеся конъюнкции в множестве (φ) и выполняя операцию склеивания, находим множество конъюнкций второго ранга: 

 

     Поскольку последнее множество состоит из одной конъюнкции, то (φ) = ∅. Объединим полученные множества конъюнкций различных рангов в одно множество R(φ) и назовем его комплексом конъюнкций заданной функции φ: . Любое подмножество , конъюнкции которого покрывают все элементарные конъюнкции множества (φ), назовем покрытием заданной функции φ. Например, следующие три подмножества являются покрытиями заданной функции: 
 

 
 

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

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

     Анализируя  элементы комплекса R(φ), можно заметить, что некоторые из них покрываются конъюнкциями меньшего ранга и что имеются элементы, которые не покрываются другими конъюнкциями. Это наблюдение позволяет нам сформулировать следующее определение. Конъюнкция K называется минималью или простым импликантом, если в комплексе R(φ) не существует другой конъюнкции K' меньшего ранга, которая покрывает конъюнкцию K. Например, множество минималей S функции, приведенной в примере 3.1, имеет вид:  
 

 

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

       Теорема 3.1. Любая минимальная дизъюнктивная нормальная форма состоит из минималей. 
 

Доказательство.

     Допустим, что форма L является МДНФ функции  φ и что в нее входит конъюнкция K, которая не является минималью. Тогда, согласно определению минимали, в  комплексе R(φ) должна существовать конъюнкция меньшего ранга K', которая покрывает K и является минималью. Поскольку K' покрывает K, то она покрывает все элементарные конъюнкции, покрываемые K, и, следовательно, в форме L можно конъюнкцию K заменить конъюнкцией K'. Обозначим ДНФ, полученную после такой замены, L. Формы L и L' отличаются только одной конъюнкцией, причем r(K) > r(K'). Следовательно, r(L) > r(L'). Итак, наше предположение о том, что L является МДНФ и содержит конъюнкцию, не являющуюся минималью, является неверным, что и доказывает справедливость теоремы.

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

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

Нахождение  сокращенной ДНФ  методом Квайна. 

      Рассмотрим процедуру построения  сокращенной ДНФ методом Квайна.

Этот  метод основан на преобразовании ДНФ с помощью операций полного  и неполного склеивания и операции поглощение. 

Полное  склеивание.

      Пусть х-булева переменная, а β  - элементарная конъюнкция. Тогда  имеет

место соотношение

                               хβ∨хβ=β .                            (10)

Для доказательства этого соотношения преобразуем  его левую часть, используя свойство дистрибутивности конъюнкции относительно дизъюнкции и равенства х∨х=1, 1⋅ х=х.

                        хβ ∨ хβ = ( х ∨  х) ⋅ β = 1 ⋅ β = β . 

Неполное  склеивание 

     Имеет место соотношение 

                          хβ ∨  хβ=β ∨ хβ ∨ хβ.                        (11) 

      Для доказательства (11) заменим в  соотношении u=u∨ u высказывание u на хβ ∨ хβ. Получим

                       хβ ∨ хβ=( хβ ∨ хβ) ∨ (хβ  ∨ хβ). 
 
 

Поглощение. 

     Наряду с конъюнкцией β рассмотрим  еще одну элементарную конъюнкцию γ. Тогда имеет место соотношение 

                             β∨β⋅γ=β                                   (12) 

Преобразуем левую часть (12). Имеем

                 β∨β⋅γ=β⋅1∨β⋅γ=β⋅(β∨γ)=β⋅1=β

      В случае полного склеивания (10) говорят, что члены хβ и хβ клеиваются по х , а случае поглощения (12) говорят, что член β⋅γ поглощается членом β.