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

На правах рукописи

Панкратова Ирина Анатольевна

РЕАЛИЗАЦИЯ ФУНКЦИЙ НА ПОЛУРЕШЕТКАХ ПЕРЕКЛЮЧАТЕЛЬНЫМИ СХЕМАМИ

Специальность 05.13.01 –

системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

ТОМСК – 2006 УДК 519.7

Работа выполнена в Томском государственном университете

Научный руководитель: доктор технических наук, профессор Агибалов Геннадий Петрович

Официальные оппоненты: доктор физико-математических наук, профессор Шоломов Лев Абрамович кандидат физико-математических наук, дтн, профессор Евтушенко Нина Владимировна

Ведущая организация: Саратовский государственный университет

Защита состоится 28 сентября 2006 г. в 10.30 на заседании диссертационного совета Д 212.267.12 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина – 36.

С диссертацией можно ознакомиться в библиотеке Томского государственного университета.

Автореферат разослан _ июля 2006 г.

Ученый секретарь диссертационного совета, д.т.н., профессор Смагин В. И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Традиционно методы логического проектирования дискретных управляющих систем, или дискретных автоматов, базируются на таком разделе дискретной математики, как конечно-значная логика. Её средства позволяют описывать статическое поведение системы (при фиксированном входном состоянии), однако недостаточны для описания динамического поведения (при асинхронном изменении компонент входного состояния). В монографии [1] было показано, что динамическое поведение дискретного автомата может быть адекватно и с заданной точностью описано средствами полурешёточно упорядоченных алгебр. Для этого множество состояний в автомате представляется как конечная верхняя полурешётка, т. е. частично упорядоченное множество, в котором для каждой пары элементов существует точная верхняя грань. Отношение порядка в полурешётке интерпретируется как отношение сравнения состояний по степени их неопределённости, а сумма состояний a + b моделирует промежуточное состояние, возникающее в процессе асинхронного изменения a на b. Задача синтеза дискретного автомата, обладающего заданным динамическим поведением, сводится к синтезу схемы в некотором базисе, реализующей функцию на полурешётках, описывающую это поведение. В связи с этим представляет научный и практический интерес разработка методов схемной реализации функций на полурешётках.

Первые результаты в этом направлении получены в работе [1], где описан метод реализации функции на полурешётке подмножеств трёхэлементного множества схемой в произвольном базисе и сформулированы необходимые и достаточные условия полноты базиса для случая однокаскадных параллельно-последовательных схем. При проектировании реальных дискретных управляющих систем на базе БИС и СБИС чаще всего используется элементный RS-базис, состоящий из элементов двух типов – резистора, представляющего собой двухполюсник с постоянной конечной проводимостью (обозначаемой X) между полюсами, и переключателей, являющихся многополюсниками, в которых проводимости между полюсами принимают значения в полурешёткеP2 всех непустых подмножеств множества {0, 1} и являются функциями от состояний полюсов элемента. К сожалению, ни один из RS-базисов не удовлетворяет критериям полноты из [1], поэтому актуальной становится проблема реализуемости функций на полурешётках схемами в заданном (неполном) RS-базисе. Решение этой проблемы предполагает формулировку критериев (необходимых и достаточных условий) реализуемости, т. е. существования схемы в RS-базисе, реализующей заданную функцию, и методов реализации – синтеза такой схемы, если она существует.

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

Цель работы. Настоящая работа посвящена выяснению условий реализуемости и разработке методов реализации функций на полурешётках переключательными схемами, в которых проводимости цепей принимают значения в полурешёткеP3 всех непустых подмножеств множества {0, X, 1}, а состояния узлов – значения в полурешётке (P3)2. Ставятся следующие задачи: (1) установить необходимые и достаточные условия реализуемости функций на полурешётках схемами в произвольном RS-базисе; (2) разработать методы синтеза в RS-базисах схем, реализующих функции на полурешётках; (3) формализовать понятие состязаний для функций на полурешётках и решить задачи (1), (2) для схем, обладающих свойством функциональной устойчивости к состязаниям на заданном множестве переходов.

Научная новизна и выносимые на защиту положения.

