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

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

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 так же монотоннаÞ ÎМ

.Кольцо.Теорема о тождествах кольца.

Кольцом называют алгебру B=  сигнатура которой состоит из 2 бин.опер. и 2 нерванных операций. Равенствадля" abcÎR

1)a+(b+c)=(a+b)+c

2)a+b=b+a

3)a+0=a

4)для каждого aÎB$a’,такой что a+a’=0.

5)a(bc)=(ab)c

6)a1I=1Ia=a

7)a(bc)=ab+ac,(b+c)a=ba+ca связь I и II,согл. Которой операция * дистрибутивна отн. сложения.

Теор. В " кольце выполняются следующие тождества.

1)0a=a0=0

2)(-a)b=-(ab)=a(-b)

3)(a-b)c=ac-dc,c(a-b)=ca=cb

До-во:

1)a+0a=1Ia+0a=(1I+0)a=1Ia=a

2)-(ab)=a(-b)имеем

a(-b)+ab=a((-b)+b)=a0=0Þ

a(-b)=-(ab)

3)a(b-c)=a(b+(-c))=ab+a(-c)=

=ab-ac

Суперпозиция булевых.Формулы.Процеесс построения формулы и его представление в виде ориентированного дерева.Подформулы.Функция,представляемая формулой.

Пусть бф f есть функция от n переменных,а булев. Функции g₁…g_n-произвольные(и не обяз. Различные) функции от одного и того же числа переменных,которое обозначим m.

Определим ф-ию f(g_1…g_n),названную суперпозицией функций f,g_1….g_nтак ,что для " имеет место равенство:f(g_1…g_n)=                    

Таким образом ,суперпозиция f(g_1…g_n)есть не что иное, как композиция булевых операторов g₀f,где булев оператор gзадается семейством коорд. функций g_i,i=