Метод минимизации ФАЛ по Квайну
Определение: Тупиковой ДНФ называется дизъюнкция простых импликант, ни одну из которых из выражения функции исключить нельзя.
Этот метод минимизации ФАЛ заключается в следующем:
Находят Сок. ДНФ. Находят все возможные тупиковые ДНФ. Из найденных ТДНФ выбирают минимальную.
Иногда в Сок. ДНФ содержатся лишние импликанты. Как уже видели в сокращенной ДНФ:
f(Х1, Х2, Х3)= Х1Х3
импликанта Х2Х3 может быть исключена. Ни одной операции склеивания и поглощения к этой форме применить нельзя, т.к. это Сок. ДНФ, т.е. дизъюнкция простых импликант. Можно применить операцию развертывания по Х1:
f= Х1Х3
Т.к. Х1Х3 покрывает Х1Х2Х3
и Х1Х2 покрывает Х1Х2Х3, то f= Х1Х3
ТЕОРЕМА:
Всякая минимальная ДНФ является тупиковой. Обратное утверждение не справедливо. Доказательство очевидно.
Из этой теоремы вытекает важное следствие: Для того чтобы найти минимальную ДНФ, нужно найти все тупиковые формы и среди них взять минимальную.
Существует несколько различных способов отыскания тупиковых форм.
Минимизация ФАЛ и ограничения при ее рассмотрении
Покажем на примере, что СДНФ не является экономной формой записи:
f(Х1, Х2)= Х1Х2
на основании полного склеивания по Х2 мы видим, что запись стала короче, т.к. содержит меньшее число связок и букв. Физически это означает, что устройство, которое реализует эквивалентную, но более простую функцию, будет иметь в своем составе меньшее количество оборудования, а следовательно, будет работать надежнее.
Итак, задача синтеза устройства должна быть дополнена задачей уменьшения оборудования в нем. С математической точки зрения это задача построения минимальной ФАЛ.
Под минимальной ФАЛ понимается такая форма, в которой содержится меньшее количество букв и членов, чем в ее исходной форме.
Речь идет именно о буквах, а не о переменных, так в функции:
f(Х1, Х2)= Х1Х2
Видно, что если какое-либо элементарное произведение входит в функцию, то при добавлении к нему новых сомножителей, полученное произведение так же будет входить в функцию.
Пример: если Х1Х2 входит в функцию от любого числа аргументов (>2), то в нее войдет, например, произведение Х1Х2Х3.
Это можно показать так:
f(Х1, Х2)= Х1Х2
Дадим ряд определений:
Произведение одной или нескольких неповторяющихся переменных, взятых с отрицанием или без него, называют элементарным.
Например, Х1 Х2 Х3 – элементарное произведение, т.к. в него входят различные буквы Х1 Х2 Х3.
Дизъюнкция элементарных произведений – ДНФ. ДНФ является минимальной, если в ней минимальное число букв и членов.
Конституентой единицы функции называют функцию, принимающую значение единицы только на одном наборе аргументов.
Обычно конституенты единицы выражают через произведение всех переменных, от которых зависит функция. СДНФ – дизъюнкция конституент единицы.
Ранг произведения – число букв, входящих в него. Собственной частью называется произведение, полученное путем отбрасывания одной или нескольких переменных.
Понятие функциональной полноты ФАЛ
Было отмечено, что техническая (физическая) задача синтеза произвольного устройства сводится к математической задаче построения произвольной ФАЛ.
Естественно возникает вопрос, какое количество связок необходимо, чтобы построить произвольную ФАЛ. Ответ на этот вопрос не однозначен. Мы видим, что, например, с помощью только функции f0 (константа 0), f15 (константа 1) произвольную ФАЛ построить нельзя. Нельзя ее построить и с помощью только инвертора. Существуют и другие базисы:
Технически синтез устройства означает, что нужно иметь некоторый набор элементов, ФАЛ которых образуют базис, чтобы можно было построить реальное устройство.
Однако, как было отмечено, задача синтеза ФАЛ – идеальная модель. В действительности, для построения реальных устройств пользуются несколько более расширенным набором элементов - усиления и коррекции сигналов.
Понятие покрытия
Определение. Если на каком-либо наборе f принимает значение а1, а
При минимизации ФАЛ стремятся получить форму, в которой будет меньше букв, чем в исходной. По отношению к ДНФ эта форма называется сокращенной (Сок. ДНФ).
Смысл построения Сок. ДНФ заключается в том, что в нее входят такие элементарные произведения, которые своими единицами покрывают не одну единицу исходной функции, а несколько.
Так, каждое элементарное произведение, входящее в СДНФ, покрывает только одну единицу функции.
Например:
f(Х1, Х2)= Х1Х2
1 1 1
Эти единицы функции могут быть накрыты более короткими произведениями: Х1 накрывает две единицы: Х1Х2 и Х1Х2 и Х2
, которое накрывает также две единицы: Х1Х2 и Х1Х2
, т.е.
f(Х1, Х2)= Х1