1. Для заданных функции на полурешётке f и произвольного элементного базиса B введено бинарное отношение f,B, состоящее из всех пар (aB, f(a)), где aB – набор значений всевозможных функций элементов в B от входных переменных схемы на наборе a их значений, и показано, что квазимонотонность этого отношения является необходимым условием реализуемости функции f в базисе B.

2. Введено понятие (, )-разделимости пары (a, b) элементов полурешётки множеством функций, означающее наличие в множестве функции, принимающей значения и на элементах a и b соответственно, и доказано, что необходимым и достаточным условием реализуемости функции f однокаскадной схемой в RS-базисе является (1, 0)-разделимость множеством базисных функций некоторых однозначно вычисляемых пар элементов из области определения функции f.

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

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

5. Предложены методы реализации функций на полурешётках и их систем переключательными схемами в RS-базисах.

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

7. Доказано, что необходимым и достаточным условием реализуемости функции f устойчивой к состязаниям схемой в заданном базисе является реализуемость в этом базисе расширения функции f, и предложены методы построения нужного расширения для обеспечения свойства функциональной устойчивости к состязаниям: а) на заданном множестве переходов, б) на наибольшем подмножестве всех возможных или только заданных переходов.

Все перечисленные результаты являются новыми.

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

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

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

Апробация работы. Результаты диссертации обсуждались на совместных научных семинарах кафедр защиты информации и криптографии, программирования, информационных технологий в исследовании дискретных структур Томского государственного университета, докладывались на XV Международной школе-семинаре «Синтез и сложность управляющих систем» (Новосибирск, 2004 г.), XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), Всероссийских конференциях «Новые информационные технологии в исследовании сложных структур» (Томск, 2000 и 2002 гг., Иркутск, 2004 г.), Сибирских школах-семинарах «Компьютерная безопасность и криптография» (Томск, 2003 и 2005 гг.).

Публикации. Основные результаты диссертации опубликованы в работах [1 – 13].

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и библиографии, включающей 64 наименования; её объём – 102 стр.

СОДЕРЖАНИЕ РАБОТЫ

В разделе 1.1 обсуждается состояние проблемы синтеза схем с заданным динамическим поведением.

Раздел 1.2 посвящён функциям на полурешётках. Пусть множество L вместе с определённым на нём отношением порядка является конечной верхней полурешёткой. Точная нижняя и точная верхняя грани в полурешётке обозначаются inf и sup соответственно. Множество точек (минимальных элементов) полурешётки L обозначается m(L); множество точек, содержащихся в элементе xL – m(x). Будем рассматривать частичные функции на полурешётке f: Uf L, где Uf Ln – область определения функции f. Говорят, что функция g есть доопределение функции f, если Uf Ug и g(a) = f(a) для любого aUf. Говорят, что функция g реализует функцию f, и пишут g f, если Uf Ug и g(a) f(a) для любого aUf. Аналогично определяется реализация функцией отношения на полурешётках. Всюду определённая функция на полурешётке L называется монотонной, если она сохраняет отношение порядка на L. Частичную функцию будем называть монотонной, если существует её всюду определённое монотонное доопределение. Функция называется квазимонотонной, если существует реализующая её монотонная функция.

В разделе 1.3 строго определяются понятия переключательных элементов, сетей, схем и их функций. Рассматриваются схемы с двухполюсным источником питания, проводимости в которых принимают значения из множества P3 = {0, 1, X}, где 0 – нулевая, 1 – бесконечная и X – конечная (резистивная) проводимости. Для описания процесса асинхронного изменения проводимостей и состояний строятся полурешётка проводимостейP3 = {0, 1, X, 0, 1, X, E} всех непустых подмножеств множества P3 и полурешётка состояний I = (P3)2. Здесь 0 = {0}, 1 = {1}, X = {X}, 0= {1, X}, 1= {0, X}, X= {0, 1}, E = {0, 1, X}; операция сложения вP3 есть объединение множеств, а в I – покомпонентное сложение значений изP3. Динамическое поведение комбинационной переключательной схемы с n входами и m выходами описывается функцией на полурешётке состояний : In Im.

