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

твом логического произведения элементарных дизъюнкций.  КНФ также

существует для любой логической функции.

     Например, для функции      4_________

                                7(     4_ 7  ) 4   _

                  f(a,b.c) = a 5. 72 0b V a 5. 0c 72 0 V a 5. 0b

                                79       0

ДНФ будет иметь вид

                                    4_   _

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

КНФ будет иметь вид

                                4_      _

                   f(a,b.c) = (a V b)(b V c).

     Одна и  та же функция путем эквивалентных преобразований мо-

жет быть представлена различными КНФ и ДНФ.  Из всей совокупности

нормальных форм, представляющих данную функцию, выделяют одну КНФ

и одну ДНФ, именуемые совершенными.

      2Минтермом 0 (m)  n аргументов называется логическое произведе-

ние этих аргументов,  причем каждый аргумент может входить в про-

изведение в прямой или инверсной форме.

     Минтермы могут быть пронумерованы, причем номер минтерма оп-

ределяется как десятичный эквивалент двоичного числа,  образован-

ного из значений переменных,  входящих в данный набор: если пере-

менная входит в прямой форме, то ей соответствует единица, если в

инверсной - ноль.

      2Макстермом 0 (M) n аргументов называется логическая сумма этих

аргументов, причем каждый аргумент может входить в сумму в прямой

или инверсной  форме.  Номер макстерма задается аналогично номеру

минтерма.

.

                              - 3 -

     Рассмотрим в качестве примера случай двух аргументов:

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

           │  a  │  b  │   минтерм   │   макстерм   │

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

           │     │     │        4_ 0  4_ 0   │        4_ 0    4_ 0  │

           │  0  │  0  │  m 40 0 = a 5. 0b   │  M 40 0 = a V b  │

           │     │     │        4_ 0     │        4_ 0      │

           │  0  │  1  │  m 41 0 = a 5. 0b   │  M 41 0 = a V b  │

           │     │     │          4_ 0   │            4_ 0  │

           │  1  │  0  │  m 42 0 = a 5. 0b   │  M 42 0 = a V b  │

           │     │     │        4    0   │              │

           │  1  │  1  │  m 43 0 = a 5. 0b   │  M 43 0 = a V b  │

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

     Минтермы и макстермы можно геометрически представить на кар-

тах (диаграммах) Вейча.  Так, для двух переменных карта Вейча бу-

дет представлять  собой  квадрат,  причем левая половина квадрата

определяется переменной a, а верхняя половина квадрата - перемен-

ной b.  Это означает,  что левая 4_ 0 половина квадрата соответствует

значению переменной a, правая - a, верхняя половина соответствует

           4_

b, нижняя b.

     Карта Вейча для двух переменных:

                                    4_

                              2a     a

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

                          │     │  4_ 0   │

                         2b  0│ a 5. 0b │ a 5. 0b │

                          │     │     │

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

                         4_ 0 │    4_ 0 │  4_ 0  4_ 0 │

                         2b  0│ a 5. 0b │ a 5. 0b │

                          │     │     │

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

.

                              - 4 -

     Карта Вейча для 5  0трех переменных:

                                           4_

                           2a               a

                    5┌──────┴──────┐ ┌──────┴──────┐

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

                  │      4_ 0 │       │  4_ 0     │  4_ 0    4_ 0 │

                 2b  0│ a 5. 0b 5. 0c │ a 5. 0b 5. 0c │ a 5. 0b 5. 0c │ a 5. 0b 5. 0c │

                  │       │       │       │       │

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

                 4_ 0 │    4_ 0  4_ 0 │    4_ 0   │  4_ 0  4_ 0   │  4_ 0  4_ 0  4_ 0 │

                 2b  0│ a 5. 0b 5. 0c │ a 5. 0b 5. 0c │ a 5. 0b 5. 0c │ a 5. 0b 5. 0c │

                  │       │       │       │       │

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

                       4_ 0     5└──────┬──────┘ 4    _

                       2c 0            2c           c

                 2Свойства минтермов и макстермов:

     1) Минтерм является инверсией некоторого макстерма и  наобо-

рот: 4                      _

                          m 4i 0 = M

                                2 5n 0-1-i

                           4_

                          M 4i 0 = m

                                2 5n 0-1-i

              4_

     Пример: m 41 0 = 4  0M 42 0 (заштрихованная площадь соответствует  макс-

терму, незаштрихованная - минтерму).

                             1┌┬┬┬ 0┬ 1── 0─┐

                             1├┼┼┼┤   │

                             1├┼┼┼ 0└ 1┬┬┬ 0┤

                             1├┼┼┼┼┼┼┼┤

                             1└┴┴┴┴┴┴┴┘

     2) Логическая сумма всех минтермов для любого заданного чис-

ла переменных равна 1.

                           2 5n 0-1

                             V m 4i 0 = 1.

                            i=0

     3) Логическое произведение всех макстермов для любого задан-

ного числа переменных равно 0.

                           2 5n 0-1

                              7L 0 M 4i 0 = 0.

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