Алгебра логики высказываний Основные понятия


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



бет4/7
Дата17.06.2016
өлшемі0.9 Mb.
#143069
1   2   3   4   5   6   7

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



Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

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

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

Например, для формулы А = х  (хy) имеем:

А = х  ( хy) = (х   х)  (хy) = хy, то есть

ДНФ А = (х   х)  (хy) и

ДНФ А = хy.

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

Как уже указывалось, СДНФ А может быть получе­на с помощью таблицы истинности.

Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:



  1. путем равносильных преобразований формулы А получают одну из ДНФ А.

  2. если в полученной ДНФ А входящая в нее эле­ментарная конъюнкция В не содержит переменную xi, то, используя закон B  (xi   xi) = B, элемен­тарную конъюнкцию B заменяют на две элементарных конъюнкции (Bxi) и (B   xi), каждая из которых со­держит переменную xi.

  3. если в ДНФ А входят две одинаковых элементар­ных конъюнкции В, то лишнюю можно отбросить, пользу­ясь равносильностью ВВ = В.

  4. если некоторая элементарная конъюнкция В, вхо­дящая в ДНФ А, содержит переменную xi и ее отрица­ние  xi, то, на основании закона xi   xi = 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой член дизъюнкции.

  5. если некоторая элементарная конъюнкция, вхо­дящая в ДНФ А, содержит переменную xi дважды, то одну переменную можно отбросить, пользуясь законом xixi = xi.

Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = xy  (x   y) ДНФ А = x  (x y)  (y   y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (xy) и (x   y), В результате получим ДНФ А = xy x   y x yy   y.

Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции xy, то отбросим лишнюю. В резуль­тате получим ДНФ A = xy x   y y   y.

Так как элементарная конъюнкция y   y содержит переменную у и ее отрицание, то y   y = 0, и ее можно отбросить как нулевой член дизъюнкции.

Таким образом, получаем СДНФ А = xy x   y.



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



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

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

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

Например, для формулы А =  (х у) х у имеем:

А = ( (х у)  х у)  (х у   (х у)) =

= (х ух у)  ( (х у)   (х у)) =

= (х х у)  (х уу)  ( х   у   х)  (  х   у   у) , то есть

КНФ А = (х х у)  (х уу)  ( х   у   х)  (  х   у   у).

Но так как х х = х, уу = у, х   х = х, у   у = у, то

КНФ A = (х у)  (ху)  ( х   у)  (  х   у).

А так как (х у)  (ху) = х у, ( х   у)  (  х   у) = (  х   у), то

КНФ A = (х у)  (  х   у).

КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:


  • Все элементарные дизъюнкции, входящие в КНФ А , различны.

  • Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.

  • Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.

  • Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

Можно доказать, что каждая не тождественно истин­ная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в исполь­зовании таблицы истинности для формулы  А. Действительно, получив с помощью таблицы истин­ности СДНФ  А, мы получим СКНФ А, взяв отрицание  (СДНФ  А), то есть СКНФ А =  (СДНФ  А).

Другой способ получения СКНФ, использующий рав­носильные преобразования, состоит в следующем:


  1. Путем равносильных преобразований формулы А получают одну из КНФ А.

  2. Если в полученной КНФ А входящая в нее эле­ментарная дизъюнкция В не содержит переменную хi, то, используя закон В  (xi   xi) = В, элементар­ную дизъюнкцию В заменяют на две элементарные дизъ­юнкции В xi и В   xi, каждая из которых содержит переменную xi.

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

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

  5. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную xi, и ее отрица­ние, то xi   xi = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно от­бросить, как истинный член конъюнкции.

Ясно, что после описанной процедуры будет получе­на СКНФ А. Например, для формулы А = xy  (x   y) КНФ А = x  (y  (x   y)) = (xy)  (xx   y). Так как обе элементарные дизъюнкции содержат все переменные (x и y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкция xx   y содержит переменную х дважды, но xx = x, поэтому КНФ А = (xy)  (x   y); причем, ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (xy)  (x   y).




Достарыңызбен бөлісу:
1   2   3   4   5   6   7




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет