В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

. . , α j−1 ,t2 (y) , α j+1 , . . . , αn= ∨0,1 (x, y) .Эту функцию назовем дизъюнкцией x и y. По аналогии построим конъюнкцию:&0,1 (x, y) = j0 (∨0,1 ( j0 (x) , j0 (y))) .Для функции произвольной f (exn ) 6≡ const, принимающей только значения 0 и 1, построим формулу, ее реализующую:f (exn ) =_jα1 (x1 ) · jα2 (x2 ) · · · jαn (xn ) .(α1 ,...,αn )f (α1 ,...,αn )=1Теперь можно реализовать и любую функцию,принимающую любые два значения: если f (exn ) принимает два значения(σ1 x = 0,∈ CSk , можно реализовать f формулойσ1 и σ2 , то, используя функцию h (x) =σ2 x 6= 0h_(α1 ,...,αn )f (α1 ,...,αn )=1jα1 (x1 ) · jα2 (x2 ) · · · jαn (xn ).Предположение индукции. Пусть реализованы все f ∈ Pk , принимающие не более l − 1 различных значений.Индуктивный переход. Реализуем произвольную функцию g (eym ), принимающую l различных значений τ1 , .

. . , τl .Разделим два случая.1. l − 1 6 k − 2. Реализуем существенную функцию, принимающую l 6 k − 1 различных значений. По основной лемменайдутся наборы (α, α2 , . . . , αn ) βe1 δ13(β , α2 , . . . , αn ) βe2 δ2(α, γ2 , . . . , γn ) βe3 δ3l, eβ4 δ4 β14 , β24 , . . . , βn4.................l −3. . . .

. . . . . . . βel δl812.3. СУЩЕСТВЕННЫЕ ФУНКЦИИна которых функция f принимает l различных значений. Далее si (eym ) — функции, принимающие l − 1 значение.y1 , . . . , ym............s1 (eym ) s2 (eym ) . . . sn (eym )βe1βe2...eβlgτ1τ2...τlf (s1 , . . . , sn )δ1δ2...n ( f (es))τ1τ2...δlτleТаким образом, во всех столбцах, составленных из i-х разрядовне более, чем l − 1 зна наборов βi , находитсяδ1 δ2 .

. . δlчение. Применим к различным значениям δi функцию n (x) =, принадлежащую классу CSk ,τ1 τ2 . . . τlследовательно, находящуюся в исходной системе.2. l = k. В этом случае последнего шага не нужно:y1 , . . . , ym............g01...k−1s1 (eym ) s2 (eym ) . . . sn (eym )eβ1βe2...eβlf (s1 , .

. . , sn )01....k−1Действительно, если все значения различны, и принадлежат множеству {0, 1, . . . , k − 1}, то каждое из них принимается ровно по одному разу, и все наборы βei можно упорядочить так, чтобы получить желаемый порядок впоследнем столбце.В качестве следствия теоремы 2.6 можно привести более слабый критерий полноты:Теорема 2.7 (И. Слупецкий). Система функций, содержащая все одноместные функции) полна тогда итолько тогда, когда она содержит существенную функцию, принимающую все k значений.Обозначим через hi, j (x) перестановку значений i и j. Очевидно, h0,1 (x) = x + j0 (x) + J1 (x). Легко проверить справедливость следующего утверждения:(1)Теорема 2.8 (С.

Пикар). Следующие системы полны в Pk :1. {x, h0,1 (x) , x + j0 (x)},2. h0,1 (x) , h0,2 (x) , . . . , h0,k−1 (x) , x + j0 (x) .Теорема 2.9 (критерий шефферовости). Функция f является шефферовой тогда и только тогда, когда изнее можно получить все функции от одной переменной, принимающие не более k − 1 значения (класс CSk ). Док-во. Необходимость в данном случае очевидна. Покажем достаточность.

Поскольку все константы принадлежат CSk , функция принимает все k значений. Докажем, что она существенная от противного: пусть она не являетсясущественной. Возможны два случая:1. у f вообще нет существенных переменных, следовательно, она константа, что невозможно;2. у f ровно одна существенная переменная, следовательно, она является перестановкой, то есть f ∈ Sk ⇒ [ f ] ⊆ Skи из нее нельзя получить константы.Таким образом, f существенная и по теореме 2.6 система { f } полна.Примеры. Используя критерий Слупецкого, доказать полноту в Pk нижеприводимых систем:1. k − 1, x − y + 2, x2 −̇y Решение.

Очевидно, что x − y + 2 — существенная функция, принимающая все k значений. Далее,(k − 1)2 −̇ (k − 1) = 0, (k − 1)2 −̇0 = 1, x − 1 + 2 = x + 1 = x, 0 + 1 = 1, 12 − x = j0 (x). Также есть все константыи все ji , x − (y + 2) + 2 = x − y, x − y − · · · − y = x + y ⇒ j1 (x) + · · · + j1 (x) = J1 (x) , h0,1 (x) = x + j0 (x) + J1 (x), так| {z }|{z}k−1k−1же имеется x + j0 (x).

Следовательно, исходная система содержит систему Софи Пикар 1 и является полной потеореме 2.7.82ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ2. {(1−̇x) · y + x · (1−̇y)} Решение. Обозначим f (x, y) = (1−̇x) · y + x · (1−̇y).f (x, x) = j0 (x) , f (x, j0 (x)) = x, j0 ( f ( j0 (x) , x)) = 0,f (0, x) = x + j0 (x) , f ( j1 (x) , x) = h0,1 (x) ,получена система Софи Пикар 1. В то же время функция существенно зависит от обеих переменных и принимаетвсе k значений, следовательно, является шефферовой по теореме 2.7.3.j2 (x) , x + y2 , x · y + 1 Решение.

