Функциональная полнота и выразимость в классе квазимонотонных функций на конечной полурешетке

• Автор: Парватов, Николай Георгиевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Томск
• Количество страниц: 95 с.

ОГЛАВЛЕНИЕ
Введение
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/) е {оу,с,Д} = { Щ/). Так как f'(E-tty)) Ф 0, то для множества U = f'(E-tty)) u {у} имеем ДАО = {£-г(у)),£} и A/t/) = {А,,сД = {а^сД, т.е. іпВДП)) 5е 0 = inf(A/t/)) и АГ(АД > W(f). Покажем, что hj є Ф*"*. Положим s/tty)) = dj = Cj, Sj(E-tty)) = bj, Sj(E) = E. Если для непустого подмножества U ç X inf(s/t/)) = 0, то s/t/) з {a,,A,}, t/ 2 {/(у)Д-/(у)}, т.е. inf(t/) = 0, и функция Sj квазимонотонная. Пусть x є X". Если fix) = tty), то ґ(х) = tty) и А/х) = = Cj =
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 , Для вся-