Совершенные дизъюнктивные и конъюнктивные нормальные формы ФАЛ

Понятие функциональной полноты ФАЛ

Было отмечено, что техническая (физическая) задача синтеза произвольного устройства сводится к математической задаче построения произвольной ФАЛ.

Естественно возникает вопрос, какое количество связок необходимо, чтобы построить произвольную ФАЛ. Ответ на этот вопрос не однозначен. Мы видим, что, например, с помощью только функции f_{0} (константа 0 ), f_{15} (константа 1 ) произвольную ФАЛ построить нельзя. Нельзя ее построить и с помощью только инвертора. Существуют и другие базисы: $$\wedge,$$ $$\oplus,$$ 1, |. Есть также одноэлементные базисы: f_{8} – стрелка Пирса, f_{14} – штрих Шеффера, И-НЕ, ИЛИ-НЕ.

Технически синтез устройства означает, что нужно иметь некоторый набор элементов, ФАЛ которых образуют базис, чтобы можно было построить реальное устройство.

Однако, как было отмечено, задача синтеза ФАЛ – идеальная модель. В действительности, для построения реальных устройств пользуются несколько более расширенным набором элементов - усиления и коррекции сигналов.

Минимизация ФАЛ и ограничения при ее рассмотрении

Покажем на примере, что СДНФ не является экономной формой записи:

$$f(Х_{1}, Х_{2})= Х_{1}Х_{2}\vee Х_{1}\overline Х_{2}\vee \overline Х_{1}\overline Х_{2} =Х_{1}\vee \overline Х_{1} \overline Х_{2}$$

на основании полного склеивания по Х_{2} мы видим, что запись стала короче, т.к. содержит меньшее число связок и букв. Физически это означает, что устройство, которое реализует эквивалентную, но более простую функцию, будет иметь в своем составе меньшее количество оборудования, а следовательно, будет работать надежнее.

Итак, задача синтеза устройства должна быть дополнена задачей уменьшения оборудования в нем. С математической точки зрения это задача построения минимальной ФАЛ.

Под минимальной ФАЛ понимается такая форма, в которой содержится меньшее количество букв и членов, чем в ее исходной форме.

Речь идет именно о буквах, а не о переменных, так в функции:

$$f(Х_{1}, Х_{2})= Х_{1}Х_{2}\vee Х_{1}\overline Х_{2}\vee \overline Х_{1}Х_{2}$$ имеется 6 букв и только 2 переменных.

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

Пример: если Х_{1}Х_{2} входит в функцию от любого числа аргументов ( >2 ), то в нее войдет, например, произведение Х_{1}Х_{2}Х_{3}.

Это можно показать так:

$$f(Х_{1}, Х_{2})= Х_{1}Х_{2}\vee \varphi (Х_{1}Х_{2})= Х_{1}Х_{2} (\overline Х_{3}\vee Х_{3})\vee \varphi (Х_{1}Х_{2})= Х_{1} Х_{2} Х_{3} \vee \overline Х_{1} Х_{2} Х_{3} \vee \varphi (Х_{1}Х_{2})=Х_{1} Х_{2} Х_{3} \vee \psi (Х_{1} Х_{2} Х_{3})$$

Дадим ряд определений:

Понятие покрытия

Определение. Если на каком-либо наборе f принимает значение а_{1}, а $$\phi$$ – значение а_{2}, то говорят, что f своим значением а_{1} покрывает значение а_{2} функции $$\phi.$$

При минимизации ФАЛ стремятся получить форму, в которой будет меньше букв, чем в исходной. По отношению к ДНФ эта форма называется сокращенной (Сок. ДНФ).

Смысл построения Сок. ДНФ заключается в том, что в нее входят такие элементарные произведения, которые своими единицами покрывают не одну единицу исходной функции, а несколько.

Так, каждое элементарное произведение, входящее в СДНФ, покрывает только одну единицу функции.

Например:

$$f(Х_{1}, Х_{2})= Х_{1}Х_{2}\vee Х_{1}\overline Х_{2}\vee \overline Х_{1}\overline Х_{2}$$

1      1       1

Эти единицы функции могут быть накрыты более короткими произведениями: Х_{1} накрывает две единицы: $$Х_{1}Х_{2}$$ и $$Х_{1}\overline Х_{2}$$ и $$\overline Х_{2}$$, которое накрывает также две единицы: $$Х_{1}\overline Х_{2}$$ и $$\overline Х_{1}\overline Х_{2}$$, т.е.

