Хорошо известно широкое распространение двоичной логики в теории и практике современной вычислительной, информационно-измерительной и управляющей технике.
Это объясняется не только простотой двоичных элементов, но и наличием достаточно разработанного математического аппарата двоичной логики.
В то же время двоичное кодирование не является эффективным при обработке разнообразной информации. Это обусловило широкое и интенсивное развитие недвоичной логики: многозначной (конечной), бесконечнозначной, непрерывной, нечеткой.
Очевидно, многозначная элементная база и недвоичные методы представления информации — следующий шаг в развитии средств сбора, обработки, преобразования, передачи информации и т. п.
Начала теории конечных (дистрибутивных) алгебр восходят к 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. Разработка методов решения многозначных уравнений, в том числе троичной и четырехзначной алгебры логики.
ЗАКЛЮЧЕНИЕ
.
Диссертация направлена на решение актуальной задачи разработки новых перспективных методов и средств для существенного повышения эффективности процессов проектирования аппаратуры автоматизированных систем управления самого различного назначениявычислительно-управляющих систем, информационно-измерительных приборов, приемо-передающих средств и другой кибернетической, измерительной и радиотехнической аппаратуры.
Основные научные и практические результаты, полученные в работе, состоят в следующем:
— Предложены новые полиномиальные представления многозначных (в том числе троичных и четырехзначных) логических функций;
— Разработаны новые асимметричные алгебры с двумя бинарными операциями: асимметричные кольца, асимметричные тела, асимметричные поля и их разновидности;
— Предложены новые обобщенные регулярные формы в асимметричных алгебрах логики и практические примеры методов преобразования и передачи информации в автоматизированных системах управления на основе аналитических представлений многозначных функций в асимметричных алгебрах;
— Впервые разработаны методы решения многозначных логических уравнений и их систем.
Научная новизна работы заключается в следующем:
— Доказана теорема о равносильности однородного многозначного логического уравнения с произвольными коэффициентами и однородного многозначного уравнения с двоичными коэффициентами- -Разработаны регулярные аналитические представления многозначных логических функций в асимметричных алгебрах логики;
— Доказана возможность сведения задачи о регулярных представлениях функций многозначной логики к задаче о разрешимости системы многозначных уравнений;
— Разработаны методы синтеза многозначных триггерных последовательностных схем.
Достоверность результатов, обоснованность выводов изложенных в диссертации подтверждается выбором адекватного математического аппарата многозначной логики.
Значение результатов для теории и практики:
— Разработаны методы решения многозначных логических уравнений и синтеза многозначных комбинационных устройств;
— Разработаны методы анализа и синтеза многозначных схем с обратными связями;
— Разработаны методы синтеза схем многозначной логики для устройств преобразования и передачи информации в автоматизированных системах управленияразработанные методы позволяют улучшить процессы проектирования устройств;
— Разработаны малоуровневые аналитические представления многозначных логических функций в асимметричных алгебрах.