Минимизация булевых функций

                            ЛЕКЦИЯ 3
                            --------

                              План
     1.Методы минимизации.
     2.Карты Карно.
     3.Алгоритм графич.минимизации.
     4.Сущность алгоритма.

                 3.Минимизация булевых функций

     Существуют несколько  способов минимизации булевых функций.Прежде всего,это аналитический символьный и аналитический кодовый методы,метод Квайна  -  Мак-Класки,метод  Блека  -  Порецкого,метод обобщенных  кодов[11]  и  графическая  минимизация с помощью карт Карно[12].
Пример для демонстрации аналитических методов:
z = x_y+xy_+xy = (x_y+xy)+(xy_+xy) = y(x_+x) + x(y_+y) = x+y.
z = 01+10+11 = (01+11)+(10+11) = -1+1- = x+y.
Первые четыре метода чрезвычайно громоздки и  малоэффективны уже при количестве аргументов более четырёх. Метод обобщенных кодов  ориентирован  на  использование ЭВМ,однако может использоваться и при ручном синтезе для функций от большого числа  переменных.

    3.1.Минимизация полностью определенных булевых функций

      Наиболее эффективна минимизация булевых функций с  помощью  карт
Карно.До  сих  пор  существует ошибочное мнение,что этим методом можно
решать задачи для функций от не более, чем 6 аргументов. На самом деле
карты  Карно  могут  применяться  для  функций даже от 8-12 переменных
[12]. На рис.3.1. представлены карты Карно для 2-6 переменных и приме-
ры минимизации с их помощью логических функций.

   \ x1            \x2x1                     \x2x1
 x2 \   0    1    x3\  00   01   11   10  x4x3\  00    01    11    10
     \ ----T-----    -----T----T----T-----     ------T-----T-----T------
    0 | а  | а  |  0 | а  |    |    | а  |  00 |  1  |  0  |  1  |  1  |
      +----+----+    +----+----+----+----+     +-----+-----+-----+-----+
    1 |    |    |  1 |    |    |    |    |  01 |  0  |  0  |  1  |  0  |
      L----+-----    L----+----+----+-----     +-----+-----+-----+-----+
          --             -- --              11 |  0  |  0  |  1  |  0  |
      а = X2         а = X3*X1                 +-----+-----+-----+-----+
                                            10 |  1  |  0  |  1  |  1  |
                                               L-----+-----+-----+------
                                                           -- --
                                                y = X2X1 + X3*X1

         а)                  б)                          в)

        \
         \  X2X1
  X5X4X3  \  00    01    11    10
           ------T-----T-----T------
      000  |  а  |  а  |  b  |  b  |
           +-----+-----+-----+-----+            -- --
      001  |     |     |  b  |  b  |        а = X3*X2
           +-----+-----+-----+-----+            --
      011  |     |     |  b  |  b  |        b = X5*X2
           +-----+-----+-----+-----+
      010  |  а  |  а  |  b  |  b  |        c = X5*X3*X2
           +-----+-----+-----+-----+
      110  |  а  |  а  |     |     |
           +-----+-----+-----+-----+
      111  |     |     |  с  |  с  |
           +-----+-----+-----+-----+
      101  |     |     |  с  |  с  |
           +-----+-----+-----+-----+
      100  | а   | а   |     |     |
           L-----+-----+-----+------

                     г)

           \  Х3Х2Х1
     Х6Х5Х4 \
             000 001 011 010 110 111 101 100
            ----T---T---T---T---T---T---T----
         000| a | в | c |   |   | c | в | a |
            +---+---+---+---+---+---+---+---+
         001| e |   |   | e |   |   |   |   |    f=X6*X5*X4
            +---+---+---+---+---+---+---+---+         __
         011| m | k | k | m | m | k | k | m |    n=X6*X4*X2
            +---+---+---+---+---+---+---+---+
         010| d | d |   |   |   |   | d | d |
            +---+---+---+---+---+---+---+---+
         110| n | n |   |   |   |   | n | n |
            +---+---+---+---+---+---+---+---+
         111| f | f | f | f | f | f | f | f |
            +---+---+---+---+---+---+---+---+
         101|   |   |   |   |   |   |   |   |
            +---+---+---+---+---+---+---+---+
         100| n | n |   |   |   |   | n | n |
            L---+---+---+---+---+---+---+----
                        д)
              Рис.3.1. Карты Карно для 2-6 переменных
       Метод Карно основан на  законе  склеивания.Склеиваются  наборы,
