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

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

f(Х1, Х2)= Х1Х2

Х1Х2 Х1Х2 =Х1Х1 Х2

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

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

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

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

f(Х1, Х2)= Х1Х2

Х1Х2 Х1Х2 имеется 6 букв и только 2 переменных.

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

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

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

f(Х1, Х2)= Х1Х2

(Х1Х2)= Х1Х2 (Х3Х3) (Х1Х2)= Х1 Х2 Х3 Х1 Х2 Х3 (Х1Х2)=Х1 Х2 Х3 (Х1 Х2 Х3)

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

1. Произведение одной или нескольких неповторяющихся переменных, взятых с отрицанием или без него, называют элементарным.

   Например, Х1 Х2 Х3 – элементарное произведение, т.к. в него входят различные буквы Х1 Х2 Х3.

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

4. Конституентой единицы функции называют функцию, принимающую значение единицы только на одном наборе аргументов.

   Обычно конституенты единицы выражают через произведение всех переменных, от которых зависит функция. СДНФ – дизъюнкция конституент единицы.

5. Ранг произведения – число букв, входящих в него.

6. Собственной частью называется произведение, полученное путем отбрасывания одной или нескольких переменных.
   
   
   
   Содержание  Назад  Вперед