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: 15655 |
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. Формируется код Грея для 2. Выбирается переменная 3. Формируется пустая матрица 4. В цикле повторений в последнем столбце матрицы C следует найти наборы из двух соседних элементов, то есть тех, у которых вес Хэмминга равен 1. 4.1. Если в сгруппированном наборе имеется одна 1 и один 0, также 4.2. В ячейки матрицы D, которые соответ- ствуют индексам элементов найденного набора матрицы C, записывается некоторый заранее определяемый ключевой символ, например, знак « 4.3. Повторяются шаги 4.1 и 4.2. 5. Выполняется символьная запись булевой производной путем сопоставления значения параметров булевой функции, записанной в матрицу G, и оставшихся наборов по следующему правилу. В каждом наборе для любого помеченного знаком « Пример. Пусть Формирование матриц алгоритма для ¶F/¶x1 показано в таблице. Таблица
Результат символьного вычисления частной булевой производной по переменной xi по примеру:
Целесообразно рассмотреть одну из возможных конструкций неопределенного интеграла, отмечая особо, что многовариантная природа логических функций обусловливает необходимость осторожного подхода к вопросу формирования конструкции интеграла булевой функции в части равенства или эквивалентности реализующих его формул. При исследовании учитывались результаты практически единственной существующей в этой области работы [5], в которой интеграл булевой функции f от n переменных введен следующим образом:
Доопределим это понятие. Очевидно, что (1) не является логической переключательной функцией. Обозначим « Часть таблицы истинности логической функции содержит результат 1, а остальная часть дает в результате 0, поэтому целесообразно ввести неопределенные интегралы «результирующие 1» и «результирующие 0» в виде
Полный неопределенный булев интеграл существует тогда, когда найдутся независимые друг от друга дискретные функции
Алгоритм 2. Символьное вычисление булева интеграла. 1. Выполнить шаги алгоритма 1 для нахождения всех n частных производных заданной булевой функции с сохранением результатов. 2. Сформировать матрицу 3. Заполнить столбец 4. Заполнить столбец 5. Заполнить единицами все ячейки столбца 6. Выполнить символьную запись термов булева интеграла, аналогично п. 5 алгоритма 1, причем между термами использовать знак «+». 7. После группировки всех слагаемых, входящих в частную производную по переменной, выражение заключить в скобки и применить обозначение дифференциала по переменной. Для функции из ранее приводимого примера выполнение шагов алгоритма 2 приводит к следующей символьной записи: Алгоритмы 1 и 2 были реализованы в системе программирования Visual Studio.Net с применением языка программирования C#. Программный комплекс имеет структуру классов, показанную на рисунке 1, которая отображена в виде иерархической диаграммы классов использования, то есть класс, вызывающий методы других, находится выше по диаграмме, а предоставляющий методы – ниже. Класс WorkWithVariables предназначен для формирования массивов переменных, определения их числа, и в зависимости от результатов он позволяет обновлять таблицы истинности класса BoolAnalis и форму ввода данных. Методы класса DrawLogicalSxema, предназначенные для работы с интерфейсом пользователя, позволяют отобразить полученный результат в символьном виде и в виде модели контактной логической схемы. Методы класса ResolveDifferential предоставляют функции определения выражения производной по n переменным и позволяют получить значение производной при заданных значениях переменных. Класс ResolveIntegral, который использует методы класса ResolveDifferential, позволяет определить и минимизировать значения Integral_0 и Integral_1. Класс BoolAnalis содержит функции, основной задачей которых является вызов методов других классов для получения таблиц истинности и выражений исходной функции, булевой производной и интеграла, а также вызов методов работы с интерфейсом.
В разработанной программе для синтаксического распознавания строковых выражений использовался вычислительно эффективный метод рекурсивного спуска, модифицированный следующим образом. Основной идеей модификации является «зашивание» правил грамматики непосредственно в управляющие конструкции распознавателя. Идеи нисходящего разбора, принятые в 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?id=764&lang=en&like=1&page=article |
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