85997 (Методы минимизации логических функций)
Описание файла
Документ из архива "Методы минимизации логических функций", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "математика" в общих файлах.
Онлайн просмотр документа "85997"
Текст из документа "85997"
Содержание
Задание 1.Определить МДНФ логической функции устройства.
-
Составить таблицу соответствия (истинности) функции.
-
Перевести логическую функцию от табличной к аналитической форме в виде ДСНФ
-
Найти МДНФ различными методами.
-
прямым (алгебраическим) преобразованием;
-
методом Квайна;
-
усовершенствованным методом Квайна (Квайна-Маккласки);
-
методом карт Карно;
-
методом неопределенных коэффициентов;
-
Задание 2. Составить алгоритм метода минимизации
2.1 Составить содержательный (словесный) алгоритм минимизации функции, разработать граф-схему алгоритма, разработать логическую схему алгоритма в нотации Ляпунова для метода Квайна.
2.2 Составить содержательный (словесный) алгоритм минимизации функции, разработать граф-схему алгоритма, разработать логическую схему алгоритма в нотации Ляпунова для метода минимального покрытия Петрика.
2.3 Разработать рабочие программы по алгоритмам.
Задание 3. Синтез схемы логического устройства.
3.1 Выполнить синтез схемы по ДСНФ и МДНФ в базисе Буля с использованием двухвходовых логических элементов и интегральных микросхем серии 155.
3.2 Функцию МДНФ в базисе Буля полученную в первом задании представить в базисах Шеффера и Пирса.
-
Обосновать выбор базиса по формулам МДНФ.
3.4 Реализовать в выбранном базисе логическую схему.
Задание 1.
1.1 Составить таблицу соответствия (истинности) функции.
Составим таблицу истинности для заданной функции F(X1,X2,X3,X4).
| № | X1 | X2 | X3 | X4 | F(X1, X2, X3, X4) |
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 | 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 |
Матрицу ДСНФ получают путем удаления тех строк, где функция равна нулю. Для нашего случая получим:
| № | X1 | X2 | X3 | X4 |
| 0 2 3 5 6 7 10 11 15 | 0 0 0 0 0 0 1 1 1 | 0 0 0 1 1 1 0 0 1 | 0 1 1 0 1 1 1 1 1 | 0 0 1 1 0 1 0 1 1 |
1.2 Перевести логическую функцию от табличной к аналитической форме в виде ДСНФ.
Переведем логическую функцию от табличной к аналитической форме в виде ДСНФ.
F(X1X2X3X4) = X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4
V X1X2X3X4 V X1X2X3X4 V X1X2X3X4 V X1X2X3X4.
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.
Эта же функция в нашем случае является и минимальной ДНФ.
-
Метод Квайна-Маккласки
В основу данного метода также положен закон неполного склеивания. Только в отличие от метода Квайна здесь производится гораздо меньше сравнений, так как, разбив исходную матрицу на несколько групп, мы сравниваем только те наборы, которые отличаются индексом на 1 или местоположением меток.
Распределим импликанты ДСНФ по индексам.
| ДСНФ | Индекс i | |
| 1 2 3 4 5 6 7 8 9 | 0000 0010 0011 0101 0110 0111 1010 1011 1111 | 0 1 2 2 2 3 2 3 4 |
