5. Многозначные логики. Алгоритм распознавания полноты конечных систем k-значных функций. Теорема Кузнецова о функциональной полноте (1268166), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. , Ms(k) .Они замкнуты и не содержатся друг в друге по построению.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыТеорема Кузнецова2. Обоснование критерия. Докажем, что построенные классыM1 , . . . , Ms(k)искомые.Пусть A ⊆ Pk .2.1) Если A ⊆ Mj для некоторого j, то по п.п. 1.1) и 1.3)[A] ⊆ [Mj ] = Mj 6= Pk .Т.е. система A — не полна.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыТеорема Кузнецова2.2) Пусть A не содержится ни в одном классе Mj ,j = 1, . . . , s(k), но система A не полна.Положим N = ([A] ∩ Pk2 ) ∪ {x1 , x2 }.Тогдаn1) N 6= Pk2 ;n2) x1 , x2 ∈ N;n3) N = [N] ∩ Pk2 , т.к. N ⊆ [N] ∩ Pk2 ⊆ ([A] ∩ Pk2 ) ∪ {x1 , x2 } = N.Отсюда M(N) ∈ S(Pk ).Но если f (x1 , .

. . , xn ) ∈ A, то для любых функций g1 , . . . , gn ∈ Nf (g1 (x1 , x2 ), . . . , gn (x1 , x2 )) ∈ [A] ∩ Pk2 ⊆ N.Поэтому A ⊆ M(N).Отсюда A ⊆ M(N) ⊆ Mj для некоторого j — противоречие.Т.е. система A полна.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыПредполный классПусть A ⊆ Pk , k ≥ 2. Множество A называется предполнымклассом в Pk , если1) [A] 6= Pk ;2) для любой функции f ∈ Pk \ A верно [A ∪ {f }] = Pk .Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыПредполные классыВ P2 пять предполных классов: T0 , T1 , L, S, M.В Pk каждый из классов M1 , .

. . , Ms(k) в теореме Кузнецоваявляется предполным.k2Из доказательства s(k) ≤ 2k − 2.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыПредполные классыДля каждого k ≥ 2 классы сохранения множества Tk (E ) исохранения разбиения Uk (D), если они не совпадают с Pk ,являются предполными в Pk .Но это не все предполные классы в Pk .Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыПредполные классыПри каждом k ≥ 3 все предполные классы конструктивноописаны.Часть предполных классов в Pk , k ≥ 3, описаныС.В. Яблонским, А.А.

Мартыненко, Ло Чжу Каем.Завершил описание предполных классов в Pk , k ≥ 3, и доказал,что других предполных классов нет, И. Розенберг.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыЛитература к лекции1. Яблонский С.В. Введение в дискретную математику. М.:Высшая школа, 2001. Ч. I, гл. 2, стр. 51–56.2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения подискретной математике. М.: Физматлит, 2004. Гл.

III 2.1–2.5,2.13, 2.19.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваКонец лекцииПредполные классы.

Характеристики

Список файлов лекций