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

ВВЕДЕНИЕ.

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. Аналитические представления многозначных функций в асимметричных алгебрах-изобгаюидах.

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

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

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

4.1. Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

14. Mukaidono M. A set of independent and complete axioms for a fuzzy algebra (Kleene algebra)//ISMVL (cm. 9.), 1981.-27-37 p.

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

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

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

18. Муттер В.М. Представление функций многозначной логики в недистрибутивных логико-алгебраических базисах / СЗПИ.-Л.,1982.-1 lc.-Деп. в ВИНИТИ. 10.11.82. №2893.iOd

19. Муттер B.M. Малоуровневые представления функций многозначной логики / СЗПИ.-Л.Д982.-22 с.-Деп. в ВИНИТИ. 10.11.82. №2894.

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

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

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

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

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

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

26. Муттер В.М., Иванова И.В. Решение уравнений троичной и четырехзначной логики. / СЗПИ.-Л .,1996.-9 с.-Деп. в ВИНИТИ. 10.11.82. № 506.

27. Муттер В.М., Иванова И.В. и др. Устройства многозначной логики на формальных нейронах (в недистрибутивных логико-алгебраических базисах) / СЗПИ.-Л.Д989.-19 с. Деп. в ВИНИТИ. 29.05.89. № 3513.

28. Муттер В.М., Иванова И.В. Преобразование Ганкеля-Теплица / СЗПИ,-Л.Д995.-42 с.-Деп. в ВИНИТИ. 20.02.95. №468.

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

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

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

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

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. Яблонский C.B. Введение в дискретную математику.-М.: Наука, 1979.-272с.

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

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

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