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

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

      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.

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

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