Методы преобразования и передачи информации в автоматизированных системах управления на основе решения логических уравнений и построения систем многозначной алгебры логики тема диссертации и автореферата по ВАК РФ 05.13.06, кандидат технических наук Калинушкина, Марина Юрьевна

• Калинушкина, Марина Юрьевна
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Калинушкина, Марина Юрьевна

ВВЕДЕНИЕ.

1 .Общие сведения об алгебрах и логиках.

1.1. Понятие о дискретных и конечнозначных алгебрах логики.

1.2. Элементарные многозначные функции.

1.3. Операция суперпозиции многозначных логических функций.

1.4. Три основные проблемы, возникающие при синтезе логических схем.

1.5. Понятие о регулярных формах в конечнозначной алгебре логики.

1.6. Функциональная полнота полиномиальных предоставлений

2. Асимметричные алгебры с парой бинарных операций.

2.1. Вводные замечания.

2.2. Определение асимметричных алгебр с парой бинарных операций.

2.3. Некоторые обобщения асимметричных алгебр.

3. Регулярные аналитические представления многозначных логических функций в асимметричных алгебрах.

3.1. Обобщенные регулярные формы.

3.1.1. Постановка задачи.

3.1.2. Малоуровневые регулярные формы.

3.1.3. Сведение задачи о регулярных представлениях функций многозначной логики к задаче о разрешимости системы многозначных уравнений.

3.2. Аналитические представления многозначных функций в асимметричных алгебрах-изобипоидах.

32.1. "Диагональная" система (базис).

3.2.2. "Треугольная" система (базис).

4. Разработка методов решения уравнений и систем многозначной алгебры логики.

4.1. Введение.

4.1.1. Классификация логических уравнений и систем уравнений

4.1.2. Приведение неоднородного логического уравнения к равносильному однородному уравнению.

4.1.3. Укрупнение системы однородных логических уравнений в одно равносильное уравнение.

4.2. Троичные логические уравнения.

42.1. Числовые троичные логические уравнения с одним неизвестным.

4.2.2. Буквенное троичное логическое уравнение с одним неизвестным.

4.2.2.1. Прямой метод решения троичного логического уравнения.

4.2.2.2. Основной метод решения троичного логического уравнения.

4.2.3. Системы троичных логических уравнений.

4.3. Понятие о решении конечнозначных логических уравнений

4.3.1. Обобщение основного метода решения.

4.3.2. Основной метод решения.

4.4. Использование логических уравнений в теории цифровых многозначных схем.

4.4.1. Анализ многозначных схем с обратными связями.

4.4.2. Синтез многозначных триггерных последовательностных схем.

5. Примеры аналитических представлений многозначных функций в асимметричных алгебрах.

5.1. Постановка задачи.

5.2. Реализация "диагонального" базиса (квазиполиномом - в интерполяционной форме Лагранжа).

5.3. Реализация "треугольного" базиса (квазиполиномом - в интерполяционной форме Ньютона).

5.4. Реализация асимметричных логико-арифметических базисов.

Введение диссертации (часть автореферата) на тему «Методы преобразования и передачи информации в автоматизированных системах управления на основе решения логических уравнений и построения систем многозначной алгебры логики»

Хорошо известно широкое распространение двоичной логики в теории и практике современной вычислительной, информационно-измерительной и управляющей технике.

Это объясняется не только простотой двоичных элементов, но и наличием достаточно разработанного математического аппарата двоичной логики.

В то же время двоичное кодирование не является эффективным при обработке разнообразной информации. Это обусловило широкое и интенсивное развитие недвоичной логики: многозначной (конечной), бесконечнозначной, непрерывной, нечеткой.

Очевидно, многозначная элементная база и недвоичные методы представления информации - следующий шаг в развитии средств сбора, обработки, преобразования, передачи информации и т.п.

Начала теории конечных (дистрибутивных) алгебр восходят к XVII и XVIII векам и связаны с именами величайших математиков П.Ферма, Л.Эйлера, Ж.-Л.Лагранжа, А.-М.Лежандра, К.-Ф.Гауса и др. Однако наиболее изящные ветви конечных (дистрибутивных) алгебр - конечные поля и двоичная алгебра логики, имеющие в настоящее время великое множество приложений в различных областях науки и техники, были разработаны в прошлом веке соответственно французским учащимся Приготовительной школы гениальным Эвари-стом Галуа (1811-1831), погибшим в двадцатилетнем возрасте на дуэли, и английским провинциальным учителем Джорджем Булем (1815-1864); в память об этих ученых конечные поля называются полями Галуа, а двоичная алгебра логики - булевой алгеброй логики [1].

