Важнейшие замкнутые классы. Теорема о полноте
Автор: d4rk3NN • Ноябрь 21, 2022 • Лекция • 2,869 Слов (12 Страниц) • 181 Просмотры
Лекция 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
...