Одним из инженерных методов минимизации логических функций, с помощью которого определяется одна из тупиковых ДНФ, принимаемая за частную минимальную ДНФ, является метод использования решетки соседних чисел и обобщенных кодов (метод Л. Т. Мавренкова).
Рассмотрим построение и возможности решетки соседних чисел и обобщенных кодов (ОК).
Известно, что логическая функция может быть задана в символической форме – в виде совокупности рабочих и запрещенных весовых состояний, представляющих десятичный (восьмеричный) эквивалент двоичных чисел, описывающих наборы переменных, на которых функция равна соответственно единице и нулю.
Любую элементарную конъюнкцию (член СДНФ) можно записать двоичным числом при выбранной базе.
Таким образом, логическая функция, представленная в СДНФ, может быть записана в виде логической суммы двоичных чисел. Например:
Запишем каждый член СДНФ в виде двоичного числа. Для этого выберем предварительно базу a, b, c, d:
Если в члене СДНФ данная переменная без инверсии, то в этом разряде ставим 1, если с инверсией – ставим 0.
|
|
Так,
Если двоичные числа перевести в десятичные, то получим рабочие весовые состояния:
В каждом разряде двоичного числа может находится либо 1, либо 0. Если двоичные числа отличаются друг от друга в одном разряде, то такие числа называются соседними. Например, 14 → 1110 и 12 → 1100 отличаются во 2-ом разряде (21), а числа 12 → 1100 и 13 → 1101 отличаются в 1-м разряде – они попарно соседние. Но 14 → 1110 и 13 → 1101 не являются соседними, так как отличаются в двух разрядах: в 1-м и во 2-м.
Соседние числа обладают следующими свойствами:
1. Количество чисел, соседних с данным двоичным числом, равно количеству его разрядов.
Чтобы получить все числа, соседние с данным числом, необходимо, идя от старшего разряда к младшему (или наоборот), поразрядно менять 0 на 1, а 1 на 0. Например, имеем число 10 → 1010. Соседними с ним являются 0010, 1110, 1000, 1011. Отобразим это в виде диаграммы, на которой соседние числа обозначим в десятичной системе счисления в кружочках (Рисунок 3.13).
2. Логическая сумма двух соседних чисел приводит к
исключению одной переменной (одного разряда). Например, сумму можно записать (при базе abcd) как , где вместо исключенного разряда ставится «–» (тире).
Заметим, что исключается именно тот разряд, в котором соседние двоичные числа отличаются. Вместо него и ставится тире.
|
|
|
Упрощенно говоря, обобщенный код – это выражение, состоящее из единиц, нулей и тире.
Обобщенный код соответствует члену ДНФ. Пусть, например, при базе abcd имеем член ДНФ Очевидно, с помощью обобщенного кода его можно записать как 10 – 1 (переменная c отсутствует).
Теперь понятно 2-е свойство: логическая сумма двух соседних чисел равна обобщенному коду, содержащему тире в том разряде, в котором числа не совпадают, т.е. поразрядно: «–»; «–».
Двоичные числа являются частным случаем обобщенного кода, в них отсутствуют тире. Двоичное число соответствует члену СДНФ.
Два обобщенных кода, отличающиеся только в одном разряде, называются соседними. Отметим, что они должны содержать тире в одних и тех же разрядах.
Свойства обобщенных кодов (ОК):
1. Количество обобщенных кодов, соседних данному, равно числу нулей и единиц в данном обобщенном коде.
Соседние ОК определяются так же, как и соседние числа. Например, для ОК 11 – 0 соседними являются 01 – 0, 10 – 0, 11 – 1.
2. Логическая сумма двух соседних ОК равна ОК, содержащему тире в том разряде, в котором записанные коды были противоположны, и совпадающему с ними в остальных разрядах. Например:
3. Обобщенный код, имеющий тире в t разрядах, равен логической сумме двоичных чисел, содержащих все комбинации 0 и 1 в этих разрядах и совпадающих с обобщенным кодом в остальных разрядах. Например,,т.е. вместо каждого тире делаем перебор 0и 1.
Эти свойства обобщенных кодов позволили создать решетку соседних чисел и обобщенных кодов – решетку Л. Т. Мавренкова.
Рассмотрим решетку (Рисунок 3.14) для четырех двоичных переменных, которая употребляется наиболее часто. Числа решетки, записанные в десятичной системе счисления, расположены на плоскости таким образом, что каждое число с четырех сторон окружено соседними. Расположение соседних чисел легко получаем из карты Карно на четыре переменных. Всего чисел – 24 = 16.
Числа решетки объединяются различными фигурами: число, линия, квадрат, полоса. Каждое число – это обобщенный код без тире – двоичное число (4-разрядное).
Каждые два соседних числа объединены линией связи, которая соответствует обобщенному коду, содержащему одно тире. Например:
Логическая сумма любых четырех попарно соседних чисел, образующих квадрат или линию, которая при замыкании также образует квадрат, соответствует обобщенному коду с двумя тире. Например, квадрат
линия
Логическая сумма восьми попарно соседних чисел, образующих на решетке полосу, соответствует обобщенному коде, содержащему 3 тире. Например:
Все фигуры (числа, линии связи, квадраты, полосы) указаны на решетке, на которой также проставлены и их обобщенные коды. Каждый обобщенный код соответствует члену ДНФ. Все эти коды очень легко выводятся при логическом сложении соседних чисел и соседних обобщенных кодов в результате последовательного выполнения операции склеивания.
Обобщенный код, соответствующий логической сумме всех 16 четырехразрядных двоичных чисел, содержит все четыре тире: Нетрудно заметить, что решетка соседних чисел и обобщенных кодов имеет очень большую аналогию с картой Карно.
Так, вершины решетки соответствуют клеткам карты Карно, а фигуры решетки соответствуют правильным контурам карты, они включают в себя 2 n вершин (n = 0, 1, 2, 3, 4).
Аналогично карте Карно простой импликанте логической функции соответствует максимальная фигура решетки, охватывающая вершины, соответствующие рабочим и условным весовым состояниям (числам). Максимальной фигуре соответствует обобщенный код, содержащий максимальное число тире.
Преимуществом решетки соседних чисел по сравнению с картой Карно является то, что для каждой фигуры (правильного контура) на ней указан обобщенный код, который эквивалентен импликанте, покрывающей конституенты, соответствующие вершинам данной фигуры.
|
|
Решетка соседних чисел и обобщенных кодов может быть выполнена и в восьмеричной системе счисления. Наиболее удобная в обращении решетка до четырех переменных; решетка для пяти-шести переменных уже теряет наглядность и удобство работы.
Каждая вершина решетки соответствует члену СДНФ функции, а обобщенный код фигуры – члену ДНФ.
С помощью решетки можно легко переходить от ДНФ к СДНФ логической функции.
Пусть дана ДНФ
Выберем базу a, b, c, d. Запишем ДНФ в обобщенных кодах:
Найдем полученные обобщенные коды в решетке соседних чисел и запишем вместо них рабочие числа, которые они охватывают:
Это и есть символическая форма записи.
Итак, рабочие числа функции:
Отсюда переходим к двоичным числам, а от них – к СДНФ:
Из решетки можно сразу выписать двоичные числа вместо десятичных.