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

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


       Пример:
f = xyz ∨ x yz ∨ xy z ∨ x y z ∨ xyz ;
f = x y z ∨ x yz ∨ xy z ;
                                        (        )(
f = x y z ∨ x yz ∨ xy z ≡ (x ∨ y ∨ z ) x ∨ y ∨ z x ∨ y ∨ z . )
      При переходе от СКНФ к СДНФ в начале необходимо получить отрица-
ние исходного высказывания за счет выписывания через конъюнкцию недос-
тающих (до полного нуля) конституент нуля, а затем взять отрицание этого вы-
сказывания и выполнить преобразования по закону Де Морга.

        Пример:

                (          )(
f = (x ∨ y ∨ z ) x ∨ y ∨ z x ∨ y ∨ z ; )
f = (x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z ) ;
f = f = (x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z )(x ∨ y ∨ z ) ≡
   xyz ∨ x yz ∨ xyz ∨ x y z ∨ xyz .

                 МИНИМИЗАЦИЯ СЛОЖНЫХ ВЫСКАЗЫВАНИЙ.

      Существует много методов минимизации сложных высказываний. Рас-
смотрим один из них, удобный для алгоритмизации, а следовательно, для пере-
носа процедуры минимизации на ЭВМ – метод Квайна. Этот метод использует
следующие равносильности:
      Неполное склеивание АВ ∨ А В ≡ АВ ∨ А В ∨ А ;
        Поглощение          А ∨ АВ ≡ А .

      Минимизация выполняется в три этапа:
1. Высказывание из произвольной формы переводится в СДНФ.
2. Исходя из СДНФ, получают сокращенную дизъюнктивную нормальную
   формулу (СКДНФ)
3. На основе СДНФ и СКДНФ строится импликантная матрица, с помощью ко-
   торой получается минимальная дизъюнктивная нормальная формула
   (МДНФ).

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