авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА

2009 Теоретические основы прикладной дискретной математики №2(4)

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

ПРИКЛАДНОЙ

ДИСКРЕТНОЙ МАТЕМАТИКИ

УДК 519.7

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

Г. П. Агибалов

Томский государственный университет, г. Томск, Россия

E-mail: agibalov@isc.tsu.ru

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

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

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

Имеются по меньшей мере четыре свидетельства полезности теории дискретных авто матов на полурешётках.

Дискретные автоматы на полурешетках Во-первых, математический аппарат классических функциональных систем (алге бра логики, конечнозначная логика, теория автоматов), будучи удобным языком для адекватного описания статического (при фиксированном входном состоянии) поведе ния дискретного устройства, к сожалению, недостаточен для адекватного описания его динамического (вызываемого асинхронным изменением компонент входного состо яния) поведения. Причина этого в отсутствии в дискретной математике средств для выражения изменения дискретной величины, подобных дифференциалу и производ ной в непрерывной математике. Этот недостаток преодолевается в функциональных системах на полурешётках, каковыми являются полурешёточно упорядоченные ал гебры. В описании динамического поведения дискретного автомата средствами такой алгебры отношение порядка в последней интерпретируется как отношение сравнения состояний в автомате по степени их неопределённости, обязанной явлению состязаний, которые возникают между компонентами состояния в процессе их асинхронного изме нения, а сумма состояний в полурешетке моделирует это изменение как промежуточное (переходное) состояние. Например, асинхронное изменение состояния входов автома та с a на b моделируется в его описании промежуточным состоянием a + b. Именно a + b предложено рассматривать как выражение для изменения значения дискретной величины с a на b.

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

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

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

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

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

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

Первые конкретные результаты, продемонстрировавшие все эти возможности тео рии дискретных автоматов на полурешётках, получены автором в [1 – 7] и систематизи рованы в его монографии [6]. Истоком для них послужили исследования [8, 9], прове дённые под руководством автора с целью создания адекватной математической модели функционирования БИС транзисторного уровня и разработки на её основе методов ло гического проектирования таких схем. Ниже в реферативной форме приводится обзор основных элементов теории дискретных автоматов на полурешётках, представленных в книге [6]. Доказательства всех теорем в нём можно найти также в [6]. Дальнейшее развитие исследования в этом направлении нашли в работах И. А. Панкратовой [10] и Н. Г. Парватова [11, 12].

1. Полурешётки 1.1. Т о ч е ч н ы е п о л у р е ш ё т к и Всюду далее под полурешёткой подразумевается конечная верхняя полурешётка, т. е. конечное частично упорядоченное множество, в котором любые два элемента a и b имеют точную верхнюю грань, называемую их суммой и обозначаемую a + b. В ней обязательно есть наибольший и минимальные элементы. Последние называются точ ками полурешетки. Полурешётка точечная, если она порождается своими точками, т. е. если каждый ее элемент равен сумме некоторых точек. Множество всех непустых подмножеств конечного множества M обозначается M. Полурешётка с элементами в M и с включением в качестве отношения порядка называется полурешеткой под множеств множества M.

Теорема 1. Всякая точечная полурешётка изоморфна полурешётке подмножеств своих точек.

1.2. П о к р ы т и я п о л у р е ш ё т о к Покрытием полурешётки S называется всякое множество P различных и непустых подмножеств множества S, называемых блоками покрытия, которые обладают следу ющими свойствами: 1) объединение блоков в P есть S;

2) каждый блок в P является подполурешёткой в S;

3) для любых блоков A и B в P существует блок C в P, назы ваемый их суммой в P и обозначаемый A B, который в P является точной верхней гранью для A + B по отношению вкючения. Покрытие P называется ассоциативным, если в нём ассоциативна определённая так операция сложения. Вместе с последней ассоциативное покрытие полурешётки само есть полурешётка. Покрытие полурешётки называется П-покрытием, если сложение в нём совпадает с пересечением.

Теорема 2. Всякая полурешётка изоморфна своему П-покрытию.

Дискретные автоматы на полурешетках 1.3. П о л у р е ш ё т к и п р о в о д и м о с т е й и с о с т о я н и й Полурешетки подмножеств множества E = {0, 1, X} называются полурешётками проводимостей, а полурешётки подмножеств r-й декартовой степени E r множества E для любого r 2 полурешётками состояний. Символы 0, 1, X в них интерпретиру ются как статические, или определённые, проводимости соответственно разомкнутой, замкнутой и резистивной электрических цепей, а их наборы в E r как статические, или определенные, состояния узла электронной схемы, представленные проводимо стями схемы от полюсов источника питания до данного узла. Соответственно этому подмножества в E, обозначаемые как 0 = {1, X}, 1 = {0, X}, X = {0, 1}, E = {0, 1, X}, это динамические, или в разной степени неопределённые проводимости цепей, а подмножества в E r это такие же состояния узлов схемы.

Теорема 3. Всякая точечная полурешётка с k точками изоморфна полурешётке состояний любой размерности r log3 k.

1.4. А д е к в а т н ы е м о д е л и п о л у р е ш ё т о к Пусть S полурешётка со сложением + и конгруэнция на ней. Каждый смеж ный класс A в S/ является подполурешёткой в S, и в нем есть наибольший элемент sup A. Смежные классы A и B как элементы фактор-полурешётки S/ и элементы в них, в том числе наибольшие, как элементы полурешётки S связаны между собой соотношением: A B sup A sup B a Ab B (a b). Пусть далее S = = {sup A : A S/}. Определим на S сложение как ab = sup [a+b]. Вместе с множество S является полурешёткой, гомоморфной полурешётке S и изоморфной полурешётке S/, и называется адекватной моделью полурешётки S с точностью.

Для любой эквивалентности R на M определим эквивалентность R на M как A R B a Ab B(a R b) b Ba A(a R b). Это есть конгруэнция на полурешётке M. Пусть {R} обозначает подполурешётку в M, порождённую смежны ми классами эквивалентности R.

Теорема 4. {R} = M R.

В случае, когда M есть декартово произведение множеств, те его непустые подмно жества, которые сами являются декартовыми произведениями множеств, называются интервалами в M. Пусть в этом случае M есть множество всех интервалов в M, R = M {R} и R есть минимальная конгруэнция на M, такая, что для любо го смежного класса A эквивалентности R существует смежный класс конгруэнции R, содержащий в качестве элементов все одноэлементные подмножества в A.

Теорема 5. R = M R.

Пусть является ядерной конгруэнцией гомоморфизма полурешёток h : {R} R, где h(P ) для P M есть наименьший интервал в R со свойством P h(P ).

Теорема 6. R = {R}.

Следствие 1. M и R адекватные модели M. Адекватные модели M яв ляются адекватными моделями M.

Полурешётки M, M и {R} точечные.

Теорема 7. Полурешётка R точечная, если M/R M.

30 Г. П. Агибалов В [6] можно найти многочисленные примеры адекватных моделей полурешёток состояний для адекватного моделирования МДП-схем различных классов с той или иной точностью.

1.5. К о д и р о в а н и е п о л у р е ш ё т о к Всюду далее через m(L) обозначается множество точек полурешётки L, через M (L) множество всех минимальных (по включению) подмножеств в L, не имеющих в L нижней грани, и r(L) = max |A|.

AM (L) Пусть B и Q полурешётки и n натуральное число. Если существуют такие полурешётка K B (с элементами и порядком в полурешётке B n ) и эпиморфизм n полурешёток h : K Q, что для любого подмножества U K, имеющего в B n нижнюю грань, подмножество h(U ) Q имеет нижнюю грань в Q, то h называется кодированием, а K кодом полурешётки Q с основанием B, длиной n и значностью k = |m(B)|.

Теорема 8. Для полурешётки Q, допускающей k-значное кодирование, k r(Q).

Точечная полурешётка Q допускает k-значное кодирование, если и только если k r(Q).

Теорема 9. Точечная полурешётка Q тогда и только тогда допускает кодирова ние с основанием B M, когда |M | r(Q).

= Для любого A Q определяется Q(A) как q Q(A) q m(Q) a A(q a) и Q(a) = Q(A) для A = {a}. Подмножество T Q(A) называется допустимым, если a A(T Q(a) = ). Вектор с |m(Q)| компонентами, поставленными во взаимно одно значное соответствие элементам в m(Q) и имеющими значения в B, называется разде ляющим вектором подмножества A Q, если существует разбиение множества Q(A) на допустимые подмножества (блоки) так, что значения любых двух компонент векто ра, соответствующих элементам в Q(A) из разных блоков разбиения, не имеют общей нижней грани в полурешётке B. Матрица с элементами в B, составленная из |m(Q)| строк и имеющая для каждого A M (Q) разделяющий вектор-столбец, называется разделяющей матрицей полурешётки Q. Подполурешётка в B порождается матри цей, если строки последней образуют порождающее множество этой полурешетки.