Переключательный элемент e(x1, …, xk, a, b) есть пара (X, fe), где X = {x1, …, xk} – множество управляющих полюсов элемента, fe: Ik P3 – монотонная функция проводимости между исполнительными полюсами a и b, зависящая от состояний управляющих полюсов; для остальных пар полюсов проводимости между ними тождественно равны 0.

Переключательная сеть N(x1, …, xn, a, b) в базисе B есть пара (X, G), где X = {x1, …, xn} – множество управляющих полюсов сети, G – параллельно-последовательный граф с двумя выделенными вершинами a и b, каждому ребру которого сопоставлен переключательный элемент (Xi, fi)B, Xi X.

Функция проводимости fN: InP3 сети N определяется следующим индуктивным образом:

а) если G содержит одно ребро (a, b), то fN = fe, где e – соответствующий этому ребру элемент;

(X, G1) и (X, G2) соответственно, – операция дизъюнкции проводимостей;

юнкции проводимостей.

Однокаскадная схема C(x1, …, xn, y) в базисе B есть пара сетей в том же базисе (N0(x1, …, xn, y, GND), N1(x1, …, xn, VDD, y)), где x1, …, xn – входные полюсы схемы, y – выходной полюс, GND, VDD – полюсы источника питания. Функция состояний C: In I схемы C определяется Двухкаскадная схема C(x1, …, xn, y) есть совокупность однокаскадных схем (C1(x1, …, xn, y1), …, Ck(x1, …, xn, yk), Ck+1(x1, …, xn, y1, …, yk, y)), где C1, …, Ck – схемы первого уровня, Ck+1 – схема второго уровня с управляющими полюсами x1, …, xn, y1, …, yk. Функция состояний схемы C определяется как суперпозиция y = C ( x1,..., xn ) = Ck +1 ( x1,..., xn, C1 ( x1,..., xn ),..., Ck ( x1,..., xn )).

r-Каскадная схема определяется аналогично, если C1, …, Ck суть (r – 1)-каскадные схемы. Поскольку (t – 1)-каскадную схему можно рассматривать как частный случай t-каскадной (при k = 0), то это определение допускает в качестве управляющих полюсов схемы Ck+1 выходы схем первого, второго, …, (r – 1)-го уровней.

Будем говорить, что переключательная сеть (схема) N реализует функцию проводимости (состояний) f, если для функции сети (схемы) fN имеет место fN f. Назовём функцию проводимости f(x1,..., xn) 1-реализуемой в базисе B, если существует сеть N(x1, …, xn, a, b) в том же базисе, реализующая f. Назовём её k-реализуемой в базисе B, если существуют функция проводимости g(x1, …, xn, y1,..., ym) и функции состояний 1(x1, …, xn),..., m(x1, …, xn), такие, что g 1-реализуема в базисе B, 1,..., m реализуемы (k –1)-каскадными схемами в этом базисе, и g(x1, …, xn, 1(x1, …, xn),..., m(x1, …, xn)) f. Наконец, назовём f реализуемой, если она k-реализуема для некоторого k 1.

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

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

В разделе 2.1 устанавливается необходимое условие реализуемости функций проводимости и состояний в произвольном базисе.

Пусть заданы функция f: Uf In L со значениями в полурешётке L{I,P3} и базис переключательных элементов B = {(X1, f1), …, (Xs, fs)}, где |Xi| = ki для i = 1, …, s. Для каждого элемента ei = (Xi, fi)B рассмотрим всевозможные отображения µj:{1, …, ki} {1, …, n} множества управляющих полюсов элемента в множество номеров аргументов x1,..., xn функции f. Их количество равно ti = n ki. Каждой паре (ei, µj), i = 1, …, s, j = 1, …, ti, сопоставим функцию fi ( µ j ) : Uf P3 такую, что ( x1,..., xn ) = f i ( xµ j (1),..., xµ j ( ki ) ). Построим бинарное отношение f,B (P3) L, где r = t1 + t2 +…+ ts:

для каждого набора aUf запишем вектор aB = ( x11,..., x1t1,..., xs1,..., xsts ) размерности r, где xij= fi ( µ j ) (a), и положим (aB, f(a))f,B. Всюду далее пусть GB = { fi ( µ j ) : i = 1, …, s, j = 1, …, ti}. Будем называть бинарное отношение на полурешётках квазимонотонным, если оно реализуется монотонной функцией.

Теорема 2.1. Если функция f: Uf In L реализуема в базисе B, то отношение f,B квазимонотонно.

В разделе 2.2 устанавливаются необходимые и достаточные условия реализуемости однокаскадными и двухкаскадными схемами функций со значениями в полурешётке (P2)2. Пусть, P3. Пару наборов (a, b), где a, bIn, назовём (, )-разделимой множеством функций проводимости G, если существует функция gG, что (g(a), g(b)) = (, ). Обозначим E2 класс переключательных элементов, функции проводимости которых принимают значения в полурешёткеP2.

Теорема 2.2. Функция состояний : U (P2)2, = (f0, f1), реализуется однокаскадной схемой в базисе B E2, если и только если для любой функции f{f0, f1} выполняется условие: для любых a, bU таких, что (f(a), f(b)) = (1, 0), пара (a, b) является (1, 0)-разделимой множеством GB.

Введём в рассмотрение бинарное отношение наP3 как Теорема 2.3. Функция состояний : U In (P2)2, не реализуемая однокаскадной схемой, реализуема в RS-базисе B{R}, если и только если отношение,B квазимонотонно и множество B содержит элемент, не сохраняющий отношения ; в этом случае реализуется двухкаскадной схемой в данном базисе.

Теорема 2.4. Функция состояний : U (P2)2, не реализуемая однокаскадной схемой, реализуема в базисе B E2, если и только если отношение,B квазимонотонно и множество B содержит элемент e = ({x1,..., xk}, fe), ограничение функции fe которого на множестве ((P2)2)k не сохраняет отношения.

В разделе 2.3 устанавливаются необходимые и достаточные условия реализуемости однокаскадными и двухкаскадными схемами функций со значениями в полурешётке I.

Теорема 2.5. Функция состояний : U In I, = (f0, f1), реализуема однокаскадной схемой в RS-базисе B{R}, если и только если для любой функции f{f0, f1} выполнены условия:

а) для любых a, bU если f(a) = 1 и f(b) 1, или f(a) 0 и f(b) = 0, то пара (a, b) является (1,0)разделимой множеством GB;

б) для любых a0, a1, bU таких, что f(a0) 1, f(a1) 0 и f(b) = X, хотя бы одна из пар (a1, a0), (a1, b) или (b, a0) является (1,0)-разделимой множеством GB.

Теорема 2.6. Функция состояний : U In I, не реализуемая однокаскадной схемой, реализуема в RS-базисе B{R}, если и только если отношение,B квазимонотонно и множество B содержит элемент, не сохраняющий отношения ; в этом случае реализуется двухкаскадной схемой в данном базисе.

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

Доказательства достаточности условий теорем главы 2 конструктивны и дают методы схемной реализации функций на полурешётках. Будучи предназначенными лишь для доказательства существования схем при выполнении достаточных условий, эти методы доставляют, как правило, избыточные схемы. В главе 3 приводятся методы синтеза с использованием эвристических приёмов, направленных на получение более простых схем. Описывается модификация декомпозиционного параметрического метода В.Л. Павлова, предназначенная для синтеза параллельно-последовательных сетей, реализующих функции проводимости со значениями в полурешёткеP2. Для данных функции f и множества функций G вводится понятие (f, G)-дополняющей системы: множество функций Q назовём (f, G)-дополняющей системой, если:

1) все функции в Q реализуемы формулами над G и 2) из (f(a), f(b)) = (1, 0) следует, что пара (a, b) является (1, 0)-разделимой множеством G или (0, 1)разделимой множеством Q.

Утверждение 3.2. Пусть базис переключательных элементов B E2 содержит элемент, не сохраняющий отношения. Тогда для реализуемости функции проводимости f в RS-базисе B{R} необходимо и достаточно существование (f, GB)-дополняющей системы.

