Логические и арифметические основы и принципы работы ЭВМ

       

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


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

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. Собственной частью называется произведение, полученное путем отбрасывания одной или нескольких переменных.



    Содержание раздела