Теорема 10. Точечная полурешетка, допускающая код с длиной n и основанием M, допускает код с длиной n и основанием B, порожденный её разделяющей B= матрицей с элементами в m(B).

Таким образом, кратчайший код точечной полурешётки Q с основанием M порож дается её разделяющей матрицей с наименьшим числом столбцов. Построение такой матрицы сводится к нахождению кратчайшего покрытия множества M (Q) векторами в M m, где m = |m(Q)| и вектор покрывает подмножество A M (Q), если он явля ется разделяющим для A. Алгоритмы нахождения кратчайших покрытий множеств хорошо известны и исследованы [13].

2. Полурешеточно упорядоченные алгебры 2.1. М е т о д т о ч е ч н о г о р а с ш и р е н и я Метод предназначен для расширения любой заданной абстрактной алгебры до полурешёточно упорядоченных алгебр. Для этого множество A элементов абстракт ной алгебры заменяется некоторой полурешёткой L, такой, что m(L) = A, и каждая n-местная алгебраическая операция, определённая на A, распространяется на L по Дискретные автоматы на полурешетках правилу точечного продолжения: (x1,..., xn ) = (a1,..., an ), где сумма берется n по всем наборам (a1...an ) (m(L)), в которых ai xi для i = 1,..., n. Таким образом строятся полурешёточно упорядоченные алгебры k-значной логики, проводимостей и состояний.

2.2. П о л у р е ш ё т о ч н о у п о р я д о ч е н н ы е а л г е б р ы k-значной логики Они являются точечными расширениями на полурешётках подмножеств в Ek = {0, 1,..., k 1} алгебры k-значной логики (Ek, ¬,, ), где ¬a = k 1 a, a b = min(a, b), a b = max(a, b). В них операции ¬,, над операндами в Ek вво дятся по правилу точечного продолжения, а именно: ¬x = {¬a : a x}, x y = {a b :

a x, b y}, x y = {a b : a x, b y}.

Теорема 11. В полурешёточно упорядоченной алгебре (Ek, ¬,, ) наряду с обыч ными законами идемпотентности, ассоциативности, коммутативности операций и, де Моргана и двойного отрицания имеют место следующие законы, где u0, ui, u1 обо значают соответственно наименьший, произвольный и наибольший элементы в Ek, содержащиеся в элементе u Ek :

1) слабого поглощения x x (x y), x x (x y);

2) слабой дистрибутивности x(yz) (xy)(xz), x(yz) (xy)(xz);

3) обобщённой дистрибутивности (x y) (x z) = (x y) (x z) (x (y z)), (x y) (x z) = (x y) (x z) (x (y z));

4) частичной дистрибутивности x (y z) = (x y) (x z), если и только если yi (yi x1 или yi x0 или yi z0 или yi x) и zi (zi x1 или zi x0 или zi y0 или zi x), x (y z) = (x y) (x z), если и только если yi (yi x0 или yi x1 или yi z1 или yi x) и zi (zi x0 или zi x1 или zi y1 или zi x);

5) частичного поглощения x = x (x y) и x = x (x y), если и только если yi (yi x0 или yi x1 или yi x).

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

2.3. А л г е б р ы п р о в о д и м о с т е й В алгебрах проводимостей элементы принадлежат полурешётке проводимостей, а операциями могут быть ¬,,,, их суперпозиции и др. На множестве E операции, и, соответственно конъюнкция, дизъюнкция и мостик, определяются как функции проводимости соответственно последовательного, параллельного и мостикового соеди нений цепей с проводимостями в E, а операция ¬ (отрицание), сохраняя X, переводит одну в другую проводимости 0 и 1. На полурешетке E они распространяются по пра вилу точечного продолжения. При таком определении (E, ¬,, ) (E3, ¬,, ).

= Теорема 12. В алгебре проводимостей (E, ¬,, ) законы частичной дистрибу тивности и частичного поглощения имеют вид: x (y z) = (x y) (x z), если и только если x = X или [(y = 1 или z X ) и (z = 1 или y X )];

x (y z) = (x y) (x z), если и только если x = X или [(y = 0 или z X ) и (z = 0 или y X )];

x = x (x y) и x = x (x y), если и только если x = X или y X )].

32 Г. П. Агибалов 2.4. А л г е б р ы с о с т о я н и й Алгебры состояний это полурешёточно упорядоченные векторные алгебры с со стояниями в полурешётке E r в качестве векторов и с проводимостями в полурешётке E в качестве скаляров. Операциями в них могут быть умножение скаляра на вектор и операции над векторами ¬, I,,. Для скаляра c в E и вектора a в E r вектор ca есть покомпонентная конъюнкция векторов cr и a. Одноместные ¬, I и двухместные, над векторами в E r определяются как покомпонентное отрицание проводимостей, ин версия порядка следования компонент и покомпонентные конъюнкция и дизъюнкция соответственно. Для проводимостей в E и состояний в E r все эти операции определя ются по правилу точечного продолжения. В электронных схемах произведение c a моделирует передачу состояния a по цепи с проводимостью c, а операция функцию узла схемы: состояние узла, в котором сходятся различные проводники, равно резуль тату применения к состояниям других концов этих проводников. Операции, не имеют аналогов в алгебре k-значной логики, свидетельствуя о её недостаточности для моделирования современных БИС и СБИС.

2.5. А д е к в а т н ы е м о д е л и полурешёточно упорядоченных алгебр В адекватной модели полурешёточно упорядоченной алгебры множество элементов является адекватной моделью с некоторой точностью для полурешётки элементов данной алгебры A, а операциями выступают адекватные модели операций в A, определяемые как (a1,..., an ) = sup [(a1,..., an )]. Адекватные модели алгебр прово димостей и состояний служат адекватному моделированию БИС и СБИС различных типов с разной степенью точности.

