Адекватные модели полурешеток, функций и автоматов на полурешетках | Вестн. Том. гос. ун-та. 2000. № 271.

Адекватные модели полурешеток, функций и автоматов на полурешетках

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

Adequate models of semilattices, functions and automata on semilattices.pdf Введение Важнейшими характеристиками всякой математической модели являются ее адекватность и степень точности. В случае дискретных моделей первая понимается как безошибочность в том смысле, что результат адекватного моделирования всегда содержит в себе истинное значение моделируемой величины, а вторая - как степень неопределенности этого результата [1]. Для управляющих систем на конечных верхних полурешетках удается формализовать эти понятия, а утверждения о них сделать доказательными [2]. Это достигается определением адекватной модели на полурешетках, составленных из наибольших элементов смежных классов полурешеток заданной системы по некоторым конгруэнци-ям, которыми и характеризуется степень точности модели. В данной работе понятия адекватной модели и ее точности определяются для полурешеток, функций и автоматов на полурешетках и для полурешеточно упорядоченных алгебр. Указан метод построения адекватных моделей для полурешеток подмножеств и интервалов с точностью до эквивалентности на множестве минимальных элементов полурешетки. Показано, что свойства монотонности и квазимонотонности функции на полурешетках передаются любой ее адекватной модели, а свойство аддитивности - лишь модели, точность которой сохраняется данной функцией. Установлено, что адекватная модель суперпозиции монотонных функций реализует суперпозицию их адекватных моделей и совпадает с ней в случае сохранения функциями точностей их моделей. В терминах стабильных троек конгруэнций охарактеризованы всевозможные адекватные модели произвольного конечного автомата на полурешетках. Показано, что свойства аддитивности, монотонности и квазимонотонности автомата на полурешетках сохраняются в его адекватных моделях. Эти результаты находят широкое применение в адекватном моделировании дискретных управ» ' их систем с различной степенью точности и в синтезе их логической структуры на базе БИС с заданным динамическим поведением [2]. Всюду далее под полурешеткой подразумевается конечная верхняя полурешетка, т.е. конечное частично упорядоченное множество, в котором любые два элемента а и Ь имеют точную верхнюю грань, называемую их суммой и обозначаемую а+Ь. В ней обязательно есть наибольший и минимальные элементы. Последние называются точками полурешетки. Адекватные модели полурешеток Пусть 5 - полурешетка со сложением + и а -конгруэнция на ней. Каждый смежный класс А в S/a является подполурешеткой в S [2], и в нем есть наибольший элемент sup/4. Смежные классы А и В как элементы фактор-полурешетки S/a и элементы в них, в том числе наибольшие, как элементы полурешетки S, связаны между собой соотношением: A h{U)=h(V), где h(P) для РсМ - наименьший интервал в , для которого РсМР). По определению отображение Л: {Я} *-> является гомоморфизмом полурешеток и отношение р - его ядерной конгруэнцией. Поэтому полурешетки и {Л}/р изоморфны и верна следующая теорема. Теорема 3. ={Л}Тр. Следствие 1. М является адекватной моделью М. Следствие *2. Адекватные модели являются адекватными моделями М. Следствие 3. есть адекватная модель М. Полурешетка S называется точечной, если каждый элемент в ней равен сумме некоторых ее точек. Так, полурешетки М, М и {/?} - точечные. Теорема 4. Полурешетка точечная, если каждый смежный класс эквивалентности R является элементом М. В этом случае минимальными элементами полурешетки являются все смежные классы эквивалентности R и только они, а всякий другой ее элемент, будучи интервалом и одновременно объединением некоторых минимальных элементов, равен сумме последних. Этим теорема доказана. Адекватные модели функций Имеются в виду функции на полурешетках, т.е. отображения полурешеток в полурешетки. Области определения и значений функции / обозначаются Df и V/ соответственно. Есть четыре замечательных класса функций на полурешетках [2] - аддитивные, точечные, монотонные и квазимонотонные. Функция точечная, если на любом элементе области определения ее значение равно сумме значений на точках последней, содержащихся в данном элементе. Функция называется аддитивной, если она является гомоморфизмом полурешеток. Функция / монотонная, если a^a)^b). Функция g реализует функцию/ если DfcDg и g(a)j{a)pj{Jb). Теорема 5. Пусть g - адекватная модель / с точностью (ст,р). Тогда справедливы следующие утверждения. (1) Если функция / монотонная или квазимонотонная, то функция g также монотонная или квазимонотонная соответственно. (2) Если функция /сохраняет (ст, р) и аддитивна, то функция £ также аддитивна (3) Пусть-,'f^), функция'go есть адекватная' модель функции f0 с точностью (5, р), функция g, для i= 1, ..., т есть адекватная модель функции/ с точностью (с,5;), 5=51x...x5m и A=g0(gi,...,gm). Тогда если функция f0 монотонная, то g

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Агибалов Геннадий ПетровичТомский государственный университетпрофессор, доктор технических наук, заведующий кафедрой защиты информации и криптографии факультета прикладной математики и кибернетики
Всего: 1

Ссылки

Агибалов Г.П., Бузанов В.А., Липский В.Б., Румянцев Б.Ф. Логическое проектирование переключательных автоматов. Томск: Изд-во Том. ун-та, 1983. 154 с.
Агибалов Г.П. Дискретные автоматы на полурешетках. Томск: Изд-во Том. ун-та, 1993.227 с.
Агибалов Г.П. Квазимоногонные функции и их минимизация // Кибернетика. 1989. №2. С. 111-113.
 Адекватные модели полурешеток, функций и автоматов на полурешетках | Вестн. Том. гос. ун-та. 2000. № 271.

Адекватные модели полурешеток, функций и автоматов на полурешетках | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия