Навигация
Найти МДНФ различными методами
26949
знаков
22
таблицы
2
изображения
1.3 Найти МДНФ различными методами.
1.3.1 Метод эквивалентных преобразований.
В основе метода минимизации булевых функций эквивалентными преобразованиями лежит последовательное использование законов булевой алгебры. Метод эквивалентных преобразований целесообразно использовать лишь для простых функций и для количества логических переменных не более 4-х. При большем числе переменных и сложной функции вероятность ошибок при преобразовании возрастает.
Проведем прямое алгебраическое преобразование, используя закон неполного склеивания.
F(X1X2X3X4) = X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V
V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 =
= (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4 V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4 V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4)V(X1X2X3X4 V X1X2X3X4) V
V (X1X2X3X4 V X1X2X3X4) V (X1X2X3X4 V X1X2X3X4) =
= X1X2X4 V X1X2X3 V X1X3X4 V X2X3X4 V X1X3X4 V X2X3X4 V X1X2X4 V
V X1X2X3V X2X3X4 V X1X2X3 V X1X3X4 =
= (X1X2X3 V X1X2X3 V X1X3X4 V X1X3X4) V X1X2X4 V
V (X1X2X3 V X1X2X3 V X2X3X4 V X2X3X4) V X1X2X4 V
V (X1X3X4 V X1X3X4 V X2X3X4 V X2X3X4) =
= X1X3 V X2X3 V X3X4 V X1X2X4 V X1X2X4.
Дальнейшее преобразование невозможно. Полученную функцию можно немного упростить с помощью вынесения за скобки общих переменных.
1.3.2 Метод Квайна
При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде ДСНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант (Q-матрица).
| ДСНФ, ранг 4 | |||
| 1 2 3 4 5 6 7 8 9 | 0000 0010 0011 0101 0110 0111 1010 1011 1111 | ||
| Наборы 3-го ранга | |||
| 1-2 2-3 2-5 2-7 3-6 3-8 4-6 5-6 6-9 7-8 8-9 | 00*0 001* 0*10 *010 0*11 *011 01*1 011* *111 101* 1*11 | 1 2 3 4 5 6 7 8 9 10 11 | |
| Наборы 2-го ранга | |||
| 2-8 2-10 3-5 4-6 5-11 6-9 | 0*1* *01* 0*1* *01* **11 **11 | ||
Как видно из таблиц, при получении матрицы второго ранга первый и седьмой наборы третьего ранга не склеились ни с какими другими наборами. Их необходимо занести в конечную матрицу простых импликант. В матрице же второго ранга мы видим, что некоторые наборы одинаковые. Их необходимо вычеркнуть, так как дизъюнкция одинаковых наборов равна этой же дизъюнкции (это следует из закона повторения)
| Простые импликанты | |
| 1 2 3 4 5 | 0*1* *01* **11 00*0 01*1 |
Перенеся все выделенные строки в конечный массив, получим матрицу СДНФ. Алгебраическая запись СДНФ будет выглядеть следующим образом:
F(X1X2X3X4) = X1X3 V X2X3 V X3X4 V X1X2X4 V X1X2X4.
Эта же функция в нашем случае является и минимальной ДНФ.
Похожие работы
осхемы К155ЛА3 (4 логических элемента 2И-НЕ). Принцип работы ЛЭ И-НЕ ТТЛ Основная особенность микросхем ТТЛ состоит в том, что во входной цепи используется специфический интегральный прибор – многоэмиттерный транзистор (МЭТ), имеющий несколько эмиттеров, объединенных общей базой. Эмиттеры расположены так, что непосредственное взаимодействие между ними через участок базы отсутствует. Поэтому МЭТ ...
... чертеж или схема выполняются в САПР AutoCAD, поэтому наиболее часто используемой вспомогательной программой является конвертор из формата P-CAD в AutoCAD. 1. Основы математического аппарата анализа и синтеза комбинационных логических устройств Все устройства, оперирующие с двоичной информацией, подразделяются на два класса: - комбинационные (дискретные автоматы без памяти). - ...
9534
1
6
... на рисунке 1 для двух переменных а), трех переменных б) и четырех переменных в). Принципиального значения не имеет, каким вариантом изображения карты Карно пользоваться. В дальнейшем для минимизации используются карты Карно, представленные на рисунке 1 и студентам рекомендуется тоже их использовать. В картах Карно, показанных на рисунке 1, области, где переменные находятся без инверсий (X i), ...
... И-НЕ. Для выполнения этой операции (при имеющемся в окошке булевом выражении) следует “нажать” стрелкой кнопку: 3. Математические модели и эквивалентные схемы в программе логического проектирования Любой реальный логический элемент(ЛЭ) не мгновенно реагирует на изменения входных сигналов, поэтому имеется некоторая паразитная задержка между моментом времени, в который на его входы поступают новые ...
0 комментариев