takya.ru страница 1
скачать файл
УДК 621.391.1:62-507

Меликян К.С

МИНИМИЗАЦИЯ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ

МЕТОДОМ ЕЕ ОРТОГОНАЛИЗАЦИИ
Алгоритмы минимизации системы булевых функций [1] в целом отличаются от алгоритмов минимизации одной булевой функции, поскольку минимизация каждой функции системы в отдельности, вообще говоря, не обеспечивает минимизацию всей системы. Причиной этого является отсуствие попарной ортогональности функций системы.

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

Основная идея предлагаемого алгоритма заключается в следующем: если функции f1 и f2 системы являются ортогональными, т.е. f1 & f2 ? 0, то они могут быть минимизи- рованы в отдельности. Затем, объединением полученных результатов, можно осуществить минимизацию всей системы. Однако, поскольку f1 и f2 , в общем случае, не ортогональны, то введением вспомогательных ортогональных функций, получаемых из f1 и f2, задачу можно свести к вышеотмеченному случаю.

Пусть имеем булевы функции f1 и f2. Рассмотрим следующие функции:



F1 = f1 & f2, F2 = ?(f1 ? (f1 & f2 )), F3 = ? (f2 ? (f1 & f2)),

которые уже можно минимизировать по известным алгоритмам минимизации одной булевой функции [2]. Далее, можно рассматривать функции f1=F1 V F2 и f2= F1 V F3 . Затем можно минимизировать последние, имея в виду следующее обстоятельство: в ходе минимизации этих функций импликанты F1 либо могут полностью поглощаться, либо останутся "нетронутыми". После такой минимизации будем иметь функции F1', F2' и F3' , где: F1' - формула, получаемая из F1 после возможного поглощения некоторых ее импликантов импликантами из F2 и F3 ; F2' - формула, получаемая из F2 после возможной ее минимизации, а также из импликантов, которые были поглощены из F1 с помощью F3; F3' - формула, полученная из F1 и F3 анологично получению F2' из F2 и F1.

С

Рис.1
хема, изображенная на рис. 1, очевидно, будет реализо­вать систему функций {f1, f2}.



Пример 1 (алгоритм не дает никакого улучшения).


x1

x2

x1

x2

0

0

0

0

0

1

1

0

1

0

0

1

1

1

1

1

F1 = f1 & f2, F2 = ?(f1 ? F1), F3 = ? (f1 ? F1).

x1

x2

F1

F2

F3

0

0

0

0

0

0

1

0

1

0

1

0

0

0

1

1

1

1

0

0


f1 = F1VF2 = ?x1 x2 V x1 x2 = x2 V x1 x2 = x2,

f2 = F1VF3 = x1?x2 V x1 x2 = x1 V x1 x2 = x1.

Нетрудно убедиться, что если будем минимизировать f1 и f2 в отдельности, то получим такой же результат.



Пример 2 (алгоритм минимизирует систему).


x1

x2

x3

f1

f2

0

0

0

0

0

0

0

1

1

0

0

1

0

0

1

0

1

1

1

0

1

0

0

0

0

1

0

1

0

0

1

1

0

0

1

1

1

1

1

1

1) без применения предложенного алгоритма имеем:



f1 =?x1?x2 x3 V?x1 x2 x3 V x1 x2 x3 =?x1 x3 V x2 x3,

f2 =?x1 x2?x3 V x1 x2?x3 V x1 x2 x3 = x1 x2 V x2?x3;
2) с применением предложенного алгоритма имеем:


x1

x2

x3

F1

F2

F3

0

0

0

0

0

0

0

0

1

0

1

0

0

1

0

0

0

1

0

1

1

0

1

0

1

0

0

0

0

0

1

0

1

0

0

0

1

1

0

0

0

1

1

1

1

1

0

0


F1 = x1 x2 x3,

F2 =?x1?x2 x3 V?x1 x2 x3 =?x1 x3,

F3 =?x1 x2?x3 V x1 x2?x3 = x2?x3.
f1 = F1VF2 = x1 x2 x3 V?x1 x3, (из-за ограничений, введенных в алгоритм, невозможно продолжать дальнейшую минимизацию функции f1).

f2 = F1VF3 = x1 x2 x3 V x2?x3 (дальнейшая минимизация функции f2 также невозможна из-за ограничений, введенных в алгоритм).

Схемы, реализующие f1 и f2, для обоих случаев представлены на рис. 2 и рис. 3.


Рис. 2





Рис. 3


Теперь приведем алгоритм минимизации для системы булевых функций, состоящей из трех функций. Пусть имеем функции f1, f2 и f3. Рассмотрим следующие соотношения:



F1 = f1 & f2 & f3.

F2 = ? ((f1 & f2)?F1),

F3 = ? ((f1 & f3)?F1),

F4 = ? ((f2 & f3)?F1),

F5 = ? (f1 ? (F1VF2VF3)),

F6 = ? (f2 ? (F1VF2VF4)),

F7 = ? (f3 ? (F1VF3VF4)).

Далее, аналогичным образом, как для двух функций, минимизируем построенные вспомогательные функции. А затем, с их помощью, учитывая введенное ограничение, построим минимизированную схему для функций f1, f2 и f3.

*

* *


Автор выражает благодарность д.ф.-м.н., проф. Бозояну Ш.Е., под руководством которого была выполнена данная работа в лабораториях “HPL Armenia”.

ЛИТЕРАТУРА


  1. Яблонский С.В. Введение в дискретную математику. –М.: Наука, Главная редакция физико-математической литературы. – 1979, -272с.

  2. Melikyan K. On a Method of Boolean Function Minimization //Computer Science and Information Technologies. - 1999, August 17-22. /Armenia, Yerevan, –p. 73-74.




"МОДЕЛИРОВАНИЕ, ОПТИМИЗАЦИЯ, УПРАВЛЕНИЕ" - Вып.3/2000г.


скачать файл



Смотрите также:
Минимизация системы булевых функций
103.13kb.
В данной работе рассматривается возможность решения задачи определения возможных значений нелинейности булевых функций многих переменных с использованием вычислений на кластере
23.39kb.
Дайте определение частично рекурсивных функций
389.08kb.
Программа курса нервно-гуморальная регуляция висцеральных функций
33.62kb.
Кафедра «Компьютерные технологии и системы» Дисциплина «управление в социальных и экономических системах» Отчётная работа
318.71kb.
Практикум на языке программирования Лисп (4-й курс, осень 2013 г.) Задание Программирование вспомогательных функций Реализовать с помощью
26.08kb.
Логическое проектирование и минимизация
871.84kb.
Лабораторная работа №1 «Вычисление значений функций» студент 304 гр д/о Иванов Иван Иванович
23kb.
Жесткие системы оду и их численное решение
36.57kb.
Практическая работа Тема : Функции в языке программирования Visual Basic
49kb.
Урока «Построение графиков математических функций»
28.09kb.
7 Минимизация рисков эффективности государственного управления. Обеспечение реализации полномочий губернатора как высшего должностного лица. (Федор Алиев)
38.3kb.