Важнейшие замкнутые классы. Теорема о полноте

Лекция 5

 Важнейшие замкнутые классы. Теорема о полноте.

Это обсуждение мы начинаем с рассмотрения важнейших замкнутых классов в Р2. Оказывается функции можно разделить по специфическим свойствам.

1. Обозначим через То класс всех булевых функций [pic 1] сохраняющих константу 0, т. е. функций, для которых выполнено равенство

[pic 2]

Т.е. если посмотреть внимательно это функции, которые на нулевом наборе имеют нулевое значению.

                                                                                Таблица 1.

[pic 3]

Легко видеть, что функции F0=0, F3 =x, F1 =x1 & x2 , F6 =x1 ⊕ x2 , F7 =x1 v x2  принадлежат  классу [pic 4] а вот функции 1, [pic 5] не входят в [pic 6].

Поскольку таблица для функции [pic 7] из класса То в первой строке содержит значение 0, то в То  содержится ровно [pic 8] [pic 9] булевых функций, зависящих от переменных [pic 10].

Задание Выпишите пересечение классов То и Т1.

Определим,  что такое замкнутый класс.

 Замкнутый класс — такое множество дискретных функций, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества

Что такое формула?

Это суперпозиция некоторого множества функций. (По определению)

Математически это

Ф([pic 11])=fi (fj (fk (x2, x3,… xn-2, fk (x2, x3), xn )        m={ fi  , fi  , fk }∈ M

M≡U  ≈ [pic 12]

Что такое замкнутый класс?

Пусть   M={ fi  , fi  , fk } и Ф – формула, тогда     ∀Ф ([pic 13]) = fx ∈M система образует замкнутый класс.

Что такое разомкнутый класс?

 Если ∃Ф ([pic 14])=fx ∉ M, то класс разомкнут. Т.е. (fx ≠ fi ) v (fx ≠ fj ) v (fx ≠ fk )

Как представить суперпозицию?

                Ф([pic 15])=fi (fj (fk (x1, x2, x3,… xn-2, fk (x2, x3), xn )                  (1)

         =>      Ф([pic 16])=fx =  fi  v fi  v fk

Практический пример.

Пусть  M={ &,⊕,->}     f1 = fi    i=1          f2 = fj  j=2            f3 = fk  k=3  

Сколько  будет  комбинаций из трех индексов и соответственно формул по схеме (1)?   

                                        i        j        k

                                        1        2        3

                                        3        2        1

                                        ……………….

                                        3        1        2

...