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

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

f(Х₁, Х₂)= Х₁Х₂ Х₁Х₂ Х₁Х₂ =Х₁Х₁ Х₂

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

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

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

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

f(Х₁, Х₂)= Х₁Х₂ Х₁Х₂ Х₁Х₂ имеется 6 букв и только 2 переменных.

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

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

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

f(Х₁, Х₂)= Х₁Х₂ (Х₁Х₂)= Х₁Х₂ (Х₃Х₃) (Х₁Х₂)= Х₁ Х₂ Х₃ Х₁ Х₂ Х₃ (Х₁Х₂)=Х₁ Х₂ Х₃ (Х₁ Х₂ Х₃)

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

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

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

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

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

1. Ранг произведения – число букв, входящих в него.
2. Собственной частью называется произведение, полученное путем отбрасывания одной или нескольких переменных.

Например, Х₁ Х₂ Х₃ Х₄, где Х₁, Х₁ Х₂, Х₁ Х₂ Х₃ – некоторые собственные части.

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

Например, Х₁ Х₁ Х₂ Х₃ Х₁Х₃=f: здесь Х₁- простая импликанта, а Х₁ Х₂ Х₃ и Х₁ Х₃ - не простые.

Дата добавления: 2014-01-06