Функция x · y + 1 — существенная и принимает все k значений. Далее, j2 ( j2 (x)) = 0, 0 · 0 + 1 =1, x + 12 = x, откуда можно получить все ji (x), x + j02 (x) = x + j0 (x) , x + j12 (x) + · · · + j12 (x) + j0 (x) = h0,1 (x). Сле|{z}k−1довательно, исходная система содержит систему Софи Пикар 1 и является полной по теореме 2.7.4. {x−̇y, (∼ x) − y} Решение. Усеченная разность является существенной функцией, принимающей все k значений.

Далее, x−̇x ≡0, (∼ 0) − 0 = k − 1, (k − 1) − y =∼ y, (∼ (∼ x)) − y = x − y, x − y − · · · − y = x + y, (. . . (x−̇ 1)−̇ · · · )−̇1 = jk−1 (x) , 0 −| {z }| {z }k−1k−2(k − 1) = 1, x + 1 = x, следовательно есть все ji (x), а, следовательно, есть и x + j0 (x), и h0,1 (x) = x + j0 (x) +j1 (x) + · · · + j1 (x). Следовательно, исходная система содержит систему Софи Пикар 1 и является полной по тео|{z}k−1реме 2.7.5.j1 (x) , x − y, x2 − y Решение. Функция x − y является существенной и принимает все k значений.

Далее, x − x ≡ 1, 12 − 1 =0, x − 0 = x, следовательно, получены все константы, суммы вида x + i и ji (x), x − y − · · · − y = x + y, h0,1 (x) =| {z }k−1x + j0 (x) + j1 (x) + · · · + j1 (x). Следовательно, исходная система содержит систему Софи Пикар 1 и является пол|{z}k−1ной по теореме 2.7.6. {x, j0 (x) , x · y} Решение. Произведение является существенной функцией, принимающей все k значений.

x · j0 (x) ≡ 0, следовательно, есть все константы и все ji (x). Далее рассмотрим функциюf (x) = (1 + (x − 1) j1 (x)) (1 + (x − 1) j2 (x)) · · · (1 + (x − 1) jk−1 (x))и заметим, что она равна как раз x + j0 (x). Осталось увидеть, что h0,1 (x) = f (x) · j0 ( j1 (x)). Следовательно, исходная система содержит систему Софи Пикар 1 и является полной по теореме 2.7.Упражнения.

Используя критерий Слупецкого, доказать полноту в Pk нижеприводимых систем:1. {x − 1, (x + j0 (x)) · (1−̇y) + (1−̇x) · (y − j1 (x))};2. {x · j0 (x − y) + (x − j1 (x)) · j0 (y) + y · j0 (x)};3. { j0 (x − y) + x · j0 (y) + (x − j1 (x)) · j1 (y)};4. {x · j0 (y) + j0 (x) · (y + j0 (y) − j1 (y)) + j1 (x) · (y − j0 (y))};5.

{y · j0 (x) + j1 (x) · (y + j0 (y)) + j1 (y) · ( j2 (x) − j1 (x))}.2.4. ОСОБЕННОСТИ МНОГОЗНАЧНЫХ ЛОГИК2.483Особенности многозначных логикПредставление функции k-значной логики полиномами. Рассматриваются функции k-значной логики при k > 3и исследуется вопрос об их представимости полиномами. Известно, что если f (exn ) 6≡ 0, то ее можно представить вовторой форме:f (exn ) =∑ f (α1 , . . .

, αn ) · jα1 (x1 ) · jα2 (x2 ) · · · jαn (xn ) .(α1 ,...,αn )f (α1 ,...,αn )6=0Из этого следует, что если все ji представить полиномами, то f (exn ) также представится полиномом. Очевидно, справедливо и обратное, то есть ∀ f ∈ Pol ⇔ ∀ ji (x) ∈ Pol, а поскольку ji (x) = j0 (x − i), то задача представимости полиномомлюбой функции сводится к задаче представимости j0 . Полином функции одного переменного f (x) = a0 + a1 x + · · · +ak−1 xk−1 можно пытаться найти методом неопределенных коэффициентов:a0= f (0) , a +a +a +···+a= f (1) ,012k−1 ...........................................a0 + a1 s + a2 s2 + · · · + ak−1 sk−1= f (s) ,...........................................a0 + a1 (k − 1) + a2 (k − 1)2 + · · · + ak−1 (k − 1)k−1 = f (k − 1) .Это — линейная система k уравнений с k неизвестными, матрица которой является матрицей Вандермонда:112...1k−1 222...2k−1 .

. . . . . . . . . . . . . . . . . . . . .k − 1 (k − 1)2 . . . (k − 1)k−1Определитель этой матрицы равен∏(i − j) (mod k) и отличен от нуля при простых k. Получим j0 (x) при про-06 j<i6k−1стых k.Теорема 2.10 (П. Ферма, малая). Пусть p — простое. Тогда для любого a такого, что 1 6 a 6 p − 1 выполняется a p−1 ≡ 1 (mod p).

Док-во. Все равенства в дальнейшем подразумеваются по модулю p. Пусть a удовлетворяет условию теоремы.Рассмотрим набор чисел вида a · 1, a · 2, . . . , a · (p − 1). Очевидно, они все различны и не равны нулю. В то же время среди них содержатся в каком-то порядке все числа 1, 2, . . . , p − 1 (по модулю p). Перемножим их всех и получимa p−1 (p − 1)! = (p − 1)! (mod p) ⇒ a p−1 ≡ 1 (mod p).По теореме 2.10 нетрудно сообразить, как при простых значениях k = p будет выглядеть полином для функции j0 (x):j0 (x) = 1 − x p−1 .

Характеристики

Список файлов книги