Содержание к диссертации
Введение
Глава 1 . Анализ тенденций развития автоматизированных систем кодирования и декодировании данных 10
1.1. Анализ требований к информационному обеспечению АСУ ТП 10
1.2. Тенденции развития методов декодирования 13
1.3. Основные понятия и классификация дискретных преобразований 17
1.4. Коды Рида-Соломона и методы декодирования 20
1.5. Некоторые применения кодов Рида-Соломона 22
1.6. Модель системы записи-воспроизведения цифровой информации 31
1.7. Кодирование и декодирование кодов Рида-Соломона во временной области 37
1.8. Операции над конечными циклическими группами и полями Галуа в процедурах кодирования и декодирования 42
1,9. Операции над расширенными полями GV{T) 51
1.10. Дискретные преобразования Фурье-Галуа и Ганкеля-Тёплица-Галуа 60
1Л І.Общие сведения об алгебрах и логиках . 84
1.11.L Понятие о дискретных и конечнозначных алгебрах логики 85
1.11.2. Элементарные многозначные функции 86
І.I.З.Операция суперпозиции многозначных логических функций 89
1 1.4. Четыре основные проблемы, возникающие при синтезе логических схем 89
11.5. Понятие о регулярных формах в копечиозначной алгебре логики 90
1.11.6. Функциональная полнота полиномиальных представлений 96
Глава 2 . Метод декодирования кодов Рида-Соломона на основебезрекуррентных процедур вычисления особых продолжений ганкелевых(теплицевых) матриц н синдромов
2.1. Степенные уравнения порядкам 103
2.2. Системы уравнений 130
2.3. Вычисление особых продолжений ганкелевых(теплицевых) матриц 140
2.4. Кодирование-декодирование в частотной области 147
2.5. Смешанное кодирование-декодирование 150
Глава 3 . Регулярные аналитические представления многозначных логических функций в асимметричных алгебрах 157
3.1. Асимметричные алгебры с парой бинарных операций 157
3.2. Некоторые обобщения асимметричных алгебр 162
3.3. Обобщенные регулярные формы и постановка задачи 168
3.3.1. Малоуровневые регулярные формы 168
3.3.2. Сведение задачи о регулярных представлениях функций многозначной логики к задаче о разрешимости системы многозначных уравнений 172
3.4. Аналитические представления многозначных функций в асимметричных алгебрах 175
3.4.1. "Диагональная" система (базис) 175
3.4.2. "Треугольная" система (базис) 179
Глава 4 . Разработка методов решения уравнений и систем уравнений многозначной алгебры логики 182
4.1. Классификация логических уравнений и систем уравнений 182
4.2. Троичные логические уравнения 186
4.2.1. Числовые троичные логические уравнения с одним неизвестным 186
4.2.2. Буквенное троичное логическое уравнение с одним неизвестным 188
4.2.3. Системы троичных логических уравнений 192
4.3. Понятие о решении конечнозначных логических уравнений 193
4.3.1. Обобщение основного метода решения 193
4.3.2. Основной метод решения 195
4.4. Использование логических уравнений в теории цифровых многозначных схем , 202
4.4.1. Анализ многозначных схем с обратными связями 202
4.4.2, Синтез многозначных трштерных последовательностных схем 204
Глава 5. Примеры практических схем и аналитических представлений элементов автоматизированных систем кодирования данных в конечных полях Галуа методами дискретной алгебры Клини 215
5.1. Базовые структуры кодеков на основе микропроцессоров 215
5.2. Функциональные расширители 225
5.3. Реализация аналитических представлений многозначных функций в асимметричных алгебрах 246
5.3.1. Реализация "диагонального" базиса (квазиполиномом в интерполяционной форме Лагранжа) 246
5.3.2. Реализация "треугольного" базиса (квазиполиномом в интерполяционной форме Ньютона) 250
5.3.3. Реализация асимметричных логико-арифметических базисов 252
Заключение 263
Библиографический список 265
- Тенденции развития методов декодирования
- Понятие о регулярных формах в копечиозначной алгебре логики
- Некоторые обобщения асимметричных алгебр
- Классификация логических уравнений и систем уравнений
Введение к работе
В диссертации представлено обобщение выполненных автором в 1985-2004 г,г. исследований по проблемам помехозащищенности информационных потоков в системах автоматизированного управления производственными процессами. Исследования охватывают широкий спектр структур получения, передачи, приема и обработки информации и подчинены разработке общего принципа выполнения процедур защиты информации от потерь или искажений в реальном времени и в автоматическом режиме.
В работе предложена концепция формирования такого «общего принципа» на основе синтеза процедур, традиционно выполняемых при использовании полей Галуа для кодов Рида-Соломона. Реализация концепции предполагает детальный системный анализ традиционных методов кодирования/декодирования и разработку «быстрых» алгоритмов автоматического введения защитных кодов в трактах передачи информации. Актуальность темы-Исследования проводились в рамках государственных программ и координационных планов, по ведомственным тематическим заказам (государственная регистрация отчетов по НИР за№№ 01850013661, 01870067179,01860107705), в соответствии с комплексной целевой программой «Российские верфи», в научно-исследовательских проектных разработках Технологического института энергетических обследований, диагностики и не-разрушающего контроля «ВЕМО», что является формальным признаком актуальности.
Исследования подчинены решению ряда проблем помехозащищенности информационных потоков в производственных средах, более точно - в системах автоматизировап- fc ного управления производственными процессами. Совокупность таких потоков (растущая чрезвычайно быстро) характерна разнообразием их по объему, по содержанию, по вероятности ошибок и требованиям к достоверности. Применение известных методов защиты во многих случаях не устраивает потребителя по ряду причин, главные из которых длительность процедур кодирования/декодирования и высокий уровень их сложности (соответственно высокая квалификация оператора).
Необходимость формирования развитого ряда методов помехозащищенности ин- формации диктуется потребностями практики и признается специалистами, ведущими разработки в данной области. Фундаментальные идеи решения проблемы содержатся в работах отечественных и зарубежных ученых: Шеннон К,, Блейхут Р,Э., Кларк Дж, Кейн Дж., Бсрлекэмп Э.Р., Питерсоп У., Уэлдон Э., Мак-Вильяме Ф-Дж., Слозн Н.Дж.А., Прэтт У., Макклеллан Дж.Х., Рейдер Ч.М., Кассами Т., Токура П., Ивадари Е., Инагаки Я., Блох 3.JL, Зяблов В.В.? Муттер В.М, Колесник В.Д., Мирончиков Е.Т., Раков М.А.? и др. В по следиие десятилетия исследования по проблемам быстрого кодирования/декодирования стали приоритетными. Приоритет исследований обусловлен высоким уровнем развития микроэлектроники, аппаратных и программных средств, обеспечивающих обмен информацией. Объективным следствием развития технических средств явились и функциональные ограничения применяемых методов конечной алгебры, многозначной логики и традиционной идеологии проектирования цифровой микроэлектронной аппаратуры на базе многозначных элементов. Известны изобретательские решения отдельных задач помехозащищенности, они не снимают проблемы в целом, но с очевидностью указывают на необходимость пересмотреть научные основы организации процедур кодирования/декодирования информации в реальном времени.
Цель диссертационной работы - обеспечение достоверности информационного обеспечения систем управления процессами и производствами методами, использующими кодирование данных в полях Галуа и дискретную алгебру.
Объект исследования - средства защиты информации от помех в автоматизированных системах управления технолопіческими процессами. Для достижения цели представлялось необходимым решить следующие основные задачи:
1. Системный анализ требований к информационному обеспечению автоматизированной системы управления технологическим процессом (АСУ ТП), помехоустойчивая запись/воспроизведение цифровых данных,
2. Переход к единому представлению цифровых данных в информационной системе (ИС) АСУ ТП с целью обеспечения помехозащищенности, анализ методов и структур кодирования/декодирования.
3. Разработка программно-аппаратных средств для выполнения операций и процедур кодирования и декодирования кодов над конечными полями,
4. Анализ причин ограничения количества исправляемых ошибок, исследование и разработка быстрых алгоритмов вычисления синдромов и спектра ошибок.
5. Обеспечение работы АСУ ТП в реальном масштабе времени, разработка безрекуррентных процедур вычисления особых продолжений ганкелевых (теплицевых) матриц и сшщромов и орбитально-табличных методов решения степенных уравнений, а также систем линейных и ли ней но-нелинейных уравнений над полями Галуа,
6. Разработка средств защиты информации от помех в ИС АСУ ТП на основе микропроцессоров, функциональных расширителей для кодеков и декодеров.
7. Создание концептуальных основ построения современных ИС АСУ ТП на основе анализа регулярных форм (в том числе предлагаемых) для многозначных функций, а также поли номиальных представлений, в том числе в троичной и четырехзначной алгебре логики.
8, Разработка научных основ создания автоматизированных систем кодирова ния/декодирования данных, использующих асимметричные алгебры многозначной логики, включая малоуровпевые представления, 9. Разработка методов анализа и синтеза ИС АСУ ТП нового поколения.
Научная новизна полученных результатов состоит в системном аналитическом описании процедур кодирования/декодирования, абстрагировании и адекватности интерпретаций и реализации результатов аналитических преобразований. Наиболее существенные научные результаты, полученные автором следующие:
1. Способ частотно-временного (гибридного) декодирования цифровой информации АСУ ТП.
2. Комплекс математических моделей, включающий:
- безрекуррентный способ продолжения синдрома для ускорения процесса декодирования;
- решение степенных уравнений и систем уравнений в полях Галуа для повышения качества декодирования;
- решение многозначных (троичных и четырехзначных) логических уравнений и их систем If для обеспечения анализа и синтеза ИС АСУ ТП нового поколения.
3. Концептуальные основы построения современных информационных систем АСУ технологических процессов, в том числе:
- полиномиальные представления многозначных, в том числе троичных и четырехзначных логических функций;
- асимметричные алгебры с двумя бинарными операциями: асимметричные кольца, асиммет- ричные тела, асимметричные поля и их разновидности;
- обобщенные регулярные формы в асимметричных алгебрах логики и практические примеры аналитических представлений многозначных функций в асимметричных алгебрах;
4. Схемные реализации математических выражений, описывающих информационные процессы в системах эффективного управления производством.
Достоверность научных положений, выводов и рекомендаций обеспечивается корректностью использования математического аппарата и практике: теории конечных нолей,
абелевых групп, ганкелевых и теплицевых матриц и циркулянтов, теории вероятности, программирования и микропрограммирования.
Практическая значимость результатов диссертационной работы состоит в том, что разработанные теоретические положения послужили основой для принципиальных, схемотехнических и конструктивных решений ряда задач помехоустойчивого кодирования/декодирования, в их перечень входят:
1. Структурные решения кодирования/декодирования цифровой информации, обеспечивающие помехоустойчивую запись и воспроизведение в широком спектре сетей и систем автоматизированной обработки данных.
2, Разработанные алгоритмы кодирования и декодирования по особым продолжениям обеспечивают автоматическое выполнение процедур защиты информации в АСУ ТП от помех.
3- Разработанный алгебраический аппарат (многозначная логика) создает основу для построения интегральных схем для практической реализации быстрых алгоритмов,
4, Предложенный способ построения поля Галуа обеспечивает наглядную интерпретацию процедур кодирования/декодирования,
5. Аналитические методы описания структур многозначной логики могут быть использованы при анализе функциональных свойств и схемотехнических решений вычислительных средств для ИС АСУ ТП.
На защиту выносится комплексное решение проблемы обеспечения достоверности информационного обеспечения систем управления процессами и производствами на основе теоретических и технических аспектов создания систем кодирования /декодирования и включающее:
1. Концептуальную модель системного метода построения кодов Рида-Соломона в полях Галуа,
2. Метод кодирования/декодирования для помехоустойчивой записи-воспроизведения цифровых данных, использующий безрекуррентные процедуры вычисления особых продолжений ганкелевых (тешпщевых) матриц и синдромов.
3. Теоретические основы кодирования/декодирования с использованием кодов Рида-Соломона над полем Галуа GF(2r)! позволяющие снизить погрешность ошибок при канальном декодировании в 2( П( раза,
4. Математические методы решения степенных уравнений (/7=3,4,5), систем линейных и линейно-нелинейных уравнений над GF(2 )4 возникающих при исправлении стираний, ошибок и стираний,
5. Новые алгебры логики и методы решения многозначных логических уравнений и их систем,
6. Структурные решения функциональных расширителей (к микропроцессорным кодекам) для выполнения алгебраических операций в конечных полях.
7. Методы анализа и синтеза многозначных схем с обратными связями, позволяющих простые реализации средствами микроэлектроники.
Реализация результатов работы. Разработанный метод декодирования кодов Рида-Соломона по особым продолжениям расширенных ганкелевых (теплицевых) матриц над полями Галуа, позволяющий безрекуррентное вычисление синдрома ошибок внедрен в рамках хоздоговорной научно-исследовательской работы СЗПИ (номера Государственной регистрации отчетов но хоздоговорным НИР; 01850013661, 01870067179, 01860107705), что подтверждено соответствующим актом использования результатов диссертационной работы для экспресс-классификации многомерных случайных сигналов при практической реализации в научно-исследовательских проектных разработках, предприятиями различного профиля при модернизации существующих систем автоматического управления, кибернетики, радиотехники, информатики, аналого-цифровой измерительной техники: Технологическим институтом энергетических обследований, диагностики и неразрушающего контроля «ВЕМО»; НИОКР ОАО «Авангард»; НИОКР, проводимых ООО «ЭлектроРа-диоАвтоматики-Р» и др., в соответствии с комплексной целевой программой «Российские верфи». Тематика диссертационной работы используется в учебном процессе высших и средних учебных заведений в курсах «Информатика», «Дискретная математика», «Математическая логика и теория алгоритмов», «Теория автоматов», «Схемотехника», «Эксплуатация средств вычислительной техники» при создании учебно-методических пособий.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на 6-й меящународной научно-практической конференции «Современные информационные и электронные технологии» (Одесса, 23-27 мая 2005г.); на всесоюзной конференции «Микропроцессорные средства локальной автоматики» - Гродно, 1989г.; на республиканском семинаре ВСОИ, Ужгород, 1984г; на всесоюзной конференции «Применение МП комплектов БИС при разработке радиоэлектронной аппаратуры», Ленинград, 1983 г. и семи научно-технических конференциях и семинарах.
Публикации. По теме диссертационной работы опубликовано две монографии (одна в соавторстве), двадцать четыре статьи, шесть из них в изданиях, рецензируемых и рекомендованных Перечнем ВАК.
Структура н объем работы. Диссертация состоит из введения, пяти глав, заключения, приложения и списка литературы. Общий объем работы составляет 276 страниц машинописного текста, 46 таблиц и 24 рисунка. Список литературы содержит 170 наименований.
Тенденции развития методов декодирования
Одна из наиболее важных и одновременно трудных задач в технике передачи, записи, воспроизведения и хранения информации - обеспечение достаточной помехоустойчивости. Широкому распространению высокоэффективных помехоустойчивых кодов с обнаружением и исправлением ошибок препятствует сложность практической реализации устройств декодирования. Ввиду большого разнообразия применяемых кодов [9,12,16,28,85,70,77,78,108,125,160] создание специализированных БИС-кодеров и БИС-декодеров во многих случаях экономически не оправдано, так как, с одной стороны, требует значительных затрат на разработку БИС, а с другой - налагает существенные ограничения на параметры используемого кода. Появление микропроцессоров (МП) изменило подход к конструированию аппаратуры для кодирования и декодирования (КИД). Все большее число функций кодирования и декодирован ияч которые ранее осуществлялись с помощью встроенной логики, в настоящее время решаются программным путем. Это делает актуальным разработку программных методов КИД. Появление МП, представляющих собой новый класс элементной базы аппаратуры, позволяет, вследствие их широких функциональных возможностей, поставить вопрос о создании унифицированных технических средств КИД в различных отраслях техники, КИД с помощью корректирующих кодов нашло широкое распространение в системах связи [89,142-144], цифровой звукозаписи [25,26,74,75,124], цифровом радиовещании [12,13], цифровом телевидении [68] запоминающих устройствах вычислительной техники [38,153].
Польза кодирования доказана Шенноном в 1948 году. Он не только связал достоверность и скорость передачи информации с пропускной способностью канала связи» но и указал путь надежной передачи данных за счет введения избыточности при кодировании сообщений, то есть до их передачи в канал или записи на носитель, В принятой Шенноном постановке задачи канал считался заданным, а коды могли меняться [137,138]. Современный инженерный подход заключается в выборе конкретного кода (из некоторого ограниченного набора кодов) и системы декодирования, после чего анализируется работа модели предполагаемой системы кодирования/декодирования в условиях изменяющегося среднего шума в канале [10]. Различные типы кодов описаны в [9, 14,16,28,85,70,108,125,130-133], их многообразие отражено в табл.1.1. В классе всех групповых кодов можно выделить важный большой подкласс, состоящий из так называемых полиномиальных кодов. Примерами полиномиальных кодов являются коды Боуза-Чоудхури-Хоквингема (БЧХ), коды Рида-Соломона, обобщенные коды Рида Маллсра, проекти вно-геометрически с, евклидово-гсометрические и квадратно-вычетные коды. Описание каждого из этих семейств кодов задается указанием алгоритма для его построения. Указанные в табл.1 Л семейства кодов пересекаются так, что некоторый конкретный код может быть одновременно кодом БЧХ и вычетпым кодом и др. Таблица 1. По форме избыточности
По способу кодирования Формально деление кодов на двоичные и недвоичные носит искусственный характер. Оправдывается такое деление усложнением алгоритмов построения, кодирования и декоди-рования недвоичных кодов (троичные, четверичные и другие коды большего основания). Систематические Символы информационной последовательности входят без изменения в передаваемое сообщение, занимая в нем отведенные им позиции, а кодирование сводится к внесению в передаваемое сообщение дополнительных (избыточных) символов, связанных определенной зависимостью с символами информационной последовательности. Блочные Информационная последовательность разбивается на блоки символов фиксированной длины, каждому из которых ставится в соответствие определенная комбинация символов алфавита канала называемая кодовым словом. Если избыточные (проверочные) символы связаны с информационными линейными зависимостями, такой код называется Линейным. Двойные линейные блоковые коды часто называют групповыми кодами, поскольку кодовые слова образуют математическую структуру, называемую группой. Поэтому их называют Групповыми, Подкласс групповых составляют Полиномиальные коды: - Боуза-Чоудхури-Хоквингема (БЧХ); - Рида-Соломона (PC); - Рида-Маллера (РМ); - Проективно геометрические; - Евклидово-гсомстричсскис; - Квадратно-вычетные. Двоичные Несистематические Символы информационной последователь ности в явном виде в передаваемое сообщение не входят, и могут быть установлены по известным зависимостям, связывающим их с символами передаваемого сообщения. Непрерывные Сверточные коды являются частным случа ем блочных линейных кодов. Эти коды име ют древовидную или решетчатую структу ру. Каждому ребру древовидной структуры соответствует определенная последователь ность т информационных символов. Нелинейные - коды с контрольной суммой; - инверсные; - Нордстрома-Робинсона (HP); - с постоянным весом и т.д. Недвоичные Исправляющие пакеты ошибок Исправляющие случайные ошибки
Понятие о регулярных формах в копечиозначной алгебре логики
Функцию/, соответствующую некоторой формуле, обычно называют суперпозицией функций, входящих в эту формулу, а процесс составления формулы (получение функции / путем подстановки других функций вместо ее аргументов) — операцией суперпозиции. Строго определить понятие суперпозиции можно с помощью следующих операций Мальцева: С, - циклическая перестановка; т - транспозиция (перестановка) пары краЙЕіих элементов; Д - отождествление аргументов; V - приписывание фиктивного аргумента; - бинарная суперпозиция. Указанные операции определяются так: (1.65) б)т f{xbx2,x3 txn) = f{x2,xux2,...,xn); e)Af(xhx2,x3,...,xII_[) = f(x[4xhx34 txn_[); д) f(xhx2,x3,...an) g(yhy2,...,ym) С помощью операций С, и т выполнима любая перестановка аргументов. В свою очередь, операции Д и V позволяют отождествлять и присоединять "лишние" аргументы; наконец, операция используется для составления сложной функции: первый аргумент/ заменяется мї-местной функцией g . \Л\Л, Четыре основные проблемы, возникающие при синтезе логических схем Первая и важнейшая проблема - проблема функциональной полноты которая сводится к установлению необходимых и достаточных условий для реатизации любой сколь угодно сложной логической функции с помощью некоторого набора элементарных функций. Для двоичной алгебры логики зі а проблема решена ЭЛостом в 1921 году, для троичной - СЯблонским в 1958 году: наконец для произвольной "значносте н к необходимые и досіаіочіше условия найдены И.Розснбсргом в 1969 году (с точки зрения абстрактной теории Галуа эти условия сформулированы в работе [59]). Вторая проблема синтеза - проблема регулярных представлений функций и соответствующих им схем. т.е. построение логического устройства по определенным правилам.
Третья проблема - проблема оптимизации схемы по заданному критерию. Например, обеспечение ее простоты, высокого быстродействия и т.п. При этом с развитием микроэлектроники (когда в одном кубическом миллиметре размешаются тысячи и тысячи элементарных логических компонент) простота схемы отступает на второй план, а на первый выходит быстродействие. Четвертая проблема - проблема декомпозиции функции и соответствующих им схем, т.е. разбиение всей системы на типовые блоки, которые и синтезируются по отдельности. Эта проблема трудно формализуема и требует инженерной смекалки и изобретательности. Первые три проблемы оказываются решенными при использовании так называемых полиномиальных представлений [111], если алгебра К;&9 является полем Галуа; в этом случае количество элементов к в множестве К равно рг, где числар и г - соответственно простое и натуральное. Если же к не равно pr, то конечные поля не существуют и представить функцию в виде полинома невозможно. В этом случае при синтезе многозначных схем используются другие алгебры с расширенной сигнатурой операций (кроме пары бинарных операций присутствуют унарные и др.) - так называемые "нормальные" формы представления логических функций [111,117,120-167]. 1.11.5. Понятие о регулярных формах в конечнозначной алгебре логики До настоящего времени анализ методики построения алгебр логик применительно к задачам синтеза схем сводился к построению регулярных форм. Так в литературе для случая к=2г т.е. двоичной алгебры логики введено обозначение , ПрИ X = G v (1.66) 0 , при x ff Д 0 \х , при х = 1 hl \х , при x t Таким образом, xG представляет собой двоичную характеристическую функцию. Сосгавим нар) логических функций: а) FN=x A .Ax A..,A х Ах ; (L67) б) 0N = X y...Vxf V...\/ X VX , pi=Gj Построим два логических выражения: e)/ = (AAWiAfl)e.(,eawA4)= Є ОМ); !=l (L68) где М - 2" - Ї - максимальный номер комбинации в таблице истинности; 0 и - некоторые бинарные ассоциативные операции (определенные ниже). Добавим к уже известным совершенным каноническим формам для двоичной алгебры логики, канонические формы не имеющие до сих пор специального названия. Известны: /= V F:= V ДлАт Л-.Дх 1 (1.69) совершенная дизъюнктивная нормальная форма (СДНФ); f= Л Ф,= Л »v/«TW/l (1.70) /ЄЇ0) /{0} "-1 ! совершенная конъюнктивная нормальная форма (СКИФ). И дадим название новым: /= ф К= Ф Х Л /"тЧ-.Л х?1 (1.7U) /ЄШ /{Ц или /= Ф Д = " Л&"1- а?1 (1-71,6) /{1} /{1} - совершенная квазиполипомиаяьиая нормальная форма (Ск-ПНФ); f= ф,= "v/ V-.V 1 (1.72) - совершенная специальная нормальная форма (ССНФ), где обозначения/е {1}и/{0}означают, что берутся только те комбинации, па которых заданная функция/ принимает значение соответственно 1 или 0, Правило построения СДНФ и Ск-ПНФ : 1, Сосгавиїь конъюнкции (произведения) из аргументов для тех их комбинаций, на которых функция/обращается в единицу; при этом если аргумент входит в данную комбинацию как 0, то в конъюнкцию вводится инверсия XI, а если как 1 - то х/. 2. Полученные конъюнкции (произведения) соединяются знаком V (для СДНФ) или (для Ск-ПНФ). » Правило построения СКНФ и ССНФ: 1. Составить дизъюнкцию для тех комбинаций, на которых функция/обращается в нуль; при этом если аргумент XJ входит в данную комбинацию как 1, то в дизъюнкцию вводится инверсия XJ , а если как 0 - то XJ . 2. Полученные дизъюнкции соединяются знаком Л (для СКНФ) или (для ССНФ). Здесь рассмотрены канонические формы с парой бинарных операций. Известны также другие канонические формы, при которых функции Fj YL Щ выражаются через бинарную и унарную операции, например, через импликацию и инверсию (так как a— b = aVb) или за-прет и инверсию (так как aVh = a\/h). Могут быть построены регулярные формы и на базе одной бинарной операции: Шеф фера или Пирса. Так, одиократпо применив правило де Моргана к СДНФ или СКНФ, можно получить логическое выражение в базисе {И-НЕ} или {ИЛИ-НЕ}, I Для построения регулярных форм в йг-значной алгебре логики; характеристической функции (ХФ) xG (1.66) в двоичном случае соответствует большая ХФ Б многозначной алгебре логики (1.58,6) По аналогии с к=2 введены функции типа (1.14): a) Fn = х Л х1»Г /к... /\ х \к = val; (1.73) g в которых символы V и Л понимаются соответственно как й-значпые конъюнкция и дизъ юнкция, т.е. как функции min и Мах. Введем бинарные 4-значные операции и со свойствами: Ова = авО = а и (к-\) а = а (к-1) = а. Например, при fc=3, к=4 требуемые операции представлены в табл.1.18 и в таблЛ.19, где пустым позициям соответствуют произвольные значения из множества Х={0,1,..,,-1} на каждой позиции может быть к значений.
Некоторые обобщения асимметричных алгебр
Особое значение -тля целей аналитического представления многозначных функций имеют такие алгебры: ас-кольцо, ас-полукольцо и ас-квазикольцо с мультипликативной единицей-левой ел , правой еп или двусторонней е (ас-тела и ас-поля содержат е ), Мультипликативными структурами для перечисленных алгебр являются соответственно: группоид с е полуїруппа с ( в случае двусторонней единицы ел=е =е - моноид) и квазигруппа с е ( в частном случае е11=еп=е -лупа). Для того, чтобы выделить подобные асимметричные алгебры, дадим им "родственные" названия: а) ас-скояьцо- ас-кольцо с единицей в (по операции ); б) яс-люшїьг/о-ас-полукольцо с единицей е (по операции ); в) ас-лукояыр - ас-квазикольцо с единицей е (по операции ). Несмотря на то, что понятие ас-кольца является весьма широким, можно построить еще более общие асимметричные алгебры, получаемые из ас-кольца за счет снятия ряда аддитивных аксиом. Так, весьма важные классы аналитических представлений многозначных функций порождаются асимметричными алгебрами с операциями, удовлетворяющими следующим на » 163 борам аксиом (разумеется, включая аксиомы о замкнутости, однозначности и полной опре деленности для обеих операций АО, МО и аксиому взаимодействия (3.1): {Л2Л,УОП,А/1Л,М4ПИЛИМЗЛ}, {ЛЗ,ЛЛл,МЗпюгаМ6п}, ДЩА/4) и другие, причем индексы п" "л" можно взаимно менять в пределах аксиом одного и того же класса (аддитивных, мультипликативных). Последняя из систем аксиом имеет столь большое значение (многие представления многозначных функций основаны на алгебрах с операциями, удовлетворяющими этой системе аксиом), что целесообразно соответствующей алгебре дать специальное название. Определение 3.6. 1. Алгебру К; ,0 с парой бинарных операций ив. удовлетворяющих системе аксиом {АО, A3: МО, Ml, М4) и (3.1), т.е. с однозначными сложением и умножением, с единственным нейтралом по сложению, односторонними доминантой и единицей по умножению и при постулировании аксиомы взаимодействия, назовем односторонним бипоидом. 2. Нсли же доминанта и единица двустороннне, то такую aлгeбpv будем называть (двусто-ронтш) бипоидом. А если кроме того в множестве \{ /}нет делителей нуля, то есть \?a,bK\ {d}, [а b d = 0), то бипоидом целостности (аналогия с кольцом целостности). Заметим, что требование существования односторонней единицы можно ослабить, заменив его условием существования хотя бы одной изотопной односторонней единицы \ Другими словами, операции в бипоиде АГ; ,0 по определению удовлетворяют следующим условиям: а) А ; 0 - (аддитивный) группоид с единственным (двусторонним) нейтральным элементом п: б) А"; - (мультипликативный) группоид с односторонней доминантой d(ii є {п,л} и односторонним делением на элемент е ( их может быть несколько); в) выполняется тождество n = dj. Более того, если единица в бипоиде изотопная, то для представления многозначных функций могут быть использованы ортогональные, а если единица обычная - то ортонорми-роваипьте базисы унарных операций [80] Б качестве доминанты (и нейтрала), а также единицы могут быть выбраны любые элементы из К (исключая, разумеется, вариант d-{ = et). Однако, как известно, на свойства 164 алгебры выбор того или иного элемента не влияет, и мы ограничимся обычным рассмотрением "с точностью до изоморфизма". Новые алгебры, пеюоморфные друг другу, можно построить следующим образом. Подвергнем тождественные соотношения в аксиомах A3, Ml, М4 трансформации с помощью перестановок (индексы "л,п" опущены): Исходные тождества Трансформированные тождества а О п = а; a d = d\ Вернемся к «старым» элементам, введя алгебры К;+ и К;- , изотопные исходным ;@ и К; , т.е. такие, что а+Ь = у-1{а1{а)Щ1(Ь)) и а-Ъ = у :l{a2(a) fo(b)), где степень -1 означает обратную перестановку. Заметим попутно, что при 0,- = ( - = 7 і {1.2} s соответствующие алгебры изоморфны. Более того, с точностью до изоморфизма нам достаточно ограничиться главной изотопией, считал перестановку у тождественной, т.е. принять а&п = Х] (а); а«е-а2(а); я й = щ{ії), где обратная перестановка of вновь обозначена через a,, a трансформированным элементам-константам, возвращены их исходные обозначения (что не нарушает изоморфизм): далее такие элементы будем снабжать штрихом, чтобы отличить их от петраї ic формированных. Замечаем, что в действительности вводить специальные операции над правыми частями в соотношениях (3-2) пет необходимости, а трансформацию правых частей можно трактовать как непосредственный результат воздействия операций и 0.
Итак, для правых и левых элементов получим (3.3) хви П -увп; =Лп; x d[t=S)lx\ п лвх = уВл\ е л ч = умп\ ё л ч = Х л;ш где -свободная переменная (упорядоченный вектор значений 0,1,..., -1), у- функция от я (от перестановки), 3) - коистаига {$) єК). 165 ft В частных случаях тождественных функций-перестановок получаем соотношения из упоминавшихся выше аксиом. Определение 3.7. Доминанту, единичный и нейтральный элементы (левые, правые, двусторонние) назовем изотопными) (кратко: изодоминантой, изоедштцей, изонейтраюм), если они удовлетворяют соответствующим соотношениям (3.3); в случае тождественных функций (& =d, х=у)9 т.е. обычных доминант, единиц, нейтралов, будем говорить о вырожденных изотопных элементах, Изотопные (правые) элементы ц і изодомипанту, изоединицу, изонейтрал) назовем эквивалентными, если VatK4[a-[ -я-є], где точка заменяет символ либо 0, иначе -ие эквтаяентнымщ аналогично для левых элементов. Эквивалентным правым изотопным элементам в таблице Кэли соответствуют одинаковые столбцы, а левым - строки. Легко видеть, что УаєК,\(а-п — &л-а) [п — вл — є)], т.е. строка е и столбец г в таблице Кэли взаимно транспонированы тогда и только тогда, когда левый и правый изотоп ные элементы совпадают. Изотопным элементам можно дать следующую физическую интерпретацию: изодо-мннанта "заглушает" (как и всякая доминанта) сигнал, внося постоянный фон, а изонейтрал и изоединица функционально "искажают" (трансформируют) его. Нетрудно на базе (33) сформулировать аксиомы, подобные {/13, ЛЯ, Л/4} о сущест _ вовании изотопных доминант, нейтральных и единичных элементов, скорректировав аксио му взаимодействия: п\ = 2?,-, ,/е{л,п,0}, атаюке дать определение асимметричных алгебр (ас-кольцо с изоединицей и т.п.). Однако понятие об изотопных элементах дает нечто большее, чем простой перенос соответствующих свойств на изотопный случай. Именно справедливо следуюшее утверждение Утверждение 32.1. Do всякой (некоммутативной) квазигруппе (лупе, группе) ровно к неэквивалентных правых и к неэквивалентных левых изотопных единичных (нейтральных) элементов; при этом в лупе и в группе имеется двусторонний вырожденный изотопный единичный (нейтральный) элемент, 2. По всякой коммутативной квазигруппе ровно к двусторонних изотопных единичных (нейтральных) элементов, причем в абелевой группе (лупе) один из них вырожден. » 166 t Это позволяет в определении, например, ас-кольца, и, вообще, абелевой группы, осво бодиться от ряда аддитивных аксиом (кроме, естественно, аксиом об однозначности и ассоциативности операции 0), заменив их следующей аксиомой о существовании к изотопов. Пусть fi{a) -любая перестановка, включая тождественную; тогда \faeK, IkfftnjeK, \aQnj = nlea = fi(a)]t / = 0,1,...Д-1, где/}(я); /у(а) при/5= у. I Заметим, что из последнего условия вытекает коммутативность операции 0, возмож ность вычитания и сокращения; если кроме того 3 , [/} (я) = д] - то и наличие нейтрала п и обратимость каждого элемента. Таким образом, при существовании нейтрала п данная аксиома определяет ЛУЛУ с обратимостью, так какУд Кч [nla = n\ а). Понятие изотоппости применимо и к элементам дистрибутивных алгебр. Так, если в коммутативном кольце какой-либо элемент мультипликативного группоида является изо-едининей, то над подобным кольцом можно, во-первых, не только построить векторное про-странство без деления (модуль), но и, во-вторых, однозначно решить систему из к уравнений, а следовательно, и составить формулу для любой функции й-значной логики, если определитель матрицы (образующей) системы равен этой изоединице. При этом справедливо известное правило Крамера. Введем ряд понятий. Определение 3.8, Пару (а,Ь) изотопных элементов (шонейтралов) назовем групповой, I если соответствующие им перестановки а,р коммутируют между собой: а р =р - а, где точ кой обозначена композиция (последовательное выполнение) перестановок. Данное понятие оправдывается следующим утверждением
Классификация логических уравнений и систем уравнений
Условимся неизвестные величины (аргументы) обозначать латинскими буквами х, у, z , а неизвестные величины (параметры) - буквами a,h, с, ... возможно с индексами. Рассмотрим уравнения типа [79,115,141] » F(X,A) g(XA) (4.1) где = ( , 2,.-.,} - вектор (упорядоченный набор) неизвестных логических неременных; А = 1 , 2,-.-, г " вектор известных параметров;/и g - произвольные логические функции (возможно, _/ 0 или р0). В частном случае, соотношения вида F(xJ)=g(xJ) (4.2) являются логическими уравнениями с одним неизвестным X. Определение 4.1. 1. Логическое уравнение (неравенство) называется числовым, если оно содержит только «числовые» параметры-константы и неизвестные переменные-аргументы. Логическое уравнение называется параметрическим, если оно содержит хотя бы один параметр в буквенной форме, причем буква может принимать жобое значение из множества К. Если логическое уравнение справедливо при любых значениях букв, то оно называет ся тождеством. 2. Если g(X,A)=0, g{x,A)=Ot то логические уравнения (4Л), (4.2) называются однородными (без правой части); иначе они называются неоднородными. 3. Некоторое значение неизвестной переменной х, обращающее уравнение (4.2) в тождество, называется решением, или корнем уравнения (с одним неизвестным). Набор значений неизвестных переменных { , 2 - } обращающий уравнение (4Л) в тождество, называется корнем этого уравнения (с несколькими неизвестными). 4. Лоїическое уравнение, имеющее хотя бы один корень, называется разрешимым; ес ли уравнение не обращается в тождество ни при каких значениях неизвестных, то оно реше ния не имеет и называется неразрешимым. Логическое уравнение может быть неразрешимо условно и безусловно. Все числовые логические уравнения, не имеющие решения, безусловно неразрешимы, или противоречивы, Для буквенных (параметрических) логических уравнений, не имеющих решения при произвольных значениях параметров, правомерна следующая постановка задачи: выделить область допустимых значений параметров, при которых уравнение имеет решение.
Если эта область пуста, то исходное буквенное уравнение противоречиво, а если не пуста - условно разрешимо (становится разрешимым в области допустимых значений параметров). Определение 4,2, Х.Любой корень логического уравнения называется частным решением, а совокупность всех частных решений - общим решением уравнения, 2. Два уравнения называются равносильными, если их общие решения совпадают. Такие понятия как система логических уравнений, их решение (частное и общее) и равносильность вводятся обычным образом. Системы логических уравнений подразделяются на следующие типы [87]: - полная система (число неизвестных равно числу уравнений); избыточная система (число неизвестных меньше числа уравнений); - неопределенная, или диофаитова, система (число неизвестных больше числа уравнений), В частности, одно уравнение с несколькими неизвестными является диофаптовым Определение 4,3, Система логических уравнений, обладающая хотя бы одним решением, называется совместимои,шк совместной, а система, не имеющая ни одного решения, - несовместимой, или несовместной. Несовместимость (так же как и неразрешимость) может быть безусловной (т.е. при любых значениях парамеїров) и условной (в некоторой области). Таким образом, возможны следующие варианты несовместимых систем логических уравнений: 1) хотя бы одно уравнение не имеет решения (неразрешимо); 2) каадос уравнение, взятое независимо от остальных, разрешимо, но вся совокупность уравнений не удовлетворяется ни при каких значениях неизвестных (в таком случае говорят, что пуста область пересечения независимых решений всех уравнений), С другой стороны, для того чтобы система логических уравнений была совместимой, должны удовлетворяться следующие условия: 1) каждое отдельно взятое уравнение должно иметь хотя бы одно решение; 2) область пересечения независимых решений всех уравнений не должна быть пуста, т.е. должна существовать хотя бы одна совокупность значений неизвестных величин, обращающая в тождество каждое уравнение системы. Наконец, так же как и алгебра логики, логические уравнения классифицируются по их "значности", т.е. по тому, сколько и какие значения могут принимать входящие в них логические переменные. В свою очередь, дискретные логические уравнения подразделяются на бесконечнозначные {к = со) и конечнозначные (к 2), например, двоичные (#=2), троичные (к=У) и т.п. Приведение неоднородного логического уравнения к равносильному однородному уравнению. Приведение основано на использовании специальной бинарной операции, позволяющей переносить логическое выражение из одной части уравнения в другую [42,59]. Определение 4,4. Бинарная операция Т называется присоединением, если она обладает следующими свойствами: ?Та = 0; аТ b = q при а Ь. (4.3) В двоичной алгебре логики свойствами (4.3) обладает операция неравнозначности Ф (синонимы: "сумма по модулю 2", исключающее ИЛИ). Операция присоединения позволяет переносить логическое выражение из правой части уравнении Б ею левую часть, или наоборот, обращая неоднородное уравнение в однородное, а именно равносильны соотношения: [/ ) = г W] & [/ ) Т g(x) = g(x) Т g( )] & [/(х) Т g{x) = 0] (4.4) Замечании. Вообще говоря, для перехода неоднородного логического уравнения в однородное операция Т может быть наделена менее жесткими, чем условия (4.3), свойствами: a Jа п\ a Jb rt при я й,гдел=сонД неК. В любой алгебре логики этими свойствами обладает целое семейство операций. Так, в двоичной алгебре логики (4=2) можно принять не только /?=0, но и л-1. Поэтому указанным условиям удовлетворяют две операции: 1) уже упоминавшаяся операция неравнозначности Ф; 2) операция равнозначности =oF В троичной алгебре логики величину п можно выбирать тремя различными способами: я=0, и=1, п=2. Кроме того, полагая Ф=1 или Ф=2 в табл.4.1, можно получить 2 вариантов доопределения операции Т (в общем случае Ф я).