Исследования Э.Галуа и Дж.Буля намного опередили время: практическое использование теории конечных полей и двоичной алгебры логики стало возможным лишь во второй половине нашего столетия в связи с потребностями новых наук - теории информации, вычислительной техники и смежных дисциплин.

История помехоустойчивой информации началась в 1948 году со статьи К.Шеннона. В настоящее время наиболее мощные коды для автоматического обнаружения и исправления многочисленных ошибок в канале связи строятся на основе теории полей Галуа [2,3].

Общеизвестны достижения в области кибернетики, микроэлектроники, вычислительной и цифровой измерительной техники, радиоэлектроники и т.д., полученные на основе использования схем двоичной логики. Однако возможностей этой логики уже недостаточно при решении ряда новых задач, в том числе далеко не технических, например, в экономике, в медицинской диагностике, при моделировании социальных процессов и др.

В настоящее время двоичная алгебра логики, по определению задаваемая на множестве из двух элементов, обобщена в следующих направлениях.

- многозначная (&-значная логика), определяемая на конечном множестве из к элементов;

- непрерывная, или бесконечнозначная, логика, задаваемая на непрерывном отрезке, т.е. на бесконечном множестве (мощности континуум);

- гибридная логика, вводимая на множестве, в котором часть объектов непрерывна, а другая - дискретна;

- нечеткая логика, определяемая на так называемом нечетком множестве.

Многозначная логика, начавшая свое развитие в начале нашего столетия с работ Я.Лукасевича 1921 год, А.Тарски 1930 год и С.Клини 1938 год, должна по прогнозам специалистов придти на смену двоичной логике, так как дальнейшее качественное повышение физико-технологических показателей цифровых микроэлектронных схем возможно лишь за счет увеличения "значности" логики, в частности, для компьютеров 5-ого поколения. Поток публикаций по многозначной логике не ослабевает уже полвека - работы [4-10] и многие другие.

Бесконечнозначная логика, предложенная Р.Мак-Нотоном в 1951 году, нашла свое применение для решения задач кибернетики (анализ динамических процессов в цифровых автоматах, обработка графической информации, принятие коллективного решения и др.), в теории вероятностей, для комбинаторной оптимизации, при поиске в массивах и прогнозировании надежности и т.п. [И]

Гибридная логика, введенная С.Гинзбургом в 1968 году, используется для описания поведения гибридных (цифро-аналоговых систем) [12].

Наконец, нечеткая логика, которая зиждется на понятии нечеткого множества, введенного Л.Заде в 1965 году, вызвала нескончаемый поток научно-технических публикаций: она используется не только в традиционных для алгебры логики областях (синтез вычислительных систем, в частности, при построении компьютеров очередного поколения), но и находит применение в бизнесе, при построении экспертных систем, и даже для нечеткого программного обеспечения [13].

Как показано в работе [14], наиболее важный класс нечеткой логики сводится к одной из разновидностей многозначной алгебры логики - алгебре Кли-ни.

Все перечисленные алгебры и логики < К; ©,* > задаются на некотором множестве К с парой дистрибутивно связанных бинарных операций © и * . Однако свойство дистрибутивности операции, хотя и является весьма важным, в ряде случаев - "непозволительная роскошь".

В данной диссертационной работе рассматриваются асимметричные алгебры логики, предложенные в статье [15] и позволяющие приблизить решение некоторые проблемы . Так, использование подобных алгебр совместно с решением логических уравнений [16] позволяет строить многозначные микросхемы [17-19] более простые, чем основанные на традиционной дистрибутивной логике.

Однако ряд математических проблем остается неразрешенными. Сюда относятся прежде всего такие актуальные вопросы:

1) Решение уравнений многозначной логики и их систем. Как известно [20], логические уравнения являются мощным инструментом для анализа и синтеза двоичных логических схем. Тем более при построении многозначных логических схем необходима разработка математического аппарата для решения уравнений многозначной логики.

Литература по этим вопросам крайне скудна.

Проблема Ml - разработка математического аппарата для решения логических уравнений многозначной логики и их систем; использование логических уравнений в теории синтеза схем, особенно с памятью.

2) Регулярные формы представления схем (функций) многозначной логики - это важнейшая проблема, которой занимаются многие ученые уже не одно десятилетие. И тем не менее все же не все вопросы решены при представлении функций в виде некоторого полинома (функциональная полнота полиномиальных представлений различными наборами функций).