$$f(Х_{1}, Х_{2})= Х_{1}\vee \overline Х_{2}$$

ТЕОРЕМА (без док-ва):

Любая ФАЛ может быть представлена единственным образом в Сок. ДНФ, т.е. записана в виде дизъюнкции простых импликант.

Сокращенная форма не означает, что эта форма является минимальной. Однако для практической реализации эта форма более удобна, чем совершенная.

Рассмотрим метод получения Сок. ДНФ, предложенный Квайном. Этот метод, и, в частности, теорема Квайна в явном и неявном виде входит практически во все методы минимизации.

Исходная форма функции – совершенная ДНФ.

ТЕОРЕМА Квайна:

Если в СДНФ в начале произвести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращенная ДНФ.

Покажем, что, применяя операцию неполного склеивания, получим все простые импликанты функции. Введем операцию развертывания, которая обратна операции склеивания: это есть умножение каждого произведения на выражение вида $$(\overline Х \vee X)=1.$$

Пусть $$\overline Х_{1}Х_{2}$$ – простая импликанта некоторой $$f(Х_{1}, Х_{2}, Х_{3})$$ трех переменных. Тогда:

$$\overline Х_{1}Х_{2} (Х_{3}\vee \overline Х_{3})=\overline Х_{1} Х_{2} Х_{3} \vee \overline Х_{1} Х_{2} \overline Х_{3}$$

получатся после многократного применения этой операции дизъюнкции конституент единицы исходной функции, т.е. ее СДНФ.

В эту форму, вообще говоря, могут входить несколько одинаковых членов, т.к. разные простые импликанты могут дать одинаковые конституенты единицы. Поэтому, отбросив в ДНФ лишние члены, получим ее СДНФ.

По отношению к СДНФ применяется операция неполного склеивания, т.к. одно и то же произведение, вообще говоря, может склеиваться с несколькими другими, давая различные импликанты, то чтобы не лишиться возможности провести все операции склеивания, приходится каждое произведение, которое участвовало в операции склеивания, оставить для других операций.

Пример:

$$f(Х_{1}, Х_{2})= Х_1\overline Х_{2}\vee \overline Х_{1}Х_{2}\vee \overline Х_{1}\overline Х_{2} = Х_1\overline Х_{2}\vee \overline Х_{1}\ или\ \overline Х_{1}Х_{2}\vee \overline Х_{2}$$

Таким образом после выполнения операции неполного склеивания получится не только дизъюнкция простых импликант, но и часть конституент единицы.

Если теперь провести все операции поглощения, то в полученной форме функции f останутся только простые импликанты. Покажем это. Пусть в результате операций склеивания получится член x, не являющийся простой импликантой.

Тогда x=y*z, где z – простая импликанта, которая так же должна входить в f, т.к. в нее входит x. Но z будет поглощать х, поэтому х не может входить в f. Это и доказывает теорему Квайна.

Замечание: Заметим, что теорема Квайна применяется по отношению к функции СДНФ.

Порядок получения Сок. ДНФ может быть следующим:

Пример 1:

$$f(Х_{1}, Х_{2})= Х_{1}Х_{2}\vee Х_{1}\overline Х_{2}\vee \overline Х_{1}\overline Х_{2}$$

Если применим операцию полного склеивания, то получим:

или

$$f(Х_{1}, Х_{2})= Х_{1}\vee \overline Х_{1}\overline Х_{2}$$

или

$$f(Х_{1}, Х_{2})= Х_{1}Х_{2}\vee \overline Х_{2}$$

т.е. у нас нет возможности далее провести операцию.

Применим теперь операцию неполного склеивания:

$$f(Х_{1}, Х_{2})= Х_{1}\vee Х_{1}Х_{2}\vee Х_{1}\overline Х_{2}\vee \overline Х_{1}\overline Х_{2}\vee \overline Х_{2} = Х_{1}\vee \overline Х_{2}\vee Х_{1}Х_{2}\vee Х_{1}\overline Х_{2}\vee \overline Х_{1}\overline Х_{2}$$

Простые импликанты: $$Х_{1},$$ $$\overline Х_{2}$$

Конституенты единицы: $$Х_{1}Х_{2},$$ $$Х_{1}\overline Х_{2},$$ $$\overline Х_{1}\overline Х_{2} $$

Теперь можем провести операции поглощения:

$$Х_{1}$$ поглощает: $$Х_{1},$$ $$Х_{1}Х_{2},$$ $$Х_{1}\overline Х_{2}$$

