Минимизация ФАЛ и ограничения при ее рассмотрении
Покажем на примере, что СДНФ не является экономной формой записи:
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.
- Дизъюнкция элементарных произведений – ДНФ.
- ДНФ является минимальной, если в ней минимальное число букв и членов.
-
Конституентой единицы функции называют функцию, принимающую значение единицы только на одном наборе аргументов.
Обычно конституенты единицы выражают через произведение всех переменных, от которых зависит функция. СДНФ – дизъюнкция конституент единицы.
-
Ранг произведения – число букв, входящих в него.
- Собственной частью называется произведение, полученное путем отбрасывания одной или нескольких переменных.
Содержание раздела