3. Функции на полурешётках 3.1. В а ж н е й ш и е к л а с с ы Рассматриваются функции, области определения и значений которых являются полурешётками. Для функции f они обозначаются Df и Vf соответственно. Функция называется аддитивной, если она является гомоморфизмом полурешёток (сохраняет операцию сложения). Функция f точечная, если a Df (f (a) = f (b). Функ bm(Df ),b a b f (a) ция f монотонная, если она сохраняет порядок: a f (b). Говорим, что функция g реализует функцию f, и пишем g f, если Df Dg, Vf Vg и g(a) f (a) для всех a Df. Функция называется квазимонотонной из полурешётки D в по лурешётку V, если она реализуется некоторой монотонной функцией g : D V.

Квазимонотонная из D в V функция f : D V называется квазимонотонной.

Введенные функции замечательны тем, что функции на полурешётках у элементов реальных схем точечные или аддитивные, у самих схем монотонные, а реализуемые схемами квазимонотонные.

Теорема 13. Всякая аддитивная функция с точечной областью определения то чечная. Всякая точечная функция с областью определения Df M аддитивная.

= Теорема 14. Все аддитивные и точечные функции монотонные. Суперпозиция монотонных или квазимонотонных функций есть функция монотонная или квазимо нотонная соответственно.

Теорема 15 (тест квазимонотонности). Функция f квазимонотонна из D в V, ес ли и только если Df D, Vf V и для любого U Df, где 2 |U | |m(V )| и Дискретные автоматы на полурешетках x U f (x) = sup V, из существования в D нижней грани для U следует существо вание в V нижней грани для f (U ).

В этом случае монотонная функция g, реализующая f, строится так: для любого a D определяется Ua = {u Df : a u} и за g(a) принимается sup V, если Ua =, или наибольшая из нижних граней множества f (Ua ) в V в противном случае.

3.2. Р е а л и з а ц и я б и н а р н ы х о т н о ш е н и й Функция g : D V реализует бинарное отношение D V, если ab g(a) g(b). Отношение квазимонотонно, если оно реализуется квазимонотонной и, значит, монотонной функцией.

Теорема 16. Отношение D V квазимонотонно, если и только если для любых (a1, b1 ),..., (am, bm ) в, где 2 m |m(V )| и {a1,..., am } имеет нижнюю грань в D, множество {b1,..., bm } имеет нижнюю грань в V.

3.3. М и н и м и з а ц и я ч и с л а а р г у м е н т о в В случае Df = X1... Xn функция f зависит от n аргументов x1,..., xn, опре делённых на полурешётках X1,..., Xn соответственно. Подмножество этих аргументов Z = {xj1,..., xjk } для j1... jk достаточно для f, если существует монотонная функция g от аргументов в Z, удовлетворяющая для каждого a = (a1...an ) Df отно шению реализации: g(aj1...ajk ) f (a). Пусть U (j1,..., jk ) = {(aj1...ajk ) : (a1...an ) U }.

Теорема 17 (тест достаточности). Подмножество Z достаточно для f, если и только если для любого подмножества U Df, для которого 2 |U | |m(Vf )|, из существования в Xj1... Xjk нижней грани для U (j1,..., jk ) следует существование в Vf нижней грани для f (U ).

Ввиду этой теоремы если каждому минимальному подмножеству U = {ai1 ai2...ain :

i = 1, 2,..., |U |} Df, для которого f (U ) не имеет нижней грани в Vf, сопоставить булев вектор b1 b2...bn, в котором для каждого j = 1, 2,..., n имеем bj = 1 тогда и только тогда, когда в Xj нет нижней грани для {aij : i = 1, 2,..., |U |}, и выписать все такие векторы один под другим, то получится матрица, номера столбцов кратчайшего по крытия которой указывают на аргументы достаточного для f подмножества наимень шей мощности. Так решается задача минимизации числа аргументов квазимонотонной функции на полурешётках.

3.4. Ф у н к ц и о н а л ь н а я р а з д е л и м о с т ь Упорядоченное разбиение множества X аргументов функции f : S n S на два или три класса, где первый класс есть A и второй B, обозначается A/B;

в нём p = |A|, q = |B| и r = n (p + q). Пусть задано некоторое такое разбиение A/B. Если x S n, т. е. x есть набор значений переменных X, то через xa, xb и xc обозначают элементы в S p, S q и S r, являющиеся наборами тех значений переменных A, B и X (A B) соот ветственно, которые содержатся в x. Функция f называется разделимой по разбиению A/B, если существуют квазимонотонные функции g : S r+q S и h : S p+r+1 S, что для любого x S n и любой квазимонотонной функции g : S r+q S, реализующей g, f (x). Пусть Hij (f ) для i S r и j S q обознача имеет место h(xa, xc, g (xc, xb )) ет множество всех квазимонотонных функций hij : S p S, реализующих функцию fij : S p S, определяемую как fij (m) = f (x), где xa = m, xb = j и xc = i.

Теорема 18. Квазимонотонная функция f : S n S разделима по разбиению A/B, если и только если для любых i S r и j S q можно указать sij S и hij Hij (f ) так, что sij1 = sij2 hij1 = hij2 и для любых m1,..., mk в S p, i1,..., ik в S r и j1,..., jk 34 Г. П. Агибалов в S q, где 2 k |m(S)|, из существования нижних граней в S r+q для {i1 j1,..., ik jk } и в S p+r+1 для {m1 i1 si1 j1,..., mk ik sik jk } следует существование нижних граней в S для {si1 j1,..., sik jk } и {hi1 j1 (m1 ),..., hik jk (mk )} соответственно.

3.5. А д е к в а т н ы е м о д е л и ф у н к ц и й Функция g называется адекватной моделью функции f с точностью (, ), если и суть когруэнции на полурешётках Df и Vf соответственно, Dg = Df, Vg = Vf и g(a) = sup [f (a)] для всех a Dg. Функция f сохраняет пару (, ), если ab f (a)f (b).

Теорема 19. Пусть g есть адекватная модель функции f с точностью (, ).

1) Если функция f монотонная или квазимонотонная, то функция g также монотон ная или квазимонотонная соответственно. 2) Если функция f сохраняет пару (, ) и аддитивна, то функция g также аддитивна. 3) Пусть f = f0 (f1,..., fm ), функция g0 есть адекватная модель функции f0 с точностью (, ), функция gi есть адекватная модель функции fi с точностью (, i ), i = 1,..., m, = 1... m и h = g0 (g1,..., gm ). Тогда если функция f0 монотонная, то g h;

если же f0 сохраняет пару (, ), то g = h.

Утверждение 3 теоремы допускает следующую интерпретацию: заменив в какой либо схеме функции элементов их адекватными моделями, получим схему, функция которой реализуется адекватной моделью функции прежней схемы, если функции эле ментов монотонные, и совпадает с ней, если функции элементов сохраняют точности их моделей. Есть примеры функций на полурешетках (см., например, [6]), показываю щие, что свойства точечности и аддитивности функции в ее адекватной модели могут теряться, причем точечность может теряться даже тогда, когда точность модели со храняется функцией.

4. Полурешёточные функции k-значной логики 4.1. С п о с о б ы з а д а н и я, м и н и м и з а ц и я n Рассматриваются функции вида f : Ek Ek для натуральных k и n;

их мно жество со всевозможными n обозначается Pk. Методологически теория функций в Pk строится так же, как для булевых функций, а именно: указывается табличный способ задания, вводятся элементарные функции, изучаются их свойства, определяются поня тия формулы и функции, ею представляемой, а также понятия ДНФ, минимальной, кратчайшей и совершенной ДНФ, устанавливается существование и единственность последней для функции, отличной от 0, показывается возможность приведения эле ментарными преобразованиями произвольной формулы к виду ДНФ, формулируется закон двойственности, ставятся и решаются задачи минимизации в классе ДНФ и т. п.

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

Прежде всего, ДНФ бывает ортогонализированной и неортогонализированной.

В последней, в отличие от первой, возможна пара элементарных конъюнкций с разны ми ненулевыми значениями. Раскрытие скобок осуществляется по правилу: x(y z) = = xk1 xk2... xkm, где k1 k2... km есть ортогонализированная ДНФ для y z.

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

В-третьих, наряду с импликантами вводятся квазиимпликанты. Элементарная конъюнкция (базисных функций) G называется импликантой или квазиимпликантой функции f, если G f = f или G f f соответственно. Импликанта G неприводи ма по форме или по значению, если не существует импликанты H, что H = G H и соответственно r(H) r(G) или H = G, где r(K) ранг (количество множителей в) элементарной конъюнкции K. Аналогично, квазиимпликанта G неприводима по форме или по значению, если не существует квазиимпликанты H, что H G H и соответ ственно r(H) r(G) или H G. Импликанты и квазиимпликанты, неприводимые одновременно по форме и по значению, называются простыми.

Устанавливается, что кратчайшая ДНФ, представляющая f, может быть постро ена из любых импликант f простых, неприводимых по форме или неприводимых по значению, а минимальная ДНФ, представляющая f, только из неприводимых по форме импликант функции f. Построение кратчайшей ДНФ, реализующей f, возмож но из неприводимых по форме квазиимпликант, а минимальной ДНФ, реализующей f, только из неприводимых по форме квазиимпликант функции f.

Наконец, требуемые импликанты и квазиимпликанты находятся не склеиванием, как в булевом случае, элементарных конъюнкций, которое в данном случае неуместно, но путём построения подходящих покрытий и квазипокрытий так называемой базис ной матрицы.

4.2. П - п о л н о т а Система квазимонотонных функций Q Pk называется П-полной, если каждая квазимонотонная функция в Pk реализуется формулой, построенной из функций в Q при помощи операций и. Система Q независима, если для любой функции f Q система Q {f } не является П-полной.

Пусть M = 0 1 {0, 1, 2}, где 0, 1, 2 суть функции в P, тождественно равные 3 {0}, {1}, {2} соответственно, и множества 0, 1 функций в P вводятся следующими определениями, где Df1...im = {a Df : f (a) = {i1,..., im }} для любых i1,..., im в E3.

i 0 2 12 1 01 1. f 0, если f P, |Df | = |Df | = 1, Df = Df = Df = и для всех p Df, 2 02 q Df, r Df, s Df выполняются условия:

a) p q =, p r =, q r = ;

b) p s = или q s =.

01 12 02 0 1 2. f 1, если f P, |Df | = |Df | = 1, Df =, Df = Df = Df = и для всех 01 12 02 p Df, q Df, r Df, s Df выполняются условия:

c) p q =, p r =, q r =, p q r = ;

d) p s = или q s = или p q s =.

По тесту квазимонотонности функции в 0 и 1 квазимонотонные.

Теорема 20. Система функций M П-полна и независима в P.

