5. Многозначные логики. Алгоритм распознавания полноты конечных систем k-значных функций. Теорема Кузнецова о функциональной полноте (1268166)
Текст из файла
Лекция: Алгоритм распознавания полноты в Pk .Замкнутые классы. Классы функций,сохраняющих множества и сохраняющихразбиения, их замкнутость. Теорема Кузнецова офункциональной полноте. Предполные классы.Лектор — доцент Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suАлгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыАлгоритм распознавания полнотыТеорема 1 (о существовании алгоритма, распознающегополноту в Pk ). Пусть k ≥ 3.
Существует детерминированныйалгоритм, которому на вход подается конечная системафункцийA = {f1 , . . . , fm } ⊆ Pk ,и который всегда через конечное число шагов останавливаетсяи выдает ответ «Да», если система A — полна, и выдает ответ«Нет», если система A не является полной.Доказательство.Т.к. можно добавлять несущественные переменные, будемсчитать, что все функции fj зависят от одного и того же наборапеременных x1 , . .
. , xn .Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыАлгоритм распознавания полнотыДоказательство. По индукции построим последовательностьмножествN0 ⊆ N1 ⊆ N2 ⊆ . . . ⊆ Pk2 .Базис индукции. N0 = ∅.Индуктивные переход. Пусть множество Nr ⊆ Pk2 ужепостроено.
Для каждой функции fj ∈ A, j = 1, . . . , m,рассмотрим все функции, которые получаются подстановкойвместо ее переменных функций из множества Nr илипеременных x1 , x2 . ПоложимNr +1 = Nr ∪ {fj (g1 (x1 , x2 ), . . . , gn (x1 , x2 )) | gi ∈ Nr ∪ {x1 , x2 }},где i = 1, . . . , n, j = 1, . . . , m.Например, множество N1 содержит все функции, которыеможно построить, если вместо переменных функций fj ∈ A,j = 1, .
. . , m, подставлять только переменные x1 и x2 .Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыАлгоритм распознавания полноты2Доказательство. Т.к. Nr ⊆ Pk2 для всех r , и |Pk2 | = k k , т.е.|Pk2 | — конечное число, найдется такое r ∗ , чтоN0 ⊂ N1 ⊂ . . . ⊂ Nr ∗ −1 ⊂ Nr ∗ = Nr ∗ +1 = . . .Пусть алгоритм останавливается, когда построено такоемножество Nr ∗ , что Nr ∗ = Nr ∗ +1 .Тогда1) если Vk (x1 , x2 ) ∈ Nr ∗ , то ответ «Да» в силу полнотысистемы {Vk };2) если Vk (x1 , x2 ) ∈/ Nr ∗ , то ответ «Нет», т.к. замыкание [A] несодержит даже все функции от двух переменных.Что можно сказать о сложности алгоритма из теоремы 1?Он крайне трудоемок и не годится для применения на практике.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыПолнота в PkА есть ли алгоритм распознавания полноты в P2 ? Да, оноснован на теореме Поста и заключается в проверке свойствсохранения констант, линейности, самодвойственности имонотонности для функций из исходной системы A ⊆ P2 .Можно ли в Pk при k ≥ 3 доказать теорему, аналогичнуютеореме Поста в P2 ?Да, это теорема Кузнецова.
Мы ее докажем чуть позже.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыЗамкнутый классПусть A ⊆ Pk , k ≥ 2. Множество A называется замкнутымклассом в Pk , если [A] = A.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыФункция, сохраняющая множествоПусть E ⊆ Ek .
Функция f (x1 , . . . , xn ) ∈ Pk сохраняетмножество E , если для всех a1 , . . . , an ∈ E верноf (a1 , . . . , an ) ∈ E .Множество функций из Pk , сохраняющих множество E ⊆ Ek ,обозначим как Tk (E ).Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыКласс функций, сохраняющих множествоТеорема 2. Пусть k ≥ 2. Для каждого множества E ⊆ Ek классTk (E ) замкнут.Доказательство. Пусть E ⊆ Ek . Заметим, что x ∈ Tk (E ).Пусть f0 (y1 , .
. . , ym ) ∈ Tk (E ), и fi (x1 , . . . , xn ) ∈ Tk (E ), гдеi = 1, . . . , m.Рассмотрим функциюf (x1 , . . . , xn ) = f0 (f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )).Тогда если a1 , . . . , an ∈ E , тоf (a1 , . . . , an ) = f0 (f1 (a1 , . . . , an ), . . . , fm (a1 , . . . , an )) == f0 (b1 , . . . , bm ) ∈ E ,т.к. b1 , . . . , bm ∈ E .Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыКлассы функций, сохраняющих множествоТеорема 3. Пусть k ≥ 2 и E ⊆ Ek .Тогда Tk (E ) = Pk , если и только если E = ∅ или E = Ek .Доказательство.1) Если E = ∅, то Tk (E ) = Pk , т.к.
никаких условий нет.2) Если E = Ek , то Tk (E ) = Pk , т.к. для всех функций условиевыполнено.3) Если E 6= ∅ и E 6= Ek , то пусть a ∈ E и b ∈ Ek \ E .Рассмотрим такую функцию f (x) ∈ Pk , что f (a) = b. Тогдаf (x) ∈/ Tk (E ).Пусть k = 2.Тогда T2 ({0}) = T0 и T2 ({1}) = T1 — классы, сохраняющиеконстанту ноль и константу один соответственно.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыНеполнота системы {∼ x, max(x, y )} в Pk при k ≥ 3Пример. Докажем, что система A = {∼ x, max(x, y )} —неполна в Pk при k ≥ 3.Рассмотрим E = {0, k − 1} ⊆ Ek .
Отметим, что E 6= Ek приk ≥ 3. Кроме того,∼ 0 = k − 1, ∼ (k − 1) = 0,max(a, b) ∈ {0, k − 1} при a, b ∈ {0, k − 1}.Значит, A ⊆ Tk (E ).По теоремам 2 и 3 получаем:[A] ⊆ Tk (E ) 6= Pk .Т.е. система {∼ x, max(x, y )} — неполна в Pk при k ≥ 3.При k = 2 система {∼ x = x̄, max(x, y ) = x ∨ y } — полна.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваРазбиение множестваСемейство D = {D1 , . . .
, Ds } называется разбиениеммножества Ek , если1) Di 6= ∅ при i = 1, . . . , s;2) Di ∩ Dj = ∅ при i 6= j;sSD i = Ek .3)i=1Предполные классыАлгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыФункция, сохраняющая разбиениеПусть D = {D1 , . . . , Ds } — разбиение множества Ek . Элементыa, b ∈ Ek называются эквивалентными по разбиению D, еслинайдется такое подмножество Di ∈ D, что a, b ∈ Di .Обозначение: a ∼D b.Наборы α = (a1 , .
. . , an ), β = (b1 , . . . , bn ) ∈ Ekn называютсяэквивалентными по разбиению D, если ai ∼D bi для всехi = 1, . . . , n. Обозначение: α ∼D β.Функция f (x1 , . . . , xn ) ∈ Pk сохраняет разбиение D, если длявсех пар наборов α, β ∈ Ekn если α ∼D β, то f (α) ∼D f (β).Множество функций из Pk , сохраняющих разбиение D,обозначим как Uk (D).Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыКласс функций, сохраняющих разбиениеТеорема 4. Пусть k ≥ 2. Для каждого разбиения D классUk (D) замкнут.Доказательство. Пусть D — разбиение множества Ek .Заметим, что x ∈ Uk (D).Пусть f0 (y1 , . .
. , ym ) ∈ Uk (D), и fi (x1 , . . . , xn ) ∈ Uk (D), гдеi = 1, . . . , m.Рассмотрим функциюf (x1 , . . . , xn ) = f0 (f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn )).Тогда если α, β ∈ Ekn и α ∼D β, тоf (α) = f0 (f1 (α), . . . , fm (α)) = f0 (γ),f (β) = f0 (f1 (β), . . . , fm (β)) = f0 (δ),и f (α) ∼D f (β), т.к.
γ ∼D δ.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыКлассы функций, сохраняющих разбиениеТеорема 5. Пусть k ≥ 2 и D = {D1 , . . . , Ds } — разбиениемножества Ek .Тогда Uk (D) = Pk , если и только если s = 1 или s = k.Доказательство.1) Если s = 1, то Uk (D) = Pk , т.к. все элементы Ekэквивалентны по разбиению.2) Если s = k, то Uk (D) = Pk , т.к.
эквивалентность поразбиению обозначает равенство элементов Ek .3) Если 1 < s < k, то найдется подмножество Di ∈ D, вкотором не менее двух элементов, т.е. a, b ∈ Di , a 6= b, инайдется еще хотя бы одно подмножество Dj ∈ D, i 6= j, и пустьc ∈ Dj . Рассмотрим такую функцию g (x) ∈ Pk , что g (a) = a,g (b) = c. Тогда g (x) ∈/ Uk (D).В P2 нет не совпадающих в ним классов, сохраняющихразбиение.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыНеполнота одной системы в Pk при k ≥ 3Пример. Докажем, что система A ={0, 1, .
. . , k − 1, j0 (x), j1 (x), . . . , jk−1 (x), max(x, y ), min(x, y )} —неполна в Pk при k ≥ 3.Рассмотрим D = {D1 , D2 } — разбиение Ek , где D1 = {0, 1},D2 = {2, . . . , k − 1}, при этом s = 2.Отметим, что 1 < s < k при k ≥ 3.Каждая константа, ji (x), i ∈ Ek , max(x, y ), min(x, y ) сохраняютразбиение D.
Значит, A ⊆ Uk (D).По теоремам 4 и 5 получаем:[A] ⊆ Uk (D) 6= Pk .Т.е. система A — неполна в Pk при k ≥ 3.При k = 2 система{0, 1, j0 (x) = x̄, j1 (x) = x, max(x, y ) = x ∨ y , min(x, y ) = xy } —полна.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыПолнота некоторой системы в Pk при k ≥ 3Пример. Докажите, что системаA = {0, 1, . . . , k − 1, J0 (x), J1 (x), .
. . , Jk−1 (x), x + y , x · y } —полна в Pk при всех k ≥ 3.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыТеорема КузнецоваТеорема 6 (А.В. Кузнецова о функциональной полноте).Пусть k ≥ 3. Существует такое конечное семейство замкнутыхи не содержащихся друг в друге классов в PkM1 , . . . , Ms(k) ,что для любого A ⊆ Pk система A полна в Pk тогда и толькотогда, когда она не содержится ни в одном из классовM1 , . . . , Ms(k) .Доказательство.1. Построение классов. Пусть N ⊆ Pk2 иn1) N 6= Pk2 ;n2) x1 ∈ N, x2 ∈ N;n3) [N] ∩ Pk2 = N.Пусть M(N) ⊆ Pk иM(N) = {f (y1 , .
. . , ym ) ∈ Pk | f (g1 (x1 , x2 ), . . . , gm (x1 , x2 )) ∈ Nдля всех g1 , . . . , gm ∈ N}.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыТеорема Кузнецова1.1) Класс M(N) — замкнут.Заметим, что x ∈ M(N).Если f0 (z1 , . . . , zt ) ∈ M(N), fi (y1 , . . . , ym ) ∈ M(N), гдеi = 1, . . . , t, иf (y1 , . .
. , ym ) = f0 (f1 (y1 , . . . , ym ), . . . , ft (y1 , . . . , ym )), то длялюбых функций g1 , . . . , gm ∈ N получаемf (g1 (x1 , x2 ), . . . , gm (x1 , x2 )) = f0 (f1 (g1 (x1 , x2 ), . . . , gm (x1 , x2 )), . . . ,ft (g1 (x1 , x2 ), . . . , gm (x1 , x2 ))) == f0 (h1 (x1 , x2 ), . . . , ht (x1 , x2 )) ∈ N,т.к. h1 (x1 , x2 ), . . . , ht (x1 , x2 ) ∈ N.Алгоритм распознавания полнотыЗамкнутые классыТеорема КузнецоваПредполные классыТеорема Кузнецова1.2) M(N) ∩ Pk2 = N.Если f (x1 , x2 ) ∈ M(N), то для x1 , x2 ∈ N получаемf (x1 , x2 ) ∈ N.Если f (x1 , x2 ) ∈ N и g1 , g2 ∈ N, тоf (g1 (x1 , x2 ), g2 (x1 , x2 )) ∈ [N] ∩ Pk2 , а значит по свойству n3 длямножества N, f (g1 (x1 , x2 ), g2 (x1 , x2 )) ∈ N. Т.е.
f (x1 , x2 ) ∈ M(N).1.3) M(N) 6= Pk по п. 1.2) и свойству n1 для множества N.Выберем из семейства замкнутых классовS(Pk ) = {M(N) | N ⊆ Pk2 , для N верны свойства n1, n2, n3}все максимальные (по включению) классы.Обозначим их как M1 , . .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
