4. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста (1268165), страница 2
Текст из файла (страница 2)
. . , xn ) ∈ Pk может быть задана формулой вида:Xf (x1 , . . . , xn ) =jσ1 (x1 ) · . . . · jσn (xn ) · f (σ1 , . . . , σn ).(σ1 ,...,σn )∈EknКонечнозначные функцииСпособы заданияНормальные формыПолиномы2-я формаПример. Пусть g (x) = J2 (x + x 2 ) ∈ P4 :x x2 x + x2 g0 0001 1232 0233 100Найдем ее 2-ю форму:g (x) = j0 (x) · g (0) + j1 (x) · g (1) + j2 (x) · g (2) + j3 (x) · g (3) == j0 (x) · 0 + j1 (x) · 3 + j2 (x) · 3 + j3 (x) · 0 = 3j1 (x) + 3j2 (x).ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыМономФормула видаxis11 · .
. . · xisrr ,где все переменные попарно различны и s1 , . . . , sr ≥ 1,называется мономом.Число его сомножителей r , r ≥ 1, называется рангом, суммаrPстепеней его сомножителей s =si , s ≥ 1, называется егоi=1степенью.По определению будем считать константу 1 мономом рангаr = 0 и степени s = 0.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолиномФормула видаc1 K1 + . .
. + cl Kl ,где Ki — попарно различные мономы и ci ∈ Ek \ {0} —коэффициенты, i = 1, . . . , l, называется полиномом помодулю k.Число l, l ≥ 1, слагаемых Ki называется его длиной.По определению будем считать константу 0 (пустым)полиномом по модулю k с длиной l = 0.Примем, что в полином можно добавлять слагаемые снулевыми коэффициентами. Полученное выражение (формулу)будем также называть полиномом. Будем считать, что такойполином совпадает с полиномом без всех слагаемых снулевыми коэффициентами.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолиномыТеорема 4 (о задании k-значных функций полиномами)Пусть k ≥ 2. Каждая k-значная функция f (x1 , . . .
, xn ) ∈ Pkзадается полиномом по модулю k тогда и только тогда, когдаk — простое число.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолиномыДоказательство.Пусть f (x1 , . . . , xn ) ∈ Pk . Запишем ее во 2-й форме:f (x1 , . . . , xn ) =Xjσ1 (x1 ) · . . . · jσn (xn ) · f (σ1 , . . . , σn ).(σ1 ,...,σn )∈EknЗаметим, что jσ (x) = j0 (x − σ).
Тогдаf (x1 , . . . , xn ) =X(σ1 ,...,σn )∈Eknj0 (x1 −σ1 )·. . .·j0 (xn −σn )·f (σ1 , . . . , σn ).Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолиномыДоказательство.1. Если k — простое число, то по малой теореме Фермаak−1 = 1(mod k) при 1 ≤ a ≤ k − 1.Тогда j0 (x) = 1 − x k−1 иf (x1 , . . . , xn ) ==X(1−(x1 −σ1 )k−1 )·. . .·(1−(xn −σn )k−1 )·f (σ1 , . . . , σn ).(σ1 ,...,σn )∈EknЗатем перемножаем скобки по свойствам дистрибутивности,коммутативности и ассоциативности; приводим подобныеслагаемые.
Получим полином по модулю k для функцииf (x1 , . . . , xn ).Существование полинома по модулю k для каждой k-значнойфункции при простых k доказано.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолиномыДоказательство.2. Пусть k — составное число. Тогда k = k1 · k2 , где k1 ≥ k2 > 1.Докажем от противного, что в этом случае функция j0 (x) незадается полиномом по модулю k.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолиномыДоказательство.Пусть функция j0 (x) задается полиномом по модулю k:j0 (x) = cs x s + cs−1 x s−1 + . .
. + c1 x + c0 ,cs , cs−1 , . . . , c1 , c0 ∈ Ek — коэффициенты, cs 6= 0.Тогдаj0 (0) = c0 = 1;j0 (k2 ) = cs k2s + cs−1 k2s−1 + . . . + c1 k2 + 1 = 0.Отсюдаk2 · (cs k2s−1 + cs−1 k2s−2 + . . . + c1 ) = k − 1(mod k).Т.к. число k2 — делитель числа k, число k − 1 обязаноделиться на k2 > 1 — противоречие.Т.е. при составных k никакой полином по модулю k не задаетфункцию j0 (x).Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолиномиальные функцииЭлементарные функцииx;x̄ = x + 1;∼ x = (k − 1) − x = (k − 1)x + (k − 1);−x = k − x = (k − 1)x;x + y;x − y = x + (k − 1)y ;x · y;x m;являются полиномиальными при всех значениях k — ипростых, и составных.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаНеполиномиальные функцииЭлементарные функцииji (x), i ∈ Ek ;Ji (x), i ∈ Ek ;max(x, y );min(x, y );x −̇y ;x → y;являются полиномиальными при простых k и НЕ ЯВЛЯЮТСЯполиномиальными при всех составных k (будет доказанодалее).Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолиномиальные функцииМножество всех k-значных функций, задающихся полиномамипо модулю k, обозначается как Polk .Следствие 4.1.Если k — простое число, то Polk = Pk ;если k — составное число, то Polk 6= Pk .Вопросы:Как строить полиномы для k-значных функций при простых k?Как выяснить, задается ли полиномом заданная k-значнаяфункция, если k — составное?Конечнозначные функцииСпособы заданияНормальные формыПолиномыЕсли k — простое числоМетоды построения полиномов k-значных функций припростых k:1.
метод из доказательства теоремы 6.4 — по 2-й форме;2. метод неопределенных коэффициентов;ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЕсли k — составное числоЕсли k — составное число, то можно применять методнеопределенных коэффициентов для выяснения, задается лиданная k-значная функция полиномом по модулю k.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЕсли k — составное числоПримеры.1. Пусть f (x) = J1 (x) + J2 (x) ∈ P4 .Выясним, задается ли функция f (x) ∈ P4 полиномом помодулю 4 методом неопределенных коэффициентов.Предположим, что функция f (x) задается полиномом помодулю 4.Сначала построим таблицу степеней x s :x x2 x3 x40 0 0 01 1 1 12 0 0 03 1 3 1Так как x 4 = x 2 , степени в полиноме по модулю 4 можнозаписывать только до третьей.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаЕсли k — составное числоТогдаf (x) = ax 3 + bx 2 + cx + d,где a, b, c, d ∈ E4 — неизвестные коэффициенты.Для определения коэффициентов составим систему уравненийпо значениям данной функции f (x) = J1 (x) + J3 (x) ∈ P4 :f (0) = d = 0;f (1) = a + b + c + d = 3;f (2) = 2c + d = 3;f (3) = 3a + b + 3c + d = 0.Конечнозначные функцииСпособы заданияНормальные формыПолиномыЕсли k — составное числоИз первого и третьего уравнения получаем:2c = 3.Подставляя все возможные значения c ∈ E4 , выясняем, чторавенство не выполняется ни при каких значениях c ∈ E4 :2 · 0 = 0; 2 · 1 = 1; 2 · 2 = 0; 2 · 3 = 2.Следовательно, система не имеет решений (по модулю 4), иf (x) = J1 (x) + J2 (x) ∈/ Pol4 .ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЕсли k — составное число2.
Пусть g (x) = 2(J1 (x) + J2 (x)) ∈ P4 .Аналогично, выясним, задается ли функция g (x) ∈ P4полиномом по модулю 4.Тогдаg (x) = ax 3 + bx 2 + cx + d,где a, b, c, d ∈ E4 — неизвестные коэффициенты.Составляем систему уравнений:g (0) = d = 0;g (1) = a + b + c + d = 2;g (2) = 2c + d = 2;g (3) = 3a + b + 3c + d = 0.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыЕсли k — составное числоИз первого и третьего уравнения получаем:2c = 2, c = 1.Тогдаa + b = 1;3a + b = 1.Откудаa = 0, b = 1.Следовательно, функция g (x) задается полиномом помодулю 4, и один из ее полиномов по модулю 4g (x) = 2(J1 (x) + J2 (x)) = x 2 + x ∈ Pol4 .ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыОперация замыканияПусть A ⊆ Pk — множество k-значных функций.Замыканием множества A называется множество всехфункций, задаваемых формулами над множеством A.Обозначение: [A].Если A = [A], то множество A называется замкнутымклассом.Примеры: ∅, Pk , Polk .ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаПолные системыЕсли [A] = Pk , то множество A называется полной системой.Примеры.1.
{0, 1, . . . , k − 1, J0 (x), J1 (x), . . . , Jk−1 (x), max(x, y ), min(x, y )}— система 1-й формы.2. {0, 1, . . . , k − 1, j0 (x), j1 (x), . . . , jk−1 (x), x + y , x · y } — система2-й формы.3. {0, 1, . . . , k − 1, x + y , x · y } при простых k — системаполиномов.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаСистема ПостаТеорема 5. Пусть k ≥ 3.
Система Поста {x̄, max(x, y )}является полной системой в Pk .Доказательство. Построим формулами на системой Поста всефункции из системы 1-й формы.1. Построение констант.x̄ = x + 1; (x + 1) + 1 = x + 2; . . .; (x + (k − 1)) + 1 = x. Тогдаmax(x, x + 1, x + 2, . . . , x + (k − 1)) = k − 1.Отсюда (k − 1) + 1 = 0; 0 + 1 = 1; 1 + 1 = 2; . . .;(k − 2) + 1 = k − 1.Все константы получены.Конечнозначные функцииСпособы заданияНормальные формыПолиномыСистема ПостаДоказательство.2.
Построение Ji (x), i ∈ Ek .Проверим, чтоJi (x) = 1 +max(x + t).t6=(k−1)−iЕсли x = i, тоk − 1 = Ji (i) = 1 +max(i + t) = 1 + (k − 2) = k − 1.t6=(k−1)−iЕсли x 6= i, то0 = Ji (x) = 1 +maxt6=(k−1)−iВсе Ji (x), i ∈ Ek , получены.(x + t) = 1 + (k − 1) = 0.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаСистема Поста.Доказательство.3. Построение min(x, y ).Проверим, чтоgi,a (x) = a · ji (x) = (a + 1) + max(Ji (x), (k − 1) − a).Если x = i, тоa = a·ji (i) = (a+1)+max(Ji (i), (k −1)−a) = (a+1)+(k −1) = a.Если x 6= i, то0 = a·ji (x) = (a+1)+max(Ji (x), (k−1)−a) = (a+1)+(k−1)−a = 0.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаСистема Поста.Доказательство.Тогда получена каждая функция f (x) ∈ Pk1 , так какf (x) = max(g0,f (0) (x), g1,f (1) (x), .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