$$\overline Х_{2} $$ поглощает: $$\overline Х_{2} ,$$ $$Х_{1}\overline Х_{2},$$ $$\overline Х_{1} \overline Х_{2} $$

Т.е. сокращенная ДНФ

$$f(Х_{1}, Х_{2})= Х_{1}\vee \overline Х_{2}$$ в данном случае она – минимальная форма.

Пример 2:

Пусть задана:

$$f(Х_{1}, Х_{2}, Х_{3})= Х_{1}\overline Х_{3} \vee \overline Х_{1}\overline Х_{2} \vee \overline Х_{1}\overline Х_{2} Х_{3}$$

Получим СДНФ:

$$f= Х_{1}\overline Х_{3} (\overline Х_{2} \vee Х_{2})\vee \overline Х_{1}\overline Х_{2} (Х_{3}\vee \overline Х_{3})\vee \overline Х_{1}Х_{2} \overline Х_{3} = Х_{1}Х_{2} \overline Х_{3} \vee Х_{1}\overline Х_{2} \overline Х_{3} \vee \overline Х_{1}\overline Х_{2} Х_{3} \vee \overline Х_{1}\overline Х_{2} \overline Х_{3} \vee \overline Х_{1}\overline Х_{2} Х_{3} = Х_{1}Х_{2} \overline Х_{3} \vee Х_{1}\overline Х_{2} \overline Х_{3} \vee \overline Х_{1}\overline Х_{2} Х_{3} \vee \overline Х_{1}\overline Х_{2} \overline Х_{3}$$

Теперь, имея СДНФ, можно получить сокращенную ДНФ:

$$f(X_{1},X_{2},X_{3})=\overline X_{1}\overline X_{2}X_{3}\vee \overline X_{2}\overline X_{3}\vee X_{1}\overline X_{3}$$

Пример 3:

$$\overline f(Х_{1}, Х_{2}, Х_{3})=\overline Х_{1}Х_{2} Х_{3}\vee \overline Х_{1}\overline Х_{2} Х_{3}\vee Х_{1}\overline Х_{2} \overline Х_{3}\vee \overline Х_{1}\overline Х_{2} \overline Х_{3} \vee Х_{1}Х_{2} \overline Х_{3} = \overline Х_{1}Х_{3} \vee \overline Х_{2}\overline Х_{3} \vee \overline Х_{1}\overline Х_{2}\vee Х_{1}\overline Х_{3}$$

Склеиваются два произведения, содержащие число переменных с отрицанием, отличающихся на единицу и расположенных соответствующим образом.

Обычно произведение, содержащее ' n ' букв, называется минтермом ' n '- ранга.

Метод минимизации ФАЛ по Квайну

Определение: Тупиковой ДНФ называется дизъюнкция простых импликант, ни одну из которых из выражения функции исключить нельзя.

Этот метод минимизации ФАЛ заключается в следующем:

Иногда в Сок. ДНФ содержатся лишние импликанты. Как уже видели в сокращенной ДНФ:

$$f(Х_{1}, Х_{2}, Х_{3})= Х_{1}Х_{3} \vee \overline Х_{2}Х_{3} \vee \overline Х_{1}\overline Х_{2 }$$

импликанта \overline Х_{2}Х_{3} может быть исключена. Ни одной операции склеивания и поглощения к этой форме применить нельзя, т.к. это Сок. ДНФ, т.е. дизъюнкция простых импликант. Можно применить операцию развертывания по Х_{1}:

$$f= Х_{1}Х_{3} \vee \overline Х_{2}Х_{3} (Х_{1}\vee \overline Х_{1}) \vee \overline Х_{1}\overline Х_{2} = Х_{1}Х_{3} \vee Х_{1}\overline Х_{2} Х_{3} \vee \overline Х_{1}\overline Х_{2} Х_{3} \vee \overline Х_{1}\overline Х_{2}$$

Т.к. $$Х_{1}Х_{3}$$ покрывает $$Х_{1}\overline Х_{2}Х_{3}$$

и $$\overline Х_{1}\overline Х_{2}$$ покрывает $$\overline Х_{1}\overline Х_{2}Х_{3}$$, то $$f= Х_{1}Х_{3} \vee \overline Х_{1}\overline Х_{2}$$

ТЕОРЕМА:

Всякая минимальная ДНФ является тупиковой. Обратное утверждение не справедливо. Доказательство очевидно.

Из этой теоремы вытекает важное следствие: Для того чтобы найти минимальную ДНФ, нужно найти все тупиковые формы и среди них взять минимальную.

Существует несколько различных способов отыскания тупиковых форм.