алгебраические преобразования исходного выражения, провести все возможные операции поглощения и склеивания в соответствии с рассмотренными в § 4 законами.

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

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

В заполненной таблице обводят прямоугольными контурами все единицы и затем записывают минимизированную функцию в виде суммы логических произведений, описыва£бщих эти контуры. При проведении контуров придерживаются следующих правил: контур должен быть прямоугольным; внутри контура должны быть только клетки, заполненные единицами; количество клеток, находящихся внутри контура, должно быть целой степенью числа 2, т. е. может быть равно 1, 2, 4, 6, 8, 16; одни и те же клетки, заполненные единицами, могут входить в несколько контуров; при проведении контуров самая нижняя и самая верхняя строки таблицы считаются соседними, то же - для самого левого и самого правого столбцов; количество контуров должно быть как можно меньшим, а сами контуры как можно большими. • Рассмотрим минимизацию с помощью диаграмм Вейча на примерах.

Пример 1. Минимизировать функцию

F = ab + ab+ab. Приводим функцию к ДНФ, пользуясь правилами де Моргана:

F = ab-\-ab-\-ab = abab-{-ab=

= {a + b)(a+b) + ab = ab + ab + ab. (1)

Табл. 1, а показывает диаграмму Вейча для функции двух переменных. В клетки таблицы вписаны соответствущие им конъюнкции. Заполняем таблицу для данной функции (табл. 1, б). В соответствии с выражением (1) минимизируемая функция равна единице, если равно единице одно из следующих произведений: аЬ, аЬ, аЬ. Поэтому при заполнении таблицы вписываем 1 в клетки, соответствующие этим произведениям, а в четвертую клетку, соответствующую произведению" аб, вписываем 0. Затем проводим два контура, охватывающие единицы так, как это показано в табл. 1, б.

Для того чтобы найти логическое выражение (простую конъюнкцию), которое описывает в диаграмме Вейча контур, охватывающий единицы, можно вначале выяснить, от каких переменных не зависит данный контур. Так, если в табл. 1, б вертикальный контур охватывает строки а к а, то, следовательно, в его обозначение переменная а не войдет. Точно так же

горизонтальный контур не зависит от переменной Ь. Суответственно горизонтальный контур описывается выражением а (так жв,-как и вторая строка

таблицы), а обозначение вертикального контура b совпадает с обозначением вторичного столбца.

Таблица 1 б) J, i

Таким образом минимизированное выражение исходной функции будет [ующим: F=a-\-b.

Пример 2. Минимизировать функцию

" " " (2)

F = {а-\-Ъ + с){а+ Ь + с) -\-аЬс + be. Приводим функцию к ДНФ:

F = a-\-b-\-c+a-\-b-\-c-\-abc-\-bc =

= аЪс + аб с + аЬс -f Ъс.

Табл. 2, а показывает диаграмму Вейча для функции трех переменных. При заполнении табл. 2, б в данном случае следует обратить внимание на то, что наличие члена из двух букв (например, Ьс) в ДНФ исходной функции

о) Ъс Ъс Ы Ъс а

Таблица 2 Ъс Ьс Ъс

ведет к написанию двух единиц в таблице (соответственно в клетках аЬс и аЬс). При проведении контуров, охватывающих единицы, следует помнить, что первый и четвертый столбцы считаются соседними - диаграмму можно представить себе как бы свернутой в виде цилиндра. Проведя контуры так, как показано в табл. 2, б, получим минимизированное выражение для функции (2):

F = а6 + с. Пример 3. Минимизировать функцию

F = а-а + bcd-\- abed + abed + abed. Приводим функцию к ДНФ: f = с (а + с + d) (fc + с -f d) + abed + abed -f abed = abc +

+ a + abd -f acd + ad + abed + abed + abed =

= abc -\-ad+ abed + abed + abed.

Выполняя последнее преобразование, мы произвели упрощения на основании закона поглощения, при этом член ad поглотил все подчеркнутые произведения.

Табл. 3, а показывает незаполненную диаграмму Вейча для логической функции четырех переменных. Первая и четвертая строки этой таблицы, равно как и первый и четвертый столбцы, считаются соседними (можно представить себе эту таблицу свернутой в виде тора).

Таблица 3

В заполненной для функции (3) табл. 3, б все единицы можно охватить четырьмя контурами. Выписав обозначения этих контуров, получим минимизированную функцию

F-bd-\- abed + ad -f абс.

Рассмотренные примеры проиллюстрировали простоту и наглядность процесса минимизации с помощью диаграмм Вейча. Некоторые затруднения, правда, могут возникнуть при приведении фикции к ДНФ в том случае, когда исходное выражение функции содержит инверсию суммы достаточно большого количества простых конъюнкций. При раскрытии такой инверсии по правилу де Моргана необходимо производить громоздкое перемножение нескольких скобок (с подобным случаем мы встретились в примере 3).

Для таких случаев, когда исходное выражение минимизируемой функции содержит инверсию суммы конъюнкций, можно рекомендовать другой способ заполнения диаграмм Вейча. При этом учитывается то, что если одна из конъюнкций в сумме, находящейся под знаком инверсии, равна 1, то вся сумма после инвертирования будет равна 0. Соответственно, если ни одна из конъюнкций в сумме не равна , то инвертированная сумма равна 1. Поэтому при заполнении диаграммы Вейча, рассматривая инверсию суммы, необходимо вписать единицы в те клетки таблицы, которые соответствуют простым конъюнкциям, не содержащимся в этой сумме.

Рассмотрим подобный случай на примере.

Пример 4. Минимизировать функцию

F = abed -f abed + abed + abc d-\- be + acd + abc d -j-

-\-abc + abcd. (4)

Заполняем табл. 4, a для функции, входящей в выражение (4) под зна--ком инверсии. В клетки, соответствующие конъюнкциям, находящимся под знаком инверсии, вписываем нули, а в оставшиеся свободными клетки - единицы.

После этого заполняем табл. 4, б для конъюнкций, входящих в выражение (4) не под знаком инверсии. Далее составляем итоговую табл. 4, в, в клетки которой переносим единицы как из табл. 4, а, так и из табл. 4, б. Оставшиеся свободными клетки заполняем нулями. Проводим контуры.