Проблема №2 - разработка математического аппарата для полиномиального представления произвольной функции многозначной логики.

3) Развитие предыдущей темы - обобщенные регулярные полиномиальные формы. Имеется в виду тот случай, когда k (значностъ логики) не является простым числом q и не представимо в виде qr (г - натуральное число). Другими словами, тот случай, когда конечное поле Галуа GF(k= qr) не существует. Как быть в этом случае? Приходится разрабатывать новые алгебры и формы, снимая те или иные аксиомы со свойств бинарных операций.

Проблема №3 -систематическое изучение асимметричных алгебр и мало-уровневых форм представления логических функций; сведение задачи о подобных регулярных представлениях к задаче о разрешимости системы уравнений, аналитическое квазиполиномиальное представление многозначных функций в различных (новых) асимметричных базисах, в том числе в логико-алгебраических.

В диссертации рассматриваются некоторые важные вопросы математических основ построения систем многозначной логики для преобразования и передачи информации: регулярные формы в конечнозначной алгебре логики, новые асимметричные алгебры логики с двумя бинарными операциями, обобщенные регулярные формы в асимметричных алгебрах логики, в том числе малоуровневые регулярные формы, решение многозначных уравнений и их систем.

Решение вопросов построения систем многозначной логики имеет большое значение как для теории, так и для практики. В настоящее время во всем мире опубликовано огромное количество работ по многозначной логике.

За последние годы достигнуты большие успехи в разработке и серийном освоении цифровых интегральных микросхем, которые используются в аппаратуре самого различного назначения - вычислительно-управляющих системах, информационно-измерительных приборах, приемо-передающих средствах и в другой кибернетической, измерительной и радиотехнической аппаратуре.

Анализ и синтез дискретных и гибридных (аналого-цифровых) вычислительных и управляющих устройств; систем сбора, записи-воспроизведения, преобразования, передачи и обработки информации; исследование динамики (переходных процессов) и надежности автоматов; поиск их неисправностей; помехоустойчивое кодирование с контролем (обнаружением и исправлением) ошибок; проектирование цифровых микроэлектронных (в частности, многозначных) логических систем и т.д. - вот далеко неполный перечень научных проблем и технических задач, требующих использования конечной алгебры, дискретной и непрерывной логики.

Поэтому в настоящее время стоит сложная и чрезвычайно важная задача: проектирования цифровой микроэлектронной аппаратуры очередного поколения на базе многозначных элементов, находящихся, как правило, в стадии разработки и освоения. При этом центр тяжести смещается на стадию логического проектирования на основе формальных методов синтеза.

Математической базой проектирования многозначных логических устройств и систем является многозначная алгебра логики на конечных множествах - дискретная и непрерывная.

Однако, многие разделы конечной алгебры и многозначной логики в области связи, радиотехники, информатики, автоматического управления, кибернетики, аналого-цифровой измерительной техники, изучены явно недостаточно.

В данной работе излагаются методы синтеза - канонические и полиномиальные и представления логических устройств, методы решения логических многозначных (троичных и четырехзначных) уравнений и их использования в теории цифровых схем. А также рассматриваются регулярные представления многозначных функций в асимметричных алгебрах, практические примеры аналитических представлений и схемной реализации многозначных функций в новых ( предложенных в работе) асимметричных алгебрах.

Многие работы по алгебре и логике опираются на классические результаты, полученные гениальными учеными прошлого века Джоржем Булем и Эва-ристом Галуа, а начала теории восходят к XVIII и даже XVII векам и связаны с именами выдающихся математиков прошлого: П.Ферма, Л.Эйлера, Ж.Лагранжа, А.Лежандра, Ф.Гаусса и других. Среди многочисленных работ 8 ученых нашего века можно выделить результаты, полученные И.Розенбергом, С.Клини, Э.Постом.

Многие вопросы многозначной логики развиты в работах В.Россера, А-Тьюкетта, С.Яблонского, А.Кузнецова, Дж.Слупецкого, А.Саломаа, В.Кудрявцева, О.Лупанова, Д.Поспелова, К.Самофалова, В.Левина, В.Сигорского, М.Ракова, В.Рабиновича, В.Кэндела, В.Тузова, В.Варшавского, Ю. Иваськива, В.Горбатова и др. По нечёткой логике - Л.Заде, А.Кофмана, А.Кандела, Т.Тэрано, К.Асана, К.Сугэмо.

Целью работы является разработка методов преобразования и передачи информации в автоматизированных системах управления на основе решения логических уравнений и построения систем многозначной аалгебры логики. Для достижения поставленной цели необходимо решить следующие задачи исследования:

1. Анализ регулярных форм (в том числе предлагаемых) для многозначных функций, а также полиномиальных представлений в троичной и четырехзначной алгебре логики, их достоинств и недостатков.

2. Разработка и анализ новых (предлагаемых автором) асимметричных алгебр многозначной логики, включая малоуровневые представления.

3. Разработка методов решения многозначных уравнений, в том числе троичной и четырехзначной алгебры логики.

Заключение диссертации по теме «Автоматизация и управление технологическими процессами и производствами (по отраслям)», Калинушкина, Марина Юрьевна

ЗАКЛЮЧЕНИЕ

Диссертация направлена на решение актуальной задачи разработки новых перспективных методов и средств для существенного повышения эффективности процессов проектирования аппаратуры автоматизированных систем управления самого различного назначения -вычислительно-управляющих систем, информационно-измерительных приборов, приемо-передающих средств и другой кибернетической, измерительной и радиотехнической аппаратуры.

Основные научные и практические результаты, полученные в работе, состоят в следующем:

- Предложены новые полиномиальные представления многозначных (в том числе троичных и четырехзначных) логических функций;

- Разработаны новые асимметричные алгебры с двумя бинарными операциями: асимметричные кольца, асимметричные тела, асимметричные поля и их разновидности;

- Предложены новые обобщенные регулярные формы в асимметричных алгебрах логики и практические примеры методов преобразования и передачи информации в автоматизированных системах управления на основе аналитических представлений многозначных функций в асимметричных алгебрах;

- Впервые разработаны методы решения многозначных логических уравнений и их систем.

Научная новизна работы заключается в следующем:

- Доказана теорема о равносильности однородного многозначного логического уравнения с произвольными коэффициентами и однородного многозначного уравнения с двоичными коэффициентами; -Разработаны регулярные аналитические представления многозначных логических функций в асимметричных алгебрах логики;

-Доказана возможность сведения задачи о регулярных представлениях функций многозначной логики к задаче о разрешимости системы многозначных уравнений;

-Разработаны методы синтеза многозначных триггерных последовательностных схем.

Достоверность результатов, обоснованность выводов изложенных в диссертации подтверждается выбором адекватного математического аппарата многозначной логики.

Значение результатов для теории и практики:

- Разработаны методы решения многозначных логических уравнений и синтеза многозначных комбинационных устройств;

- Разработаны методы анализа и синтеза многозначных схем с обратными связями;

01

- Разработаны методы синтеза схем многозначной логики для устройств преобразования и передачи информации в автоматизированных системах управления; разработанные методы позволяют улучшить процессы проектирования устройств;

- Разработаны малоуровневые аналитические представления многозначных логических функций в асимметричных алгебрах.

Список литературы диссертационного исследования кандидат технических наук Калинушкина, Марина Юрьевна, 2001 год

1. Биркгоф Г., Барти Т. Современная прикладная алгебра. - М: Мир, 1976. -400 с.

2. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. -576 с.

3. Мугтер В.М. Основы помехоустойчивой телепередачи информации. — Л.: Энергоатомиздат, 1990.-288 с.

4. Rosser S., Tuquette A. Many-valued logic. Amsterdam, 1952. - 124 с.

5. Зиновьев А.А. Философские проблемы многозначной логики. М.,1960-81 с.

6. Самофалов К.Г. Цифровые многозначные элементы и структуры. Киев: Вшца школа, 1974. - 168 с.

7. Раков М.А Реализация многозначных структур автоматики. Киев, 1976. -350 с.

8. Rine D. (ed). Computer science and multiple-valued logic. Amsterdam, 1984. -641c.

9. Proceeding of the 4th -14й1 International Symposium on multiple-valued logic (ISMVL). N.Y.,1974 -1984.

10. Поспелов Д.А. Логические методы анализа и синтеза схем, М.: Энергия, 1974.-368 с.

11. И. Левин В.И. Бесконечнозначная логики в задачах кибернетики. М.: Радио и связь, 1982. -176 с.

12. Гинзбург С.А., Любарский Ю.Я. Функциональные преобразователи с аналого-цифровым представлением информации. М.: Энергия, 1973. -136 с.

13. Прикладные нечеткие системы. / Ред. Т.Тэрано и др. М.: Мир, 1993. -368с.

14. Mulcaidono М. A set of independent and complete axioms for a fuzzy algebra (Kleene algebra) //ISMVL (см. 9.), 1981.-27-37 p.

