ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА НЕПОСРЕДСТВЕННЫХ ПРЕОБРАЗОВАНИЙ ДЛЯ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ В СДНФ ИЛИ СКНФ
Несмотря на то, что основные подходы к минимизации булевых функций были предложены ещѐ в середине прошлого века [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.
1. Глушань В.М. Математическая логика и теория алгоритмов. Учебное пособие. – 2-е изд., испр. и доп. – Таганрог: Изд-во ТТИ ЮФУ, 2009. – 236 с.
2. Глушань В.М., Додонов А.Д., Тютюнников Р.В. Алгоритмические особенности минимизации булевых функций табличным методом. Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT‘10». Научное издание в 4-х томах. – М.: Физматлит, 2010. – Т. 3., с. 236-245.
3. Закревский А.Д., Топоров Н.Р. Минимизация булевых функций многих переменных в классе ДНФ – итеративный метод и программная реализация// Прикладная дискретная математика. № 1(3), Минск, 2009, с. 5-14.