Вычислительные машины и системы

рассматривается в отдельности, и в соответствующие ему квадратики

вписывается 1  (т.е. дизъюнктивный член развертывается до минтер-

мов).

     Например, нанесение на карту вейча заданной функции выполня-

ется в следующей последовательности:

       a

   ┌───┴───┐

  ┌┌───┬───┬───┬───┐    ┌───┬───┬───┬───┐    ┌───┬───┬───┬───┐

  ││  _1 . │   │   │  _1 . │    │  _1 . │  _1 . │   │ 1 │    │ 1 │ 1 │   │  _1 . │

b ┤├───┼───┼───┼───┤┐   ├───┼───┼───┼───┤    ├───┼───┼───┼───┤

  ││   │   │   │   ││   │   │   │   │   │    │   │   │   │  _1 . │

  └├───┼───┼───┼───┤├ d ├───┼───┼───┼───┤    ├───┼───┼───┼───┤

   │   │   │   │   ││   │   │   │   │   │    │   │   │   │   │

   ├───┼───┼───┼───┤┘   ├───┼───┼───┼───┤    ├───┼───┼───┼───┤

   │  _1 . │   │   │  _1 . │    │ 1 │   │   │ 1 │    │ 1 │   │   │ 1 │

   └───┴───┴───┴───┘    └───┴───┴───┴───┘    └───┴───┴───┴───┘

       └───┬───┘

         4__ 0 c 4              0  4   __     _          __     _   _ _

        cd                   cd V abd          cd V abd V abc

   ┌───┬───┬───┬───┐    ┌───┬───┬───┬───┐    ┌───┬───┬───┬───┐

   │ 1 │ 1 │   │ 1 │    │ 1 │ 1 │   │ 1 │    │ 1 │ 1 │   │ 1 │

   ├───┼───┼───┼───┤    ├───┼───┼───┼───┤    ├───┼───┼───┼───┤

   │   │   │   │ 1 │    │   │   │   │ 1 │    │   │   │   │ 1 │

   ├───┼───┼───┼───┤    ├───┼───┼───┼───┤    ├───┼───┼───┼───┤

   │   │   │   │   │    │  _1 . │   │   │   │    │ 1 │  _1 . │  _1 . │   │

   ├───┼───┼───┼───┤    ├───┼───┼───┼───┤    ├───┼───┼───┼───┤

   │ 1 │   │  _1 . │ 1 │    │ 1 │   │ 1 │ 1 │    │ 1 │   │ 1 │ 1 │

   └───┴───┴───┴───┘    └───┴───┴───┴───┘    └───┴───┴───┴───┘

     4__     _   _ _       __     _   _ _       __     _   _ _

    cd V abd V abc V     cd V abd V abc V     cd V abd V abc V

       4__ _                 __ _    __          __ _    __

    V abcd               V abcd V abcd       V abcd V abcd V bcd

     Следующий шаг заключается в нахождении на карте простых имп-

ликант, т.е. в склеивании минтермов. Нахождение простых импликант

является результатом последовательного применения теоремы:

                             4_

              x 41 0x 42 0x 43 0...x 4n 0 V x 41 0x 42 0x 43 0...x 4n 0 = x 42 0x 43 0...x 4n

     Нахождение простых  импликант  производится  на картах путем

группировки минтермов, отмеченных единицей.

     Рассмотрим правила группировки на диаграмме для четырех  пе-

ременных, учитывая,  что  их  легко обобщить на случай для любого

                              - 4 -

числа переменных. Группирование выполняется в следующем порядке:

     а) группа из восьми членов может быть представлена одной пе-

ременной, если две смежные строки, либо два смежных столбца, либо

две крайние  строки,  либо  два крайних столбца,  соответствующих

этой переменной, заполнены единицами;

     б) группа из четырех членов может быть представлена посредс-

твом двух переменных всякий раз, когда единицами заполнены:

     - строка диаграммы,

     - столбец диаграммы,

     - квадрат из двух строк и двух столбцов,

     - концы двух смежных строк,

     - концы двух смежных столбцов,

     - четыре угла диаграммы;

     в) группа из двух членов может быть представлена посредством

трех переменных всякий раз, когда единицами заполнены:

     - два смежных квадратика,

     - два противоположных конца одной строки,

     - два противоположных конца одного столбца.

     При группировке единиц на  диаграмме  необходимо  попытаться

сначала образовать члены,  содержащие одну переменную, затем чле-

ны, содержащие две переменные,  и, наконец, члены, содержащие три

переменные.  Один  и тот же минтерм может входить 2 несколько раз 0 в

выражение функции,  не изменяя ее значения.  Поэтому единицу  или

группу единиц  можно  несколько раз включать в различные комбина-

ции. В нашем случае минимизированная функция будет иметь вид:

                       4__     _   _ _    0  4_    _ 0     ___

         f(a,b,c,d) = cd V abd V abc V abd V bcd V abd.

                         ПЕРВЫЙ СЕМЕСТР

                           ЛЕКЦИЯ N 8

                2МЕТОДЫ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ

                           (окончание)

     Обычно для  проверки правильности результата,  полученного с

помощью одного из методов минимизации, либо используют другой ме-

тод (хотя при наличии у функции нескольких минимальных форм могут

быть получены несовпадающие результаты),  либо проверяют на  тож-

дественность  исходную  и минимальную формы методом перебора всех

возможных комбинаций значений переменных (однако уже для 20 пере-

менных число возможных комбинаций превышает миллион).

     В качестве примера  проведем  минимизацию  рассматривавшейся

ранее функции

                  4_    _   _    _

     f(a,b,c) = ab V bc V bc V ab

с помощью карты Вейча. Как видно из диаграммы, возможны две мини-

мальные дизъюнктивные формы:

                            a

                        ┌───┴───┐

                        ┌───┬───┬───┬───┐

                      b │ 1 │   │  _1 . │  _1 . │

                        ├───┼───┼───┼───┤

                        │ 1 │  21 0 │  21 0 │   │

                        └───┴───┴───┴───┘

                            └───┬───┘

                                c

                                  4_   _    0  4_

                     f(a,b,c) = ac V ab V bc

1	2	3	4	5	6	7	8	9	10	11	12