Методы минимизации логических функций (стр. 3 из 5)
5. Произвести раскрытие скобок в полученном выражении с учетом законов поглощения.
6. Выбрать одну из полученных конъюнкций и представить ее как совокупность соответсвующих простых импликант.
7. Если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.
8. Формировать МДНФ.
9. Вывод полученной матрицы.
10. Конец.
Логическая схема алгоритма в нотации Ляпунова.
1 1
VHV1V2V3V4¯V5Z1V6V7VK
VH – начало.
V1 – ввести матрицу ДСНФ исходной функции и простые импликанты, полученные в методе Квайна.
V2 – составить таблицу меток.
V3 – по таблице меток построить конъюнкцию дизъюнкций, каждая из которых есть совокупность тех импликант, которые в данном столбце имеют метки.
V4 – произвести раскрытие скобок в полученном выражении с учетом законов поглощения.
V5 – выбрать одну из полученных конъюнкций и представить ее как совокупность соответсвующих простых импликант.
Z1 – если выбранная комбинация не является минимальной, то перейти к пункту 6, в противном случае перейти к пункту 8.
V6 – формировать МДНФ.
V7 – вывод полученной матрицы.
VK – конец.
Граф-схема алгоритма.
 | ||
 | ||
Описание машинных процедур
Procedure FormMatrix;
Данная процедура формирует матрицу меток путем попарного анализа дизъюнктов из ДСНФ и матрицы простых импликант. Если стравнение прошло успешно, то соответствующему элементу матрицы меток присваивается значение 1, в противном случае – значение 0.
Function Pokritie(var S: string16): boolean;
Данная функция проверяет, является ли данная комбинация простых импликант полной, то есть накрывает ли она все дизъюнкты матрицы ДСНФ. Это сравнение происходит следующим образом: вводится новый массив – массив соостветсвия столбцам. Каждому элементу нового массива сначала присваивается значение 0. Далее, пробегая все заданные строки матрицы,определяем в каких столбцах стоит 1 и в новом массиве ставим на соответсвующее место 1. Таким образом, если в векторе есть нули, значит данная комбинация дизъюнктов не накрывает полностью все столбцы матрицы. В этом случае функция возвращает значние False, в противном случае функция возвращает значение True.
Задание 3. Синтез схемы логического устройства.
1. Представление МДНФ в базисе Буля. В базисе Буля используется 3 логические схемы: НЕ, ИЛИ, И. Вот их графическое изображение:
 | |||
 |  |  | |
НЕ: X = X*X ИЛИ: X1VX2 = X1*X1 * X2*X2
| | ||
 | | |
И: X1*X2 = X1*X2 * X1*X2
Минимальная ДНФ выглядит так:
f(X1, X2, X3, X4) = X3X4VX2X3VX1X3VX1X2X4VX1X2X4;Переведем ее в базис Шеффера с помощью указанных выше формул.
 |
 |
 |
ОбозначимA = X3X4VX2X3VX1X3 = X3·( X4VX2VX1) = X3·X4·X4·X2·X1=  | |
 | |
= X3·X4·X4·X2·X1·X2·X1.  | |
 | |
 |  |
B = X1X2X4VX1X2X4= X1·(X2·X4VX2·X4) = X1·X1·X2·X2·X4·X4·X2·X4.  |
Окончательно получим Y = A · B .Отсюда видно, что для реализации минимальной ДНФ в базисе Шеффера требуется 12 элементов И-НЕ. Соответственно для аппаратной реализации нам потребуется 3 интегральные микросхемы К155ЛА3.
3. Представление МДНФ в базисе Пирса. Для того, чтобы реализовать минимальную ДНФ в базисе Пирса, необходимо как и в предыдущем пункте перевести МДНФ из базиса Буля в базис Пирса, в котором используется только один элемент ИЛИ-НЕ.