Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Парватов, Николай Георгиевич
05.13.01
Кандидатская
2002
Томск
95 с.
Стоимость:
499 руб.
ОГЛАВЛЕНИЕ
Введение
1. Основные понятия
1.1. Проблема полноты и выразимости в замкнутых классах конечнозначных функций
1.2. Замкнутые классы в и отношения на X
1.3. Классы функций на верхней полурешетке
1.4. Выводы
2. Функциональная полнота в классах квазимонотонных и монотонных функций на полурешетке подмножеств двухэлементного множества
2.1. Некоторые отношения на Е
2.2. Одноместные функции в @
2.3. 7^-полнота в классе М
2.4. Полнота в классе М
2.5. Классы Слупецкого в ()
2.6. Критерий полноты в классе ()
2.7. Выводы
3. Полнота в классе квазимонотонных функций на произвольной полурешетке
3.1. Инвариантность отношений на множествах Ф/,, Ql
3.2. Отношение ру
3.3. Предполные Ф^-классы в бх,
3.4. Тест квазимонотонности
3.5. Выводы
4. Выразимость минимальных функций в классе монотонных функций
4.1. Г^-полнота в Мь
4.2. Отношение сводимости наборов и 7/,-предполные Г^-классы в
4.3 Случай £=25*
4.4. Выводы
5. Слабая полнота в классе квазимонотонных функций
5.1. Инвариантность на 0^ и отношений
5.2. Некоторые отношения на £
5.3 Критерий полноты
5.4. Некоторые следствия из теоремы 5.
5.5. Выводы
Заключение
Литература
ВВЕДЕНИЕ
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Основу математического аппарата для логического проектирования дискретных управляющих систем (дискретных автоматов) составляет такой раздел дискретной математики, как конечнозначная логика. Ее средства позволяют описывать статическое поведение автомата (при фиксированном входном состоянии). Однако, при описании динамического (вызываемого асинхронным изменением компонент входного состояния) поведения автомата возникают трудности, обусловленные явлением состязаний между асинхронно изменяющимися компонентами его состояний. В монографии [1] показано, что динамическое поведение дискретных автоматов может быть адекватно и с заданной точностью описано средствами полурешеточно упорядоченных алгебр. При таком описании каждое из множеств входных, выходных и внутренних состояний автомата, функционирующего в динамическом режиме, образует структуру полурешетки, то есть частично упорядоченного множества, в котором для каждой пары элементов существует точная верхняя грань. Отношение порядка на множестве состояний интерпретируется как отношение сравнения состояний по степени их неопределенности, обязанной явлению состязаний. В связи с этим научный интерес представляет изучение функций, определенных и принимающих значения на полурешетках. Важнейшими классами таких функций являются классы монотонных, квазимонотонных и минимальных точечных функций. Минимальными точечными функциями обладают реальные физические элементы (транзисторы, резисторы, вентили и т.д.), монотонные функции принадлежат комбинационным схемам, построенным из них, а квазимонотонные функции реализуются такими схемами, в связи с чем актуальна задача функциональной полноты в указанных классах функций. Квазимонотонные функции реализуются монотонными, а те, в свою очередь, реализуются минимальными точечными функциями, поэтому актуальна задача выра-
для непустого подмножества UqL верно inf(s(t/)) = 0, то s(U) 2 {tty),E - /(у)} и, следовательно, U 2 {g(a),g(A)} = {0,1}, т.е. inf'{U) = 0, и функция і квазимо-нотонная. Построим функции hj : L" —> L, j є Nm, для всякого х є X" положив: (h,ty),...,hmty)) = с и (Ai(x),...,Am(x)) = а, еслиДх) = tty); (A|(x),...,A„,(x)) = А, если Дх) = E - tty)', (Ai(x),...,A„,(x)) = (E,...,E), если Дх) = £ и i ^ у Тогда / = s(g(hi,-,hm)). Пусть С/ - непустое подмножество в X" ну є JVm. Если inf(A/t/)) = 0, то множество Я(£7) = {(Ai(x),...,Am(x)) | х є t/} содержит {а,А} или {А,с}, и тогда ДАО 2 {/(у), Х-Ду)} или ДАО э {E-tty)JE},yeU. Если ДА/) 3 {t(y),ii-/y)}, то inf(t/) = 0 в силу квазимонотонности f. Если же ДАО а {E-tty),Е) иуєї/, то t(U) а {г(у),£-г(у)} и inf(t/) = 0 в силу квазимонотонности t. Следовательно, функция hj квазимонотонная. По построению А/Z") ç {aj,bj,Cj,E}, поэтому если а/тй/зс,- Ф 0, то hj є Т. Пусть а/чА/хс; = 0. Тогда щ = Cj. Если {E-tty)) = 0, то A/t/) е {оу,с,Д} = {
Sj(tty)) = Sj(t(x)). Если fix) = Е-tty), то t(x) = E-tty) и s/t(x)) = bj = А/х). Если Дх) = X и x * у, то А/х) = E > Sj(t(x)). Кроме того, А/у) = су = fytytyj). Таким образом, функция hj реализуется функцией s/г) є g2(1>. Следовательно, hj є Ф0" и предложение доказано.
Следствие. Пусть g є Q2- Qityt). Тогда Ф 2 [ Qг(1) u*fu {g} ].
Доказательство. Пусть/ є Ф(,) - Y - Q2m. В соответствии с предложением 8 найдем такое разложение функции/по функции вида s(g), s є Qi , Для вся-
Название работы | Автор | Дата защиты |
---|---|---|
Методы и алгоритмы поиска дефектов в системах автоматического управления на основе моделей дефектов | Шалобанов, Сергей Сергеевич | 2013 |
Разработка и исследование алгоритмов первичного анализа и схем индексации изображений в визуальных информационных системах | Белков, Александр Владимирович | 2003 |
Методы и алгоритмы решения задачи структурного синтеза системы источников и детекторов зондирующего излучения | Горшков, Антон Валерьевич | 2014 |