04 марта 2016г.
1 Работа выполнена при поддержке гранта РФФИ № 15-01-05669
Введение.
Несмотря на то, что основные подходы к минимизации булевых функций были предложены ещѐ в середине прошлого века [4], интерес к ним не затухает и в настоящее время. Это можно объяснить двумя обстоятельствами. Во-первых, цифровые устройства, для которых задача минимизации булевых функций имеет решающее значение, все больше вытесняют аналоговые устройства. Во-вторых, методы минимизации булевых функций рассматриваются в соответствующих учебных курсах. Поэтому современные подходы и возможности их программной реализации являются вполне актуальными с точки зрения процесса обучения [1]. В качестве подтверждения выше сказанного можно привести и тот факт, что в наши дни все еще выходят публикации известного ученого-исследователя данной тематики [3].
Для минимизации булевых функций наибольшее применение находят:
1) табличный метод – метод карт Карно или Вейча – Карно;
2) расчетный метод – метод непосредственных логических преобразований;
3) расчетно-табличный метод Квайна.
В работе [2] приведены результаты исследования алгоритмических особенностей и программной реализации табличного метода минимизации булевых функций. Экспериментальные исследования, проведенные с помощью разработанного программного кода, позволили установить, что алгоритмическая сложность этого метода является экспоненциальной и составляет величину 𝑂 𝑛 = 21,33𝑛 , где 𝑛 – число переменных в минимизируемой булевой функции.
Табличный метод является наглядным, когда число переменных равно не более 6. При большем числе переменных он теряет свою наглядность и становится громоздким. К тому же при разработке алгоритма и программного кода неожиданно проявилась трудность построения покрытий для большого числа переменных. Поэтому в данной статье приводятся результаты программной реализации и исследований с ее помощью процесса минимизации булевых функций методом непосредственных преобразований, который предположительно более просто реализуется и требует меньший объем памяти.
Каноническое представление булевых функций
Общая запись любой логической функции 𝑓 в СДНФ имеет вид:
Значение 𝑘𝑖 определяет факт вхождения конституенты единицы 𝑐𝑖 1 в 𝑓. При 𝑘𝑖 = 1 конституента 𝑐𝑖 1 входит в 𝑓, а при 𝑘𝑖 = 0 – не входит.
Общая запись любой логической функции f в СКНФ имеет вид:
Здесь 𝑘𝑖 определяет факт вхождения конституенты нуля 𝑐𝑖 в 𝑓. Иначе говоря, в СНКФ будет отсутствовать тот дизъюнктивный член, для которого 𝑘𝑖 = 1.
СДНФ и СКНФ являются каноническими формами, так как к ним можно свести любую произвольную аналитически заданную логическую функцию. Поэтому во всех трѐх выше указанных методах для минимизации используется каноническая форма представления логических функций.
Программа минимизации и еѐ использование для исследования метода непосредственных преобразований Метод непосредственных преобразований предполагает выполнение трех операций:
· Склеивание всевозможных членов исходной СДНФ/СКНФ, т.е. сначала конституент, затем импликант
ранга 𝑛 − 1 и т.д., пока склеивание возможно. Результатом выполнения операции является сокращенная ДНФ/КНФ (сДНФ/сКНФ).
· Проверка каждой простой импликанты в сДНФ/сКНФ на избыточность с целью еѐ удаления. Проверка состоит в следующем. Так как любая импликанта равна 1 для ДНФ и 0 для КНФ лишь на одном наборе переменных, то если на этом наборе сумма остальных членов в сДНФ также обращается в 1 и в 0 в сКНФ, то рассматриваемая импликанта не влияет на значение истинности данной логической функции, т.е. она является избыточной. Удаляя все такие импликанты, получим тупиковую Д(К)НФ (ТД(К)Ф.
· Переход от ТД(К)НФ к минимальной форме (МД(К)НФ) логической функции. Эта операция уже не является регулярной, как две предыдущие, поэтому требует определенной сноровки, интуиции и опыта. Для уменьшения числа операций отрицания применяют законы де Моргана, а для уменьшения числа конъюнкций и дизъюнкций – распределительные законы алгебры логики.
Для автоматической минимизации булевых функций используются две первые операции. Третья операция алгоритмически неразрешима, поэтому при дальнейшем рассмотрении она не используется.
Предлагаемая программа написана на языке С++ и состоит из трех структурных классов: Parser, Minimizer, GUI. Класс Parser анализирует поданное на вход программы выражение и переводит его в форму, удобную для последующей обработки, определяет тип выражения – СДНФ или СКНФ. Он также формирует сообщения об ошибках, если выражение введено некорректно.
Класс Minimizer отвечает за выполнение первой и второй операции – за склеивание и удаление избыточных импликант. Он же формирует строку, в которую записывается результат – минимизированная функция.
Класс GUI отвечает за графический интерфейс пользователя, т.е. через него осуществляется взаимодействие с программой. С помощью разработанного программного продукта были получены графические зависимости времени минимизации булевой функции от количества конституент при 12, 15 и 32 входящих в них переменных. Эти зависимости представлены на Рисунке 1. Данные для построения графиков были получены с помощью отдельного алгоритма, который случайным образом формировал функции и замерял время их минимизации. Количество конституент менялось от 0 до 500.
Для установления эмпирической формулы оценки временной сложности алгоритма минимизации булевых функций методом
непосредственных преобразований была построена
временная зависимость с расширенным диапазоном варьирования конституент для 12 переменных. Эта зависимость приведена на Рисунке
2.
Экспериментальные исследования проводились на компьютере с процессором Intel Core i5-3330 CPU @3.1
GHz.
Используя результаты Рисунка 2 и метод средних
для построения эмпирических формул по экспериментальным данным,
была получена формула
оценки времени минимизации от числа конституент n в исходной булевой функции
𝑂 𝑛 = 0,05 ⋅ 20,003 𝑛 .
Эта оценка, также, как
и
для табличного метода,
описывается показательной функцией, и
с алгоритмической точки зрения является экспоненциальной. От оценки для табличного метода
она отличается лишь постоянными коэффициентами. Причем эти коэффициенты существенно меньше, чем у оценки для табличного метода.
Указанное различие
может быть вызвано
особенностями программных реализаций.
Объем кода разработанной программы
для метода непосредственных преобразований составляет 113 килобайт, а со всеми используемыми библиотеками – 44,4 мегабайт. Совместно
с подпрограммой создания случайных функций
и замера времени
их минимизации он включает 1017 строк кода на языке C++.
На Рисунке 3 представлен интерфейс пользователя программы. Он достаточно прост и удобен в использовании. В верхнее
поле ―Функция ввода‖
помещается функция, которую нужно минимизировать. После нажатия кнопки ―МИНИМИЗИРОВАТЬ‖, программа
начинает сокращать выражение, ход процесса
отображается на прогресс-баре, расположенном ниже. Ещѐ ниже отображается этап минимизации, выполняемый в данный момент. Когда процесс завершится, выводится надпись
―Готово‖. В поле ―Функция
вывода‖ отображается минимизированная логическая функция. Если введенная
функция не может быть сокращена,
или
введена некорректно, в поле ―Функция вывода‖ выводится
надпись ―Неудачно‖. Кнопка ―Пошагово‖ позволяет просмотреть процесс
минимизации поэтапно, а также,
если выражение было введено
некорректно, она позволяет увидеть, что конкретно в исходном выражении
не удалось распознать. Поля ввода и вывода логического выражения поддерживают операции
вставки и копирования. Нажав на кнопку ―Language‖ можно сменить
язык на английский или русский.
Используется следующий
формат ввода символов:
операция конъюнкции может быть представлена символами
‗&‘ или ‗*‘, дизъюнкции – символами ‗|‘ или ‗+‘, отрицания – символами ‗!‘ или ‗-‘. Операнду может быть дано любое имя, состоящее из любого
количества символов.
Заключение.
Программная реализация метода непосредственных преобразований для минимизации булевых функций опровергла существовавшее до проведенного исследования представление о предпочтительности табличного
метода при практическом использовании. Его временная
сложность оказывается такой же, как и для табличного метода, а трудозатраты на его программную реализацию оказались меньшими.
Вместе с тем представляет когнитивный
интерес использования в учебных
целях программных реализаций различных методов
минимизации булевых функций, включая
и метод Квайна. С практической точки зрения важным является
вопрос упрощения ввода в программу исходной
булевой функции многих переменных в сокращенном символическом виде, когда вместо полной булевой функции со всеми конституентами вводится лишь список их номеров. Отмеченные здесь высказывания являются
целью дальнейших исследований.
Список литературы
1. Глушань В.М. Математическая логика
и теория алгоритмов. Учебное пособие.
– 2-е изд., испр. и доп. – Таганрог: Изд-во ТТИ ЮФУ, 2009. – 236 с.
2.
Глушань В.М., Додонов А.Д., Тютюнников Р.В. Алгоритмические особенности минимизации булевых функций табличным
методом. Труды Конгресса
по интеллектуальным системам и информационным технологиям
«AIS-IT‘10». Научное издание в 4-х томах. – М.: Физматлит, 2010. – Т. 3., с. 236-245.
3.
Закревский А.Д., Топоров
Н.Р. Минимизация булевых функций
многих переменных в классе
ДНФ – итеративный
метод и программная реализация// Прикладная дискретная математика. № 1(3), Минск, 2009, с. 5-14.
4.
Karnaugh M. The map method for synthesis of combinational logic circuits. – «AIEE Journ. P.I. Communication and Electronics», 1953, v. 72, p. 593 – 598.