Journal influence
Bookmark
Next issue
Abstract:
Аннотация:
Authors: Chernov A.V. (avche@yandex.ru) - Rostov State Transport University, PL Rostovskogo Strelkovogo Polka Narodnogo Opolcheniya (Professor, Head of Chair), Rostov-on-Don, Russia, Ph.D, () - | |
Keywords: , , , , algorithmic support |
|
Page views: 16882 |
Print version Full issue in PDF (1.83Mb) |
Логическое дифференциальное и интегральное исчисления являются направлениями современной дискретной математики и находят свое применение в задачах динамического анализа и синтеза дискретных цифровых структур. Основным понятием логического дифференциального исчисления является производная булевой функции, представление о которой в виде булевой разности было получено еще в работах [1,2]. Булева производная по некоторым своим свойствам является аналогом производной в классическом дифференциальном исчислении. Заметим, что идеи об определении булевой производной вряд ли могли бы появиться без известной алгебраической нормальной формы и представления логической функции в виде полинома Жегалкина [3]. Развитие дифференциального исчисления в области дискретной математической логики происходило в нескольких направлениях [4], и к настоящему времени в этой области достигнуто немало результатов. Тем не менее, на наш взгляд, недостаточно исследованными остаются две важных нерешенных задачи: задача о символьных (нечисленных) аналитических преобразованиях логических функций в стиле компьютерных алгебр в области логического дифференциального исчисления и задача доопределения понятия о булевых интегралах и выполнения аналитических логических интегральных преобразований, пригодных для реализации в алгоритмах компьютерных алгебр. В данной работе обозначено решение поставленных задач, для чего авторами разработано алгоритмическое обеспечение и выполнена программная реализация алгоритмов. Программные системы символьных вычислений открыли новые широкие возможности для поддержки теоретических и прикладных научных исследований. На протяжении почти четырех последних десятилетий компьютерные алгебры, начиная с системы MASCYMA, совершенствуются, приобретают улучшенные функциональные возможности. В их числе такие известные реализации, как MAXIMA, AXIOM, GAP, DERIVE, SINGULAR, NUMPI, OCTAVE, PARI/GP, YASIMCA, YACAS, и алгебраические возможности пакетов MAPLE, MATHCAD, MATLAB, R и прочих менее распространенных программных продуктов. Несмотря на такое разнообразие систем и предлагаемых ими символьных преобразований, ни одна из них не располагает функциональными возможностями аналитических преобразований в области логического дифференциального и интегрального исчислений. Причина тому – имеющаяся разрозненность в применяемой терминологии, способах исследований в данной области, что, естественно, не снижает актуальности этой тематики, а лишь подчеркивает настоятельные требования разработки единой методологической основы такой технологии динамического анализа и синтеза цифровых структур. Обратимся к задаче символьного дифференцирования логических функций. Представляемый метод основан на нахождении частных булевых производных для полностью определенной логической функции. Алгоритм построен для производных ; его модификация для нахождения весьма незначительная. В алгоритме используется код Грея, но его построение не вызывает особых трудностей и подробно не обсуждается. Алгоритм 1. Символьное вычисление частных производных булевой функции. На входе алгоритма имеется булева функция от двоичных переменных. 1. Формируется код Грея для переменных и в столбец записываются значения исходной булевой функции f при соответствующих наборах аргументов. 2. Выбирается переменная , , относительно которой будет выполняться операция символьного дифференцирования. 3. Формируется пустая матрица , в которую затем записываются элементы в соответствии со следующими правилами. 4. В цикле повторений в последнем столбце матрицы C следует найти наборы из двух соседних элементов, то есть тех, у которых вес Хэмминга равен 1. 4.1. Если в сгруппированном наборе имеется одна 1 и один 0, также и значение булевой функции , то такой набор считается сменой полярности булевой производной функции f (в связи с ее известным свойством). 4.2. В ячейки матрицы D, которые соответ- ствуют индексам элементов найденного набора матрицы C, записывается некоторый заранее определяемый ключевой символ, например, знак «». 4.3. Повторяются шаги 4.1 и 4.2. 5. Выполняется символьная запись булевой производной путем сопоставления значения параметров булевой функции, записанной в матрицу G, и оставшихся наборов по следующему правилу. В каждом наборе для любого помеченного знаком «» элемента матрицы C выбираются переменные исходной булевой функции f, имеющие значение 1, которые затем включаются термами в выражение булевой функции, причем значение в терм не вносится. Пример. Пусть . Формирование матриц алгоритма для ¶F/¶x1 показано в таблице. Таблица
Результат символьного вычисления частной булевой производной по переменной xi по примеру: = . Целесообразно рассмотреть одну из возможных конструкций неопределенного интеграла, отмечая особо, что многовариантная природа логических функций обусловливает необходимость осторожного подхода к вопросу формирования конструкции интеграла булевой функции в части равенства или эквивалентности реализующих его формул. При исследовании учитывались результаты практически единственной существующей в этой области работы [5], в которой интеграл булевой функции f от n переменных введен следующим образом: . (1) Доопределим это понятие. Очевидно, что (1) не является логической переключательной функцией. Обозначим «» и «» операторы логического переключения булевой функции из состояния 0 в состояние 1 и из состояния 1 в состояние 0 соответственно. Тогда полная конструкция неопределенного булева интеграла будет записываться в виде: Часть таблицы истинности логической функции содержит результат 1, а остальная часть дает в результате 0, поэтому целесообразно ввести неопределенные интегралы «результирующие 1» и «результирующие 0» в виде , (2) . (3) Полный неопределенный булев интеграл существует тогда, когда найдутся независимые друг от друга дискретные функции и , имеющие не менее n реализаций, чтобы , в таком случае можно утверждать, что , если . Необходимым условием существования неопределенного булева интеграла можно считать . Теперь на основе алгоритма 1 нахождения частных производных и выражений (2) и (3) можно предложить алгоритм символьного вычисления булева интеграла. Алгоритм 2. Символьное вычисление булева интеграла. 1. Выполнить шаги алгоритма 1 для нахождения всех n частных производных заданной булевой функции с сохранением результатов. 2. Сформировать матрицу , заполнив столбцы по принципу кода Грея. 3. Заполнить столбец матрицы I символом 1, если вычисление по (2) дает в результате 1. 4. Заполнить столбец матрицы I сим- волом 0, если вычисление по (3) дает в результа- те 1. 5. Заполнить единицами все ячейки столбца матрицы I, если расстояние Хэмминга соседней с ними ячейке равно 1. 6. Выполнить символьную запись термов булева интеграла, аналогично п. 5 алгоритма 1, причем между термами использовать знак «+». 7. После группировки всех слагаемых, входящих в частную производную по переменной, выражение заключить в скобки и применить обозначение дифференциала по переменной. Для функции из ранее приводимого примера выполнение шагов алгоритма 2 приводит к следующей символьной записи: Алгоритмы 1 и 2 были реализованы в системе программирования Visual Studio.Net с применением языка программирования C#. Программный комплекс имеет структуру классов, показанную на рисунке 1, которая отображена в виде иерархической диаграммы классов использования, то есть класс, вызывающий методы других, находится выше по диаграмме, а предоставляющий методы – ниже. Класс WorkWithVariables предназначен для формирования массивов переменных, определения их числа, и в зависимости от результатов он позволяет обновлять таблицы истинности класса BoolAnalis и форму ввода данных. Методы класса DrawLogicalSxema, предназначенные для работы с интерфейсом пользователя, позволяют отобразить полученный результат в символьном виде и в виде модели контактной логической схемы. Методы класса ResolveDifferential предоставляют функции определения выражения производной по n переменным и позволяют получить значение производной при заданных значениях переменных. Класс ResolveIntegral, который использует методы класса ResolveDifferential, позволяет определить и минимизировать значения Integral_0 и Integral_1. Класс BoolAnalis содержит функции, основной задачей которых является вызов методов других классов для получения таблиц истинности и выражений исходной функции, булевой производной и интеграла, а также вызов методов работы с интерфейсом. Интерфейс программы и результаты исполнения показаны на рисунках 2 и 3. В разработанной программе для синтаксического распознавания строковых выражений использовался вычислительно эффективный метод рекурсивного спуска, модифицированный следующим образом. Основной идеей модификации является «зашивание» правил грамматики непосредственно в управляющие конструкции распознавателя. Идеи нисходящего разбора, принятые в LL(1)-грамматиках, в нем полностью сохраняются: происходит последовательный просмотр входной строки слева направо; очередной символ входной строки является основанием для выбора одной из правых частей правил группы при замене текущего нетерминального символа; терминальные символы входной строки и правой части правила взаимно уничтожаются; обнаружение нетерминального символа в правой части рекурсивно повторяет этот же процесс. В методе рекурсивного спуска идеи претерпевают такие изменения: каждому нетерминальному символу соответствует отдельная вычислительная подпрограмма, распознающая, выбирающая и закрывающая одну из правых частей правила, имеющего в левой части этот нетерминальный символ (то есть для каждой группы правил пишется свой распознаватель); во входной строке имеется указатель (индекс) на текущий закрываемый символ. Этот символ и является основанием для выбора необходимой правой части правила. Сам выбор встроен в распознаватель в виде алгоритмических конструкций языков программирования if и switch. Правила выбора базируются на построении множеств выбирающих символов, как это принято в LL(1)-грамматике; просмотр выбранной части реализован в тексте процедуры-распознавателя путем сравнения ожидаемого символа правой части и текущего символа входной строки; если в правой части ожидается терминальный символ и он совпадает с очередным символом входной строки, то символ во входной строке пропускается, а распознаватель переходит к следующему символу правой части; несовпадение терминального символа правой части и очередного символа входной строки свидетельствует о синтаксической ошибке; если в правой части встречается нетерминальный символ, то для него необходимо вызвать аналогичную распознающую подпрограмму. Список литературы 1 Reddy, S.M. Easily Testable Realizations for Logic Functions // IEEE Trans. Computers. Vol. 21, no. 11, Nov., 1972. 2 Muller, D.E. Application of Boolean algebra to switching circuits design and to error detection // IRE Trans. Electron. Comp. Vol. EC-3, 1954., р. 6-12. 3 Жегалкин И.И. О технике вычислений предложений в символической логике. // Матем. сб. - 1927. - № 34. - С. 9-28. 4 Янушкевич С., Бохманн Д., Станкович Р., Тошич Ж., Шмерко В. Логическое дифференциальное исчисление: достижения, тенденции и приложения. // Автоматика и телемеханика. - 2000. - № 6. - С. 155-170. 5 Tucker, J.H. Tapia, M.A. Bennett, A.W. Boolean Integral Calculus for Digital Systems // IEEE Trans. On Comp., vol. 34, issue 1, Jan. 1985, p. 78-81. |
Permanent link: http://swsys.ru/index.php?page=article&id=764&lang=en |
Print version Full issue in PDF (1.83Mb) |
The article was published in issue no. № 2, 2008 |
Perhaps, you might be interested in the following articles of similar topics:
- Алгоритмическое обеспечение адаптивной системы тестирования знаний
- Алгоритмическое обеспечение обработки данных процесса структурирования эластомерного композита с целью решения задачи управления
- Алгоритмическое обеспечение программного комплекса технического обслуживания с контролем уровня надежности средств обеспечения полетов
Back to the list of articles