Систолическая технология реализации функций порядковой логики
Порядковая логика – математический аппарат, широко применяемый при решении многих задач обработки, преобразования непрерывной информации. Рекуррентные соотношения для математической модели систолического алгоритма реализации функций порядковой логики.
Рубрика | Математика |
Вид | статья |
Язык | русский |
Дата добавления | 22.08.2020 |
Размер файла | 27,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Систолическая технология реализации функций порядковой логики
Андреев Д.В.
Порядковая логика [1] - математический аппарат, широко применяемый при решении многих задач обработки и преобразования непрерывной (аналоговой) информации, в частности, таких задач, как сортировка континуальных данных, фильтрация, динамический анализ дискретных автоматов, сжатие информации и др.
Алгебра порядковой логики образована системой , где - множество континуальных переменных (действительных чисел), на котором задана операция выбора элемента определенного ранга .
Произвольная n-арная операция (функция) порядковой логики может быть явно выражена через базовые непрерывно-логические (НЛ) операции в следующей дизъюнктивной (конъюнктивной) нормальной форме [1]:
, (1)
где символами и , обозначены соответственно НЛ-дизъюнкция и НЛ-конъюнкция; ; , ; есть количество неповторяющихся НЛ-конъюнкций (НЛ-дизъюнкций ), определяемое как число сочетаний из n по q.
Классические способы реализации функций порядковой логики основаны на вычислении выражений (1) [2,3]. Однако, при реализации указанных функций более перспективным представляется ориентация на систолические методы обработки информации, использующие, как известно, рекуррентную процедуру решения поставленной задачи. Значительный интерес к этим методам обусловлен их высокой производительностью и непосредственной аппаратурной воспроизводимостью однородными вычислительными средствами (систолическими матрицами), эффективно воплощаемыми в однокристальном исполнении [4-6].
В работе [7] предложены рекуррентные соотношения
; , (2)
представляющие математическую модель систолического алгоритма реализации функций порядковой логики. Здесь ; , - ранг переменной в кортеже континуальных переменных ; ; ; ; ; . Существенным недостатком этой математической модели является большой объем вычислений, поскольку .
Введем на множестве континуальных переменных рекуррентную НЛ-функцию вида
, (3)
где ; ; ; . В работе [8] доказано следующее утверждение.
Утверждение 1. Для любой функции имеет место равенство
. (4)
Утверждение 2. Для любой функции () имеет место равенство
, (5)
где
(6)
есть j-я простая симметричная НЛ-функция, зависящая от i аргументов . В (6) (); есть количество неповторяющихся НЛ-конъюнкций , определяемое как число сочетаний из i по j.
При доказательстве данного утверждения воспользуемся методом математической индукции. Когда утверждение 2 справедливо, поскольку согласно (3) получаем
;
;
…
.
Предположим теперь, что утверждение 2 верно для некоторого , то есть
; ;…; . (7)
Тогда при с учетом (3), (4) и (6), (7) можно записать
;
;
… (8)
.
Из соотношений (8) следует, что равенство (5) остается справедливым и для . Утверждение 2 доказано.
С учетом принципа двойственности и утверждения 2 нетрудно получить следующее равенство:
, (9)
где есть оператор двойственного преобразования. Заметим, что
(10)
и
, (11)
причем соответственно ; и - количество неповторяющихся НЛ-дизъюнкций .
Если , , то выражение (6) совпадет с дизъюнктивной нормальной формой (1.1). Условие совпадения выражения (11) с конъюнктивной нормальной формой (1.2) определяется как , . Таким образом, согласно (5) и (6) (согласно (9) и (11)) воспроизводится операция
.
Последние равенства позволяют сделать вывод, что соотношения (3) и (10) могут быть использованы для реализации произвольных n-арных функций порядковой логики. При этом в силу рекуррентности соотношений (3), (10) алгоритмы такой реализации будут систолическими. Здесь уместно отметить, что математические модели систолических алгоритмов реализации функций , представляемые выражениями (3), (10) при (указанное обычно всегда выполняется на практике), свободны от упомянутого в начале статьи недостатка, поскольку в этих моделях .
Литература
порядковый логика математический систолический
1. Левин В.И. Бесконечнозначная логика в задачах кибернетики. - М.: Радио и связь, 1982. - 175 с.
2. Андреев Д.В. Принципы организации реляторной комбинаторной сети с распределенным кодовым управлением// Информационные технологии. - 2001. - №8. - С.17-20.
3. Андреев Д.В. Рекуррентные реляторные процессоры: математические модели и схемная реализация// Приборы и системы. Управление, контроль, диагностика. - 2001. - №10. - С.38-41.
4. Кухарев Г.А., Шмерко В.П., Зайцева Е.Н. Алгоритмы и систолические процессоры для обработки многозначных данных. - Мн.: Наука и техника, 1990. - 296 с.
5. Кун С. Матричные процессоры на СБИС: Пер. с англ. - М.: Мир, 1991. - 672 с.
6. Систолические структуры: Пер. с англ./ Под ред. У. Мура, Э. Маккейба, Р. Уркхарта. - М.: Радио и связь, 1993. - 416 с.
7. Патент РФ №2172980. Ранговый селектор/ Д.В.Андреев, Е.В.Кирюхин. - Заявлено 16.05.2000. - Опубликовано 27.08.2001. - Бюл. №24.
8. Андреев Д.В. Об одном систолическом алгоритме сортировки континуальных данных// Материалы 2-й международной науч.-техн. конф. «Новые методологии проектирования изделий микроэлектроники». - Владимир: ВГУ, 2003. - С.93-96.
Размещено на Allbest.ru
...Подобные документы
Основные аксиомы и тождества алгебры логики. Аналитическая форма представления булевых функций. Элементарные функции алгебры логики. Функции алгебры логики одного аргумента и формы ее реализации. Свойства, особенности и виды логических операций.
реферат [63,3 K], добавлен 06.12.2010История возникновения и развития математической логики как раздела математики, изучающего математические обозначения и формальные системы. Применение математической логики в технике и криптографии. Взаимосвязь программирования и математической логики.
контрольная работа [50,4 K], добавлен 10.10.2014Применение методов математической логики и других разделов высшей математики в задачах теоретической лингвистики при анализе письменной речи на русском и английском языках. Исследование и распознавание речевых единиц. Методы математической логики.
реферат [39,8 K], добавлен 01.11.2012Основы формальной логики Аристотеля. Понятия инверсии, конъюнкции и дизъюнкции. Основные законы алгебры логики. Основные законы, позволяющие производить тождественные преобразования логических выражений. Равносильные преобразования логических формул.
презентация [67,8 K], добавлен 23.12.2012Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.
контрольная работа [133,5 K], добавлен 08.06.2010Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
контрольная работа [345,3 K], добавлен 29.11.2010Этапы развития логики. Имена ученых, внесших существенный вклад в развитие логики. Ключевые понятия монадической логики второго порядка. Язык логики предикатов. Автоматы Бучи: подход с точки зрения автоматов и полугрупп. Автоматы и бесконечные слова.
курсовая работа [207,1 K], добавлен 26.03.2012Математическая теория нечетких множеств и нечеткая логика как обобщения классической теории множеств и классической формальной логики. Сферы и особенности применения нечетких экспертных систем. Анализ математического аппарата, способы задания функций.
презентация [1,0 M], добавлен 17.04.2013Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
учебное пособие [702,6 K], добавлен 29.04.2009Определение формулы исчисления высказываний, основные цели математической логики. Построение формул алгебры высказываний. Равносильность формул исчисления высказываний, конъюнктивная и дизъюнктивная нормальная форма. Постановка проблемы разрешимости.
контрольная работа [34,3 K], добавлен 12.08.2010Основные определения математической логики, булевы и эквивалентные функции. Общие понятия булевой алгебры. Алгебра Жегалкина: высказывания и предикаты. Определение формальной теории. Элементы теории алгоритмов, рекурсивные функции, машина Тьюринга.
курс лекций [651,0 K], добавлен 08.08.2011Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Применение системы MathCAD при решении прикладных задач технического характера. Основные средства математического моделирования. Решение дифференциальных уравнений. Использование системы MathCad для реализации математических моделей электрических схем.
курсовая работа [489,1 K], добавлен 17.11.2016Операции над логическими высказываниями: булевы функции и выражение одних таких зависимостей через другие. Пропозициональные формулы и некоторые законы логики высказываний. Перевод выражений естественного языка на символическую речь алгебры логики.
контрольная работа [83,3 K], добавлен 26.04.2011Изложение теории бесселевых функций, их приложения к уравнениям математической физики. Виды цилиндрических функций. Применение бесселевых функций в математической физике на примере некоторых задач. Уравнение Лапласа в цилиндрических координатах.
дипломная работа [226,4 K], добавлен 09.10.2011Понятие формальной системы. Основные понятия логики первого порядка. Доказательство неразрешимости проблемы остановки. Машина Тьюринга, ее структура. Вывод неразрешимости логики первого порядка из неразрешимости проблемы остановки и методом Геделя.
курсовая работа [243,0 K], добавлен 16.02.2011Порядок доказательства истинности заключения методом резолюции (с построением графа вывода пустой резольвенты) и методом дедуктивного вывода (с построением графа дедуктивного вывода). Выполнение бинарных операций и составление результирующих таблиц.
курсовая работа [185,3 K], добавлен 24.05.2015Литералы рассуждения и вопрос об их отрицаниях. Математическая модель отрицания для рассуждения, содержащего связную совокупность суждений. Отрицания в математической логике и дополнения в алгебре множеств. Интерпретации формул математической логики.
контрольная работа [40,8 K], добавлен 03.09.2010Основная функционально полная система логических функций. Законы алгебры логики в основной функционально полной системе и их следствия. Переместительный и распределительный законы. Закон инверсии (правило Де Моргана). Системы логических функций.
реферат [40,5 K], добавлен 17.11.2008Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011