3 5. Системы уравнений на полурешётках 5.1. Д и н а м и ч е с к о е п о в е д е н и е Рассматриваются системы уравнений, связывающие функциональной зависимо стью переменные, определённые на полурешётках. Они могут служить как функцио 36 Г. П. Агибалов нальными, так и структурными моделями дискретных автоматов. Каждое уравнение в системе имеет вид z = f (Z) и указывает на зависимость f переменной z от пере менных множества Z. Обозначая через x, y и q наборы переменных, встречающихся соответственно только в правых, только в левых и в обеих частях системы уравнений L, последнюю можно записать в общем случае как пару векторных уравнений y = (x, q), q = (x, q). Переменные в x, y и q называются соответственно входными, выходными и внутренними переменными, а наборы их значений соответствующими состояниями системы L. Множества последних обозначаются X, Y и Q соответственно. По условию функции на полурешётках, : X Q Y, X, Y и Q полурешётки, а и : X Q Q. Они называются функциями синхронных соответственно выходов и переходов системы L. В случае их монотонности система L называется монотон ной. Функция называется монотонной в точке ar X Q, если (a, r) r или (a, r) r;

в этом случае ar называется точкой монотонности функции. В частно сти, если (a, r) = r, то стабильна в ar и ar точка стабильности. Множества точек монотонности и стабильности функции обозначаются M и S соответственно.

Для монотонной системы L вводятся функции : M Y и : M Q, опреде ляемые как (a, r) = (a, (a, r)) и (a, r) = q(m), где q(1) = r, q(i + 1) = (a, q(i)) для i = 1, 2,... и m находится из условия q(m + 1) = q(m). Они называются её функ циями асинхронных выходов и переходов соответственно. Набор из семи элементов (ab, rts, uv), где ar S, b X, t = (a + b, r), s = (b, t), u = (a + b, r), v = (b, t), называется динамическим переходом в монотонной системе L (рис. 1). Его содержа тельный смысл следующий: если в дискретном автомате, моделируемом системой L и имеющем внутреннее состояние в r, входное состояние в некоторый момент време ни асинхронно меняется из a в b, то в автомате возникает такой переходный процесс, в течение которого внутреннее и выходное состояния не выходят за пределы t и u соответственно и по завершению которого оказываются в s и v соответственно. Сово купность T (L) всех динамических переходов системы L называется её динамическим поведением.

'&%$ !"# /'&%$ !"# / '&%$ !"# a (a + b)/u b/v r s t (a + b)/u b/v Рис. 1. Диаграмма динамического перехода Операция, состоящая в подстановке в правую часть некоторого уравнения e систе мы вместо некоторой внутренней переменной z правой части f (Z) уравнения для z, называется элементарной подстановкой. Если уравнение e и уравнение для z это разные уравнения, то элементарная подстановка называется элементарной суперпо зицией, в противном случае самоподстановкой. Уравнение, которое не изменяется в результате самоподстановки, называется нормальным.

Теорема 21. Пусть система уравнений L получена из монотонной системы L элементарными подстановками. Тогда: 1) T (L) T (L );

2) если все уравнения в L нормальные, то T (L) = T (L );

3) если все подстановки элементарные суперпозиции, то T (L) = T (L ).

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

В общем случае, когда система уравнений L не обязана быть монотонной, её функ ции асинхронных переходов и выходов определяются на множестве X Q при помощи следующего определения, в котором для любой функции на полурешётках f : A B монотонная функция f + : A B определена как f + (a) = f (b):

bDf,b a (x, q) = + (x, (x, q)) и (x, q) = p(k), где p(k) удовлетворяет условиям p(k + 1) = p(k), p(i + 1) = + (x, p(i)) для i 1, + p(1) = p(m) и m удовлетворяет условиям q(m + 1) = q(m), q(i + 1) = q(i) + (x, q(i)) для i 1 и q(1) = q.

С использованием этих функций динамический переход в произвольной системе L определяется для любой точки ar X Q так же, как в монотонном случае.

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

Теорема 22. Пусть система уравнений L получена минимизацией монотонной системы L и для любых x X и q Q символы x и q обозначают те входное и внутреннее состояния системы L, которые являются частями x и q соответственно.

Тогда если (ab, rts, uv) T (L), то (a b, r t s, uv) T (L ). В случае немонотонной L это утверждение ослабляется до следующего: если (ab, rts, uv) T (L) и (a b, r pq, wz) T (L ), то p = t, q = s, w u, z v.

6. Конечные автоматы на полурешётках 6.1. Г о м о м о р ф и з м ы, м о д е л и, р е а л и з а ц и и, точечные продолжения Конечный автомат S = (X, Q, Y,, ), где X входной и Y выходной алфа функция переходов, : X Q Q, и виты и Q множество состояний, функция выходов, : X Q Y, называется автоматом на полурешётках, если множества X, Q, Y являются полурешётками. Под автоматом далее подразумевается именно автомат на полурешётках, а автомат S с абстрактными множествами X, Q, Y называется абстрактным автоматом. Автомат называется точечным, аддитив ным, монотонным или квазимонотонным, если соответственно таковы его функции переходов и выходов. Автомат S называется гомоморфным (изоморфным) автомату L = (U, P, V,, ), если существуют эпиморфизмы (соответственно изоморфизмы) по лурешёток h1 : U X, h2 : P Q, h3 : V Y, что для всех up U P вы полняются равенства h2 (u, p) = (h1 u, h2 p), h3 (u, p) = (h1 u, h2 p);

в этом случае 38 Г. П. Агибалов h1 h2 h3 называется гомоморфизмом (изоморфизмом) L на S, а автомат S гомо морфным образом, или моделью, автомата L, который, в свою очередь, называется наибольшим гомоморфным прообразом автомата S, если (u, p) = sup h1 (h1 u, h2 p), (u, p) = sup h1 (h1 u, h2 p).

Теорема 23. Любая модель квазимонотонного, монотонного или аддитивного ав томата является соответственно квазимонотонным, монотонным или аддитивным ав томатом.

Теорема 24. Всякий наибольший гомоморфный прообраз квазимонотонного или монотонного автомата является соответственно квазимонотонным или монотонным автоматом.

Подавтомат автомата на полурешётках называется точным подавтоматом, если его полурешётки являются подполурешётками соответствующих полурешёток авто мата. Говорят, что автомат S (точно) реализуется автоматом L, если существует в L (точный) подавтомат L = (X, P, V,, ) и гомоморфизм (соответственно изо морфизм) h1 h2 h3 автомата L на автомат S такие, что для любого W U P из существования для (W ) нижней грани в P следует существование для h2 (W ) ниж ней грани в Q, а из существования для (W ) нижней грани в V существование для h3 (W ) нижней грани в Y.

Теорема 25. Автомат тогда и только тогда реализуется квазимонотонным авто матом, когда он сам квазимонотонный.

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

Теорема 26. Пусть абстрактный автомат L гомоморфно отображается на аб страктный автомат S и автомат на полурешётках S является точечным продолже нием автомата S. Тогда существует точечное продолжение L автомата L, такое, что L гомоморфно отображается на S.

6.2. А д е к в а т н ы е м о д е л и а в т о м а т о в Для автомата S и конгруэнций 1, 2, 3 на его полурешётках X, Q, Y соответ ственно определяется автомат S 1 2 3 = (X 1, Q 2, Y 3,, ), в котором и являются адекватными моделями функций и с точностями (1 2, 2 ) и (1 2, 3 ) соответственно. Если он является моделью автомата S, то он называется адекватной моделью последнего с точностью 1 2 3. Тройка конгруэнций 1 2 3 на зывается стабильной в автомате S, если пара (1 2, 2 ) сохраняется функцией, а пара (1 2, 3 ) функцией.

Теорема 27. Если тройка конгруэнций 1 2 3 стабильна в автомате S, то автомат S 1 2 3 является моделью автомата S и, следовательно, его адекватной моделью.

Обратно, если автомат S является моделью автомата S, то существует стабильная в S тройка конгруэнций 1 2 3, такая, что S и S 1 2 3 изоморфны и, следовательно, S изоморфен адекватной модели S с точностью 1 2 3.

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

Дискретные автоматы на полурешетках 6.3. С и н т е з Пара уравнений y = (x, q), q = (x, q) называется канонической системой урав нений автомата S = (X, Q, Y,, ). Это есть система уравнений на полурешётках.

