Минимизация частично заданных ФАЛ картами Карно

Минимизация частично заданных ФАЛ

Если ФАЛ однозначно определена на всех возможных наборах значений ее аргументов, то она называется полностью заданной (полностью определенной) [1]. Если же на некоторых наборах значение функции является безразличным и однозначно не определено, то такая функция называется неполностью (частично) определенной (заданной).

Для обозначения «безразличного» значения функции используются различные символы. При табличном, координатном и графическом способах задания ФАЛ в местах неопределенных значений проставляются знаки: «~» (тильда), «*» (звездочка) или «–» (тире), а при аналитическом способе используется знак равнозначности «».

Минимизация частично заданных функций имеет некоторые особенности, с которыми мы далее познакомимся. Упрощать неполностью заданные ФАЛ можно с использованием карт Карно, методов Квайна, Квайна–Мак-Класки, существенных переменных и др.

Использование карт Карно для минимизации частично заданных ФАЛ является наиболее удобным и простым.

При составлении карт Карно для неполностью заданной функции в клетках, соответствующих координатам неиспользованных входных наборов проставляются звездочки (прочерки, тильды). Клетки со звездочками (прочерками, тильдами) при необходимости включаются в контуры как вместе с «1» (при получении формулы на базе ДНФ), так и вместе с «0» (при получении формулы на базе КНФ). При этом выражение функции после минимизации оказывается более простым. Рассмотрим, например, карту Карно для четырех переменных, представленную на рисунке 4.7. В том случае, если при ее минимизации не учитывать безразличные состояния, то будет получена функция, образованная тремя контурами (на рисунке показаны сплошными линиями) .

Эта функция значительно упростится, если использовать безразличные состояния при выделении контуров. При этом образуется всего лишь один контур (на рисунке показан штриховой линией). Результирующая функция .

4.3.2 Минимизация частично заданных ФАЛ методами Квайна
и Квайна–Мак-Класки

При упрощении неполностью заданных ФАЛ методами Квайна и Квайна – Мак-Класки необходимо выполнить следующие этапы.

1 Из частично заданной функции f получить полностью заданную функцию f ₀ посредством замены на нуль безразличных состояний функции f.

2 Из той же частично заданной функции f получить новую полностью заданную функцию f ₁ путем замены на единицу безразличных состояний функции f.

3 Упростить функцию f ₁ обычным путем (как это описано в пп. 4.2.3 или 4.2.4 данного пособия).

4 Составить таблицу перекрытий между элементарными конъюнкциями функции f ₀ и упрощенной функции f ₁ и по этой таблице выбрать окончательную минимальную форму частично заданной функции f.

Рассмотрим процесс минимизации частично заданной функции, заданной таблицей 4.6, методом Квайна.

Реализуем описанные этапы минимизации. Получим из неполностью заданной функции f две полностью заданные f ₀ и f ₁ и запишем их в таблицу 4.7 наряду с функцией f.

Упростим полностью заданную функцию f ₁. Для этого запишем СДНФ этой функции .

Выполним склеивание конъюнкций полученной СДНФ.

.

В результате склеивания получены три минтерма первого ранга , и . Все эти минтермы образуют ядро функции f ₁, и поэтому можно сразу записать результат минимизации .

Далее строим таблицу 4.8, в которой отражается результат перекрытия между конъюнкциями упрощенной функции и функции f ₀.

Анализируя варианты перекрытий минтермами функции импликант функции f ₀, можно получить три варианта упрощения неполностью заданной функции f. Первый из них – это , второй – и третий – . Наиболее оптимальным следует считать третий вариант, так как в нем отсутствует инверсия переменной. Таким образом, запишем результат минимизации .

В таблицах перекрытий между функциями возможны также случаи, когда один или несколько минтермов функции не перекрывает ни одной из импликант функции f _0. В таком случае эти минтермы не войдут в конечную минимальную формулу.

Дата добавления: 2015-07-02