О.Б. Лупанов - Курс лекций по математической логике (1109964), страница 4
Текст из файла (страница 4)
. . , σn ), поскольку Jσi (σi ) = k − 1 — максимально возможномузначению. Если же (α1 , . . . , αn ) 6= (σ1 , . . . , σn ) ⇒ ∃ i : σi 6= αi ⇒ Jσi (αi ) = 0 — минимально возможному значению, следовательно, Jσ1 (α1 )& . . . &Jσn (αn )&f (σ1 , . . . , σn ) = 0. Значит, формула верна и мы предъявили явноевыражение для произвольной функции над заданным множеством. Следствие 2.1. Для любого k существуют конечные полные системы.Утверждение 2.3.
Система {x + 1 (mod k), max(x1 , x2 )} — полная. Здесь и далее арифметические операции подразумеваются по модулю k (для краткости). Из функцииx + 1 многократным применениемможно получить функцию вида x + c, где c — константа. Далее, заметим, чтоmax x, x + 1, . . . , x + (k − 1) = k − 1. Из этой константы можно получить все остальные. Теперь рассмотримфункцию ϕt (x) := max x, x + 1, . . .
, x + (t − 1), x + (t + 1), . . . , x + (k − 1) + 1 и заметим, что(k − 1, x = k − 1 − t;ϕt (x) =то есть ϕt (x) = Jk−1−t (x).0,x 6= k − 1 − t,10Функцию min(x1 , x2 ) выразим так: min(x1 , x2 ) = N max (N (x1 ), N (x2 )) , применив аналог правила Де Моргана x1 x2 = x1 ∨ x2 . Покажем, как получить любую функцию одной переменной. Построим функции вида(β, x = αϕα,β (x) :=0, x 6= α.Такие функции можно выразить формулой ϕα,β (x) = max(Jα (x), k − (β + 1)) + β + 1.
Тогда любая функцияψ(x) ∈ Pk (1) выражается формулой ψ(x) = max(ϕ0,ψ(0) , ϕ1,ψ(1) , . . . , ϕk−1,ψ(k−1) ). Таким образом мы можемполучить N (x). Следовательно, наша система полная. Утверждение 2.4. Система {V (x) := max(x1 , x2 ) + 1} — полная.Функция V (x) является аналогом штриха Шеффера и называется функцией Вебба. В самом деле,V (x, x) = x + 1 ⇒ можно получить функцию вида x + c. Возьмем c = k − 1. Тогда V (x1 , x2 ) + k − 1 = max(x1 , x2 ),а полученные функции образуют базис Pk .
Теорема 2.5. Для любого k в Pk существует конечное число предполных классов A1 , . . . Aq . [F ] = Pk ⇔⇔ F * Ai ∀ i = 1, q. Доказательства этой теоремы в нашем курсе не будет.Пусть π(k) — количество предполных классов в Pk . Вот их количество при разных k:kπ(k)253184805667615237Справедлива асимптотическая формула:π(k) ⋍ δ(k) · k · 2Cmk−1,k−1m=,2δ(k) =(1, k ≡ 1 (mod 2);2, k ≡ 0 (mod 2).Рассмотрим алгоритм распознавания полноты в Pk . Пусть F = {f1 (x1 , . . .
, xn1 ), . . . , fs (x1 , . . . , xns ), . . . }. Возьмём переменныеx1 и x2 и построим последовательность множеств Πi по следующему правилу: Π1 = ∅; Πi+1 == Πi ∪ fj (A1 , . . . , Anj ) , где Ak ∈ {x1 , x2 } ∪ Πi . Тогда Π1 ⊆ Π2 ⊆ Π3 ⊆ · · · ⊆ Pk (2), но так как |Pk (2)| < ∞, тоначиная с некоторого момента Πt = Πt+1 = Πt+2 = . .
. . Очевидно, что [F ] = Pk ⇔ V (x1 , x2 ) ∈ Πt .2.3. Критерии полноты в Pk . Теорема Слупецкого – ЯблонскогоОпределение. f (x1 , . . . , xn ) ∈ Pk (n) — существенная функция, если она зависит не менее, чем от 2 переменных и принимает k значений.Теорема 2.6 (Слупецкого – Яблонского). Пусть F ⊇ Pk (1). [F ] = Pk ⇔ F содержит существеннуюфункцию. Усиление С. В. Яблонского: тот же самый вывод исходя из предположения о том, что F содержитвсе функции одной переменной, принимающие не более k − 1 значения. ⇒ Будет доказано для случая Слупецкого. Предположим, что F содержит все функции от одной переменной и ни одной существенной.
Тогда покажем, что F неполная. В самом деле, любая формула над Fимеет вид fi1 (fi2 (. . . fil (g(xl1 , xl2 , . . . )) . . . )), где fij ∈ Pk (1), а g — самая внешняя в этой формуле среди всехфункций более чем одной переменной. Но g не является существенной функцией по предположению, значит,она принимает не более k − 1 значения. Но тогда и вся формула не может принимать больше k − 1 значения,следовательно, любая функция над F принимает не более k − 1 значения.
Значит, F — неполная.⇐ Докажем для случая Яблонского, а значит и для случая Слупецкого. Пусть k > 3. Нам понадобитсяЛемма 2.7 (о трёх наборах). Пусть f ∈ Pk (n) существенно зависит не менее, чем от 2 переменных ипринимает не менее 3 значений. Тогда существуют 3 набораA = (α, α2 , .
. . , αn ),B = (β, α2 , . . . , αn ),C = (α, δ2 , . . . , δn ),такие, что f (A) 6= f (B) 6= f (C). Для определенности будем считать, что f существенно зависит от переменной x1 . Следовательно, найe = ε2 , причём ε1 6= ε2 . Рассмотримдутся наборы αe = (α, α2 , . . . , αn ) и βe = (β, α2 , . . . , αn ), такие что f (eα) = ε1 , f (β)множество наборов M = {(0, α2 , . . . , αn ), (1, α2 , .
. . , αn ), . . . , (k − 1, α2 , . . . , αn )}. Возможны 2 случая:1◦ Если среди f (M) имеется только 2 различных значения, то по условию существует набор δe = (δ, δ2 , . . . , δn ),e 6= ε1 , f (δ)e 6= ε2 . Тогда (δ, α2 , . . . , αn ) ∈ M, и f (δ, α2 , . . . , αn ) ∈ {ε1 , ε2 }. Пусть, для определенности,такой, что f (δ)11f (δ, α2 , .
. . , αn ) = ε1 . Тогда найдётся γ, такое что f (γ, α2 , . . . , αn ) = ε2 . Таким образом, искомые наборы —(δ, α2 , . . . , αn ),(γ, α2 , . . . , αn ),(δ, δ2 , . . . , δn ).2◦ Среди f (M) имеется не менее 3 различных значений. Среди функцийf (0, x2 , . . . , xn ), . . . , f (k − 1, x2 , . . . , xn )хотя бы одна — не константа, поскольку f существенно зависит не только от x1 . Пусть f (α, x2 , . .
. , xn ) — неконстанта. Тогда найдётся набор (δ2 , . . . , δn ), такой, что ε1 = f (α, δ2 , . . . , δn ) 6= f (α, α2 , . . . , αn ) = ε2 , но в силусущественной зависимости от x1 существует β : f (β, α2 , . . . , αn ) = ε3 . Определение. Квадрат — это четыре набора вида(α1 , . . . , αi−1 ,(α1 , . . . , αi−1 ,(α1 , .
. . , αi−1 ,(α1 , . . . , αi−1 ,α,γ,α,γ,αi+1 , . . . , αj−1 ,αi+1 , . . . , αj−1 ,αi+1 , . . . , αj−1 ,αi+1 , . . . , αj−1 ,β,β,δ,δ,αj+1 , . . . , αn ),αj+1 , . . . , αn ),αj+1 , . . . , αn ),αj+1 , . . . , αn ),где α 6= γ, β 6= δ.Лемма 2.8 (о квадрате). Пусть f существенно зависит не менее, чем от 2 переменных, и принимаетне менее 3 значений.
Тогда существует квадрат, на котором одно значение принимается ровно 1 раз. По лемме о трёх наборах существуют наборыσe1 = (α1 , α2 , . . . , αn ),σe2 = (δ1 , α2 , . . . , αn ),σe3 = (δ1 , δ2 , . . . , δn ),причем ε1 6= ε2 6= ε3 . Построим цепочку квадратовα1 α2 δ1 α2 α1 δ2 δ1 δ2 α1 δ2 δ1 δ2. . . . . .δ1 δ2α3α3α3α3δ3δ3...δ3α4α4α4α4α4α4...δ4f (eσ1 ) = ε1 ,f (eσ2 ) = ε2 ,f (eσ3 ) = ε3 ,........................αnαn αn αn αn αn . .
.δnЗдесь первый квадрат — это строки [1 . . . 4], второй — [3 . . . 6], третий — [5 . . . 8], и т. д. На первых двух наборахзначения функции равны соответственно ε1 и ε2 , а на последнем — ε3 . Значит, рано или поздно в последовательности квадратов появится квадрат, на котором одно из значений ε1 , ε2 , ε3 принимается ровно 1 раз. Приступим к доказательству основной теоремы. Сначала построим все функции, принимающие ровно 2значения, а затем по индукции из всех функций, принимающих не более l значений, получим все функции, принимающие l + 1 значение. По условию, у нас есть существенная функция f .
Поскольку k > 3, она удовлетворяетусловиям леммы о квадрате. Рассмотрим наборы, образующие квадрат, на котором какое-то значение, скажем,ε1 , принимается ровно 1 раз, т. е. ε1 ∈/ {ε2 , ε3 , ε4 }:f (α βf (γ βf (α δf (γ δα3α3α3α3............αn ) = ε1αn ) = ε2αn ) = ε3αn ) = ε4Введем обозначение ϕ(x1 , x2 ) := f (x1 , x2 , α3 , . . . , αn ). Теперь рассмотрим функции:(((0, x = ε1α, x = 0;β, x = 0;ψ(x) :=λ1 (x) :=λ2 (x) :=ω(x1 , x2 ) := ψ ϕ λ1 (x1 ), λ2 (x2 ) .1; x 6= ε1 ,γ, x 6= 0,δ, x 6= 0,Все эти функции у нас есть, поскольку они принимают не более 2 (а значит, и не более k − 1) значений.Заметим, что на наборах из нулей и единиц функция ω ведёт себя так же, как обычная дизъюнкция, поэтому12Wобозначим её через e (x1 , x2 ). Кроме того, у нас есть функция jα (x) :=(1, x = α0, x 6= α,так как она принимаетe 1 , x2 ) := j0 ω j0 (x), j0 (x2 ) , которая на наборах из нулей и едиництолько 2 значения.
Построим функцию &(xWe позволяют соорудить аналог СДНФ и получить всеведет себя как обычная конъюнкция. Функции e и &функции, которые на наборах из 0 и 1 принимают значения 0 и 1, т. е. все функции из P2 ⊂ Pk . Теперь спомощью этих функций получим функцию, которая принимает любые 2 значения ((а не только 0 и 1). Пустьα, x = 0;h(x1 , . .
. , xm ) принимает только значения α и β. По условию у нас есть µ(x) :=Но у нас естьβ, x 6= 0.(0, h(x1 , . . . , xm ) = α;и g(x1 , . . . , xm ) :=тогда h(x1 , . . . , xm ) = µ g(x1 , . . . , xm ) . Таким образом, мы умеем1, h(x1 , . . . , xm ) = β,делать функции, принимающие любые 2 значения.Теперь из функций, принимающих не более l − 1 значения, получим функции, принимающие l значений.Пусть g(x1 , . .
. , xm ) принимает значения {ε1 , . . . , εl }. Из леммы о трех наборах следует существование такойсовокупности наборов, чтоf (αα2 . . . αn ) = ε1f (βα2 . . . αn ) = ε2f (αδ2. . . δn ) = ε 3(1)f (β41 β42 . . . β4n ) = ε4...f (βl1 βl2 . . . βln ) = εlВ каждом столбце этой матрицы наборов стоит не более l − 1 различных значений. Значения ε1 , ε2 , ε3 фигурируют в лемме о трех наборах и все различны. Функция f — существенная и потому принимает k значений.Следовательно, значения ε4 , . . . , εl мы можем выбрать так, чтобы все εi были различны.
Покажем, как можно получить произвольную функцию, принимающую эти же l значений. Нам нужно получить функцию g(x1 , . . . , xm )такую, что Im g ⊆ {ε1 , . . . , εl }. Каждому набору σe = (σ1 , . . . , σm ) сопоставим число (индекс) i(eσ ) ∈ {1, 2, . . . , l} :g(eσ ) = εi(eσ) . Построим n функций hj (eσ ) : hj (x1 , . . . , xm ) = βi(eσ )j , где элемент βij соответствует ij-тому элементуприведённой выше матрицы наборов. Функции hj у нас есть по предположению индукции, т.к. принимаютнеболее l − 1 значения. Тогда функция g выражается формулой g = f (h1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