15. Муттер В.М. Недистрибутивные абстрактные алгебры для аналитического представления функций многозначной логики. ВИНИТИ № 2895, 1982. -22 с.

16. Муттер В.М. Уравнения многозначной и нечеткой (дискретной и непрерывной) логики. Доклад на II Международной конференции. Актуальные проблемы фундаментальных наук. М.: МВТУ, 1994. - 6 с.

17. Муттер В.М. Регулярные аналитические (интерполяционные) представления функций многозначной логики в недистрибутивных и в ассиметриче-ких алгебрах. ВИНИТИ № 1279,1982. 12 с.

18. Муттер В.М. Представление функций многозначной логики в недистрибутивных логико-алгебраических базисах. ВИНИТИ № 2893,1982. 11 с.

19. Муттер В.М. Малоуровневые представления функций многозначной логики. ВИНИТИ № 2894,1982. 22 с.10Ь

20. Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства: Учебное пособие для втузов. СПб.: Политехника, 1996. - 885 с.

21. Муттер В.М., Иванова И.В. Проблема функциональной полноты в алгебре многозначной логики (необходимые и достаточные условия) с точки зрения абстрактной теории Галуа. // Проблемы системотехники и АСУ.- Л.: СЗПИ, 1991.-143-171 с.с.

22. Курош А.Г. Лекции по общей алгебре. М.: Наука, 1962.

23. Курош А.Г. Курс высшей алгебры. М.: Наука, 1971.

24. Горенбургов М.А., Муттер В.М., Калинушкина М.Ю. Методы нечеткой логики в информатизации предпринимательства (доклад и тезисы).- СПб.: УЭФ, 1996.3с.

25. Куликов Л.Я. Алгебра и теория чисел. -М.: Высшая школа, 1979. -559 с.

26. Муттер В.М., Иванова И.В. Решение уравнений троичной и четырехзначной логики. ВИНИТИ № 506,1996. 9 с.

27. Муттер В.М., Иванова И.В. и др. Устройства многозначной логики на формальных нейронах (в недистрибутивных логико-алгебраических базисах). ВИНИТИ №3513, 1989.-19 с.

28. Муттер В.М., Иванова И.В. Преобразование Ганкеля-Теплица. ВИНИТИ №468, 1995.-42 с.

29. Мкртчян С.О. Проектирование логических устройств ЭВМ на нейронных элементах. -М.: Энергия, 1977.-200 с.

30. Моделирующие системы с многозначным и гибридным кодированием /Под ред. М.А.Ракова-Киев: Наукова думка, 1980.

31. Муттер В.М., Боброва Л.В. и др. Устройство для вычисления полинома. Авторское свидетельство № 1179323, 1985.

32. Муттер В.М., Иванова И.В., Калинушкина М.Ю., Холкин В.Ю. Некоторые методы синтеза цифровых схем многозначной логики. Деп. в ВИНИТИ 1997. №2157, 31 с.

33. Закревский А.Д. Логические уравнения. Минск, 1975.

34. Иваськив Ю.Л. Принципы построения многозначных физических схем.-Киев: Наукова думка, 1971.

35. Клини С.К. Математическая логика.-М.: Мир, 1973.

36. Кметь А.Б. Четырехзначная логика. Реализация функций.-М.: 1991.

37. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.-М.: Энергоатомиздат, 1988.-480 с.

38. Лидл Р.,Нидеррайтер Г. Конечные поля (в 2-хтомах).-М.: Мир, 1988.-822 с.

39. Муттер В.М. Электронные цифровые устройства автоматики, телемеханики и радиотехники .-Л.: СЗПИ, 1980.-80 с.

40. Раков М.А. Реализация многозначных структур автоматики.-Киев: Наукова думка, 1976.-350 с.

41. Фрид Э. Элементарное введение в абстрактную алгебру.-М.: 1979.-260 с.

42. Яблонский С.В. Введение в дискретную математику.-М.: Наука, 1979.-272с.юн

43. Яглом И.М. Математические структуры и математическое моделирование.-М: Сов .радио,1980.-144 с.

44. Муттер В.М., Трофимов В.В., Иванова И.В., Калинуппсина М.Ю. Математические основы цифровой техники (прикладная конечная алгебра и многозначная логика). Литера плюс, СПб, 1999.351 с. (монография).

45. Муттер В.М., Иванова И.В., Калинушкина М.Ю. Недистрибутивные конечные алгебры и логики в теории информационных и вычислительных систем. Деп. в ВИНИТИ 1999. № 1207,10 с.