Динамические переходы в ней и её динамическое поведение называются соответствен но динамическими переходами и динамическим поведением автомата S. Последова тельность динамических переходов = (T1 T2...Tn ) называется цепью переходов, если Ti = (ai ai+1, ri ti ri+1, ui vi ) для каждого i = 1,..., n. Командой над тройкой полурешёток X, Q, Y называется всякий набор из шести объектов c = (ab, rp, wz), где a X, b X, r Q, p Q, w Y, z Y. В ней ar называется начальной точкой. Последователь ность команд = (c1 c2...cn ) называется цепью команд, если ci = (ai ai+1, pi pi+1, wi zi ) для i = 1,..., n. Команда c реализуется в автомате S динамическим переходом T = (ab, rts, uv), если s p, u wиv z. Цепь команд реализуется в S це пью переходов, если r1 = p1, ri+1 pi+1, ui wi и vi zi для i = 1,..., n. Система SC некоторых команд на X, Q, Y реализуется автоматом S, если каждая команда в ней реализуется некоторым динамическим переходом в S;

система SC сильно реали зуется в S, если каждая цепь команд в ней реализуется цепью динамических прехо дов в S. Система команд называется автоматной, если она реализуется монотонным автоматом.

Теорема 28. Система команд SC сильно реализуется монотонным автоматом S, если и только если она реализуется этим автоматом.

Теорема 29 (теорема синтеза). Система команд SC автоматна, если и только ес ли для каждой её команды c = (ab, rp, wz) можно указать такие tc и pc в Q, что r tc, pc = inf(p, tc ) и бинарные отношения (X Q) Y и (X Q) Q, определён ные высказываниями (b, tc )z, (a + b, tc )w, (b, tc )pc и (a + b, tc )tc, квазимонотонны и монотонная функция, реализующая, стабильна в начальных точках всех команд в SC;

в этом случае SC реализуется автоматом S = (X, Q, Y,, ), где монотонная функция, реализующая.

6.4. Д е к о м п о з и ц и я Конечная последовательность N = Q0 z1 S1 z2 S2...zl Sl zl+1 Ql+1 автоматов состояний Sj = (Xj, Qj, j ) для j = 1, 2,..., l и отображений zj : Q0 Q1... Ql Xj для j = 1, 2,..., l + 1, где Xl+1 = Ql+1, называется автоматной сетью. В ней S1,..., Sl называются компонентами, z1,..., zl связями, Q0 входным алфавитом, Ql+ выходным алфавитом, zl+1 функцией выходов и l длиной сети. Далее предпола гается, что в сети N все множества X1,..., Xl и Q0, Q1,..., Ql суть полурешётки и все связи z1,..., zl суть гомоморфизмы полурешёток. Сеть N называется квазимонотон ной, если квазимонотонны функции всех её компонент и её функция выходов.

Сеть N имеет стандартную форму, если для любого j = 1,..., l в ней Xj = X0j X1j... Xlj и zj (q0 q1...ql ) = z0j (q0 )z1j (q1 )...zlj (ql ) для некоторых zij : Qi Xij, i = 0, 1,..., l. Автоматом сети N называется автомат SN = (Q0, Q1... Ql, Ql+1, N, N ), где для x в Q0 и q = q1...ql в Q1... Ql N (x, q) = (1 (z1 (x, q), q1 ), 2 (z2 (x, q), q2 ),..., l (zl (x, q), ql )), N (x, q) = zl+1 (x, q).

Сеть N (точно) реализует автомат S, если её автомат SN (точно) реализует S.

Если сеть N в стандартной форме точно реализует автомат S и h1 h2 h3 есть соответ ствующий изоморфизм точного подавтомата в SN на автомат S, то для любых i и j в ряду 1, 2,..., l можно определить бинарные отношения i, ij на полурешётке Q и бинарное отношение µj на полурешётке X как ядерные конгруэнции гомоморфизмов 40 Г. П. Агибалов i h1, zij i h1 и z0j h1 соответственно, где i (q1...ql ) = qi. Они называются конгруэн 2 2 циями, индуцированными в S сетью N (при гомоморфизме h1 h2 h3 ). Наконец, система конгруэнций на полурешётке полна, если их пересечение совпадает с равенством.

Теорема 30. Для автомата S, конгруэнций j и ij на полурешётке Q и конгру энций µj на полурешётке X для i, j в {1,..., l} существует квазимонотонная сеть N в стандартной форме, точно реализующая S и индуцирующая в S данные конгруэн ции, если и только если выполняются следующие условия:

1) i ij для всех i и j;

2) система конгруэнций 1,..., l полна;

3) для каждого j пара конгруэнций (µj (1j... lj j ), j ) сохраняется функ цией ;

4) для каждого j и любого Uj Dj, где Dj = X/µj Q/1j... Q/lj Q/j, Uj = {[xm ]µj [qm ]1j...[qm ]lj [qm ]j : m = 1,..., kj } и 2 |m(Q/j )|, из существо kj вания для Uj нижней грани в Dj следует существование в Q/j нижней грани для Vj = {[(xm, qm )]j : m = 1,..., kj };

5) для любого A D, где D = X Q/1... Q/l, A = {xm [qm ]1...[qm ]l :

|m(Y )|, из существования для A нижней грани в D следует m = 1,..., k} и 2 k существование в Y нижней грани для {(xm, qm ) : m = 1,..., k};

6) для любого W X Q, где W = {xm qm : m = 1,..., k} и 2 |m(Q)|, из k существования в Q/1... Q/l нижней грани для V = {[(xm, qm )]1...[(xm, qm )]l :

m = 1,..., k} следует существование в Q нижней грани для {(xm, qm ) : m = 1,..., k}.

Говорят, что компонента Si сети N не зависит от компоненты Sj или входа, ес ли связь zi (q0, q1,..., ql ) не зависит существенно от qj и q0 соответственно. Сеть N называется каскадной, параллельно-последовательной или параллельной, если в ней i, для j = i 1 или каждая компонента Si не зависит от компоненты Sj для j для всех j соответственно. Параллельно-последовательная сеть последовательная, ес ли каждая компонента Si для i = 1 не зависит от входа сети. Каскадная, параллельно последовательная, параллельная или последовательная сеть N, (точно) реализую щая автомат S, называется его (точной) соответственно каскадной, параллельно последовательной, параллельной или последовательной декомпозицией. Число состо яний в автомате называется его порядком. Конгруэнция на полурешётке A называется нетривиальной, если она отличается от наименьшей (0A ) и наибольшей (1A ) конгру энций на A.

Теорема 31. Квазимонотонный автомат S допускает точную параллельную ква зимонотонную декомпозицию на компоненты меньшего порядка, если и только если на полурешётке его состояний существует полная система нетривиальных конгруэнций 1,..., l, сохраняемых функцией и удовлетворяющих условиям 5 и 6 теоремы 30.

Теорема 32. Квазимонотонный автомат S допускает точную каскадную квази монотонную декомпозицию на компоненты меньшего порядка, если и только если на полурешётке его состояний существует полная система из двух нетривиальных кон груэнций 1, 2, таких, что 1 сохраняется функцией и удовлетворяются условия 5 и 6 теоремы 30 для l = 2 и следующее условие:

4 ) из существования в X Q/1 Q/2 нижней грани для {xm [qm ]1 [qm ]2 :

m = 1,..., k} следует существование в Q/2 нижней грани для {[(xm, qm )]2 :

m = 1,..., k}.

Дискретные автоматы на полурешетках Теорема 33. Квазимонотонный автомат S допускает точную параллельно-пос ледовательную квазимонотонную декомпозицию длины l 2, если и только если на полурешётке его состояний существует полная система конгруэнций 1,..., l, таких, что конгруэнция 1 и пары конгруэнций (0X (i1 i ), i ) для i = 2,..., l сохраняются функцией и выполняются условия 4 – 6 теоремы 30.

Теорема 34. Квазимонотонный автомат S допускает точную последовательную квазимонотонную декомпозицию длины l 2, если и только если на полурешётке его состояний существует полная система конгруэнций 1,..., l, таких, что конгруэнция 1 и пары конгруэнций (0X (i1 i ), i ) и (1X i, i ) для i = 2,..., l сохраняются функцией и выполняются условия 4 – 6 теоремы 30.

Покрытие P полурешётки Q регулярно, если для любых его блоков A и B из суще ствования a A и b B, таких, что a b, следует A B. Покрытие P сохраняется в автомате S, если x XA P B P ((x, A) B). Система покрытий P1,..., Pl называется ортогональной, если |A1 · · · Al | 1 для всех A1 P1,..., Al Pl.