Предлагается алгоритм реализации функции проводимости fF2 двухкаскадной схемой в RSбазисе B{R}, одним из этапов которого является построение (f, GB)-дополняющей системы. Формулируются два алгоритма построения (f, G)-дополняющих систем, один из которых получает кратчайшую систему, а второй минимизирует верхнюю оценку сложности схемы, реализующей функцию f.

Предлагаются также метод реализации функции проводимости f со значениями вP3 и методы реализации систем функций со значениями вP2 и вP3.

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

Глава 4. Реализация функций на полурешетках схемами, функционально устойчивыми к состязаниям Пусть даны полурешётка состояний L, переключательная схема C с функцией fC: Ln L и a, bLn.

В силу монотонности функции схемы имеем fC(a) + fC(b) fC(a + b). Будем говорить, что переключательная схема C функционально устойчива к состязанию на переходе (a, b), если имеет место равенство fC(a + b) = fC(a) + fC(b); в противном случае будем называть схему C функционально неустойчивой к этому состязанию. Функциональная устойчивость схемы к состязанию на переходе (a, b) означает, что при любом распределении задержек элементов и любом порядке изменения компонент входного состояния выход схемы останется в пределах минимально возможного значения fC(a) + fC(b) в процессе изменения входного состояния с a на b.

Пусть дана функция f: Uf Ln L, a, bUf и a + bUf. Будем говорить, что функция f содержит функциональное состязание (ф-состязание) на переходе (a, b), если для любой монотонной определённой на a + b функции g из условия g f следует ¬ (g(a + b) f(a) + f(b)). Функцию, не содержащую ф-состязания на переходе (a, b), будем называть также свободной от ф-состязания на этом переходе. Будем говорить, что функция f, свободная от ф-состязания на переходе (a, b), содержит логическое состязание (л-состязание) на этом переходе, если существует монотонная определённая на a + b функция g такая, что g f и ¬ (g(a + b) f(a) + f(b)).

Построим для функции f и перехода (a, b) расширение fab следующим образом: U f ab = Uf {a + b}, для всех x a + b положим fab(x) = f(x), и fab(a + b) = f(a) + f(b). Следующее утверждение является другим (конструктивным) определением понятия ф-состязания.

Утверждение 4.1. Функция f содержит ф-состязание на переходе (a, b), если и только если её расширение fab не квазимонотонно.

Для квазимонотонной функции f: Uf Ln L построим всюду определённую функцию f *: Ln L следующим образом: для любого aLn пусть Xa = {xUf : a x}, и f * (a) = Построенная так функция f * является наибольшей монотонной реализацией функции f.

Теорема 4.1 (тест на наличие функционального состязания).

Квазимонотонная функция f содержит ф-состязание на переходе (a, b), если и только если существует элемент cm(a + b) такой, что f *(c)(f(a) + f(b)) =.

Теорема 4.2 (тест на отсутствие состязаний).

Пусть функция f: Uf L квазимонотонна, f * – её наибольшая монотонная реализация, a, bUf и a + bUf. Тогда f не содержит ни логического, ни функционального состязания на переходе (a, b), если и только если f *(a + b) f(a) + f(b).

Множество переходов T назовём совместимым для функции f, если существует монотонная функция g такая, что g f и для любого (a, b)T функция g определена на a + b и g(a + b) f(a) + f(b).

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

Теорема 4.3 (тест совместимости множества переходов).

множество переходов T совместимо для функции f, если и только если f свободна от ф-состязания на каждом переходе из T и для любого xM существует нижняя грань множества {fab*(x): (a, b)T}.

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

Будем говорить, что состязание на переходе (a, b) в схеме C существенно для функции f, если ¬( fC(a + b) f(a) + f(b)), и схему C назовём f-устойчивой к состязанию на переходе (a, b), если fC(a + b) f(a) + f(b).

Для заданных функции f: Uf Ln L и множества переходов T построим отношение f, T Ln L следующим образом: f, T = {(x, f (x)): xUf} {(a + b, f(a) + f(b)): (a, b)T}. Будем говорить, что функция f: Uf Ln L реализует отношение LnL, и писать f, если для любой пары (x, y) выполняются условия xUf и f(x) y. Говорим, что схема C является реализацией отношения LnL, если fC. Будем называть отношение реализуемым в базисе B, если существует его реализация в этом базисе.

