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

                                              -6-                             Математическая логика


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

      Примеры:
      I. Получить МДНФ для высказывания                           (x ↓ y)∨ ((x ∨ y)z ).
      Получим СДНФ
(x ↓ y)∨ ((x ∨ y)z ) ≡ x y ∨ x z ∨ yz ≡ x yz ∨ x yz ∨ xyz ∨ x yz ∨ xyz .
                                        1          2          3        4      5

      Получим СКДНФ. При склеивании будем указывать порядковые номера
конъюнкции, участвовавших в склеивании, и рядом записывать результат. Не-
полное склеивание будет обеспеченно за счет того, что конъюнкции, участво-
вавшие в склеивании, не уничтожаются:
                     1− 2 : xy 6                            7 − 10 : z
                     2 − 4 : yz 7                           8−9 : z
                     2 − 5 : xz 8
                     3 − 4 : xz 9
                  3 − 5 : yz 10
      Далее выполняются поглощения. Результат каждого склеивания погло-
щает конъюнкции, участвовавшие в склеивании. Выполнив все возможные
склеивания, получаем СКДНФ x y ∨ z .
      Получим МДНФ (табл.2):
                                              Таблица 2

                                 xy z       x yz       xy z         x yz     xy z
                         xy       +          +
                          z                  +          +             +       +


       Из импликантной матрицы следует, что МДНФ совпадает с СКДНФ.

       2. Получить МДНФ для высказывания ((x | y ) → (x ↓ z )) ∨ x → z .
       Получим СДНФ:
       ((x | y) → (x ↓ z ))∨ x → z ≡ xy ∨ yz ∨ xz ≡ xy ∨ yz ∨ xz ≡
       xyz ∨ xy z ∨ x yz ∨ x yz ∨ xyz ∨ x yz .