Теорема 35. Пусть Q = P1 · · · Pl, где P1,..., Pl суть регулярные ассоциа тивные покрытия полурешётки Q состояний квазимонотонного автомата S, сохраняе мые его функцией переходов и образующие ортогональную систему, и для любого W = {a1 q1,..., ak qk } X Q и любых (A1m... Alm ) Q, где m = 1,..., k и A1m · · · Alm = {qm }, выполняются условия:

1) из 2 k |m(Y )| и существования для {am A1m... Alm : m = 1,..., k} X Q нижней грани в X Q следует существование в Y нижней грани для (W );

|m(Q)| и существования в Q нижней грани для V = {B1m... Blm :

2) из 2 k m = 1,..., k} Q, где для i = 1,..., l и m = 1,..., k блок Bim является минималь ным (по порядку в Pi ) из тех блоков Bi в Pi, для которых (am, Aim ) Bi, следует существование в Q нижней грани для (W ).

Тогда сеть N = Xz1 S1 z2 S2... zl Sl zl+1 Y, где для каждого i = 1,..., l в компоненте Si = (X, Pi, i ) для любых a X и Ai Pi блок i (a, Ai ) является минимальным (по порядку в Pi ) из тех блоков Bi Pi, для которых (a, Ai ) Bi, zi (aA1... Al ) = a и (a, q), если q A1 · · · Al, zl+1 (aA1... Al ) = если A1 · · · Al =, sup Y, является квазимонотонной параллельной декомпозицией автомата S.

Утверждение остаётся в силе, если в нём за i (a, Ai ) и соответственно за Bim при нимается не минимальный из указанных блоков в Pi, но наибольший из них.

Теорема 36. Пусть Q = P1 P2, где P1 и P2 суть ассоциативные покрытия по лурешётки Q состояний квазимонотонного автомата S, образующие ортогональную пару, покрытие P1 регулярно и сохраняемо функцией переходов автомата и для любого W = {a1 q1,..., ak qk } X Q и любых (A1m A2m ) Q, где m = 1,..., k и A1m A2m = {qm }, выполняются условие 1) теоремы 35 при l = 2 и следующие усло вия:

|m(Q)| и существования в Q нижней грани для V = {B1m B2m :

2) из 2 k m = 1,..., k} Q, где для m = 1,..., k блок B1m является минимальным (по порядку в P1 ) из тех блоков B1 в P1, для которых (am, A1m ) B1, и блок B2m является наибольшим (по порядку в P2 ) из тех блоков B2 в P2, для которых (am, qm ) B2, следует существование в Q нижней грани для (W );

42 Г. П. Агибалов |m(P2 )| и существования для {am A1m A2m : m = 1,..., k} X Q 3) из 2 k нижней грани в X Q следует существование в P2 нижней грани для {B21... B2k } P2, где для m = 1,..., k блок B2m является наибольшим (по порядку в P2 ) из тех блоков B2 в P2, для которых (am, qm ) B2.

Тогда сеть N = Xz1 S1 z2 S2 z3 Y, где S1 = (X, P1, 1 ), S1 = (X P1, P2, 2 ) и для лю бых a X, A1 P1 и A2 P2 блок 1 (a, P1 ) является минимальным (по порядку в P1 ) из тех блоков B1 в P1, для которых (a, A1 ) B1, 2 (aA1, A2 ) является наибольшим (по порядку в P2 ) из тех блоков B2 в P2, для которых (a, A1 A2 ) B2, z1 (aA1 A2 ) = a, z2 (aA1 A2 ) = aA1 и (a, q), если q A1 A2, z3 (aA1 A2 ) = если A1 A2 =, sup Y, является квазимонотонной каскадной декомпозицией автомата S.

Утверждение остаётся в силе, если в нём за 1 (a, A1 ) и соответственно за B1m при нимается не минимальный, но наибольший блок или за 2 (aA1, A2 ) и соответственно за B2m принимается не наибольший, но минимальный блок из числа указанных.

6.5. К о д и р о в а н и е Автомат L = (X, P, V,, ), где P B n, называется кодом автомата S = = (X, Q, Y,, ), если существует эпиморфизм полурешёток h : P Q, что для всех xp X P выполняются равенства h(x, p) = (x, h(p)), (x, p) = (x, h(p)) и для лю бого W X P из существования для W нижней грани в X B n следует существова ние для (W ) и (W ) нижних граней в B n и Y соответственно, а из существования для (W ) нижней грани в B n существование для h(W ) нижней грани в Q;

в этом слу чае h называется кодированием автомата S, а полурешётка B и числа n и k = |m(B)| соответственно основанием, длиной и значностью кодирования h и кода L. Код L называется наибольшим, если автомат L является наибольшим гомоморфным прооб разом автомата S при гомоморфизме h. Автомат L называется квазимонотонным на полурешётке G P, если его функции и квазимонотонны из X G в G и в Y соответственно.

Теорема 37. 1) Всякий код автомата с основанием B и длиной n является авто матом, квазимонотонным на B n. 2) Всякий автомат, допускающий кодирование, ква зимонотонный. 3) Всякий наибольший код автомата квазимонотонный;

наибольший код монотонного автомата монотонный. 4) Любому кодированию автомата отвечает по крайней мере один монотонный код.

Теорема 38. Любое кодирование полурешётки состояний квазимонотонного ав томата является кодированием самого автомата.

Теорема 39. Автомат тогда и только тогда допускает кодирование, когда он ква зимонотонный.

Пусть r(S) = max |A|, где M (S) = M0 (S) M1 (S) M2 (Q) M (Q) и для любого AM (S) A M (Q):

1) A M0 (S), если A (X Q);

2) A M1 (S), если существует Z = {x1 q1,..., xm qm } X Q, что x1,...,xm имеют общую нижнюю грань в X, A {q1,..., qm } и хотя бы одно из подмножеств (Z) Q и (Z) Y не имеет нижней грани в полурешётках Q и Y соответственно;

Дискретные автоматы на полурешетках 3) A M2 (Q), если A = {a1, b}, где b Q и a1 m(Q) Q(b).

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

Теорема 40. Непримитивный квазимонотонный автомат S с точечной полуре шёткой состояний тогда и только тогда допускает k-значное кодирование, когда k r(S).

Теорема 41. Непримитивный квазимонотонный автомат S с точечной полуре шёткой состояний допускает кодирование с основанием B M, если и только если = |M | r(S).

6.6. М и н и м и з а ц и я ч и с л а с о с т о я н и й Говорят, что автомат L словарно реализует автомат S, если q Qp P X ((, p) (, q)).

Говорят также, что L словарно реализует S с моделированием автомата состоя ний, если существует эпиморфизм полурешёток h : Q P, что h(x, q) = (x, hq) и (x, hq) (x, q). Ассоциативное покрытие P полурешётки состояний Q квази монотонного, монотонного или аддитивного автомата S согласуется с S, если су ществуют соответственно квазимонотонные, монотонные или аддитивные функции : X P P и : X P Y, что для любых x X и A P имеет место включение (x, A) (x, A) и значение (x, A) является в Y нижней гранью для (x, A);

в этом случае если P = Q/ для некоторой конгруэнции на Q, то говорят, что согласуется с S.

Теорема 42. Если аддитивный автомат S словарно реализуется аддитивным ав томатом с m состояниями, то на полурешётке состояний в S существует П-покрытие мощности не более m, согласуемое с S. Обратно, если на полурешётке состояний ад дитивного автомата S существует П-покрытие мощности m, согласуемое с S, то S словарно реализуется аддитивным автоматом с m состояниями.

Теорема 43. Квазимонотонный, монотонный или аддитивный автомат тогда и только тогда словарно реализуется с моделированием автомата состояний соответ ственно квазимонотонным, монотонным или аддитивным автоматом с m состояния ми, когда на его полурешётке состояний существует согласуемая с ним конгруэнция индекса m.

Ставятся следующие задачи минимизации числа состояний в заданном классе A автоматов на полурешётках: для автомата S из класса A найти автомат L в клас се A с наименьшим числом состояний, который либо словарно реализует автомат S задача 1, либо словарно реализует S с моделированием автомата состояний зада ча 2. Ввиду теорем 42 и 43 задача 1 для класса аддитивных автоматов и задача 2 для любого из классов квазимонотонных, монотонных и аддитивных автоматов сводится к построению на полурешётке состояний заданного автомата согласуемых с ним соот ветственно П-покрытия наименьшей мощности и конгруэнции наименьшего индекса.

