В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 25
Текст из файла (страница 25)
Таким образом, получено, что при простых значениях k любая функция представима полиномом.Пусть теперь k — составное. Докажем результат от противного: пусть j0 (x) = a0 + a1 x + · · · + as xs . Тогда j0 (0) = 1 ⇒a0 = 1. Пусть 0 6= k1 | k ⇒ j0 (k1 ) = 1 + a1 k1 + · · · + as k1s = 0 ⇒ a1 k1 + · · · + as k1s = k − 1 ⇒ k1 | k − 1, чего не может бытьпри k > 3. Объединить два полученных выше результата можно в следующей теореме.Теорема 2.11. Класс функций, представимых полиномами полон тогда и только тогда, когда k — простое.Теоремы о замкнутых классах в Pk при k > 3.
В P2 любой замкнутый класс имеет конечный базис, следовательно,замкнутых классов в P2 — счетное множество. В Pk при k > 3 ситуация совершенно другая.Теорема 2.12 (Янов). В Pk при k > 3 существует замкнутый класс, не имеющий базиса. Док-во. Построим этот класс. Определим последовательность функций следующим образом: f0 = 0, для i = 1, ∞(1 x1 = x2 = · · · = xi = 2,fi = fi (x1 , . . . , xi ) =0 иначе.F = { f0 , f1 , . . . , fm , . . .}. Рассмотрим все функции, получаемые из этих переименованием переменных без отождествления, это множество обозначим M .
Докажем по индукции, что класс M замкнут. Для i = 1 это очевидно. Пусть теперьэто верно для i 6 n, докажем для i = n + 1. Рассмотрим f (A1 , . . . , Ai ). Если среди A1 , . . . , Ai есть хотя бы одна формула,то функция является тождественным нулем и принадлежит M . Если же все A j различные переменные, то функцияполучается из некоторой функции F переименованием переменных без отождествления, то есть принадлежит M .Предположим, что у M существует базис. Тогда в нем существует функция f y1 , . .
. , yn0 , имеющая наименьшеечисло существенных переменных n0 среди всех функций базиса. Тогда возможны два различных случая.84ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ1. Существует еще одна функция f (u1 , . . . , un ), зависящая от n > n0 существенных переменных. Тогда первую функцию можно получить из этой переименованием переменных с отождествлением.2. В базисе одна функция.
Если это константа 0, то это не базис, следовательно, она должна иметь существенные переменные. В этом случае любая суперпозиция f (A1 , . . . , An ), содержащая формулы на местах переменных,реализует тождественный ноль, а не содержащая формулы, зависит не более, чем от n переменных, то есть суперпозициями нельзя получить функцию fm , существенно зависящую от m > n переменных.Теорема 2.13 (Мучник). В Pk при k > 3 существует замкнутый класс со счетным базисом. Док-во. Построим этот класс.
Пусть F = { f2 , f3 , . . . , fi , . . .}, где(1 x1 = x2 = · · · = x j−1 = x j+1 = · · · = xi = 2, x j = 1, j = 1, ifi (x1 , . . . , xi ) =0 иначе.Рассмотрим замыкание M = [F ]. Докажем, что F — базис. Действительно, F полна в M . Покажем, что из F нельзяудалить ни одну из функций. Пусть для m 6= n существует fn (x1 , . . . , xn ) = fm (A1 , . . .
, Am ). Возможны три случая:1. Среди Ai есть хотя бы две формулы. Тогда они обе принимают значения 0 и 1 иfm (A1 , . . . , Am ) ≡ 0), но fn (x1 , . . . , xn ) 6≡ 0. Противоречие.2. Среди Ai есть ровно одна формула. Тогда при m > 2 существует место, где есть символ переменной xl , 1 6 l 6 n.Тогда на наборе xl = 1, xi = 2 (l 6= l) fn = 1, fm = 0. Противоречие.3. Все Ai суть символы переменных. Тогда для m > n ввиду существенности каждой переменной fn неизбежны повторы, и есть два места с xl . На наборе xl = 1, xi = 2 (i 6= l) fn = 1, fm = 0.
Противоречие.Построенный в теореме 2.13 замкнутый класс не имеет конечных базисов. Из хода доказательства видно, что есливзять бесконечную систему F 0 = { fi1 , fi2 , . . . , fis , . . .}, то замкнутый класс M 0 = [F 0 ] будет иметь также счетный базис F 0 , то есть разные подпоследовательности F порождают разные замкнутые классы. Таким образом, справедливоследующее утверждение.Следствие 2.4.1 (из теоремы 2.13).
Число замкнутых классов в Pk при k > 3 равно континуум.Примеры.1. Разложить в полином по модулю k функцию f из Pk :(a) f = 2x−̇x2 , k = 50 1 2 2 4 Решение. Эта функция задает подстановку. Представим ее во второй форме: 2x−̇x2 =0 1 0 0 2j1 (x) + 2 j4 (x) = j0 (x − 1) + 2 j0 (x − 4) = j0 (x − 1) + 2 j0 (x + 1) = 1 − (x − 1)4 + 2 − 2 (x − 4)4 = 3 − x4 + 4x3 −6x2 + 4x − 1 − 2x4 − 8x3 − 12x2 − 8x − 2 = 2x4 + x3 + 2x2 + x.(b) f = max (2x−̇y, x · y) , k = 3 Решение. Таблица этой функции имеет следующий вид:yHx H012002110122021Теперь легко видеть, что эта функция просто равна xy + 2x j0 (y) = xy + 2x 1 − y2 = xy2 + xy + 2x.(c) f = min x2 , y , k = 3852.4. ОСОБЕННОСТИ МНОГОЗНАЧНЫХ ЛОГИК Решение. Таблица этой функции имеет следующий вид:yHx H012000010112011Теперь легко видеть, что эта функция просто равна x2 y2 .2.
Выяснить, представима ли полиномом по модулю k функция f из Pk , если:(a) f = 2 (J1 (x) + J4 (x)) , k = 60 1 2 2 Решение. Эта функция задает подстановку0 4 0 0лю 6 с тем, чтобы ограничить степень искомого полинома:xx0x1x2x3010001111121242313335. Выпишем табличку степеней по моду0444144451515Легко видеть, что начиная с кубов все степени повторяют стоящие на две строки выше. Следовательно,достаточно ограничиться квадратами. Поскольку функция сохраняет ноль, искать ее полином будем в видеax2 + bx.
Решим соответствующую систему линейных уравнений:123451434014000 ∼ 04000120024410 ∼004124⇒4a = 2, b = 2;a = 5, b = 5.Таким образом, f (x) = 2x2 + 2x = 5x2 + 5x при k = 6.(b) f = (max (x, y) − min (x, y))2 , k = 4 Решение. Если x > y, то выражение в скобках равно x − y, иначе оно равно y − x, но в любом случаеего квадрат равен (x − y)2 = x2 − 2xy + y2 = x2 + (k − 2) xy + y2 , при k = 4: x2 + 2xy + y2 . Заметим, что даннаяфункция представима полиномом при любом значении k.(c) f = 3 j0 (x) , k = 60 1 2 2 4 5 Решение. Эта функция задает подстановку.
Как было показано в примере 2a,0 4 0 0 4 0достаточно ограничиться квадратами. Также, поскольку f (0) = 3, полином имеет смысл искать в виде3 + ax + bx2 . Решим соответствующую систему линейных уравнений:123451434031000 ∼ 000001200230303Третья строчка показывает, что решений нет.3. Доказать, что приводимые ниже системы полны в Pk тогда и только тогда, когда k — простое число:(a) {1, x + y + x · z} Решение.
Очевидно, что при составных k система не полна, так как состоит из полиномов. При k = 2система сохраняет единицу, так что в дальнейшем k — простое и нечетное. Имеем 1 + y + 1 · 1 = y +2, x + 2 + · · · + 2 = x + 1. Из этого можно получить все константы, x + y + x · 0 = x + y, x + 0 + x · y =| {z }p+12x (y + 1) , x (y + (k − 1) + 1) = xz. Получен базис системы полиномов — умножение, сложение и константа1, следовательно, при простых k система полна.86ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ(b)x − y + 1, x2 − y, x · y2 Решение. Поскольку все представленные в системе функции — полиномы, она не полна при составныхзначениях k.
При k = 2 система полна, так как первая функция не сохраняет ноль, не самодвойственная и немонотонная, вторая не сохраняет единицу, а третья нелинейная, так что в дальнейшем k простое и нечетное.Имеем x − x + 1 ≡ 1, 12 − 1 = 0, x − 0 + 1 = x + 1, следовательно, есть все константы и все функции видаx + i. Теперь получаем функцию x + (k − 1) y + 1 + · · · + (k − 1) y + 1 = x + y + k − 1, откуда x + y + 1 + k − 1 =|{z}k−1x + y. Далее, 1 · x2 = x2 , (x + y)2 − x2 + y2 = 2xy, 2xy + · · · + 2xy = xy.
Получен базис системы полиномов —|{z}k+12умножение, сложение и константа 1, следовательно, при простых k система полна.(c) {1 + x1 − x2 + x1 · x2 · · · xk } Решение. Поскольку все представленные в системе функции — полиномы, она не полна при составныхзначениях k. В дальнейшем k простое. Имеем, 1+x −x +xk = x +1, 1+x −x +x ·xx · · · (x + (k − 1)) ≡ 0, 1+x1 −x2 + x1 x2 · 0 · · · 0 = 1 + x1 − x2 , 1 + x1 − (x2 + 1) = x1 − x2 , x1 − x2 − · · · − x2 = x1 + x2 , 1 + x1 − 1 + x1 · 1 · · · 1 · x2 =|{z}k−1x1 + x1 x2 , x1 + x1 x2 − x1 = x1 x2 . Получен базис системы полиномов — умножение, сложение и константа 1,следовательно, при простых k система полна.Упражнения.1. Разложить в полином по модулю k функцию f из Pk :(a) f = min x2 , x3 , k = 5;(b) f = max 2x−̇1, x2 , k = 5;(c) f = 3x−̇ (x−̇2x) , k = 7;(d) f = max (x−̇1)2 , x3 , k = 7;(e) f = x−̇y, k = 3;(f) f = Jk−2 (x) , k — произвольное простое число;(g) f = j2 x − x2 , k — произвольное простое число.2.
Выяснить, представима ли полиномом по модулю k функция f из Pk , если:(a) f = 3x−̇2x2 , k = 4;(b) f = (x−̇y) −̇y, k = 4.3. Доказать, что приводимые ниже системы полны в Pk тогда и только тогда, когда k — простое число:(a) x − 1, x + y, x2 · y ;(b) {k − 1, x · y + x − y + z};(c) k − 2, x + 2y, x · y2 ;(d) ∼ x, x − y, x2 · y ;(e) {x − 2, x + 2y + 1, x · y − x − y};(f) 1, 2x + y, x · y2 − x + y ;(g) x + y + 1, x · y − x2 ;(h) {x − 2y, x · y + x + 1}..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
