Содержание
Конъюнкция и дизъюнкция…………………………………………………………. 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) говорят, что член β⋅γ поглощается членом β.

    

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

      1. Найдем совершенную ДНФ заданной функции f.

      2. Привести в полученной ДНФ все конъюнктивные члены к одному рангу n.

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

      4. Провести все возможные операции поглощения, в результате чего получим ДНФ, состоящую из элементарных конъюнкций ранга n-1.

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

      6. Описанную выше процедуру следует проводить до тех пор, пока это

будет возможно. Полученная в итоге ДНФ и будет сокращенной. Образующие

ее элементарные конъюнкции называются простыми импликантами функции f.

  

   Пример. Найти сокращенную ДНФ булевой функции

                       f(x,y,z) = xz ∨ xyz ∨ xyz ∨ xyz.

      Решение.                          

1. Прежде всего приведем все конъюнктивные члены к одному и тому же рангу r=3. Для этого умножим первый член xz на y∨ y=1. Имеем

                  xz = xz1 = xz(y ∨ y) = xzy ∨ xzy = xzy ∨ xzy.

Тогда исходная функция f примет вид

                   f(x,y,z)=xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz               (13)

      2. Приведем все возможные операции неполного склеивания в два приема:

      а) склеим (полное склеивание) каждую из конституент единицы ДНФ (13) с последующими.
         1-ый член   склеивается   со 2-м по y,     получим      xz,

         1-й               »       с 5-м по х,         »         yz,

         2-й                  ни     с чем не     склеивается,

         3-й член    склеивается   с 4-м по y,      получим      xz,

         4-й              »        с 5-м по z,         »         xy.
     б) конъюнкции, полученные в результате полного склеивания, выпишем вначале ДНФ, соединив их между собой и с ДНФ знаками дизъюнкций.

           f(x,y,z)=xz ∨ yz ∨ xz ∨ xy ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz

      3. Проведем все возможные операции поглощения в соответствии с формулой β∨β⋅γ=β. Первый член xz поглощает xyz и xyz, т.е.

                         xz ∨ xyz = xz ∨ (xz)y =xz ,

                         xz ∨ xyz = xz ∨ (xz)y =xz .

Аналогичным образом член yz поглощает xyz. Далее, xz поглощает xyz и xyz. В итоге получим

                    f(x,y,z)=xz ∨ yz ∨ xz ∨ xy.                        (14)

     4. Непосредственной проверкой убеждаемся, что применение операций склеивания и поглощения невозможно. Полученное соотношение (14) является сокращенно ДНФ заданной функции. Конъюнктивные члены (14) представляют собой простые импликанты функции f.

    
                                                                                                              
Список используемой литературы

Белоусов А.И., Ткачев С.Б. Дискретная математика