7. Переключательные сети Рассматриваются сети, называемые переключательными, в которых рёбра наде лены проводимостями со значениями из некоторой полурешётки проводимостей C, 44 Г. П. Агибалов а полюсы (внешние вершины) состояниями со значениями из некоторой полуре шётки состояний S, где (S,, C, ) является полурешёточно упорядоченной алгеброй и S содержит высокоимпедансное состояние 0r. Решаются задачи анализа таких се тей, состоящие в построении полных проводимостей между вершинами данной сети и функций состояний ее вершин.

7.1. П о л н ы е п р о в о д и м о с т и Переключательная сеть бесповторная, если проводимости всех рёбер в ней явля ются попарно различными переменными. Если набор значений переменных про водимостей всех рёбер сети N, то через N () обозначается сеть, которая получается из сети N замещением в ней всех переменных проводимостей рёбер их значениями из набора. Для любых двух вершин i и j сети N через Nij обозначается сеть, которая остаётся после удаления из N всех рёбер, не принадлежащих цепям в N, соединяю щим i с j.

Во всякой переключательной сети конъюнкция проводимостей всех рёбер неко торой цепи называется проводимостью этой цепи. Цепь называется разомкнутой, замкнутой или резистивной, если её проводимость равна 0, 1 или Х соответственно.

С каждой парой вершин ij переключательной сети связываются два типа проводи непосредственная и полная. Формально непосредственная проводимость мостей любой сети от вершины i к вершине j определяется как дизъюнкция проводимостей всех рёбер сети, соединяющих i с j, а полная проводимость бесповторной сети N от iкj как точечная функция fij от переменных проводимостей рёбер в N, которая на любом наборе значений этих переменных в множестве E = {0, 1, X} принимает значение 0, если в Nij () все цепи разомкнуты, fij () = 1, если в Nij () есть замкнутая цепь, X, если в Nij () есть резистивная и нет замкнутых цепей.

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

В дистрибутивной сети, в алгебре проводимостей (C,, ) которой выполнены законы дистрибутивности и поглощения (теорема 11), полные проводимости строятся методами, известными из теории контактных схем (методы цепей, сечений, возведение в степень матрицы непосредственных проводимостей, последовательного разложения, последовательного исключения вершин и др.), а для произвольных сетей, для кото рых эти методы не работают, с указанной целью предлагаются новые общие методы комбинаторный, короткого замыкания, характеристических функций и метод ими тационного моделирования. В следующем их изложении, относящемся к бесповторной сети N, символ Dij обозначает дизъюнкцию проводимостей всех цепей в последней, соединяющих вершину i с вершиной j, и xc = 1, если x = c, и xc = 0 в противном случае.

Комбинаторный метод. В Dij подставляются значения переменных из набора, равные 0 или 1;

в полученной формуле выполняются всевозможные поглощения по правилу A (A B) = A, после чего в неё подставляются значения остальных пере менных из ;

константа, в которую таким образом свёртывается Dij, и есть fij ().

Дискретные автоматы на полурешетках Метод короткого замыкания:

1(c1 ) 1(c2 ) (c...cn ) · · · x1(cn ) Dij x fij (x1,..., xn ) = (x1 ), n ){0,1}n (c1...cn (c...c ) где z (c) = z, если c = 1, z (c) = ¬z, если c = 0, и Dij 1 n получается из Dij подстанов кой 1 вместо каждой переменной xk, для которой ck = 1, с последующим выполнением всевозможных поглощений.

Метод характеристических функций. Используется булево представление прово димостей в E, а именно: проводимость x представляется булевым вектором из трёх компонент ( x, 1 x, X x), где c E(c x = 1 c x). Выражение для fij строится (fij c), fij = ¬1 fij ¬X fij, fij = ¬0 fij ¬X fij, c 0 по следующим формулам: fij = cE fij = ¬0 fij ¬1 fij, fij = ¬X fij 0 fij 1 fij, fij = ¬1 fij 0 fij X fij, fij = ¬0 fij 1 fij X X’ 1 X fij, fij = 0 fij 1 fij X fij и, если Dij = (xk1 xk2 · · · xkmk ), то 1 fij = 1 Dij = E k (1 xk1 1 xk2 · · · 1 xkmk ), 0 fij = 0 Dij = (0 xk1 0 xk2 · · · 0 xkmk ), а выражение = k k для X fij получается из выражения для fij последовательным применением следующих X действий: 1) приведение к виду ДНФ;

2) замещение каждого выражения ¬1 x ¬0 x равным xX ;

3) подстановка X x, x0 и x1 вместо xX, 0 x и 1 x соответственно;

4) замещение каждого ¬x0 равным 1 x X x и каждого ¬x1 равным 0 x X x.

7.2. Ф у н к ц и и с о с т о я н и й Рассмотрим произвольную вершину j переключательной сети N с m полюсами и n переменными проводимостями рёбер. Пусть s = (a1 a2... am ) S m и C. Вы полним следующую итеративную процедуру приписывания состояний вершинам сети N (), где для любой вершины i через si обозначено состояние, приписанное вершине i в последний раз:

1) для каждого i = 1,..., m припишем ai полюсу сети с номером i;

каждой вершине, не являющейся полюсом, припишем высокоимпедансное состояние;

2) если в сети N () есть ребро ab с проводимостью 1, то вершины a и b стя нем к одной вершине, которой припишем новое состояние sa sb и которую в случае j {a, b} (и только в этом случае) обозначим как j;

эта операция повторяется до тех пор, пока в сети не останется рёбер с проводимостью 1, после чего 3) если для некоторого ребра ab, где a = j, имеет место sb = q = sb (c(ab)sa ), где c(ab) есть проводимость ребра ab (в этом случае ребро ab называется возбуждённым), то вершине b припишем новое состояние, равное q;

эта операция повторяется до тех пор, пока в сети N () не останется ни одного возбуждённого ребра ab с a = j, после чего процесс приписывания состояний вершинам сети считается законченным.

Пусть в результате этого процесса вершине j приписано состояние sj. Положим fj (s, ) = sj. Определённая таким образом функция fj : S m C n S называется функцией состояний вершины j в сети N.

Переключательная сеть N называется разделительной со стороны вершины j, если для любых её полюсов i и k сети Nij и Nkj не имеют общего ребра, проводимость которого может принять значение X.

Теорема 44. Для любой разделительной со стороны j сети N, а также для любой вершины j во всякой дистрибутивной сети N :

m ai, fj (a1,..., am, ) = i=1 fi j () где i вершина сети, являющаяся её i-м полюсом.

46 Г. П. Агибалов 8. Переключательные схемы 8.1. П е р е к л ю ч а т е л ь н а я с х е м а к а к м о д е л ь интегральных схем транзисторного уровня Схема это тройка объектов (X, Z, Z0 ), где X конечное множество элементов схемы, Z множество её узлов, или цепей, и Z0 множество полюсов схемы, Z0 Z.

Элемент схемы характеризуется конечным множеством своих полюсов и, в свою оче редь, может быть схемой из других элементов. Множество узлов Z является разбиени ем множества всех полюсов элементов в схеме. Элемент схемы, имеющий m полюсов, называется переключательным элементом, если выделено подмножество его полюсов, названных управляющими, и элементу поставлена в соответствие квадратная матри ца ||gij || размера m m, в которой gij есть монотонная функция на полурешётках, названная проводимостью элемента от его полюса i к полюсу j, принимающая значе ния в некоторой полурешётке проводимостей C и зависящая от аргументов, которые поставлены во взаимно однозначное соответствие управляющим полюсам элемента и принимают значения в некоторой полурешётке состояний S. Предполагается, что в S есть высокоимпедансное состояние и что (S,, C, ) и (C,, ) суть полурешёточно упорядоченные алгебры: первая векторная алгебра состояний, вторая алгебра проводимостей. Пара (C, S) называется типом элемента, и схема из однотипных пе реключательных элементов называется переключательной схемой. Тип элемента в ней называется её типом. Узел в переключательной схеме называется управляющим уз лом схемы, если он содержит управляющий полюс некоторого элемента.

Различным узлам переключательной схемы присваиваются различные переменные со значениями в S, названные собственными переменными этих узлов. Те из них, что присвоены управляющим узлам, названы управляющими переменными схемы. Раз личным полюсам в схеме, кроме того, присвоены разные переменные со значениями в S, отличные от собственных переменных схемы и названные её входными переменны ми, а также разные переменные, отличные как от собственных, так и входных пере менных и названные выходными переменными схемы. Таким образом, одному и тому же полюсу схемы присвоены три переменные входная, выходная и собственная.

