В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 20
Текст из файла (страница 20)
Здесь существенно наличие s различных наборов, удовлетворяющих предикату. В противном случае, если предикат имеет следующий вид:(1 xi1 = xi2 = · · · = xil 0 6 l 6 s,P (x1 , . . . , xs ) =,0 иначе,то любая функция его сохраняет. Действительно, в этом случае из s наборов l должны быть равными. Но и значениялюбой функции на них будут равны. А поскольку на оставшихся s − l наборах функция может принимать произвольныезначения, любая функция такой предикат сохранит. С другой стороны, если потребовать, чтобы некоторые наборы были не просто равны друг другу, а еще и совпадали с вполне определенным фиксированным набором, то класс функций,сохраняющих такой предикат снова будет неполным.Лемма 2.1.3. Для любого предиката класс сохраняющих его функций замкнут.68ГЛАВА 2.
КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ Док-во. Так как тождественная функция сохраняет любой предикат, для доказательства замкнутости этого классадостаточно доказать, что суперпозиция сохраняющих предикат функций также сохраняет предикат. Для этого рассмотрим функцииf1 (exn ) , f2 (exn ) , . . . , fm (exn ) , f (z1 , . . .
, zm ) ∈ W (P)для некоторого предиката s-местного предиката P и докажем, что суперпозицияF (exn ) = f ( f1 (exn ) , . . . , fm (exn )) ∈ W (P) .e1 , αe2 , . . . , αe j, . . . , αes ) , сохраняющих предикат. Для каждого наПредложим этой суперпозиции любой набор наборов (αбора вычислим все fl .e1 )) F (αe1 , )e1 = α11 , α21 , . . . , αi1 , . . . , αn1 ( f1 (αe1 ) , f2 (αe1 ) , . . . , fi (αe1 ) , .
. . , fm (αα2222eeeeee2 , )α2 = α1 , α2 , . . . , αi , . . . , αn( f1 (α2 ) , f2 (α2 ) , . . . , fi (α2 ) , . . . , fm (α2 )) F (α.........jjjje j = α1 , α2 , . . . , αi , . . . , αne j ) , f2 (αe j ) , . . . , fi (αe j ) , . . . , fm (αe j )) F (αe j, )α( f1 (α.........es ) , f2 (αes ) , . . . , fi (αes ) , . . . , fm (αes )) F (αes , )es = (α1s , α2s , .
. . , αis , . . . , αns ) ( f1 (ααУпорядоченная s-ка наборов, составленных из значений функций, очевидно, удовлетворяет предикату. Следовательно,и s-ка, составленная из значений суперпозиции также удовлетворяет предикату.Предикаты могут описывать различные свойства функций.(Можно легко, определив соответствующий предикат,1 x1 6 x2 ,предложить замкнутый класс монотонных функций: P (x1 , x2 ) =Функцией, двойственной к f (x1 , .
. . , xn ),0 x1 > x2 .называется функций f ∗ (x1 , . . . , xn ) =∼ f (∼ x1 , . . . , ∼ xn ). Функция f называется самодвойственной, если f = f ∗ . Также( можно описать замкнутый класс самодвойственных функций, определив соответствующий предикат: P (x1 , x2 ) =1 x1 =∼ x2 ,Несмотря на то, что предикаты являются достаточно мощным средством описания замкнутых классов,0 x1 6=∼ x2 .позже будет показано, что используя предикаты, нельзя описать все замкнутые классы.Другими примерами замкнутых классов являются, например, класс линейных функций, класс функций, представи(1)мых полиномами Pol, класс функций, существенно зависящих не более, чем от одной переменной Pk . Эти классы неявляются полными системами при любых значения k, за исключением второго, который является полной системой прилюбом простом k.
Замыкание множества всех функций, зависящих от двух переменных, в свою очередь совпадает совсем Pk .В заключение пункта приведем еще один пример замкнутого класса T (E , s) , s = 1, k. Фиксируются произвольныеE , A0 , A1 , A2 , . . . , An ⊆ Ek , |Ai | = s, i = 0, n, E 6= Ek . Функция n переменных f (x1 , . .
. , xn ) ∈ T (E , s) тогда и только тогда,когда f (E ∪ A1 , E ∪ A2 , . . . , E ∪ An ) ∈ E ∪ A0 . Этот класс также является неполным в нетривиальных случаях.Полные системы, примеры полных систем. Пусть A — некоторое множество функций из Pk . Если [A ] = Pk , тоговорят, что A образует полную систему.
Минимальная (по удалению функций) полная система называется базисом.Полноту произвольной системы B будем доказывать сведением к заведомо полным системам, используя следующуюсхему:[A ] = Pk⇒ [B] = Pk .A ⊆ [B]Следующие системы являются полными в Pk при любом значении k:1. система Россера-Туркетта (теорема 2.1);2. {0, . . . , k − 1, j0 , . .
. , jk−1 , +, ·} (теорема 2.2);3. система Поста (теорема 2.3);4. {x, min (x, y)} (упражнение 1a);5. Vk (x, y) (следствие 2.1.1);6. {1, k − 1, x−̇y}.692.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИ Док-во. Сведем эту систему к системе Поста. Минимум получается тривиально: min (x, y) = x−̇ (x−̇y). Получим теперь все одноместные функции, в том числе и отрицание Поста. Реализуем для этого сначала все константы(k − 1 и 1 уже есть):k − 2 = (k − 1) −̇1, . . . , 3−̇1 = 2, 1−̇1 = 0.Получим теперь все ji :j0 (x) = 1−̇x; j1 (x) = ((2−̇x) −̇ j0 (x)) −̇ j0 (x) ; ji (x) = j0 (x−̇i) −̇ j0 (x−̇ (i − 1)) , i = 1, k − 1.Имея все ji можно получить систему функций(sx = i,gi,s (x) =k − 1 x 6= i.следующим образом:gi,s (x) = (· · · ((k − 1) −̇ ji (x))−̇ · · · )−̇ ji (x).|{z}k−s−1 разОтсюда произвольную одноместную функцию строим по правилуf (x) = min g0, f (0) (x) , . .
. , gl, f (l) (x) , . . . , gk−1, f (k−1) (x) .Таким образом можно построить и отрицание Поста, следовательно, система полна.7. { j0 (x) , x + y} при k > 3. Заметим, что при k = 2 эта же система не полна, так как она целиком содержится в класселинейных функций ( j0 (x) = x, x + y = x ⊕ y). Док-во. Действительно, x + x + · · · + x = 0 (mod k), далее j0 (0) = 1; x+1 = x, откуда получаются все константы|{z}k рази все ji (x). Отсюда можно получить систему функций fl,s = jl (x) + · · · + jl (x). Таким образом, можно получить|{z}s разпроизвольную одноместную функцию:k−1f (x) =∑ fi, f (i) (x) ,i=0в том числе и ∼ x, x. Получим теперь все двухместные функции. Для этого построим сначала вспомогательнуюсистему функций:(1 x = y = 0,j0,0 (x, y) = j2 ( j0 (x) + j0 (y)) =(2.6)0 иначе;(1 x = l, y = m,jl,m (x, y) = j0,0 (x + (k − l), y + (k − m)) =0 в противном случае.Теперь мы готовы построить все функции двух переменных.
Действительно,(s x = l, y = m,fl,m,s (x, y) = jl,m (x, y) + · · · + jl,m (x, y) =|{z}0 иначе.s разТогда любая двухместная функция может быть представлена в видеk−1 k−1f (x, y) =∑∑fl,m, f (l, m) (x, y) ,l=0 m=0в частности, функция Вебба. Следовательно, система 7 полна.Отметим, что условие k > 3 существенно используется на шаге 2.6, где необходимо наличие в Pk функции j0 (x),что, очевидно, выполняется тогда и только тогда, когда k > 3.70ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИТеорема о полноте системы Поста.Системой Поста называется система функций{x, max (x, y)} .Теорема 2.3. Система Поста полна в Pk .
Док-во. Сведем систему Поста к системе Россера-Туркетта. Для начала получим константы. Имея отрицание Поста, можно получить функцию x + i для любого i. Тогда справедливо равенствоmax (x, x + 1, x + 2, . . . , x + k − 1) = k − 1.Если есть одна константа и циклический сдвиг с шагом 1 (в нашем случае — отрицание Поста), то можно получить всеконстанты: k − 1 = 0, 0 = 1, .
. . , k − 3 = k − 2. Получим все Ji :01... k −2 k −1max (x + 1, . . . , x + k − 1) == Jk−1 (x) .k −1 k −2 ... k −1 k −2Аналогично, имея циклический сдвиг с шагом 1 и Jk−1 , можно получить уже все Ji по следующему правилу: Jk−2 (x) =Jk−1 (x) , . . . , J0 (x) = J1 (x).Таким образом, получены все константы, все Ji , а максимум входит в систему Поста. Осталось получить минимум.
Заметим, что в силу 2.1 достаточно реализовать над системой Поста отрицание Лукасевича. Реализуем системуфункций, над которой реализуются все функции одного переменного, в частности, и отрицание Лукасевича. Построимсистему функций(s x = r,fr,x (x) =.0 x 6= r.Действительно,max (J0 (x) , k − 2) + 2 = j0 (x)max (J0 (x) , k − 3) + 3···max (J0 (x) , k − s − 1) + s + 1···max (J0 (x) , 0)= f0,1 (x)= f0,2 (x)= f0,s (x)= f0,k−1 (x)Далее, для любого sfk−1,s (x) = f0,s (x)···f1,s (x) = f2,s (x)Таким образом, для любых 0 6 r, s 6 k − 1 построены fr,s (x) С помощью полученной системы, очевидно, можно построить любую одноместную функцию f (x):f (x) = max f0, f (0) (x) , f1, f (1) (x) , .
. . , fl, f (l) (x) , . . . , fk−1, f (k−1) (x) ,в том числе и отрицание Лукасевича:∼ x = max f0,k−1 (x) , f1,k−2 (x) , . . . , fl,k−l−1 (x) , . . . , fk−1,0 (x) .Тогда, согласно 2.1, min (x, y) =∼ max (∼ x, ∼ y), что завершает доказательство.Заметим, что эта система функций является полной при любом значении k.
Дело в том, что некоторые системыполны лишь при определенных значениях k, например, при k > 3 или при только при простых k.Функция Вебба. Функцией Вебба называется функцияmax (x, y) = max (x, y) + 1.Эта функция является аналогом шефферовой функции в P2 : ее замыкание совпадает со всем Pk :Следствие 2.1.1 (из теоремы 2.3).
Система {Vk (x, y)} полна в Pk . Док-во. Сведем эту систему к системе Поста. Отождествим переменные: Vk (x, x) = x + 1 = x. Затем применим k − 1раз полученное отрицание Поста к самой функции Вебба: Vk (x, y) − 1 = max (x, y).Следствие 2.1.2 (из следствия 2.1.1). Из любой полной системы в Pk можно выделить полную конечную подсистему. Док-во. Действительно, если система A полна, то функция Вебба реализуется формулой над A : Vk (x, y) =F ( fi1 , .
. . , fir ) , fi j ∈ A ∀ j = 1, r. Но тогда система функций { fi1 , . . . , fir } также полна.712.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИПримеры.1. Используя метод сведения к заведомо полным системам, доказать полноту в Pk следующих систем:(a) J0 (x) , J1 (x) , . . . , Jk−1 (x) , x2 , x−̇y . Решение. Отождествлением переменных в усеченной разности получаем константу 0: x−̇x = 0. Далее,подставляя на место переменной функции J0 (x) эту константу, получаем константу k − 1.
Подставляя k − 1 вx2 , получаем константу 1. Таким образом, в исходной системе содержится заведомо полная система 6.(b) {k − 1, x−̇y, x + y}. Решение. Суммируя k −1 раз константу k −1, получаем константу 1: k − 1 + · · · + k − 1 = 1. Таким образом,|{z}k−1в исходной системе содержится заведомо полная система 6.(c) {∼ x, x + 2, x−̇y}. Решение. Отождествлением переменных в усеченной разности получаем константу 0. Отрицание Лукасевича нуля равно константе k − 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
