Теорема о наименьшем решении линейного уравнения в замкнутом полукольце

Т-ма: наименьшими решениями уравнений x=ax+b и x=xa+b в замкнутых п/к будут соответственно x=a*b и x=ba*, a* - итерация элемента а.

Д-во: использую формулу для вычисления наименьшей неподвижной точки и записывая в случае в случае замк п/к как бесконечную сумму, для уравнения х=а*b получим х=Е(n>=0, беск): f^n(O), где О – нуль п/к, а f(x)=ax+b. Учитывая, что

f^0(O)=O

f^1(O)=aO+b=b

f^2(O)=ab+b

----------

f^n(O)=(a^(n-1) +…+a^2+a+1)b

получаемЕ(n=0, беск): f^n(O)= Е(n=1, беск):(II+a+...+a^(n-1))b

Используя непрерывность умножения, выносим b за знак бесконечной суммы

Е(n=1, беск): (II+a+...+a^(n-1))b = (Е(n=1, беск): (II+a+...+a^(n-1)))b

Классы Поста Примеры.Теерема о замкнутости классов Поста.

Пять функциональных классов,называемые классами Поста.

1)Т₀=ífÎP₂:f(0,….0)=0ý-класс функций, сохраняющих нуль.

2)Т₁=ífÎP₂:f(1,….1)=1 класс функций, сохраняющих 1.

3)L=ífÎP₂:f(x₁,….x_n)=a₀+a₁x₁+a_nx_n-класс линейных функциий,полином жигалкина которых не содержит ни одной коньюкции материалов.

4)Класс самодвойственности ф-ий S-ífÎP₂:f( )=f( )

5)

-класс монотонных функций

Теор.Каждый класс Поста замкнут.

Д-во:Нужно для каждого класса Поста           ,доказать что замыкание  множества бф С совпадает с С.Пусть f(g_1….g_n)-какая –то суперпозиция над С, обозначим ее через .Без ограничения обязоности можно считать,что все функции f,g_1….g_nÎP_2n.Рассуждаем,используя индукцию по определению суперпозиции ,если для каждого функция g_ix_i,где x_i-переменное,то =f(x,…x_n)ÎC.предположим,что в суперпозиции  все функции g_i есть эл-ты класса Поста C.Докажем, что и =f(g,…g_n)ÎC

1)Если С=Т_0,то

2)При С=  аналогино

3)Пусть с= .Фиксируем произвольно набор           Вычислим:

4)С=М.Берем произвольные наборы так,что Докажем ÎМ.Имеем:                                  т.к. все функции     монотонные и тем сильнее вектор                 не больше вектора               ,а функция f так же монотоннаÞ ÎМ