В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 23
Текст из файла (страница 23)
Если она в нем есть, то мы свели систему к функции Вебба, следовательно, система полна. Еслиже функция Вебба не содержится в последнем уникальном классе, то система не полна в силу следующих рассуждений. Выделяем из замыкания исходной системы функций A функции, зависящие только от x1 , x2 — множество [A ]x1 ,x2 .Очевидно, [A ]x1 ,x2 = Nr∗ . В то же время, если бы A была бы полна, то она содержала бы функцию Вебба Vk (x1 , x2 ).Следовательно, в этом случае система не полна.Теорема Кузнецова о функциональной полноте. В этом пункте мы покажем существование системы 2.5 в Pk длялюбого k.
Рассмотрим N — некоторое множество функций k-значной логики, зависящих от переменных y1 , . . . , ym . Дляудобства будем считать, что сами переменные в это множество включены: yi = gmi (y1 , . . . , ym ) ∈ N.Определение. Функция k-значной логики f (x1 , . . . , xn ) сохраняет N, если для любых h1 , . . . , hn ∈ N суперпозицияf (h1 , . . . , hn ) ∈ N. Множество функций M ссохраняет N, если все функции, сохраняющие N, заключены в M.Пример .
Пусть m = 1, N : f (∼ y) =∼ f (y). Множество N содержит, например, тождественную функцию, само отрицание Лукасевича. Множество функций, сохраняющих данное N, является множеством всех самодвойственных функций:M :∼ g (∼ x1 , . . . , ∼ xn ) = g (x1 , . . . , xn ). Действительно, для любых h1 (y) , . . .
, hn (y) ∈ N ⇒ F (y) = f (h1 (y) , . . . , hn (y)) =f (∼ h1 (∼ y) , . . . , ∼ hn (∼ y)) ∈ N, то есть F (∼ y) =∼ F (y) ⇔∼ f (∼ x1 , . . . , ∼ xn ) = f (x1 , . . . , xn ). Заметим, что сами функции f (y) входят в M.Лемма 2.2.1. Пусть N — множество функций, зависящих от переменных y1 , . . . , ym , содержащее тождественные функции gmi , а M — множество функций, сохраняющих N. Тогда M замкнуто. Док-во. Так как тождественные функции сохраняют N, достаточно доказать, что суперпозиция сохраняющих Nфункций также сохраняет N. Пусть f (z1 , .
. . , zl ) , fi (x1 , . . . , xn ) ∈ M, i = 1, l, то есть для любых h1 , . . . , hn ∈ N выполняется fi (h1 , . . . , hn ) ∈ N. Рассмотрим суперпозицию F (x1 , . . . , xn ) = f ( f1 , . . . , fl ). Для любых h1 , . . . , hn ∈ N ⇒ Hi =fi (h1 , . . . , hn ) ∈ N для всех i = 1, l. Но тогда и F (h1 , . . . , hn ) = f (H1 , . . . , Hl ) ∈ N.Лемма 2.2.2. Пусть N — множество функций, зависящих от переменных y1 , . . . , ym , содержащее тождественные функции gmi и [N]y1 ,...,ym = N. Тогда для M, сохраняющего N, выполнено My1 ,...,ym = N.78ГЛАВА 2.
КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ Док-во. Рассмотрим любую функцию f (y1 , . . . , ym ) ∈ N. Для любых h1 , . . . , hn ∈ N по условию теоремыf (h1 , . . . , hm ) ∈ [N]y1 ,...,ym = N ⇒ f ∈ M, и при этом она зависит от y1 , . . . , ym , то есть f ∈ My1 ,...,ym . Таким образом,N ⊆ My1 ,...,ym .mОбратно: для любой функции f ∈ My1 ,...,ym ⇒ f (y1 , . . . , ym ) = f (gm1 , .
. . , gm ) ∈ N в силу замкнутости N по переменнымy1 , . . . , ym . Следовательно, My1 ,...,ym ⊆ N.Из доказанного немедленно вытекает, что N = My1 ,...,ym .Теорема 2.5 (А.В. Кузнецов). Для любого k > 2 существует система, называемая критериальной, M1 , . . . , Msзамкнутых классов, попарно не содержащих друг друга, таких, что любой класс функций A ⊆ Pk полон тогда и только тогда, когда A целиком не лежит ни в одном из классов M1 , . . .
, Ms . Док-во. Построим эти классы. Рассмотрим множество всех функций Pkx1 ,x2 , зависящих от переменных x1 и x2 —2k2всего их kk . Это множество имеет 2k подмножеств, из которых мы выбираем все подмножества Ni , i = 1, s0 , удовлетворяющие следующим трем условиям:1.
Ni не пусто и не совпадает с Pkx1 ,x2 для любого i = 1, s0 ,2. Ni содержит тождественные функции g21 (x1 , x2 ) и g22 (x1 , x2 ) для любого i = 1, s0 и3. Ni замкнуты по переменным x1 , x2 для любого i = 1, s0 .Для каждого Ni строится замкнутый класс M0i функций, сохраняющих Ni . Всего M0i — конечное число.
Упорядочим ихпо включению. Как легко проверить, это будет являться частичным порядком. В построенном частично упорядоченноммножестве возьмем систему максимальных элементов M1 , . . . , Ms (s < s0 ), заметив, что Mi 6= Pk ∀i = 1, s. Последнеевытекает из того, что если бы какой-то из них совпадал со всем Pk , то он в силу замкнутости содержал бы функциюВебба переменных x1 , x2 . Но тогда в силу замкнутости соответствующего Nl по лемме 2.2.2, Nl также совпадало бы совсем Pk , что противоречит построению.
Далее, любой класс M0i содержится в одном из классов этой системы. Очевидно,что если A ⊆ Mi , то A не полна: [A ] ⊆ Mi Pk .пусть A не Обратно, лежит ни в одном из классов Mi , i = 1, s. Тогда рассмотрим систему M =A ∪ g21 (x1 , x2 ) , g22 (x1 , x2 ) ⊇ A . Очевидно, что A и M полны или не полны одновременно. Предположим, что Mнеполная. Тогда в Mx1 ,x2 не содержится Vk (x1 , x2 ). По лемме 2.2.2 существует такое j, что Mx1 ,x2 = N j . Но тогдаM ⊆ M0j ⊆ Mk , где M0j — класс функций, сохраняющих N j , что противоречит тому, что A не лежит ни в одном изклассов Mi .Можно тривиально оценить снизу число функций критериальной системы числом функций, сохраняющих множества: s > 2k − 2.2.3Существенные функцииОпределение.
Функция k-значной логики f называется существенной, если она существенно зависит не менее, чемот двух переменных.Леммы о существенных функциях.Лемма 2.3.1 (о трех наборах). Пусть функция f (x1 , . . . , xn ) — существенная (x1 — ее существенная переменная) и принимает l > 3 различных значений.
Тогда существует три набора вида(α, α2 , . . . , αn ) ,(β , α2 , . . . , αn ) ,(α, γ2 , . . . , γn ) ,на которых функция принимает три различных значения. Док-во. По предположению теоремы x1 — существенная переменная функции f . Это означает, что существуюттакие константы α1 , . . . , αn , что f (x1 , α1 , . . . , αn ) 6≡ const. Рассмотрим цепочку(1, α2 , . .` . , αn )2 ,` . . .
, αn )`P` P (k − 1, αPPPPPP`PP`PP` ` (0, α2 , . . . , αn )`(α, γ2 , . . . , γn )Возможны два случая:792.3. СУЩЕСТВЕННЫЕ ФУНКЦИИ1. На этой цепочке функция принимает не все l значений. Тогда существует набор (α, γ2 , . . . , γn ), на котором функцияпринимает оставшееся значение. Берем также проекцию этого набора на цепь (α, γ2 , . . . , γn ) и какой-то другойнабор с цепи (β , α2 , .
. . , αn ). На полученных трех наборах функция принимает три разных значения.2. На цепи принимаются все значения. Но у f есть по крайней мере еще одна существенная переменная, то естьсуществуют такие α, γ2 , . . . , γn , что f (α, α2 , . . . , αn ) и f (α, γ2 , . . . , γn ) различны.
Кроме этих двух значений беремеще одно с цепи.Лемма 2.3.2 (Основная). Пусть f — существенная функция, принимающая l > 3 различных значений, и x1— ее существенная переменная. Тогда существуют множества Qi ⊆ Ek , i = 1, n : |Qi | 6 l − 1 такие, что наQ1 × Q2 × · · · × Qn функция f принимает все свои l значений.
Док-во. Дополним три набора из леммы 2.3.1 l − 3-мя наборами так, чтобы получилось l наборов, на которых функция принимает все свои значения:(α ,α2 , . . . ,αn )(β ,α2 , . . . ,αn )(α ,γ2 ,...,γn )α14 ,α24 , . . . ,αn4. . . . . . . . . . . . .
. . . . . . .α1l−3 , α2l−3 , . . . , αnl−3Q1Q2...QnМножество первых разрядов обозначим Q1 , его мощность благодаря равенству первых разрядов первого и третьегонаборов не превосходит l − 1; множество i-ых разрядов обозначим Qi для i = 2, n, его мощность благодаря равенствуi-ых разрядов для i = 2, n также не превзойдет l − 1.
По построению наборов, на их декартовом произведении функцияпримет все свои значения.Лемма 2.3.3 (о квадрате). Пусть f — существенная функция, принимающая l > 3 различных значений, и x1— ее существенная переменная. Тогда существует четверка наборов, называемая квадратом, видаα1 , .
. . , αi−1 , α, αi+1 , . . . , α j−1 , γ, α j+1 , . . . , αn α1 , . . . , αi−1 , α, αi+1 , . . . , α j−1 , δ , α j+1 , . . . , αn,α1 , . . . , αi−1 , β , αi+1 , . . . , α j−1 , γ, α j+1 , . . . , αn α1 , . . . , αi−1 , β , αi+1 , . . . , α j−1 , δ , α j+1 , . . . , αnна вершинах которого функция либо принимает не менее трех различных значений, либо принимает двазначения, но одно из них только на одной вершине.
Иными словами, одна из вершин квадрата являетсяуникальной. Док-во. Согласно лемме 2.3.1 найдутся три набора указанного вида такие, что функция на них принимает три различных значения a, b и c. Два набора находятся в одной гиперплоскости, а третий — в другой, но является проекциейпервого. Рассмотрим первый квадрат, две вершины которого равны соответственно a и b. Если среди оставшихся двухвершин есть одна, значение на которой отлично от значений на первых двух или значения на них равны, то лемма доказана.x = β (β , α2 , . . .` , αn ) `(β` , γ2 , .
. . , γn ) !!!a!` ! \!` ! \!` ! \` a(b)a(b)b(a)b(a)``!!!`x=α` ! \!` ! \!` !b!\` c1(α, γ2 , .. . , γn ) (α, α2 , . . . , αn )В противном случае, если на одной вершине значение равно a, а на другой — b, то перейдем к рассмотрению следующегоквадрата. Для него повторим все эти рассуждения. Если мы таким образом дойдем до последнего квадрата, что будетозначать, что во всех предыдущих квадратах на одних двух вершинах принимается значение a, а на других двух — b, тоутверждение леммы выполнится потому, что в последнем квадрате будет три различных значения.80ГЛАВА 2.
КОНЕЧНОЗНАЧНЫЕ ЛОГИКИТеоремы о существенных функциях.Теорема 2.6 (С.В. Яблонский). Система функций, содержащая все одноместные функции, принимающиене более k − 1 различных значений (CSk ) полна тогда и только тогда, когда она содержит существеннуюфункцию, принимающую все k значений.
Док-во. Необходимость доказывается от противного. Возможны два варианта.1. Система вообще не содержит существенных функций. В этом случае она, очевидно, не полна, так как содержится(1)в классе Pk .2. Система содержит существенную функцию, но она принимает (не ограничивая общности) k − 1 значение. Но тогда подстановкой на места переменных этой функции других функций системы нельзя получить существеннуюфункцию двух переменных, принимающую все k значений, например, x + y.Таким образом, в этом случае система не полна.Достаточность. Пусть система содержит CSk и существенную функцию, принимающую все k значений. В этом случае, очевидно, все константы принадлежат системе. Докажем достаточность системы по индукции.Базис индукции. Построим все функции, принимающие не более двух значений. Для функции f справедлива лемма 2.3.3, то есть существует квадрат, на одной из вершин которого принимается уникальное значение a:f α1 , .
. . , αi−1 , x, αi+1 , . . . , α j−1 , y, α j+1 , . . . , αn равно a при x = α и y = β . Рассмотрим функции, существенно зависящие от одной переменной, и принимающие не более k − 1 значения, заведомо содержащиеся в исходной системе(((α x = 0,β y = 0,0 z = a,t1 (x) =t2 (y) =t (z) =β x 6= 0,α y 6= 0,1 z 6= a.и возьмем третью от f , на местах переменных x и y у которой стоят первые две:t f α1 , . . . , αi−1 ,t1 (x) , αi+1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
