4. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста (1268165), страница 3

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

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

. . , gk−1,f (k−1) (x)).Действительно, для каждого значения a ∈ Ek верноf (a) = max(g0,f (0) (a), . . . , ga,f (a) (a), . . . , gk−1,f (k−1) (a)) == max(0, . . . , 0, f (a), 0, . . . , 0) = f (a).В частности, получена функция f (x) =∼ x.Тогдаmin(x, y ) =∼ max(∼ x, ∼ y ).Функция min(x, y ) получена.Все функции системы 1-й формы построены формулами надфункциями системы Поста. Система Поста — полна.Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаФункция ВеббаСледствие 5.1. Пусть k ≥ 3. Множество, состоящее из однойфункции Вебба Vk (x, y ) = max(x, y ) + 1, является полнойсистемой в Pk .Доказательство. Построим из функции Вебба функции изсистемы Поста.x̄ = Vk (x, x) = max(x, x) + 1 = x + 1;max(x, y ) = Vk (x, y ) + 1| + .{z.

. + 1} .k−1Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаНеполиномиальность максимумаСледствие 5.2. Если k — составное число, то max(x, y ) ∈/ Polk .Доказательство проведем от противного. Пустьmax(x, y ) ∈ Polk при некотором составном k.Но x̄ = x + 1 ∈ Polk .Тогда {x̄, max(x, y )} ⊆ Polk .Но система Поста полна в Pk , следовательно, каждая функцияиз Pk задается полиномом по модулю k при составном k —противоречие.Отсюда, max(x, y ) ∈/ Polk .Конечнозначные функцииСпособы заданияНормальные формыПолиномыПолнотаБесконечные полные системы в PkСледствие 5.3.

Из каждой бесконечной полной в Pk системыможно выделить конечную полную подсистему.Доказательство. Пусть A ⊆ Pk — бесконечная полнаясистема.Т.к. система A — полна, в ней найдутся функции такиеg1 , . . . , gt , что функция Вебба Vk (x, y ) выражается формулойнад ними.Тогда подсистема A0 = {g1 , . . . , gt } — полна в Pk .Конечнозначные функцииСпособы заданияНормальные формыПолиномыЛитература к лекции1. Яблонский С.В. Введение в дискретную математику. М.:Высшая школа, 2001. Ч. I, гл. 2, стр. 43–50.2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения подискретной математике. М.: Физматлит, 2004.

Гл. III 1.1, 1.11,1.12, 2.7, 2.12.ПолнотаКонечнозначные функцииСпособы заданияНормальные формыКонец лекцииПолиномыПолнота.

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

Список файлов лекций