Дизъюнкция всех проводимостей элементов схемы от их полюсов в узле a к их полюсам в узле b, в которых (проводимостях) каждый аргумент замещён управляю щей переменной узла схемы, содержащего тот управляющий полюс элемента, который соответствует этому аргументу, называется непосредственной проводимостью схемы между её узлами a и b (от a к b). Бесповторная переключательная сеть N называется соответствующей данной переключательной схеме K, если вершинами и полюсами в сети N являются соответственно узлы и полюсы схемы K и ребро ab существует в N тогда и только тогда, когда непосредственная проводимость схемы K от a к b не есть 0. В этом случае функция, которая получается замещением в полной проводимо сти между вершинами a и b сети N переменной проводимости каждого ребра kl непо средственной проводимостью схемы K между k и l, называется полной проводимостью схемы K между узлами a и b (от a к b). Аналогичным образом определяется функция состояний узла j в схеме K по функции состояний вершины j в соответствующей сети N. По теореме 14 непосредственные и полные проводимости в переключательной схеме являются монотонными функциями от её управляющих переменных, а функции состояний узлов монотонными функциями от входных и управляющих переменных схемы.

Дискретные автоматы на полурешетках Переключательные элементы являются математическими моделями физических компонент в БИС и СБИС диодов, резисторов, транзисторов. Например, полевой транзистор моделируется переключательным элементом с тремя полюсами, каждый из которых управляющий;

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

Соответственно этому переключательные и функциональные схемы (из функциональ ных элементов) это математические модели БИС и СБИС на транзисторном и вен тильном уровнях абстракции. Функции состояний в них определяются при помощи одних и тех же процедур анализа переключательных сетей, которые (процедуры) не привязаны к какому-либо типу БИС, благодаря чему сама эта модель в равной мере эффективна и для NМОП, и для КМОП, и для других типов БИС и СБИС.

Уравнение yi = zi, где yi и zi соответственно выходная и собственная перемен ные, присвоенные полюсу i, называется уравнением для выходной переменной полюса i.

Уравнение zj = j (x1,..., xn, Zj ), где zj собственная переменная узла j, x1,..., xn все входные переменные схемы, j функция состояний узла j и Zj набор ее существенных аргументов из множества управляющих переменных схемы, называет ся уравнением для собственной переменной узла j. Совокупность уравнений для всех выходных и достижимых собственных переменных схемы K называется канонической системой уравнений схемы K. На неё, а вместе с ней и на схему K распространяют ся все понятия и утверждения, относящиеся к системам уравнений на полурешётках, в том числе понятия внутренней переменной, состояния, динамического перехода и ди намического поведения, процедура минимизации числа внутренних переменных и др.

Переключательная схема называется комбинационной, если число внутренних пе ременных в ней после минимизации равно 0;

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

8.2. С и н т е з к о м б и н а ц и о н н ы х с х е м Говорят, что система команд CC, где каждая команда имеет вид c = (ab, wz) и в ней a и b принадлежат полурешётке B n, w и z полурешётке B m и B E r, динами чески реализуема, если существует комбинационная схема с n входами и m выходами, в которой для любой команды c = (ab, wz) в CC есть динамический переход (ab, uv), удовлетворяющий соотношениям u w и v z.

Теорема 45. Система команд CC динамически реализуема, если и только если бинарное отношение B n B m, определённое высказываниями bz и (a + b)w, выписанными для всех команд (ab, wz) в CC, квазимонотонно.

В силу этой теоремы синтез комбинационной схемы с заданным динамическим поведением осуществляется так: сначала проверяется условие динамической реали зуемости данной системы команд (теорема 16) и в случае их выполнения способом, изложенным в доказательстве достаточности условий теоремы 16, строится квазимо нотонная функция f, выражающая зависимость выходных состояний искомой схемы от её входных состояний;

затем из элементов заданного базиса строится комбинацион ная схема, реализующая функцию f.

48 Г. П. Агибалов 8.3. С и н т е з п о с л е д о в а т е л ь н о с т н ы х с х е м Автомат, чья каноническая система уравнений есть минимизированная канониче ская система уравнений последовательностной схемы, называется автоматом этой схемы. Говорят, что система команд SC, где каждая команда имеет вид c = (ab, qs, wz) и в ней a и b принадлежат полурешётке X, w и z полурешётке Y и q и s полурешёт ке Q, динамически реализуема, если существует последовательностная схема K, подав томат L = (U, P, V,, ) автомата схемы K и эпиморфизмы полурешёток h1 : U X, h2 : P Q, h3 : V Y, такие, что:

1) для любых u1, u2 в U и p1, p2 в P из h1 (u1 ) = h1 (u2 ) и h2 (p1 ) = h2 (p2 ) следует h2 (u1, p1 ) = h2 (u2, p2 ) и h3 (u1, p1 ) = h3 (u2, p2 );

2) для любой команды c = (ab, qs, wz) в SC найдётся в L динамический переход T = (u1 u2, ptr, v1 v2 ), в котором h1 (u1 ) = a, h1 (u2 ) = b, h2 (p) = q, h2 (r) s, h3 (v1 ) w и h3 (v2 ) z.

Теорема 46. 1) Всякая динамически реализуемая система команд SC автоматна.

2) Автоматная система команд SC на полурешётках X, Q, Y динамически реализуема, если эти полурешётки точечные и допускают 3-значное кодирование.

Согласно этой теореме, синтез последовательностной схемы с заданным динамиче ским поведением сводится к следующей цепочке действий: сначала проверяются усло вия автоматности заданной системы команд SC (теорема 29) и в случае их выполнения способом, изложенным в доказательстве достаточности условий теоремы 29, строится автомат S, реализующий SC;

затем проверяются условия существования кода необ ходимой значности для автомата S (теорема 40) и в случае их выполнения способом, изложенным в доказательстве достаточности условий теоремы 40, строится автомат L код автомата S требуемой значности;

наконец синтезируется комбинационная схема в заданном базисе, реализующая функции автомата L, и в ней замыкаются обратные связи в соответствии с каноническими уравнениями автомата L. В эту цепочку мо гут быть вставлены процедуры минимизации и декомпозиции автомата S, описанные в п. 6.6 и 6.4.

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

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

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

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

ЛИТЕРАТУРА 1. Агибалов Г. П. Функциональные системы на полурешётках // Алгоритмы решения задач дискретной математики. Вып. 2. Томск: Изд-во Том. ун-та, 1987. С. 3–39.

2. Agibalov G. P. Functional systems on semilattices // Fundamentals of Computation Theory / Eds. R. G. Bukharaev, O. B. Lupanov. Berlin: Springer Verlag, 1987. P. 5–9.

3. Агибалов Г. П. Квазимонотонные функции и их минимизация // Кибернетика. 1989. № 2.

С. 111–113.

4. 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.

5. Агибалов Г. П. К кодированию полурешёток и автоматов на полурешётках // Дискретная математика. 1991. Т. 3. Вып. 2. С. 74–87.

6. Агибалов Г. П. Дискретные автоматы на полурешётках. Томск: Изд-во Том. ун-та, 1993.

227 с.

7. Агибалов Г. П. Адекватные модели полурешёток, функций и автоматов на полурешёт ках // Вестник Томского госуниверситета. Июнь 2000. № 271. С. 118–121.

8. Агибалов Г. П., Бузанов В. А., Липский В. Б., Румянцев Б. Ф. Математическая модель схем из элементов с управляемой проводимостью // Автоматика и телемеханика. 1982.

№ 9. С. 89–98.

9. Агибалов Г. П., Бузанов В. А., Липский В. Б., Румянцев Б. Ф. Логическое проектирова ние переключательных автоматов. Томск: Изд-во Том. ун-та, 1983. 154 с.

10. Панкратова И. А. Реализация функций на полурешётках переключательными схемами // Прикладная дискретная математика. 2009. № 2. С. 50–55.

11. Парватов Н. Г. Функциональная полнота в замкнутых классах квазимонотонных и мо нотонных трёхзначных функций на полурешётке // Дискретный анализ и исследование операций. Сер. 1. 2003. Т. 10. № 1. С. 61–78.

12. Парватов Н. Г. Теорема о функциональной полноте в классе квазимонотонных функций на конечной полурешётке // Дискретный анализ и исследование операций. Сер. 1. 2006.

Т. 13. № 3. С. 62–82.

13. Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.



 




 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.