Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Для функций А, /2 и А мы имеем схему одновременной примитивной рекурсии. Следовательно, мы можем утверждать, что Д, Д, /э ^ Лвр. Возьмем теперь
рДД« ?) = 0}.
Данная функция принадлежит классу Рчр и определяет для каждого а/ момент останова машины. Если эту величину подставить в Д, то получим
А (я', рД/з(аА ?) = 0})\ -?
т. е. если машина останавливается, то получим натуральное чдсло, двоичной записью которого будет код /(я)..
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 1Є9
В таком случае, если учесть, что
х' ..., xn)t
ГДЄ О (*Ct) • • •) і • *| 2(), ТО
/(яі, .... зЛ^
“ Р (/* (*' (*i, . . X») , Hi (/a (O' (Яі, . . Жя) , 0 = 0) ) ) -5- 1.
Если положить
*/<*1. ї/)“Р(/і(® • 1 ^n)l &))
G/ (J^jj ..ЗГп» ?/) /а ("& (^і» * ? •» ®n), У),
то получим требуемое. Теорема доказана.
Как следствие из теорем получается Теорема 6. Рвы, = Рар.
Таблица 22
Х1 хй
0 ‘ 2 3
0 1 0 0 0
1 0 2 0 0
2 0 0 3 0
3 0 0 0 4
Ив последних двух теорем имеем также, что каждая частично-рекурсивная функция может быть записана через примитив но-рекурсив пые функции в виде канонического уравнения, даваемого представлением Клини.
Теорема 7. Система функций (0, 5{я), /1 (я)] полна в Рви* относительно набора операций {С, Пр, рК
Теорема 8. Система функций {0, 5(т)} полна в Рвы* относительно набора операций {С1 Пр, р}.
170 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Доказательство. Функция {#) определяется через 0 и ?(#) при помощи следующей схемы:
П(0) = о,
Я(* + 1)-5(/1<*)).
Теорема 9. В функциональной системе (Р ВЫЧ) С, Пр, р) существует аналог функции Шеффера*).
Доказательство. Возьмем функцию /(л:ь х2) (см. табл. 22). Очевидно,/(^1, 2,1) = 5{а:1) и 1{хи 5 (^1)) = 0(яч). Затем, как в предыдущей теореме, получаем I] (л^, а:*), ^(#1) =? ^1(^1 ^1) и все ^т(л'и •••} х>‘)' Отсюда легко построить также класс ^ыыч*
*) Здесь через ^ЫЧ обозначим .множество ^ьыч\^80*
ЧАСТЬ II
КОМБИНАТОРНЫЙ АНАЛИЗ
Комбинаторный апалпз занимается изучением объектов из конечного множества Е ~ {аи ..ап} и их свойств.
Этими объектами могут быть подмножества множества ?, подмножества с повторяющимися элементами из множества Е, упорядоченные подмножества множества Е и т. п.
Комбинаторный анализ является разделом дискретной математики, истоки которого уходят в глубокую древность. В настоящее время интерес к нему значительно усилился. Благодаря этому комбинаторный анализ сегодня превратился в достаточно развитую ветвь математики, которая непрерывно разрастается. Это делает трудным четко очертить круг объектов и их свойств, которые принадлежат комбинаторике. Ввиду этого мы начинаем с описания простейших (элементарных) комбинаторных объектов.
§ 1. Комбинаторные объекты и комбинаторные числа
1. Система подмножеств множества Е. Пусть Е=> *= {я1} ..., ап) — конечное мпожество. Рассматриваются все его подмножества. Эту систему обозначим через <$„.
Пример. Е = {аи а2, я3). Система его подмножеств имеет вид:
©а ~ (А, {я,}, {я21, (я31, {Яд, я21, {я1( й31, {я2) я31, {я1( я3, я3П.
2. Размещения элементов из Е по к. Пусть Е = {а17 .„.
,.я„К Размещением элементов из Е по к называется упорядоченное подмножество из к элементов, принадлежащих Е.
Пример. Е = (йд, я2, я3} и к — 2. Выпишем все размещения из этого множества по 2:
(йд, й2) , (йг, Яд), (Яд, й3), (й3, Яд), (йг, й3), (й3, й2) .
3. Перестановки элементов множества Е. Пусть Е =» = (йд. ..., ял}. Перестановками называются упорядоченные подмножества из п элементов множества
172
Ч. II. КОМБИНАТОРНЫЙ АПАЛИЗ
Пример. Е — {«lt аа, os). Перестановками множества
Е будут (аи Да, flj), {«1, 08, Да), («а, ff-i, Я3), («а, «а, Oi),
(Дз, Й1, flajj (#s, <Ь, Щ).
Очевидно, что перестановки — частный случай размещений элементов из Е по к, когда к — д.
4. Сочетания элементов из # но к. Сочетанием элементов из Е но к называется неупорядоченное подмножество из к элементов, принадлежащих Е.
Пример. Е = {аи ад3) и к = 2. Сочетаниями из Е по 2 будут (а,, а2), (щ, д3), (дз, «зЬ
5. Сочетания^ с повторениями элементов из Е по к. Сочетанием с /гоеторс/шялш элементов из Е по к является неупорядоченная система из к элементов, принадлежащих Е, в которой допускается повторение элементов.
Пример. Е=*{аи яа, и к = 2. Сочетаниями с повторениями из Е по 2 будут {«[, а,}, {а1( aj, (щ, а3}, {д2, д 2), {д2, ДгД, ДзК
6. n-мернын куб размера к (к^>2). Совокупность всех наборов (оц, ..., ал) (упорядоченных сочетаний с повторениями) из множества ?V=(0, 1, ..., /с — 1) по п называется п-мерным кубом размера к и обозначается череа
Е1(Е1 = Екх...хЕк).
п раз
Пример 1. З-мериьхй куб размера 2. Ег = (О, О. Мы имеем следующую совокупность наборов: (0, 0, 0),
(0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1,1,1). Эти наборы можно рассматривать как вершины единичного З-мертюго куба (см. рис. 1).
Пример 2. На рис. 2 изображен 3-мерный куб размера 3.
7. Разбиения множества Е, Разбиением множества Е называется неупорядоченная система из непустых подмножеств (&и &ь) множества Е, обладающая
двумя свойствами:
1) artu...u<Г* = Я;