отличающиеся друг от друга лишь значением одного разряда.
     Такие наборы называются соседними,  и они соответствуют  соседним
клеткам  карты  Карно.Формируются  такие наборы(коды Грея) по принципу
симметрии[11,12].
     Введем определение прямоугольника Карно,  под которым будем пони-
мать некоторую, зачастую разрозненную, фигуру покрытия,удовлетворяющую
принципу симметрии,т.е. сплошь состоящую из элементарных прямоугольни-
ков Карно,закодированных только соседними наборами.

                      Алгоритм "НИИРТА"
           графической минимизации логических функций

     1.Заполнить карту Карно нулями и единицами в соответствии с  таб-
лицей истинности.
     2.Покрыть все единичные наборы  минимальным  количеством  прямоу-
гольников Карно, каждый из которых имеет максимальную площадь.
     3.Каждому прямоугольнику  Карно  соответствует  одна  импликанта,
причем,  если  в  границах  прямоугольника Карно какая-либо переменная
принимает значение как 0, так и 1, то она склеивается.
     На рис.  3.2  представлены  фигуры покрытия,не являющиеся прямоу-
  гольника Карно
    \ x3x2x1
 x5x4 \ 000 001 011 010 110 111 101 100
       ----T---T---T---T---T---T---T----
   00  | К | К |   | К | К |   | К | К |
       |   |   |   |   |   |   |   |   |
       +---+---+---+---+---+---+---+---+
  01   | П |П  |   |   |   |   |   |   |
       |   |   |   |   |   |   |   |   |
       +---+---+---+---+---+---+---+---+
  11   |   |   |   | М |М  |М  |М  |   |
       |   |   |   |   |   |   |   |   |
       +---+---+---+---+---+---+---+---+
  10   | П |П  |   | М |М  |М  |М  |   |
       |   |   |   |   |   |   |   |   |
       L---+---+---+---+---+---+---+----
  Рис. 3.2  Фигуры покрытия,не являющиеся прямоугольниками Карно

     Применим карту Карно для решения задачи 2.1  о  синтезе  автомата
для тайного голосования.Это решение представлено на рис. 3.3

      \ x2x1
 x4x3  \  00  01   11   10
        ----T----T----T-----
    00 |  0 | 0  | 0  | 0  |   y= x4x1 + x4x2 + x4x3 + x3x2x1
       +----+----+----+----+
    01 |  0 | 0  | 1  | 0  |   Это выражение представляет собой пример
       +----+----+----+----|   минимальной дизъюнктивной нормальной
    11 |  1 | 1  | 1  | 1  |   формы (МДНФ).
       +----+----+----+----+
    10 |  0 | 1  | 1  | 1  |
       L---------+----------

     Рис. 3.3. Решение задачи 2.1.

     В некоторых случаях приведение результата минимизации к скобочной
форме позволяет уменьшить сложность булевой функции.  Скобочная  форма
для (3.3) имеет вид
      y= x4(x1 + x2 + x3) + x3x2x1.
     Реализация скобочной формы логической функции автомата для тайно-
го голосования в виде релейной схемы изображена на рисунке.

|             x3    x2     x1                              |
+----------------L-----L------L--------------              |
|                                           |   -------    |
|   x4        x3                            |   |     |    |
+------L---T-----L-----T--------------------+---+ УИ  +----+
|          |  x2       |                        |     |    |
|          +-----L-----+                        L------    |
|          |  x1       |                                   |
|          L-----L------                                   |
|                                                          |
|+Еп                                                       |-Еп

   Релейная схема автомата к задаче 2.1

     На схеме представлены  контакты  реле  x4,x3,x2,x1.При  включении
тумблера  срабатывает  соответствующее  реле  и  замыкает свои контак-
ты.Например,если за прием абитуриента проголосовали председатель(x4) и
3-й  член  комиссии(х3),то замкнутся контакты х4 и х3 и сработает уст-
ройство индикации(УИ),запитанное от источника с напряжением Еп.

                        Домашнее задание.

   1.Найти z5,z7,z11,z13,z14,z15 для функций от трех переменных.
------T---T---T---T---T---T---T---T---T---T---T---T---T---T---T---T----
| uxy |z0 |z1 |z2 |z3 |z4 |z5 |z6 |z7 |z8 |z9 |z10|z11|z12|z13|z14|z15|
+-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 000 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 001 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 010 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 011 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 100 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 101 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 110 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 111 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
L-----+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+----
   2.Найти общее количество функций от 3-х переменных.
Hosted by uCoz