Минимизация частично заданных ФАЛ картами Карно
Использование карт Карно для минимизации частично заданных ФАЛ является наиболее удобным и простым.
При составлении карт Карно для неполностью заданной функции в клетках, соответствующих координатам неиспользованных входных наборов проставляются звездочки (прочерки, тильды). Клетки со звездочками (прочерками, тильдами) при необходимости включаются в контуры как вместе с «1» (при получении формулы на базе ДНФ), так и вместе с «0» (при получении формулы на базе КНФ). При этом выражение функции после минимизации оказывается более простым. Рассмотрим, например, карту Карно для четырех переменных, представленную на рисунке 4.7. В том случае, если при ее минимизации не учитывать безразличные состояния, то будет получена функция, образованная тремя контурами (на рисунке показаны сплошными линиями) 
.
Эта функция значительно упростится, если использовать безразличные состояния при выделении контуров. При этом образуется всего лишь один контур (на рисунке показан штриховой линией). Результирующая функция 
.
4.3.2 Минимизация частично заданных ФАЛ методами Квайна
и Квайна–Мак-Класки
При упрощении неполностью заданных ФАЛ методами Квайна и Квайна – Мак-Класки необходимо выполнить следующие этапы.
1 Из частично заданной функции f получить полностью заданную функцию f0 посредством замены на нуль безразличных состояний функции f.
2 Из той же частично заданной функции f получить новую полностью заданную функцию f1 путем замены на единицу безразличных состояний функции f.
3 Упростить функцию f1 обычным путем (как это описано в пп. 4.2.3 или 4.2.4 данного пособия).
4 Составить таблицу перекрытий между элементарными конъюнкциями функции f0 и упрощенной функции f1 и по этой таблице выбрать окончательную минимальную форму частично заданной функции f .
Рассмотрим процесс минимизации частично заданной функции, заданной таблицей 4.6, методом Квайна.
Реализуем описанные этапы минимизации. Получим из неполностью заданной функции f две полностью заданные f0 и f1 и запишем их в таблицу 4.7 наряду с функцией f.
Упростим полностью заданную функцию f1. Для этого запишем СДНФ этой функции 
.
Выполним склеивание конъюнкций полученной СДНФ.
.
В результате склеивания получены три минтерма первого ранга 
, 
и 
. Все эти минтермы образуют ядро функции f1, и поэтому можно сразу записать результат минимизации 
.
Далее строим таблицу 4.8, в которой отражается результат перекрытия между конъюнкциями упрощенной функции 
и функции f0.
Анализируя варианты перекрытий минтермами функции 
импликант функции f0, можно получить три варианта упрощения неполностью заданной функции f. Первый из них – это 
, второй – 
и третий – 
. Наиболее оптимальным следует считать третий вариант, так как в нем отсутствует инверсия переменной. Таким образом, запишем результат минимизации 
.
В таблицах перекрытий между функциями возможны также случаи, когда один или несколько минтермов функции 
не перекрывает ни одной из импликант функции f0. В таком случае эти минтермы не войдут в конечную минимальную формулу.
Дата добавления: 2019-02-12; просмотров: 365; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!