Содержание к диссертации
Введение
1 История возникновения, становления и развития математической логики, решаемые задачи 8
1.1 История создания и развития математической логики 8
1.2 Минимизация булевых функций и проблемы оптимальной реализации булевых функций из отдельных классов в разных базисах , 10
1.3 Булевы функции, базисы, формулы и схемы, показатели сложности, математико-формационное описание 13
1.3.1 Постановка задачи 15
1.3.2 Теорема Жегалкина 18
1.4 Методы декомпозиции, функционалы качества 21
1.4.1 Методы декомпозиции булевых функций 23
1.4.2 Основные функционалы качества, оптимизация 28
1.5 Функциональные уравнения (ФУ) 31
1.6 Примеры реализации булевых функций 35
Математический аппарат для синтеза дискретных логических устройств управления и обработки информации. Оптимизирующие логико-комбинаторные преобразования 39
2.1 Удаление фиктивных переменных 39
2.2 Эквивалентные преобразования 41
2.3 Скобочные формулы и их показатели сложности 44
2.4 Многокритериальная оптимизация 46
3 Оценки качества булевых функций на основе алгебраической декомпозиции 50
3.1 Верхние оценки показателей качества БФ 51
3.1.1 Показатель качества LB 51
3.1.2 Показатель качества Lp 51
3.2 Минимизация полученных оценок 52
3.2.1 Показатель качества LB (і 2, () 52
3.2.2 Показатель качества L (L 2, () 60
3.3 Реализация в классе схем 67
3.3.1 Показатель качества L# (і 2 G\) 67
3.4 Сравнение результатов 81
3.4.1 Сравнение оценок LB 81
3.4.2 Сравнение оценок Ls 85
4 Автоматизация
4.1 Разработка алгоритма 86
4.1.1 Используемые обозначения 88
4.1.2 Алгоритм 90
4.2 Программная реализация 92
4.2.1 Примеры работы алгоритма 92
4.2.2 Частные случаи 95
Заключение 100
Литература
- Минимизация булевых функций и проблемы оптимальной реализации булевых функций из отдельных классов в разных базисах
- Эквивалентные преобразования
- Показатель качества Lp
- Используемые обозначения
Минимизация булевых функций и проблемы оптимальной реализации булевых функций из отдельных классов в разных базисах
Рассматривается проблема представления определенной булевой функции в классах формул и — схем из функциональных элементов (ФЭ) в разных базисах. Причем функции, в основном, характеризуются аналитической (полиномиальной или скобочной) формой задания. Возможно также задание вектором ее значений. Задача, в общем случае, имеет много решений, качество-сложность получаемых при этом формул и схем оценивается при помощи дискретных функционалов. Начальным показателем сложности является размерность булевой функции. Для практики важны ее различные обобщения, например - число переменных в формуле. Остальные рассматриваемые показатели качества (число подформул и глубина формулы; число ФЭ и глубина схемы) являются производными этого по казателя в большей или меньшей степени. Повышение надежности схемы выполняется неявно (специальных методов повышения надежности здесь не рассматривается) [1].
По практическим соображениям показатели качества (функционалы) минимизируем. При представлении функции в классе формул для минимизации показателей сложности используются эквивалентные преобразования, включая получение скобочных формул, - в классе схем для минимизации числа ФЭ применяется ветвление их выходов [1-6].
Большая трудоемкость получения оптимального по какому-либо показателю решения, неизбежно использующего алгоритмы переборного характера, привела к отказу от стандартных подходов постановки задачи и ее решения [1-6]. В связи с этим изучаются различные подходы к разработке алгоритмов синтеза, заметно отличающихся по трудоемкости от переборных. В их числе имеется асимптотический подход, основывающийся на функции Шеннона. Используя его, О.Б. Лупанов [1] первым разработал метод и получил асимптотическую оценку числа элементов схемы, реализующей булеву функцию. Затем, развивая метод, асимптотическая оценка для глубины схемы получена в работе [8].
Зависимость между минимальными значениями глубины и сложности эквивалентных формул изучалась в работах [9-10] и были получены верхние оценки для глубины булевой функции. Представляя линейную функцию схемой из ФЭ, Н.П. Редькин аналитически получил показатель сложности по числу ФЭ в схеме и доказал его минимальность [3-5].
В работах Ю.И. Журавлева, СВ. Яблонского и Д.А. Поспелова предложено ограничить трудоемкость синтеза и в ограниченном классе искать алгоритмы, приводящие к схемам наилучшего качества. В этих же работах показано, что в классе алгоритмов, заметно отличающихся по трудоемкости от переборных, далеко не всегда удается получить решение, сколько-нибудь близкое к оптимальному [3-5].
Несмотря на имеющиеся успехи в области синтеза схем, однако, в целом, в теории булевых функций нет полных ответов на следующие вопросы. Как использование скобочных формул, математических моделей, улучшают качество проектируемых схем из ФЭ? Как ветвление выходов ФЭ позволяет минимизировать их число в схеме? Как зависит трудоемкость синтеза от результатов минимизации перечисленных выше показателей (как они связаны)? С помощью каких средств можно уменьшить трудоемкость синтеза и др.? В научной литературе приводятся и исследуются примеры, когда одна функция в некотором базисе имеет меньшие значения показателей сложности по сравнению с другим базисом, другая же функция, наоборот [1-3]. Для таких задач интересны ответы на вопросы: во сколько раз или как может измениться сложность функции при переходе из одного базиса в другой (и наоборот).
Имеющихся ответов на все эти вопросы в известных публикациях недостаточно [1-5]. Причем в [5] сказано: «Асимптотические оценки важны не только с точки зрения понимания сложности получаемых схем, но и как способ оценки качества алгоритмов синтеза. Однако при построении схем для конкретных функций асимптотически наилучшие методы синтеза часто не дают хороших результатов».
Тем не менее, поиск минимальных решений может быть успешным, но искать его следует на основе классификации множества булевых функ ций, совершенствования методов декомпозиции с привлечением понятия строение-структура [7-10]. Поэтому в качестве математических моделей, для большей части рассматриваемых задач, выбирались все БФ, а также -симметрические булевы функции и их представления в классе формул и -схем из ФЭ.
Отметим, что синтезируемые схемы применяются при проектировании различных дискретных логических устройств для вычислительной и управляющей техники [7-10].
Используемые обозначения: \х\ для приближения чисел с избытком (наименьшее целое, не меньшее числа ж); \_х\ для приближения чисел с недостатком (наибольшее целое, не большее числа х ); следующие логические операции обозначаются двумя способами: конъюнкция как & или (точка-знак умножения), но точкой иногда обозначается также арифметическое умножение; отрицание как или надчеркивание над переменной, например, X] эквивалентность как -Ф= . В записи формул для простоты иногда внешние скобки опускаем.
Эквивалентные преобразования
Отметим две важные особенности, которые составляют основу метода минимизации ДНФ и приведения их к скобочному виду: в рассмотренных выше эквивалентностях вместо каждой переменной Хі: і = 1,2,3, может быть, подставлена, в свою очередь, некоторая формула; в общем случае упрощение ДНФ начинается с поиска и анализа такой конъюнкции x Szx : которая имеет наибольшее число повторений в математико-информационном описании. Для поиска конъюнкции Xi&LXj с наибольшим числом повторений используется матрица D формулы /.
Эти особенности сокращают число просматриваемых вариантов и время решения задачи на ЭВМ.
Часть алгоритма, выполняющая преобразование монотонной ДНФ в скобочную формулу, полностью применима при преобразовании полинома Жегалкина в скобочную формулу. Вынесение общих множителей в формуле (полиноме Жегалкина, монотонной ДНФ и др.) зависит от базиса и может как сохранять, так и увеличивать значение глубины функции. При изучении таких преобразований можно рассматривать разбиение множества функций, зависящих от п переменных, на классы функций, сохраняющих глубину или ее увеличивающих.
Рассмотрим суть алгоритмов вынесения общих множителей в формуле (полиноме Жегалкина, монотонной ДНФ и др.) на основе матриц С и D (вектора с).
Алгоритм 2.1. (основные пункты алгоритма). В матрице С выбирается максимальный элемент, относящийся к некоторой переменной, и в соответствующих элементарных конъюнкциях выносится общий множитель за скобки, выражение в скобках обозначается за новую, вспомогательную переменную. Таким образом, получили представление одной формулы в виде суперпозиции двух, более простых формул. Применяя эту процедуру к полученным формулам и так далее, получим окончательное представление исходной функции в виде суперпозиции более простых функций. Это вариант так называемой естественной декомпозиции (без учета базиса).
Алгоритм 2.2. (основные пункты алгоритма). В матрице D выбирается максимальный элемент, относящийся к двум некоторым переменным, и в соответствующих элементарных конъюнкциях выносится общий элемент за скобки, выражение в скобках обозначается за новую, вспомогательную переменную. Таким образом, получили представление одной формулы в виде суперпозиции двух, более простых формул. Применяя эту процедуру к полученным формулам и так далее, получим окончательное представление исходной функции в виде суперпозиции более простых функций. Это вариант так называемой естественной декомпозиции, но, в отличие от предыдущего варианта, можно ожидать, что в дальнейшем он для двухместного базиса будет предпочтительным в отношении минимизации глубины суперпозиционной формулы (схемы).
Алгоритм 2.3. (основные пункты алгоритма). Возможен совместный вариант проведения этих преобразований на каждом шаге (для каждой повторяющейся переменной), в результате которого выбирается более эффективное преобразование.
При приведении исходной формулы / к скобочному виду имеются явные случаи, когда скобочная формула /с& в двухместном базисе G из множества &,V,0 имеет не болыную( не меньшую) глубину по сравнению с исходной формулой строения г. Рассмотрим некоторые типовые случаи. Пусть /(") = К0- #10 К0- К2 — полином Жегалкина строения г = = (го + Ті,Го + г2) где ГІ, і = 0,1,2 — ранг элементарной конъюнкции КІ (не элементарной конъюнкции формулы), причем П = Т о + Т\ + Г2 и Г\ г2- В качестве формулы могут быть монотонные ДНФ или КНФ и другие формулы строения г, и с модификацией формулируемые ниже правила могут применяться к произвольным ДНФ или КНФ. Иногда будем записывать Кь = К\, где гг — местность элементарной конъюнкции запишем скобочную формулу: fk = Ko- (К\ 0 К2). Их показатели сложности (по числу букв) соответственно
Для сложности справедливость неравенства (2.4.1) устанавливается непосредственным подсчетом, а для глубины доказательство проведем индукцией по п, причем только для глубины(для сложности оно будет аналогичным). Заметим, что в силу условия при п — оо достаточно рассмотреть При n = 3, 4 или 5 утверждение 2.1 проверяется непосредственно.
Показатель качества Lp
Отметим две важные особенности, которые составляют основу метода минимизации ДНФ и приведения их к скобочному виду: в рассмотренных выше эквивалентностях вместо каждой переменной Хі: і = 1,2,3, может быть, подставлена, в свою очередь, некоторая формула; в общем случае упрощение ДНФ начинается с поиска и анализа такой конъюнкции x Szx : которая имеет наибольшее число повторений в математико-информационном описании. Для поиска конъюнкции Xi&LXj с наибольшим числом повторений используется матрица D формулы /.
Эти особенности сокращают число просматриваемых вариантов и время решения задачи на ЭВМ.
Часть алгоритма, выполняющая преобразование монотонной ДНФ в скобочную формулу, полностью применима при преобразовании полинома Жегалкина в скобочную формулу. Вынесение общих множителей в формуле (полиноме Жегалкина, монотонной ДНФ и др.) зависит от базиса и может как сохранять, так и увеличивать значение глубины функции. При изучении таких преобразований можно рассматривать разбиение множества функций, зависящих от п переменных, на классы функций, сохраняющих глубину или ее увеличивающих.
Рассмотрим суть алгоритмов вынесения общих множителей в формуле (полиноме Жегалкина, монотонной ДНФ и др.) на основе матриц С и D (вектора с).
Алгоритм 2.1. (основные пункты алгоритма). В матрице С выбирается максимальный элемент, относящийся к некоторой переменной, и в соответствующих элементарных конъюнкциях выносится общий множитель за скобки, выражение в скобках обозначается за новую, вспомогательную переменную. Таким образом, получили представление одной формулы в виде суперпозиции двух, более простых формул. Применяя эту процедуру к полученным формулам и так далее, получим окончательное представление исходной функции в виде суперпозиции более простых функций. Это вариант так называемой естественной декомпозиции (без учета базиса).
Алгоритм 2.2. (основные пункты алгоритма). В матрице D выбирается максимальный элемент, относящийся к двум некоторым переменным, и в соответствующих элементарных конъюнкциях выносится общий элемент за скобки, выражение в скобках обозначается за новую, вспомогательную переменную. Таким образом, получили представление одной формулы в виде суперпозиции двух, более простых формул. Применяя эту процедуру к полученным формулам и так далее, получим окончательное представление исходной функции в виде суперпозиции более простых функций. Это вариант так называемой естественной декомпозиции, но, в отличие от предыдущего варианта, можно ожидать, что в дальнейшем он для двухместного базиса будет предпочтительным в отношении минимизации глубины суперпозиционной формулы (схемы).
Алгоритм 2.3. (основные пункты алгоритма). Возможен совместный вариант проведения этих преобразований на каждом шаге (для каждой повторяющейся переменной), в результате которого выбирается более эффективное преобразование.
При приведении исходной формулы / к скобочному виду имеются явные случаи, когда скобочная формула /с& в двухместном базисе G из множества &,V,0 имеет не болыную( не меньшую) глубину по сравнению с исходной формулой строения г. Рассмотрим некоторые типовые случаи. Пусть /(") = К0- #10 К0- К2 — полином Жегалкина строения г = = (го + Ті,Го + г2) где ГІ, і = 0,1,2 — ранг элементарной конъюнкции КІ (не элементарной конъюнкции формулы), причем П = Т о + Т\ + Г2 и Г\ г2- В качестве формулы могут быть монотонные ДНФ или КНФ и другие формулы строения г, и с модификацией формулируемые ниже правила могут применяться к произвольным ДНФ или КНФ. Иногда будем записывать Кь = К\, где гг — местность элементарной конъюнкции запишем скобочную формулу: fk = Ko- (К\ 0 К2). Их показатели сложности (по числу букв) соответственно Для сложности справедливость неравенства (2.4.1) устанавливается непосредственным подсчетом, а для глубины доказательство проведем индукцией по п, причем только для глубины(для сложности оно будет аналогичным). Заметим, что в силу условия при п — оо достаточно рассмотреть При n = 3, 4 или 5 утверждение 2.1 проверяется непосредственно.
Используемые обозначения
Вынесение общих множителей в формуле (полиноме Жегалкина, монотонной ДНФ и др.) зависит от базиса и может как сохранять, так и увеличивать значение глубины функции. При изучении таких преобразований можно рассматривать разбиение множества функций, зависящих от п переменных, на классы функций, сохраняющих глубину или ее увеличивающих.
Рассмотрим суть алгоритмов вынесения общих множителей в формуле (полиноме Жегалкина, монотонной ДНФ и др.) на основе матриц С и D (вектора с).
Алгоритм 2.1. (основные пункты алгоритма). В матрице С выбирается максимальный элемент, относящийся к некоторой переменной, и в соответствующих элементарных конъюнкциях выносится общий множитель за скобки, выражение в скобках обозначается за новую, вспомогательную переменную. Таким образом, получили представление одной формулы в виде суперпозиции двух, более простых формул. Применяя эту процедуру к полученным формулам и так далее, получим окончательное представление исходной функции в виде суперпозиции более простых функций. Это вариант так называемой естественной декомпозиции (без учета базиса).
Алгоритм 2.2. (основные пункты алгоритма). В матрице D выбирается максимальный элемент, относящийся к двум некоторым переменным, и в соответствующих элементарных конъюнкциях выносится общий элемент за скобки, выражение в скобках обозначается за новую, вспомогательную переменную. Таким образом, получили представление одной формулы в виде суперпозиции двух, более простых формул. Применяя эту процедуру к полученным формулам и так далее, получим окончательное представление исходной функции в виде суперпозиции более простых функций. Это вариант так называемой естественной декомпозиции, но, в отличие от предыдущего варианта, можно ожидать, что в дальнейшем он для двухместного базиса будет предпочтительным в отношении минимизации глубины суперпозиционной формулы (схемы).
Алгоритм 2.3. (основные пункты алгоритма). Возможен совместный вариант проведения этих преобразований на каждом шаге (для каждой повторяющейся переменной), в результате которого выбирается более эффективное преобразование.
При приведении исходной формулы / к скобочному виду имеются явные случаи, когда скобочная формула /с& в двухместном базисе G из множества &,V,0 имеет не болыную( не меньшую) глубину по сравнению с исходной формулой строения г. Рассмотрим некоторые типовые случаи. Пусть /(") = К0- #10 К0- К2 — полином Жегалкина строения г = = (го + Ті,Го + г2) где ГІ, і = 0,1,2 — ранг элементарной конъюнкции КІ (не элементарной конъюнкции формулы), причем П = Т о + Т\ + Г2 и Г\ г2- В качестве формулы могут быть монотонные ДНФ или КНФ и другие формулы строения г, и с модификацией формулируемые ниже правила могут применяться к произвольным ДНФ или КНФ. Иногда будем записывать Кь = К\, где гг — местность элементарной конъюнкции запишем скобочную формулу: fk = Ko- (К\ 0 К2). Их показатели сложности (по числу букв) соответственно LB(/ ) = 2 го + Гі + Г2 = п + То и Lck(f{n)) =г0 + П +г2 = п. Для сложности справедливость неравенства (2.4.1) устанавливается непосредственным подсчетом, а для глубины доказательство проведем индукцией по п, причем только для глубины(для сложности оно будет аналогичным). Заметим, что в силу условия при п достаточно рассмотреть. При n = 3, 4 или 5 утверждение 2.1 проверяется непосредственно.
Справедливость неравенств (2.4.6), (2.4.7), (2.4.8) и (2.4.9) устанавливается на основе параллельной декомпозиции и непосредственным подсчетом.
Теперь для каждой булевой функции, задаваемой строением г = (го + Г\]Го + г і), и любых го и г\ по следующему простому алгоритму определяется представление функции минимальной глубины: определяется знак разности; для соответствующего случая (знака разности) по неравенству выбирается меньшее значение, характеризующее определенную формулу. Глава З
Оценки качества булевых функций на основе алгебраической декомпозиции Математическое моделирование в научном и техническом мире все больше становится компьютерным моделированием с постоянно расширяющимися интеллектуальными свойствами технических (аппаратурных) средств. При этом сохраняется потребность в совершенствовании математического аппарата (различных разделов дискретной математики). Поэтому в данной главе отрабатывается техника получения различных оценок показателей сложности на основе рекуррентных соотношений (функциональных уравнений). На первом этапе происходит приблизительная оценка каждого из показателей. После чего происходит минимизация полученных оценок с использованием методов алгебраической декомпозиции. В последнем параграфе данной главы все полученные оценки сравниваются.