ДИСКРЕТНЫЕ АВТОМАТЫ НА ПОЛУРЕШЁТКАХ | ПДМ. 2009. № 2(4).

ДИСКРЕТНЫЕ АВТОМАТЫ НА ПОЛУРЕШЁТКАХ

Теория дискретных автоматов на полурешетках является одним из значительных достижений научной школы прикладной дискретной математики (ПДМ) Томского государственного университета (ТГУ), представляя собой сравнительно новое научное направление на стыке математической кибернетики и общей алгебры, в рамках которого впервые удалось формализовать такие понятия, относящиеся к дискретным управляющим системам, как динамическое поведение, физическая реализуемость, адекватная модель и ее точность, и решить задачи логического проектирования таких систем в постановке, отражающей динамику поведения системы, возможность ее физической реализации на современной электронной базе и адекватность моделирования с любой наперед заданной точностью. Статья написана к 50-летию школы ПДМ ТГУ и является рефератом одноимённой монографии автора, вышедшей в Издательстве ТГУ в 1993 г. и ныне практически не доступной. В ней отражены почти все основные результаты теории дискретных автоматов на полурешётках, полученные к тому времени.

DISCRETE AUTOMATA ON SEMILATTICES .pdf Под дискретным автоматом здесь подразумевается дискретная управляющая система со свойствами конечных абстрактного и структурного автоматов, понимаемых в том широком смысле, который допускает в схеме автомата элементы с управляемой проводимостью, двунаправленные каналы передачи информации, отождествление выходных полюсов компонент и многозначность структурного алфавита, присущие современным большим (БИС) и сверхбольшим (СБИС) цифровым интегральным микросхемам. В автомате на полурешётках каждая переменная принимает значения в некоторой конечной верхней полурешётке, т. е. в частично упорядоченном множестве, в котором любые два элемента имеют точную верхнюю грань, называемую суммой этих элементов, и которое вместе с математическими действиями, моделирующими структурные операции в автомате, образует полурешёточно упорядоченную алгебру. Имеются по меньшей мере четыре свидетельства полезности теории дискретных автоматов на полурешётках.Дискретные автоматы на полурешетках27Во-первых, математический аппарат классических функциональных систем (алгебра логики, конечнозначная логика, теория автоматов), будучи удобным языком для адекватного описания статического (при фиксированном входном состоянии) поведения дискретного устройства, к сожалению, недостаточен для адекватного описания его динамического (вызываемого асинхронным изменением компонент входного состояния) поведения. Причина этого - в отсутствии в дискретной математике средств для выражения изменения дискретной величины, подобных дифференциалу и производной в непрерывной математике. Этот недостаток преодолевается в функциональных системах на полурешётках, каковыми являются полурешёточно упорядоченные алгебры. В описании динамического поведения дискретного автомата средствами такой алгебры отношение порядка в последней интерпретируется как отношение сравнения состояний в автомате по степени их неопределённости, обязанной явлению состязаний, которые возникают между компонентами состояния в процессе их асинхронного изменения, а сумма состояний в полурешетке моделирует это изменение как промежуточное (переходное) состояние. Например, асинхронное изменение состояния входов автомата с а на b моделируется в его описании промежуточным состоянием a + b. Именно a + b предложено рассматривать как выражение для изменения значения дискретной величины с а на Ь.Далее, в дискретных функциональных системах с частично определенными функциями, такими, как частичные функции конечнозначной логики, частично рекурсивные функции, частичные конечно-автоматные функции и т.п., неопределённость значения переменной (аргумента, функции) трактуется обычно одним способом - как любое из всех возможных определенных значений этой переменной. В приложениях к дискретным автоматам, в особенности на базе БИС и СБИС, такая трактовка ведет нередко к снижению точности используемых моделей со всеми вытекающими отсюда неприятными последствиями: в синтезе - затрудняются формализация исходных функций и их декомпозиция, в анализе - теряется необходимая информация. Этот недостаток математического аппарата можно преодолеть, если в область значений каждой переменной ввести значения разной степени неопределённости, трактуемые как любые из некоторых определённых значений и образующие в совокупности верхнюю полурешётку подмножеств определённых значений.Важнейшими характеристиками любой математической модели, чем в сущности и служит дискретный автомат, являются ее адекватность и степень точности. В случае дискретных моделей первая понимается как безошибочность в том смысле, что результат адекватного моделирования всегда содержит в себе истинное значение моделируемой величины, а вторая - как степень неопределённости этого результата. Формализовать эти понятия традиционными средствами дискретной математики не удается. Аппарат же теории полурешеток позволяет сделать это путём определения адекватной модели полурешётки как множества из наибольших элементов всех смежных классов последней по некоторой конгруэнции на ней, которая, в свою очередь, представляет собой степень точности этой модели. В результате утверждения об адекватности и точности дискретных моделей становятся теоремами.Наконец, рассматривая функции и автоматы как определённые на полурешётках, можно дать точное определение их физической реализуемости. Это понятие оказывается равносильным математическому понятию квазимонотонности, ибо квазимонотонные функции и автоматы на полурешётках и только они допускают схемную реализацию на современной микроэлектронной базе.28Г. П. АгибаловТаким образом, изучая дискретные автоматы на полурешётках, можно определить такие важные атрибуты дискретной управляющей системы, как динамическое поведение, физическая реализуемость, адекватная модель и ее точность, и сделать утверждения о них доказательными. Традиционные задачи проектирования дискретных автоматов на абстрактном и структурном уровнях представления, включая задачи эквивалентных преобразований, минимизации, декомпозиции, кодирования, моделирования, анализа, синтеза и др., удается теперь поставить и решить в новой, более общей постановке, отражающей динамику поведения автомата, его физическую реализуемость и адекватность моделирования с любой наперёд заданной точностью.Первые конкретные результаты, продемонстрировавшие все эти возможности теории дискретных автоматов на полурешётках, получены автором в [1 - 7] и систематизированы в его монографии [6]. Истоком для них послужили исследования [8, 9], проведённые под руководством автора с целью создания адекватной математической модели функционирования БИС транзисторного уровня и разработки на её основе методов логического проектирования таких схем. Ниже в реферативной форме приводится обзор основных элементов теории дискретных автоматов на полурешётках, представленных в книге [6]. Доказательства всех теорем в нём можно найти также в [6]. Дальнейшее развитие исследования в этом направлении нашли в работах И. А. Панкратовой [10] и Н. Г. Парватова [11, 12].1. Полурешётки1.1.Точечные полурешёткиВсюду далее под полурешёткой подразумевается конечная верхняя полурешётка, т. е. конечное частично упорядоченное множество, в котором любые два элемента а и b имеют точную верхнюю грань, называемую их суммой и обозначаемую a + b. В ней обязательно есть наибольший и минимальные элементы. Последние называются точками полурешетки. Полурешётка точечная, если она порождается своими точками, т. е. если каждый ее элемент равен сумме некоторых точек. Множество всех непустых подмножеств конечного множества М обозначается М. Полурешётка с элементами в М и с включением в качестве отношения порядка называется полурешеткой подмножеств множества М.Теорема 1. Всякая точечная полурешётка изоморфна полурешётке подмножеств своих точек.1.2.Покрытия полурешётокПокрытием полурешётки S называется всякое множество Р различных и непустых подмножеств множества S, называемых блоками покрытия, которые обладают следующими свойствами: 1) объединение блоков в Р есть S; 2) каждый блок в Р является подполурешёткой в S; 3) для любых блоков А и В в Р существует блок С в Р, называемый их суммой в Р и обозначаемый А (В В, который в Р является точной верхней гранью для А + В по отношению вкючения. Покрытие Р называется ассоциативным, если в нём ассоциативна определённая так операция сложения ф. Вместе с последней ассоциативное покрытие полурешётки само есть полурешётка. Покрытие полурешётки называется П-покрытием, если сложение в нём совпадает с пересечением.Теорема 2. Всякая полурешётка изоморфна своему П-покрытию.Дискретные автоматы на полурешетках291.3. Полурешётки п р о в о д и м о с т е й и состоянийПолурешетки подмножеств множества Е = {0,1,Х} называются полурешётками проводимостей, а полурешётки подмножеств r-й декартовой степени Ег множества Е для любого г ^ 2 - полурешётками состояний. Символы 0, 1, X в них интерпретируются как статические, или определённые, проводимости соответственно разомкнутой, замкнутой и резистивной электрических цепей, а их наборы в ЕТ - как статические, или определенные, состояния узла электронной схемы, представленные проводимо-стями схемы от полюсов источника питания до данного узла. Соответственно этому подмножества в Е, обозначаемые как 0' = {1, X}, 1' = {О, X}, X' = {0, 1}, Е = {0, 1, X}, - это динамические, или в разной степени неопределённые проводимости цепей, а подмножества в Ет - это такие же состояния узлов схемы.Теорема 3. Всякая точечная полурешётка с к точками изоморфна полурешётке состояний любой размерности г ^ log3 к.1.4. Адекватные модели полурешётокПусть S - полурешётка со сложением + и а - конгруэнция на ней. Каждый смежный класс А в S/a является подполурешёткой в S, и в нем есть наибольший элемент sup А. Смежные классы А ж В как элементы фактор-полурешётки S/a и элементы в них, в том числе наибольшие, как элементы полурешётки S связаны между собой соотношением: А ^ В -Ф^ sup A ^ sup В -Ф^ За G АЗЬ G В (а ^ Ъ). Пусть далее S"f a = = {sup A : A G S/a}. Определим на S"f= М| R.Пусть р является ядерной конгруэнцией гомоморфизма полурешёток h : {R} -^< R >, где h(P) для Р С М есть наименьший интервал в < R > со свойством Р С h(P).Теорема 6. < R >= {Д}|р-Следствие 1. М и < R > - адекватные модели М. Адекватные модели М являются адекватными моделями М.Полурешётки М, М и {R} точечные.Теорема 7. Полурешётка < R > точечная, если M/R С М.30Г. П. АгибаловВ [6] можно найти многочисленные примеры адекватных моделей полурешёток состояний для адекватного моделирования МДП-схем различных классов с той или иной точностью.1.5. Кодирование полурешётокВсюду далее через m(L) обозначается множество точек полурешётки L, через M(L)- множество всех минимальных (по включению) подмножеств в L, не имеющих в Lнижней грани, и r(L) = max \A\.Аем(ь)Пусть В и Q - полурешётки и п - натуральное число. Если существуют такие полурешётка К С Вп (с элементами и порядком в полурешётке Вп) и эпиморфизм полурешёток h : К -> Q, что для любого подмножества U С К, имеющего в Вп нижнюю грань, подмножество h(U) С Q имеет нижнюю грань в Q, то h называется кодированием, & К - кодом полурешётки Q с основанием В, длиной п и значностъю к= \т{В)\.Теорема 8. Для полурешётки Q, допускающей fc-значное кодирование, к ^ t(Q). Точечная полурешётка Q допускает fc-значное кодирование, если и только если k>r{Q).Теорема 9. Точечная полурешётка Q тогда и только тогда допускает кодирование с основанием В = М, когда \М\ ^ r{Q).Для любого ACQ определяется Q(A) как q Е Q(A) -ФФ- q E m(Q) Л За Е A(q ^ а) и Q(a) = Q(A) для А = {а}. Подмножество Т С Q(A) называется допустимым, если За Е A(TOQ(a) = 0). Вектор с |ra(Q)| компонентами, поставленными во взаимно однозначное соответствие элементам в m(Q) и имеющими значения в В, называется разделяющим вектором подмножества ACQ, если существует разбиение множества Q(A) на допустимые подмножества (блоки) так, что значения любых двух компонент вектора, соответствующих элементам в Q(A) из разных блоков разбиения, не имеют общей нижней грани в полурешётке В. Матрица с элементами в В, составленная из |ra(Q)| строк и имеющая для каждого А Е M(Q) разделяющий вектор-столбец, называется разделяющей матрицей полурешётки Q. Подполурешётка в В порождается матрицей, если строки последней образуют порождающее множество этой полурешетки.Теорема 10. Точечная полурешетка, допускающая код с длиной п и основанием В = М, допускает код с длиной п и основанием В, порожденный её разделяющей матрицей с элементами в т(В).Таким образом, кратчайший код точечной полурешётки Q с основанием М порождается её разделяющей матрицей с наименьшим числом столбцов. Построение такой матрицы сводится к нахождению кратчайшего покрытия множества M(Q) векторами в Мт, где т = \m{Q)\ и вектор покрывает подмножество А Е M(Q), если он является разделяющим для А. Алгоритмы нахождения кратчайших покрытий множеств хорошо известны и исследованы [13].2. Полурешеточно упорядоченные алгебры2.1. Метод точечного расширенияМетод предназначен для расширения любой заданной абстрактной алгебры до полурешеточно упорядоченных алгебр. Для этого множество А элементов абстрактной алгебры заменяется некоторой полурешёткой L, такой, что m(L) = А, и каждая гг-местная алгебраическая операция и, определённая на А, распространяется на L поДискретные автоматы на полурешетках31правилу точечного продолжения: и)(х\, ...,хп) = ^ui(a\,..., an), где сумма ^2 берется по всем наборам (a\...an) Е (m(L))n, в которых а» ^ х^ для г = 1, ...,п. Таким образом строятся полурешёточно упорядоченные алгебры fc-значной логики, проводимостей и состояний.2.2. Полурешёточно упорядоченные алгебрыfc-значной логикиОни являются точечными расширениями на полурешётках подмножеств в Ек = {0,1,..., А; - 1} алгебры fc-значной логики (Ек, ->, А, V), где ->а = к - 1 - а, а А Ъ = min(a, b), a V Ъ = тах(а, Ъ). В них операции -i, Л, V над операндами в Ек вводятся по правилу точечного продолжения, а именно: -ix = {->а : а Е х},х Ay = {a Ab : aEx,bEy},x\/y={a\/b: a E x,b E у}.Теорема 11. В полурешёточно упорядоченной алгебре (Ек, -i, Л, V) наряду с обычными законами идемпотентности, ассоциативности, коммутативности операций Л и V, де Моргана и двойного отрицания имеют место следующие законы, где щ,щ,и\ обозначают соответственно наименьший, произвольный и наибольший элементы в Ек, содержащиеся в элементе и Е Ек'-1))слабого поглощения - ж С ж V (ж Л у), ж С ж Л (ж V у);2)слабой дистрибутивности - хА(у\/z) С (жЛу)\/(xAz), жV(yЛz) С (x\/y)A(x\/z);3)4))обобщённой дистрибутивности - (ж А у) V (х A z) = (х А у) V (х A z) V (x А (у V z)), (х V у) А (х V z) = (х V у) А (х V z) А (х V (у A z));5)6))частичной дистрибутивности - х А (у V z) = (х А у) V (х A z), если и только если7)Ууг(Уг > Х\ ИЛИ J/j < Xq ИЛИ J/j ^ Zq ИЛИ J/j E х) И Vz^Zj > Х\ ИЛИ Zj < Xq ИЛИz% ^ Уо или Zj G ж), ж V (у Л z) = (х V у) А (х V z), если и только если Ууг(Уг < Xq илиJ/i > Х\ ИЛИ J/j ^ Zi ИЛИ yi E х) И \/Zi(Zi < Xq ИЛИ Zj > Ж1 ИЛИ Zj ^ J/i ИЛИ Zi Е Х)\5)частичного поглощения - х = х V (х Ау) и х = х А (х V у), если и только еслиVyi(yi < Ж0 ИЛИ yi > Х\ ИЛИ Уг Е х).Таким образом, законы поглощения и дистрибутивности алгебры fc-значной логики не сохраняются в её точечном расширении на полурешётке Ек- Это есть отражение известого свойства асинхронных схем - зависимости их функционирования от состязаний, которые в разных логических структурах проявляются по-разному.2.3. Алгебры проводимостейВ алгебрах проводимостей элементы принадлежат полурешётке проводимостей, а операциями могут быть -i, Л, V, в, их суперпозиции и др. На множестве Е операции Л, V и в, соответственно конъюнкция, дизъюнкция и мостик, определяются как функции проводимости соответственно последовательного, параллельного и мостикового соединений цепей с проводимостями в Е, а операция -i (отрицание), сохраняя X, переводит одну в другую проводимости 0 и 1. На полурешетке Е они распространяются по правилу точечного продолжения. При таком определении (Е,->, A,V) = (Ез,->, A,V).Теорема 12. В алгебре проводимостей (Е,- f(a) ^ f(b). Говорим, что функция g реализует функцию /, и пишем g ^ /, если Df С Dg, V/ С Vg и g(a) ^ f(a) для всех а Е Df. Функция называется квазимонотонной из полурешётки D в полурешётку V, если она реализуется некоторой монотонной функцией д : D -> V. Квазимонотонная из D в V функция / : D -> V называется квазимонотонной.Введенные функции замечательны тем, что функции на полурешётках у элементов реальных схем точечные или аддитивные, у самих схем - монотонные, а реализуемые схемами - квазимонотонные.Теорема 13. Всякая аддитивная функция с точечной областью определения точечная. Всякая точечная функция с областью определения Df = М аддитивная.Теорема 14. Все аддитивные и точечные функции монотонные. Суперпозиция монотонных или квазимонотонных функций есть функция монотонная или квазимонотонная соответственно.Теорема 15 (тест квазимонотонности). Функция / квазимонотонна из D в V, если и только если Df С D,Vf С V и для любого U С Df, где 2 ^ \U\ ^ |га(У)| иДискретные автоматы на полурешетках33х Е U => f(x) ф sup V, из существования в D нижней грани для U следует существование в V нижней грани для f(U).В этом случае монотонная функция д, реализующая /, строится так: для любого a Е D определяется Ua = {u Е Df : а ^ и} и за д(а) принимается sup V, если Ua = 0, или наибольшая из нижних граней множества f(Ua) в V в противном случае.3.2. Реализация бинарных отношенийФункция д : D -> V реализует бинарное отношение а С D х V, если ааЪ =>-(/(а) ^

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

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

Авторы

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

Ссылки

Агибалов Г. П. Функциональные системы на полурешётках // Алгоритмы решения задач дискретной математики. Вып. 2. Томск: Изд-во Том. ун-та, 1987. С. 3-39.
Agibalov G. P. Functional systems on semilattices // Fundamentals of Computation Theory / Eds. R. G. Bukharaev, О. В. Lupanov. Berlin: Springer Verlag, 1987. P. 5-9.
Агибалов Г. П. Квазимонотонные функции и их минимизация // Кибернетика. 1989. №2. С.111-113.
Agibalov G. P. Finite automata on partially ordered sets // Automatic Control. 11th IFAC World Congress Proceedings / Eds. V. Utkin, U. Jaaksoo. Oxford; New York; Seoul; Tokyo: Pergamon Press, 1991. V. 3.
Агибалов Г. П. К кодированию полурешёток и автоматов на полурешётках // Дискретная математика. 1991. Т. 3. Вып. 2. С. 74-87.
Агибалов Г. П. Дискретные автоматы на полурешётках. Томск: Изд-во Том. ун-та, 1993. 227 с.
Агибалов Г. П. Адекватные модели полурешёток, функций и автоматов на полурешётках // Вестник Томского госуниверситета. Июнь 2000. №271. С. 118-121.
Агибалов Г. П., Бузанов В. А., Липский В. Б., Румянцев Б. Ф. Математическая модель схем из элементов с управляемой проводимостью // Автоматика и телемеханика. 1982. №9. С. 89-98.
Агибалов Г. П., Бузанов В. А., Липский В. Б., Румянцев Б. Ф. Логическое проектирование переключательных автоматов. Томск: Изд-во Том. ун-та, 1983. 154 с.
Панкратова И. А. Реализация функций на полурешётках переключательными схемами // Прикладная дискретная математика. 2009. №2. С. 50-55.
Парватов П. Г. Функциональная полнота в замкнутых классах квазимонотонных и монотонных трёхзначных функций на полурешётке // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10. №1. С. 61-78.
Парватов П. Г. Теорема о функциональной полноте в классе квазимонотонных функций на конечной полурешётке // Дискретный анализ и исследование операций. Сер. 1. 2006. Т. 13. №3. С. 62-82.
Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.
 ДИСКРЕТНЫЕ АВТОМАТЫ НА ПОЛУРЕШЁТКАХ             | ПДМ. 2009. № 2(4).

ДИСКРЕТНЫЕ АВТОМАТЫ НА ПОЛУРЕШЁТКАХ | ПДМ. 2009. № 2(4).

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