Лабораторная работа №8. Лабораторная работа № 8. Лабораторная работа Вариант Тема работы Минимизация логических функций методом Квайна МакКласки
 Скачать 87.5 Kb.
|
|
Лабораторная работа № 8. Вариант 6. Тема работы: Минимизация логических функций методом Квайна – Мак-Класки Цель работы: Изучить метод Квайна – Мак-Класки минимизации логических функций. Задание на работу: Минимизировать методом Квайна – Мак - Класки логическую функцию (таблица 1).
Ход работы Выпишем двоичные векторы области единиц логической функции и найдем их индексы
1-ый этап – нахождение всех простых импликант логической функции. Разделим двоичные векторы на секции в соответствии с их индексами, получим таблицу:
Склеиваем между собой ближайшие векторы соседних секций пока это возможно. Проводим попарное сравнение между соседними по номеру группами кубов. В результате сравнения кубов получим:
2-ой этап – минимизация полученного множества простых импликант логической функции. Строим таблицу меток, в нее вписываем исходные и первичные импликанты в виде двоичных кодов. Таблица5- Таблица покрытий
В данном случае импликанты из второй, третьей, четвертой, пятой и шестой строк обеспечивают минимальное покрытие. Таблица 6- Выбор минимального покрытия
Таблица 7- Все области покрыты простыми импликатами
Все векторы области единиц покрыты простыми импликантами (в каждом столбце хотя бы один «х»). Получаем оптимальное покрытие: 0х001, 001х1, 011х0, х1110,10000 Таким образом, f(a,b,c,d,e) = (¬a¬c¬de)V(¬a¬bce)V(¬abc¬e)V(bcd¬e)V(a¬b¬ c¬d¬e) Выводы: В данной работе изучен метод Квайна – Мак-Класки минимизации логических функций. Используя алгоритм метода Квайна – Мак-Класки, выполнено практическое задание по рассматриваемой теме. Контрольные вопросы: В каком виде должна быть представлена функция для минимизации по методу Квайна–Мак-Класки? Как в методе Квайна–Мак-Класки называются непоглощенные n-кубы? Какова особенность минимизации n-кубов в методе Квайна – Мак-Класки? Для чего в методе Квайна–Мак-Класки строится таблица покрытий? По какому принципу производится выбор подмножества простых импликант? В какой форме представляется результат минимизации по методу Квайна–Мак-Класки? Ответы на вопросы: Функция должна быть представлена в канонической форме СДНФ (Совершенная дизъюнктивная нормальная форма). В методе Квайна–Мак-Класки непоглощенные n-кубы называются простые импликаты. Особенность метода Квайна состоит в том, что функция задается в форме СДНФ. При упрощении в данном методе используются операции поглощения и склеивания. Для выполнения операции склеивания в выражении функции выявляются пары членов, различающиеся лишь тем, что один из аргументов в одном из членов представлен без инверсии, а в другом – с инверсией. Затем проводится склеивание таких пар членов. В результаты склеивания вводятся в выражение функции в качестве дополнительных членов. Далее выполняется операция поглощения. При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате операции склеивания. Операции склеивания и поглощения выполняются последовательно до тех пор, пока это возможно. Таблицу покрытия используют для нахождения всех тупиковых ДНФ (им соответствует неприводимое покрытие подмножества ) заданной функции, из которых путем анализа их сложности можно выбрать минимальную ДНФ (дизъюнктивно нормальная форма). По таблице покрытий Квайна — Мак-Класки строится конъюнкция дизъюнкций, каждая из которых есть совокупность тех импликант, которые в данном столбце имеют метки (число дизъюнкций в конъюнкции равно числу столбцов таблицы покрытий). После этого происходит раскрытие скобок с учетом свойства поглощения. Каждая конъюнкция в полученном после этого выражении соответствует некотором тупиковой ДНФ рассматриваемой функции. Выбор подмножества импликант с минимальным числом аргументов осуществляется следующим образом. Для выбора такого подмножества прежде всего найдем колонки имеющие единственную метку (х). Соответствующая данной метке импликанта должна обязательно входить в логическую функцию. После этого находим импликанты, перекрывающие остальные колонки. В наиболее компактном её представлении в виде нормальной минимальной дизъюнктивной формы (МДНФ) Литература Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. – 3-е изд., стереотип. – М.: Издательство МГТУ им. Н.Э. Баумана, 2004. – 744 с. Савельев А.Я. Основы информатики. – М.: Издательство МГТУ имени Н.Э.Баумана, 2001. – 328 с. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||