Содержание к диссертации
Введение
Глава 1. Состояние проблемы и основные понятия 10
1.1, Краткая характеристика состояния проблемы 10
1.2- Функции на полурешётках 12
1.3. Переключательные схемы и их поведение 13
1.4. Постановка задач реализации функций па полурешётках 22
Глава 2. Условия реализуемости функций на полурешётках 24
2.1. Необходимое условие реализуемости функции на полурешётках 24
2.2. Необходимые и достаточные условия реализуемости функций со значениями в полурешётке (Р2) 26
2.3. Необходимые и достаточные условия реализуемости функций со значениями в полурешётке/ 34
2.4. Условия реализуемости функций проводимости сетями с мостиковыми соединениями 45
Глава 3, Методы реализации функций на полурешётках 53
3.1. Реализация функций проводимости со значениями в Рг 53
ЗЛ.1,1-реализация 53
ЗЛ.2.2-реализация 56
3.2. Реализация функций проводимости со значениями в Р^ 67
3.3. Реализация систем функций на полурешётках 72
3.3 Л. Реализация систем функций со значениями в Рг 73
3.3,2. Реализация систем функций со значениями в Р$ 76
Глава 4. Реализация функций на полурешетках схемами, функционально устойчивыми к состязаниям 78
4.1. Определение состязаний 78
4-2. Тесты на наличие состязаний 80
4.3. Совместимость переходов 83
4.4. Условия реализуемости со свойством функциональной устойчивости к состязаниям 86
4.5. Синтез функционально устойчивых схем 90
Заключение 95
Литература 97
- Постановка задач реализации функций па полурешётках
- Условия реализуемости функций проводимости сетями с мостиковыми соединениями
- Реализация систем функций на полурешётках
- Условия реализуемости со свойством функциональной устойчивости к состязаниям
Введение к работе
Актуальность проблемы. Изначально методы логического проектирования дискретных управляющих систем [43], или дискретных автоматов [15], базируются на таком разделе дискретной математики, как копечпо-значная логика [44]. Её средства позволяют описывать статическое поведение системы (при фиксированном входном состоянии), однако недостаточны для описания динамического поведения (при асинхронном изменении компонент входного состояния). В дальнейшем в теории дискретных автоматов широкое распространение получили обгцеалгебраические методы [2, 4, 8, 48, 49]. На этом пути было показано, в частности, [2], что динамическое поведение дискретного автомата может быть адекватно и с заданной точностью описано средствами полурешёточно упорядоченных алгебр. Для этого множество состояний в автомате представляется как конечная верхняя полурешётка, т. е. частично упорядоченное множество, в котором для каждой пары элементов существует точная верхняя грань. Отношение порядка в полурешётке интерпретируется как отношение сравнения состояний по степени их неопределённости, а сумма состояний а + Ъ моделирует промежуточное состояние, возникающее в процессе асинхронного изменения а па Ъ. Задача синтеза дискретного автомата, обладающего заданным динамическим поведением, сводится к синтезу схемы в некотором базисе, реализующей функцию на полурешётках, описывающую это поведение, В связи с этим представляет научный и практический интерес разработка методов схемной реализации функций на полурешётках.
Первые результаты в этом направлении получены в работе [2], где описан метод реализации функции на полурешётке подмножеств трёхэлементного множества схемой в произвольном базисе и сформулированы необходимые и достаточные условия полноты базиса для случая однокаскадных параллельно-последовательных схем. Проблеме полноты в классе функций на произвольной конечной полурешётке посвящена также работа [29], доказа тельства в которой конструктивны и доставляют методы реализации полурешёточных функций. При проектировании реальных дискретных управляющих систем на базе БИС и СБИС чаще всего используется элементный RS-базис, состоящий из элементов двух типов -резистора, представляющего собой двухполюсник с постоянной конечной проводимостью (обозначаемой X) между полюсами, и переключателей, являющихся многополюсниками, в которых проводимое™ между полюсами принимают значения в полурешётке Рг всех непустых подмножеств множества {0,1} и являются функциями от состояний полюсов элемента. К сожалению, ни один из RS-базисов не удовлетворяет критериям полноты из [2, 29], поэтому актуальной становится проблема реализуемости функций на полурешётках схемами в заданном (неполном) RS-базисе. Решение этой проблемы предполагает формулировку критериев (необходимых и достаточных условий) реализуемости, т. е. существования схемы в RS-базисе, реализующей заданную функцию, и методов реализации - синтеза такой схемы, если она существует.
На практике к схемам проектируемых управляющих систем, помимо их функционального поведения, зачастую предъявляются дополнительные требования, такие, как легкотестируемость, самопроверяемость, ограниченность глубины и/или нагрузочных способностей элементов, и т. п. Одно из таких требований состоит в обеспечении функциональной устойчивости схемы к состязаниям на заданном множестве переходов. Поскольку понятие состязаний до сих пор определялось только для булевых функций и реализующих их схем, то для постановки и решения задач проектирования схем, реализующих функции на полурешётках и функционально устойчивых к состязаниям, необходима формализация понятия состязаний применительно к функциям на полурешётках и разработка подходящих методов синтеза.
Цель работы. Настоящая работа посвящена разработке критериев реализуемости и методов реализации функций па полурешётках переключательными схемами, в которых проводимости цепей принимают значения в полурешётке Рз всех непустых подмножеств множества {О, X, 1}5 а состояния узлов - значения в полурешётке (Рз) . Ставятся следующие задачи: (1) установить необходимые и достаточные условия реализуемости функций на полурешётках схемами в произвольном RS-базисе; (2) разработать методы синтеза в RS-базисах схем, реализующих функции на полурешётках; (3) формализовать понятие состязаний для функций на полурешётках и разработать методы синтеза схем, реализующих такие функции и обладающих свойством функциональной устойчивости к состязаниям на заданном множестве пере-ходов.
Научная новизна и выносимые на защиту положения.
1, Для заданных функции на полурешётке/и произвольного элементного базиса В введено бинарное отношение Г/д, состоящее из всех пар (а5, /(a)), где ав - набор значений всевозможных функций элементов в Я от входных переменных схемы на наборе а их значений, и показано, что квазимонотонностъ этого отношения является необходимым условием реализуемости функции/в базисе В.
2, Введено понятие (8, с)-разделимости пары (а, Ь) элементов полурешётки множеством функций, означающее наличие в множестве функции, принимающей значения б и а на элементах аиЬ соответственно, и доказано, что необходимым и достаточным условием реализуемости функции/ однокаскадной схемой в RS-базисе является (1? 0)-разделимость множеством базисных функций некоторых однозначно вычисляемых пар элементов из области определения функции/
3. Введено отношение у - расширение отношения сравнения проводимо- стей по значению на подмножества проводимостей, и установлено, что необходимым и достаточным условием реализуемости функции/двух- каскадной схемой в RS-базисе В является квазимонотонностъ отношения Г/;д и наличие в В элемента, функция которого не сохраняет у,
4. Доказано, что классы функций на полурешётках, реализуемых в RS- базисе параллельно-последовательными схемами и схемами с мостико- выми соединениями, совпадают.
5. Предложены методы реализации функций на полурешётках и их систем переключательными схемами в RS-базисах.
6. Формализованы понятия состязаний для функций на полурешётках и функциональной устойчивости к состязаниям схем, реализующих такие функции; сформулированы тесты на отсутствие состязаний и тест совместимости для заданной функции / (существования монотонной функции, реализующей/и свободной от состязаний на всех переходах) произвольного множества переходов,
7. Доказано, что необходимым и достаточным условием реализуемости функции/устойчивой к состязаниям схемой в заданном базисе является реализуемость в этом базисе расширения функции/ и предложены методы построения нужного расширения для обеспечения свойства функциональной устойчивости к состязаниям: а) на заданном множестве переходов, б) на наибольшем подмножестве всех возможных или только заданных переходов.
Все перечисленные результаты являются новыми.
Методы исследования представляют собой сочетание методов дискретной математики, теории управляющих систем и общей алгебры (теории конечных полурешёток).
Достоверность полученных результатов. Все полученные в диссертации теоретические результаты имеют строгое математическое доказательство. Кроме того, работоспособность методов синтеза подтверждена экспериментально на ряде случайно сгенерированных и известных по литературе примеров. Частным случаем приведённого в диссертации определения состязаний для функций на полурешётках является известное ранее определение этого понятия для булевых функций.
Теоретическая и прикладная ценность, В диссертационной работе решён ряд задач, связанных с реализуемостью функций на полурешётках в заданном неполном базисе. Предлагаемые методы могут быть использованы на практике при логическом синтезе схем с заданным динамическим поведениєм в реальных базисах переключательных элементов, в том числе схем, функционально устойчивых: к состязаниям,
Апробация работы. Результаты диссертации обсуяедались на совместных научных семинарах кафедр защиты информации и криптографии, программирования, информационных технологий в исследовании дискретных структур Томского государственного университета, докладывались на XV Международной школе-семинаре «Синтез и сложность управляющих систем» (Новосибирск, 2004 г,), XIV Международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.)5 Всероссийских конференциях «Новые информационные технологии в исследовании сложных структур» (Томск, 2000 и 2002 гг., Иркутск, 2004 г.), Сибирских школах-семинарах «Компьютерная безопасность и криптография» (Томск, 2003 и 2005 гг.).
Публикации. Основные результаты диссертации опубликованы в работах [52-64].
Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения и библиографии, включающей 64 наименования; её объём -102 стр.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Всюду под функцией будем иметь в виду функцию на полурешётках.
В первой главе приводится обзор литературы, формулируются основные понятия и ставятся задачи, которые решаются в последующих главах. Строго определяются понятия переключательных элементов, сетей, схем и их функций при тех ограничениях, при которых в последующих главах решается задача реализации функций на полурешётках.
Главы 2 и 4 носят теоретический характер, основные результаты в них формулируются в виде теорем. Глава 3 - прикладного характера, основными результатами в пей являются алгоритмы синтеза.
Вторая глава диссертации посвящена формулировке условий реализуемости функций на полурешетках переключательными схемами. Для данных функции/и произвольного базиса переключательных элементов В вводится отношение Tffi и доказывается, что его квазимонотонность является необходимым условием реализуемости функции/схемами в базисе В. Вводится понятие (5, ст)-разделимости элементов полурешётки множеством функций, определённых на этой полурешётке, и отношение у сравнения проводимостей. Доказывается, что необходимым и достаточным условием реализуемости функции/однокаскадной схемой в RS-базисе В является (1„ 0)-разделимость определённых пар элементов из области определения/множеством базисных функций, а необходимым и достаточным условием реализуемости функции/ двухкаскадной схемой в том же базисе является квазимонотонность отношения Г/ и наличие в базисе элемента, функция которого не сохраняет отношения у, В последнем разделе главы устанавливается, что классы функций, реализуемых в RS-базисе параллельно-последовательными схемами и схемами с мостиковыми соединениями, совпадают.
Доказательства достаточности условий теорем главы 2 конструктивны и дают методы построения схем, реализующих функции на полурешётках. Будучи предназначенными лишь для доказательства существования схем при выполнении достаточных условий, эти методы доставляют, как правило, избыточные схемы. В главе 3 приводятся практические методы синтеза, направленные на получение более простых схем. Описывается модификация декомпозиционного параметрического метода BJL Павлова [27], предназначенная для синтеза параллельно-последовательных сетей, реализующих функцпи со значениями в полурешётке Р2- Для данных функции/и множества функций G вводится понятие (/ (7)-дополнятоіцей системы, существование которой является необходимым и достаточным условием реализуемости функции/в базисе элементов с функциями из G. Формулируются два алгоритма построения (f, С)-дополняющих систем, один из которых позволяет получать схемы с минимальным общим числом ячеек, второй минимизирует верхнюю оценку сложности реализации функции / Формулируется метод реализации функций со значениями в полурешётке Р$ схемами в RS-базисе, а также методы реализации систем функций со значениями в Рг и в Р3. Все методы проиллюстрированы примерами; для функций со значениями в Р2 примеры взяты из литературы, для функций со значениями в Р$ из-за отсутствия таковых - случайно сгенерированы. Следует отметить, что методы, приводимые в литературе, решают задачу реализации булевых функций; наши методы, будучи предназначенными для решения более обшей задачи -реализации функций на полурешётках, и в этом частном случае зачастую не уступают или незначительно проигрывают известным по качеству доставляемых ими схем.
Последняя, четвёртая, глава диссертации посвящена решению задачи реализации функций на полурешётках схемами, функционально устойчивыми к состязаниям на заданном множестве переходов. Определяются понятия функциональных и логических состязаний для функций и функциональной устойчивости к состязаниям для схем; формулируются тесты на отсутствие состязаний, тест совместимости произвольного множества переходов, необходимые и достаточные условия реализуемости функции на полурешётках устойчивой к состязаниям на заданном множестве переходов схемой в заданном базисе. Показывается, что задача реализации функции на полурешётках устойчивой к состязаниям схемой есть задача реализации расширения исходной функции. Предлагаются методы построения нужного расширения для решения задач синтеза схемы, обладающей свойством устойчивости к состязаниям: а) на заданном множестве переходов, б) на наибольшем подмножестве из всех возможных или только заданных переходов. Показывается, что перестройка схемы с целью максимизации числа переходов, на которых схема устойчива к состязаниям, требует в общем случае синтеза схемы заново.
Постановка задач реализации функций па полурешётках
Требуется из элементов заданного базиса построить переключательную комбинационную схему С, реализующую функцию (р.
В главе 2 обсуждаются условия существования решения, в главе 3 -методы реализации функций на полурешётках для случаев І = (Р2)2 и L = (Рз)2, а также методы реализации систем таких функций.
Будем называть переходом (от а к Ь) упорядоченную пару (а, Ь) наборов из области определения функции т. Схема называется функционально устойчивой к состязанию на переходе (а, Ь\ если состояние её выхода не выходит за пределы значения $а) + р(й) при изменении входного состояния с а на Ь.
Задача 2
Заданы:
1) функция на полурешётке p\U - L;
2) множество переходов Г- {(att Ь,): i- 1, ...,.s};
3) элементный базис.
Требуется из элементов заданного базиса построить переключательную схему, реализующую функцию р и функционально - устойчивую к состязаниям на всех переходах из множества Т.
В главе 4 даются формальные определения и классификация состязаний для функций на произвольных полурешётках, описывается способ сведения данной задачи к задаче 1 и обсуждаются условия существования решения. Глава 2, Условия реализуемости функций на полурешётках
Цель данной главы - формулировка условий реализуемости функций на полурешётках переключательными схемами в RS-базисе.
2,1. Необходимое условие реализуемости функции на полурешётках
Пусть задана функция (состояний или проводимости)/: U/Qln- L со значениями в полурешётке І є {/, Р$}. Переформулируем для неё тест квазимонотонности из [3] в терминах сохранения отношений. Для этого введём тернарное отношение а на Рз как a(xry,z)o xc\yr\zf0. Это отношение естественным образом (покомпонентно) распространяется на полурешётки / и Г. Тогда функция/квазимонотонна, если и только если она сохраняет отношение а.
Пусть задан базис переключательных элементов В = {(ЛГь/0,..., (ЛГ„/)}, где j = fc для / = 1, ...,s. Для каждого элемента ei=(Xitfy є В рассмотрим всевозможные отображения /$: {1, ...,} - (1, ...,я} множества управляющих полюсов элемента в множество номеров аргументов х\, ,.., хп функции/ Их количество равно =пк - Каждой паре fe#), /=1,..., j - 1, --j » сопоставим функцию f ] ; Uf- P$t область определения которой совпадает с областью определения функции / и / ( ,-, ) = /( (1),-, ( ))- Содержательно, /W - это функция проводимости базисного элемента е, между его исполнительными полюсами после отождествления его управляющих полюсов с полюсами ///1), ...,/ () схемы. Перебирая всевозможные отображения //у, получим функции проводимости элемента е{ при всевозможных способах подключения его управляющих полюсов к входным полюсам схемы. Всюду далее пусть
в Построим шнаіігое откоіііенйе Г/$ с: (P XL, где Г = I+ fe+ -.. + ҐЛ следующим образом: для каждого набора а є U/ запишем вектор aB=(xn,...,xXli ...,xsl,„.9xs;J размерности г, где xj = f {а\ и положим (as f(a)) є Г Других пар в Где нет. В соответствии с [2] будем называть бинарное отношение на полурешётках ГсМхі квазилюнотонным, если оно реализуется монотонной функцией, т. е. если для некоторой монотонной функцииg: Ug(zM- L верно следующее: (а, Ь) є Г а GUs&cg(a) b. Тесты квазимонотонности для отношений и функций на полурешётках совпадают»
Условия реализуемости функций проводимости сетями с мостиковыми соединениями
В предыдущих разделах рассматривались условия реализуемости функций состояний переключательными схемами, состоящими только из параллельно-последовательных сетей. Понятно, что параллельно-последовательными сетями не исчерпывается всё множество сетей; в частности, в таких сетях не используется мостиковое соединение (мостик) - сеть с выделенными полюсами 1 и 2, представленная на рис. 2.1. Обозначим функцию этого соединения через 0(р, д, г, s, t), где;?, q, г, s t- переменные со значениями в Р3, приписанные рёбрам сети; она определяется через проводимости цепей pr, qs pts и qtr на точках полурешётки (P f следующим образом: 0(p,q,r,s,t) =
1, если хотя бы одна из цепей имеет проводимость 1, О, если проводимости всех цепей равны О, X, если хотя бы одна цепь имеет проводимость X и ни одна цепь не имеет проводимость 1.
На остальных элементах полурешёттси (Р )5 значения функции 0 вычисляются по правилу точечного продолжения.
Возникает вопрос: расширяется ли класс реализуемых функций состоя ний, если в схемах для их реализации, кроме последовательного и парал лельного соединений переключательных элементов, допускается еще и мос-тиковое соединение их? Ниже дается отрицательный ответ на этот вопрос, а именно: показывается, что функцию Э мостика можно реализовать параллельно-последовательной сетью. Последнее очевидно, если проводимости р, q9 г 5, t в мостике принимают значения в полурешетке {0, 1, X }, ибо в этом случае применимы эквивалентные преобразования сетей, описанные Шенноном [41]. Так, преобразовав звезду, образованную рёбрамир, г, t, в треугольник, получим сеть, изображённую па рис, 2.2 (а), которой соответствует П-формулаФ:
Фі =pr v (q vpt)(s v /r). Другое преобразование - треугольника, образованного рёбрами р, t, q, в звезду, приводит к сети рис. 2.2 (б) и П-формуле Ф2:
Фг = ІР v q) А ((р v t) г v (q v f) s).
Эквивалентность преобразований треугольника в звезду и звезды в треугольник обосновывается выполнением в булевой алгебре законов поглощения и дистрибутивности соответственно. В полурешётке Р$ эти законы не выполняются вследствие чего функция мостикового соединения не реализуется П-формулами Ф] и Ф2; например, 8(Х , X , 1,1, X) = X , но Фі(Х , X , 1,1, X) = (X A1)V(XVX AX)A(1V1AX) = XV(XV1 )A1 = XVE = E, и Ф2(Х ,Х , 1, l,X) = (X vX ((XVX)Alv(XVX)Al) = XTA(XVX) = X AOr=E.
По аналогии с П-формулой, введем понятие М-формулы над множеством функций проводимости G
1. Если g есть символ л-местной функции из G и х{ хп - переменные со значениями в области определения функции g, то R =g(xu ..., хп) есть М-формула над G, и eS функция равна g,
2. Если RHS- М-формулы над G, то (R v S) и (Й A S) - также М-формулы над G; их функции равны gRv gs и gR Ags соответственно, где gR) gs-функции М-формул R и S,
3. Если Л 2, KS,T- М-формулы над Gt то 6(F, Q, R,S,T)- также М-формула над G5 и её функция равна 6(gP, gQi gR, gSt gT\ где gF, gQb gRi gSi gT- функции М-формул P, Q, R, S и T соответственно.
4. Других М-формул над G пет.
Заметим, что класс сетей, соответствующих М-формулам, допуская мос-тиковьте соединения, строго включает в себя класс параллельно-последовательных сетей, однако всё же не исчерпывает класса произвольных сетей, так как в последних, кроме параллельных, последовательных и мости-ковых, возможны другие способы соединения двухполюсников.
Теорема 2.7. Функция проводимости /; U/ с /"- Р$ реализуется М-формулой над множеством G и {X} для G с F2, если и только если /реализуется П-формулой над G и {X}.
Доказательство. Достаточность очевидна.
Необходимость докажем индукцией по построению М-формулы. База индукции. Докажем реализуемость П-формулой суперпозиции функций 9(р, g, rt s, і) при {р, q, r9s,t}tzGv {X}. Если {р, q, г, s, /} с: G, то Q(p} q, г, s} t) = pr v qs vptsv qtr, поэтому достаточно рассмотреть случай, когда хотя бы одна из функций , q9 г, s или /равна константе X.
1,Пусть/? = Хи {q, r,s,t) czG. Значения функции 8(Х, q, г, s, t)npiiq, г, s, і є {0,1} представлены матрицей в коде Грея на рис. 2.3; в табл. 2.10 приведена соответствующая функция на полурешётке (на элементах, отсугст-вующих в таблице, функция принимает значение Е). Декомпозиционным методом, описанным в доказательстве достаточности условий утверждения 2.6, с последующим упрощением П-формулы, получаем следующее разложение:
Реализация систем функций на полурешётках
Состязания в реальных схемах возникают из-за наличия ненулевых задержек в элементах и соединениях схемы и заключаются в более чем однократном изменении состояния выхода схемы при однократном изменении входного состояния. В этой главе вводятся все необходимые определения, связанные с формализацией понятия состязания и относящиеся к переключательным схемам и функциям на полурешётках, формулируются тесты на наличие или отсутствие состязаний у последних (функций) и тесты на реализуемость функции на полурешётках схемой, функционально устойчивой к состязаниям, показывается, как методами предыдущей главы решается задача синтеза схем, реализующих функции на полурешётках и обладающих свойством функциональной устойчивости к состязаниям па заданном или наибольшем подмножествах переходов.
Пусть даны полурешётка состояний І, переключательная схема С с функцией fc :Ln L и а, Ь єя. В силу монотонности функции схемы имеем fd,a) +/с(Ь) fdft + b). Будем говорить, что переключательная схема С функ-щюналъно устойчива к состязанию на переходе (а, Ь\ если имеет место равенство/ + Ь) =fdfl) +_/с(6); в противном случае будем называть схему С функционально неустойчивой к этому состязанию. Функциональная устойчивость схемы к состязанию на переходе (а, Ь) означает, что при любом распределении задержек элементов и любом порядке изменения компонент входного состояния выход схемы останется в пределах минимально возможного значения/с(д) +/ # ) в процессе изменения входного состояния с а на Ь,
Пусть дана функция f:U/c.Ln L,a,bG Uf и а + Ь g U/. Будем говорить, что функция f содержит функциональное состязание (ф-состязание) на переходе (а, 6), если для любой монотонной определённой на я.+ Ь функции g из условия g /следует -і (g(a + b) f{a) +/(6))- По определению не-квазимонотонная функция содержит ф-состязания на всех переходах. Функцию, не содержащую ф-состязания на переходе (д, Ь), будем называть также свободной от ф-состязапия на этом переходе. Будем говорить, что функция / свободная от ф-состязапия на переходе (д, Ь\ содержит логическое состязание (я-состязание) на этом переходе, если существует монотонная определённая на a + b функция g такая, что g /и -i (g(a + b) f(a) +/(6)).
Содержательный смысл определений тот же, что для булевых функций и реализующих их схем. Если функция / содержит ф-состязание на переходе (а, Ь), то невозможно построение функционально устойчивой к этому состязанию схемы, реализующей функцию / Если функция / содержит л-состязание на переходе (а, Ь\ то для реализации/возможно построение как устойчивой, так и неустойчивой к состязанию на этом переходе схемы. Заметим, что определение состязания симметрично относительно а и Ь, т. е. состязания на переходах (д, Ь) и ф, а) присутствуют или не присутствуют одновременно.
Построим для функции/и перехода (а, Ь) расширние fob следующим образом: Uf = Ufu{a + b} для всех хфа + Ь положим fta(x)-f(x)t и fah{a + b) = f{a) +/() Следующее утверждение является другим (конструктивным) определением понятия ф-состязания.
Утверждение 4.1. Функция/содержит ф-состязание на переходе (а, Ь), если и только если её расширение/ не квазимонотонно.
Доказательство.
Необходимость. Пусть функция / содержит ф-состязание на переходе (д, й). Если расширение fab квазимонотошю, то существует монотонная функция g, реализующая fab и определенная на a + b в силу й + йе Uf . Но тогда g / ввиду fab / и g(a + Ь) U{a + b) =f(a) +/(й), что противоречит определению ф-состязания. Достаточность. Пусть расширение fab не квазнмонотонно и функция / свободна от ф-состязания на переходе {а, Ь). Тогда существует монотонная определённая на а + Ъ функция g такая, что g /и g(a + Ь) й/{а) +/(й). Последние два неравенства равносильны условию g f t что противоречит пе-квазимонотонности/й. Утверждение доказано.
Заметам, что возможность неквазимонотонности расширения/& квазимонотонной функции / вытекает из того, что для я, 6, с є Ln возможно выполнение условия сП{а + Ь)Ф0 при спа = 0 и с п & = 0, что влечет не-квазимонотонность/й в случае/(с) п (/(д) +/()) = 0. Для L = I эта ситуация может возникнуть уже при п = 1 (например, 00 п (01 +10) = 00 г\ Х Х = 00), а для = S-только при и 1:(01,10) п ((01,01)+ (10,10)) = (01,10) п
{(01, ou (ois юх (ю, 01), (ю, ю)! = (01, ю).
Условия реализуемости со свойством функциональной устойчивости к состязаниям
Рассмотрим следующую ситуацию. Предположим, что функция /реали зовапа некоторой схемой С, функционально неустойчивой к состязанию на переходе (а, Ь\ т. е. имеет место неравенство fda) +/с(6) f(fl+b)9 где /с функция схемы С- Вместе с тем, ввиду /с(д) +fdp) /(a)+/(6), возможно выполнение условия fda+b) f(a) +/(6), т. е. выходной сигнал схемы ни при каком распределении задержек не выходит за пределы предполагаемого зна чения/(д) +/(й) при изменении входного состояния с а на Ъ. Будем считать такое состязание в схеме несущественным для данной функции/ Соответственно этому будем говорить, что состязание на переходе (а, Ь) в схеме С существенно, если -I(/C(G + b) f{a) +/(6)), и будем называть схему С /-устойчивой к состязанию па переходе (а, Ь), если fda + b) f{a) +/(6)- Заметим, что если функция/принимает только точечные значения, то все состязания в схеме С являются существенными, так как в этом случае ввиду fdfl) =f(a) ufdP) =f{b) невозможна цепочка неравенств /da) +fc(b) fc{a+b)
Сформулируем условия реализуемости произвольной функции f;U/QL" L схемой в заданном базисе, /-устойчивой к состязаниям па всех переходах из заданного множества Г. Для этого построим отношение Q/iT LnxL следующим образом: 1/,т= {(я,/(х)); хьЩ и {{а + Ь, f(a) +f(b)): (а, Ь) є 1). (В общем случае это действительно отношение, а не функция, ввиду возможности равенства а + b = с + d при (аь Ь) Ф (с, d)\ Будем говорить, что функция /: UrcLn- L реализует отношение Гсілх, и писать / , Г, если для любой пары (х, у) є Г выполняются условия х Ё U/ и f(x) у. Говорим, что схема С реализует отногиеиие Г с Ln х I, или является его реализацией, если/с , Г, Будем называть отношение Г реализуемым в базисе В9 если существует его реализация в этом базисе.
Теорема 4.4. Функция/реализуема в базисе В схемой,/-устойчивой к состязаниям на всех переходах из множества Г, если и только если отношение QjtТреализуемо в В; в этом случае любая реализация Q/iTреализует/и является /устойчивой к состязаниям на всех переходах из Т.
Доказательство. Рассмотрим некоторую схему С в базисе В, Необходимость, Пусть схема С реализует/и/устойчива к состязаниям па всех переходах из 7". Тогда для её функции/с выполняется:/ ) /( ) для любого д: є Uf\if({a+ b)f(a)+f(b) для любого (а, Ь) є Г, что по определению 2/, г означает/с й Qft т Достаточность. Пусть схема С реализует Q/t г- Тогда /с(х) /(х) для любого х є Ufi что означает/с / и, кроме того, fda + b) uf(a) +/(6) для любого (я, Ь) є Г, что означает/устойчивость схемы С к состязаниям на всех переходах из множества Г. Теорема доказана.
Из определения совместимого множества переходов следует, что множество Т совместимо для функции/ если и только если отношение lr т квазимонотонно. В этом случае по тесту квазимонотонности [2] для любого (а, А) Е Г существует нижняя грань множества Fab- {f(c)+f(d): (c d) є Т & c + d = a + b}, и можно построить расширение fT функции/на множество U/U {а + Ь\ (а, Ь) є Т), лоложив/Кд + b) = infFab.
Теорема 4,5. Функция/реализуема в базисе В схемой,/устойчивой к состязаниям на всех переходах из совместимого для/множества Г, если и только если в базисе В реализуема функция//-.
Доказательство.
Непосредственно проверяется, что всякая функция, реализующая расширение/ реализует отношение С1/Т. Докажем обратное. Пусть g QffT, Рассмотрим произвольный переход (а, Ь) є Т и любой переход (с, d) є Т такой, что а+ b = c + d. Ввиду последнего равенства и условия (с + d, /(c) +/( /)) є % т- имеем g(a + ft) = g(c + d) /(c) +/(d), что по определеншо Fab и в силу произвольности выбора (с, d) равносильно условию g(a + 6) inf Fff -/Т(Й + й). Кроме того, для любого х є U/ ввиду ( ,/( )) є % 7 выполняется g(;c) /(х) = /j(x). Таким образом, g % г « g fTf и доказываемая теорема следует из теоремы 4Л.
