Математическая логика. - 5 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

- 4 - Математическая логика
конституентой нуля) содержит все элементарные высказывания либо их отри-
цания по одному разу. Конституенты нуля в СКНФ не повторяются.
Каждое высказывание, кроме тавтологии и противоречия, имеет единст-
венную СДНФ и единственную СКНФ.
Тавтология не имеет СКНФ, а противоречие – СДНФ.
П р и м е р ы :
6.
zyxzxy ∨ - не является СДНФ;
7.
(
)
(
)
zxw zyx ∨∨∨∨ - не является СКНФ;
8.
zxyxyzzxy ∨∨ - не является СДНФ.
При переходе от ДНФ к СДНФ используются следующие равносильности:
П р и м е р :
При переходе от КНФ к СКНФ используются следующие равносильности:
П р и м е р :
При переходе СДНФ к СКНФ в начале необходимо получить отрицание
исходного высказывания за счет выписывания через дизъюнкцию недостающих
(до полного перечня) конституент единицы, а затем взять отрицание этого вы-
сказывания и выполнить преобразования по закону Де Морга.
()()
()
()()
КНФ; как и ДНФ как атьрассматрив можно - yx 5.
СКНФ; - zyx zyx zyx 4.
СДНФ; - zyxxyzzyxzyx 3.
КНФ; - x zx yx 2.
ДНФ; - y xz xy.1
∨
∨∨∨∨∨∨
∨∨∨
∨∨
∨∨
(
)
(
)
(
)
zyxzyxyzxzyxzyxzxyxyz
zyxzzyxzz yyxzyxyxx
∨∨∨∨∨∨
≡∨∨∨∨∨≡∨∨
(
)
. ВААВВВАА ; 1ВВ ; А1А ∨≡∨≡≡∨≡⋅
(
)
(
)
. ВА ВАВВАА ; 0ВВ ; А0А ∨∨≡∨≡≡⋅≡∨
(
)
(
)
(
)
(
)
(
)
()
()()()()()()
zyzyzyzzzyx
zyzzyzzyyxzyyxx
∨∨∨∨∨∨∨∨∨∨∨∨∨∨
≡∨∨∨∨∨∨≡∨∨∨
x x x yx yx zyx
x x x 
                                                           -4-                 Математическая логика


     конституентой нуля) содержит все элементарные высказывания либо их отри-
     цания по одному разу. Конституенты нуля в СКНФ не повторяются.
           Каждое высказывание, кроме тавтологии и противоречия, имеет единст-
     венную СДНФ и единственную СКНФ.
           Тавтология не имеет СКНФ, а противоречие – СДНФ.

              Примеры:

1.      xy ∨ xz ∨ y         - ДНФ;
2.      (x ∨ y)(x ∨ z ) x    - КНФ;
3.      xyz ∨ x yz ∨ xyz ∨ x yz                     - СДНФ;
4.      (x ∨ y ∨ z ) (x ∨ y ∨ z )(x ∨ y ∨ z )       - СКНФ;
5.      x∨y         - можно рассматривать как ДНФ и как КНФ;
 6. xyz ∨ x yz - не является СДНФ;
 7.     (x ∨ y ∨ z )(w ∨ x ∨ z ) - не является СКНФ;
 8.        xy z ∨ xyz ∨ xy z - не является СДНФ.

     При переходе от ДНФ к СДНФ используются следующие равносильности:
                                      (
 А ⋅1 ≡ А ; В ∨ В ≡ 1 ; А ≡ А В ∨ В ≡ АВ ∨ А В .)
              Пример:

                        (     )(      )         (
     x ∨ xy ∨ x yz ≡ x y ∨ y z ∨ z ∨ x y z ∨ z ∨ x yz ≡)
     xyz ∨ xy z ∨ x yz ∨ x y z ∨ xyz ∨ xy z ∨ x yz


     При переходе от КНФ к СКНФ используются следующие равносильности:
      А ∨ 0 ≡ А ; В ⋅ В ≡ 0 ; А ≡ А ∨ ВВ ≡ (А ∨ В) А ∨ В .       (   )
              Пример:

       (       )(          ) (               )(           )(
      x x ∨ y x ∨ y ∨ z ≡ x ∨ y y ∨ zz x ∨ y ∨ zz x ∨ y ∨ z ≡         )
      (x ∨ y ∨ z ) (x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )

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

Страницы