Теорема 4.4. Функция f реализуема в базисе B схемой, f-устойчивой к состязаниям на всех переходах из множества T, если и только если отношение f, T реализуемо в B; в этом случае любая реализация f, T реализует f и является f-устойчивой к состязаниям на всех переходах из T.

Из определения совместимого множества переходов следует, что множество T совместимо для функции f, если и только если отношение f, T квазимонотонно. В этом случае по тесту квазимонотонности [1] для любого (a, b)T существует нижняя грань множества Fab = {f(c) + f(d): (c, d)T & c + d = a + b}, и можно построить расширение fT функции f на множество Uf {a + b: (a, b)T}, положив fT(a + b) = inf Fab.

Теорема 4.5. Функция f реализуема в базисе B схемой, f-устойчивой к состязаниям на всех переходах из совместимого для f множества T, если и только если в базисе B реализуема функция fT.

Теорема 4.6. Пусть множество переходов T совместимо для функции f и множество B E2 содержит элемент, не сохраняющий отношения. Тогда fT реализуется схемой в базисе B{R}, если и только если для любого yM = U m( xB ) существует нижняя грань множества Ty = {fT(x): x U fT & ym(xB)}.

Совместимое для функции f множество переходов T будем называть B-совместимым для f, если расширение fT реализуемо в базисе B.

Для случая, когда B есть RS-базис, приводится алгоритм построения всех максимальных по включению B-совместимых для функции f подмножеств множества переходов T.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Панкратова И. А. Синтез комбинационных функциональных схем в многозначной логике // Алгоритмы решения задач дискретной математики. Вып.2. – Томск: Изд-во Том. ун-та, 1987. – 2. Панкратова И. А., Быкова С. В., Николаева Л. А., Оранов А. М. Система автоматического синтеза комбинационных схем СИНТЕЗ-Ф // Управляющие системы и машины. – 1991. – № 1. – С. 3 – 9.

3. Панкратова И. А. К проектированию РЭС методом вентильных матриц // Труды третьей международной научно-технической конференции АПЭП – 96. – Новосибирск, 1996. – Т.6, ч.2. С. 53 – 4. Панкратова И. А. Реализация функций на полурешетках переключательными схемами // Новые информационные технологии в исследовании дискретных структур. Доклады III всероссийской конференции. – Томск, 2000. – С. 257-261.

5. Панкратова И. А. О системе программ моделирования динамического поведения переключательных схем с задаваемой точностью // Вестник Томского государственного университета. – 2000. – 6. Панкратова И. А. Синтез комбинационных переключательных схем с заданным динамическим поведением // Вестник Томского государственного университета. – 2000. – № 271. – C. 107 – 111.

7. Панкратова И. А. Синтез двухкаскадных переключательных схем, реализующих функции на полурешётках // Вестник Томского государственного университета. Приложение. – 2002. – № 1 (II).

8. Панкратова И. А. О статических состязаниях в переключательных схемах // Вестник Томского государственного университета. Приложение. – 2003. – № 6. – C. 147 – 152.

9. Панкратова И. А. Синтез комбинационных переключательных схем без состязаний // Вестник Томского государственного университета. Приложение. – 2004. – № 9 (I). – C. 245 – 249.

10. Панкратова И. А. Анализ состязаний в переключательных комбинационных схемах // Материалы XV Международной школы-семинара «Синтез и сложность управляющих систем» (Новосибирск, 18-23 октября 2004 г.) – С. 61–65.

11. Панкратова И. А. Условия реализуемости функций на полурешётках переключательными схемами // Тезисы докладов XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 23-28 мая 2005 г.) – С. 113.

12. Панкратова И. А. Параллельно-последовательная реализация функции мостикового соединения на полурешётках // Вестник Томского государственного университета. Приложение. – 2005. – № 13. Панкратова И. А. Реализация функций проводимости переключательными сетями глубины 2 // Вестник Томского государственного университета. Приложение. – 2006. – № 18. – С. 14 – 19.

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