Новости
09.05.2023
с Днём Победы!
07.03.2023
Поздравляем с Международным женским днем!
23.02.2023
Поздравляем с Днем защитника Отечества!
Оплата онлайн
При оплате онлайн будет
удержана комиссия 3,5-5,5%








Способ оплаты:

С банковской карты (3,5%)
Сбербанк онлайн (3,5%)
Со счета в Яндекс.Деньгах (5,5%)
Наличными через терминал (3,5%)

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА НЕПОСРЕДСТВЕННЫХ ПРЕОБРАЗОВАНИЙ ДЛЯ МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ В СДНФ ИЛИ СКНФ

Авторы:
Город:
Таганрог
ВУЗ:
Дата:
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.