К синтезу формул, реализующих и представляющих квазимонотонные и монотонные функции на полурешетке подмножеств конечного множества | Вестн. Том. гос. ун-та. 2000. № 271.

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

Предлагаются методы синтеза формул из одноместных функций и двухместной дизъюнкции (конъюнкции) для реализации и представления квазимонотонных и монотонных функций на полурешетке подмножеств k-элементного множества.

To the synthesis of formulas realizing and representing the quasimonotonic and monotonic functions defined on the semila.pdf Постановка задачи Будем рассматривать функции, которые вместе со своими аргументами принимают значения из верхней полурешетки С всех непустых подмножеств множества £={0,..., А-1}. Множество всех таких функций обозначим Рс- Функции из Рс заслуживают внимания в связи с тем, что с их помощью удается адекватно и с наперед заданной точностью моделировать динамическое поведение интегральных схем логического управления [1]. Область определения Df любой такой функции / от п переменных является полурешеткой С - л-й декартовой степенью полурешетки С. В ней элементы суть наборы длины п с компонентами в С, отношение порядка й есть покомпонентное включение и сложение есть покомпонентное объединение. Функция/называется аддитивной, если она является гомоморфизмом полурешеток, т.е. если J[a+b)= -J[a)+J{b) для любых anbmD/. Функция/называется точечной, если ее значение на любом элементе d из Dj равно сумме (объединению) элементов, содержащихся в d. Функция / называется монотонной, если для произвольных а и b из Df всякий раз из а=inf{XDM/),..., J[Dur)}=inf({Du,v...vDUr)). Так как inf([D„;u..AJA4)= =[гф*0, то, по условию леммы infty(Z)wu ...иД,,))*0 и, следовательно, inf{p(U))*(d, откуда по тесту квазимонотонности следует, чтоpeQ. Значит, в качестве функции s можно взять любую функцию из 7*1', реализующую функциюр. Следствие. Пусть /е&а) и V£/cC"(inf(/(L'))= =0^>inf([ С]у)=0).Тогда Bsef^xt.....xn)Zs(Xj)). Лемма 2. Пусть feinf(.4 #0. Пришли к противоречию. Следовательно, тД /f Ov)= =0. Заметим, что veA, ve /4Пусть У-v-A v{vi..., v,}. Из определения класса Ф следует, что inf(/4 \_л>,)*0, откуда, в свою очередь, следует inf(^ Vjv( и т.д. Применяя индукцию, получим inf (A V^la^u... ...uv,)Nnf(F-v)*0. Предположим, что существует такое подмножество U множества У), что inf(U)=0 и У не содержится в U. Пусть 11-Иг\У, LhU\j{u\,..., и/}. Так как И не содержится в U, то 1Гс У и 3v€ VaV-vfeU). А так как inf(K-v>^0, то и \nSJjyt0. Из определения V, так как то и2и... ...иц)=т1({/)*0 Полученное противоречие доказывает, что VUЦ^У). Так как верно Vt/c £F/tbK=>inf(l/)=0), то VCfc^LfeKo ЩЦу=0). Пусть I?={deDtf(d)ey}. Так как infjXZ>O)Hnf(F>=0, то по тесту квазимонотонности для функции / следует, что in%D*J=&. Следовательно, существует число j в множестве {!,.., т} такое, что inf([Dv]/)=0. А так как Vve^OD/hU то Vf^DXinflXLO)=0=i>Cb£)v), и, следовательно, VLtD/infO(L')>=0=>inflIf/l ,)= 0, откуда по следствию из леммы 1 имеем xm)^s(xj)). Лемма доказана. Пусть/- произвольная квазимонотонная функция. Весом функции / будем называть число Wj=Y\c\-\Df\, где суммирование ведется по всем с из С. Так как VseSVc€C(|c|=Kc)|), то VseSV/e£(fF/= -W5(fj). Можно показать также, что J

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Парватов Николай ГеоргиевичТомский государственный университетаспирант кафедры математической логики и проектирования радиофизического факультета
Всего: 1

Ссылки

Агибалов Г.П. Дискретные автоматы на полурешетках. Томск: Изд-во Том. ун-та, 1993.227 с.
Агибалов Г.П. О полных системах операций и синтезе схем для квазимонотонных функций на конечных полурешетках // Новые информационные технологии в исследовании дискретных структур. Екатеринбург: Из-во УрО РАН, 1998. С. 149-152.
Агибалов Г.П. О полных системах функций на полурешетке подмножеств конечного множества // Всесибирские чтения по математике и механике: Математика Томск: Изд-во Том. ун-та, 1997. Т. 1. С. 148-149.
Агибалов Г.П. К синтезу схем, реализующих квазимонотонные функции на полурешетке подмножеств двухэлементного множества //Всесибирские чтения по математике и механике: Математика Томск: Изд-во Том. ун-та, 1997. Т. 1. С. 147-148.
 К синтезу формул, реализующих и представляющих квазимонотонные и монотонные функции на полурешетке подмножеств конечного множества | Вестн. Том. гос. ун-та. 2000. № 271.

К синтезу формул, реализующих и представляющих квазимонотонные и монотонные функции на полурешетке подмножеств конечного множества | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия