Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Итак, для Pk {к > 3) мы получаем следующие ответы на поставленные в начале параграфа вопросы.
1. Существуют в Ph замкнутые классы, не имеющие конечного базиса.
2. Мощность множества всех замкнутых классов в Pk равна с.
3. Всякая функция в Ph может быть записана в виде полинома по mod к (соответственно над полем Галуа) в том и только том случае, когда к = р (соответственно, Когда к = рт).
ГЛ. 3. О.-Д. ФУНКЦИЙ С ОПЕРАЦИЯМИ
73
Сопоставляя эти ответы с ответами для двузначного случая, мы видим, насколько существенно различие указанных логик. Кроме того, мы видим, что некоторые вопросы решаются по-разному в зависимости от значения числа к.
Глава 3
ОГРАНИЧЕННО-ДЕТЕРМИНИРОВАННЫЕ (АВТОМАТНЫЕ) ФУНКЦИИ С ОПЕРАЦИЯМИ
Мы познакомились с двумя функциональными системами с операциями:
(Р2, С)—алгебра логики — система функций алгебры логики с операцией суперпозиции;
(Рк, С)—/с-значная логика—система функций к-вначной логики с операцией суперпозиции.
Путем вариации функционального объекта и операции можно получать другие системы. Так, усложняя функциональные объекты, естественным образом получаем:
, С)— счетнозначную логику, т. е. систему, содержащую константы 0,1,..к,... и функции }(х1}..хп), переменные которых определены на расширенном натуральном ряде Ек0 — {0,1,2, ...}г а сами функции принимают значения на с операцией суперпозиции;
(Ра С) — континуумзначную логику, т. е. систему, содержащую константы из [0. 1] и функции, переменные которых определены на сегменте [0, 1] и сами принимают значения па [0, 1], с операцией суперпозиции.
Мы не будем подробно рассматривать эти две системы, а познакомимся с другими, более важными. В этой главе речь будет идти о функциональной системе, связанной с автоматами.
§ 1. Детерминированные функции
Функциональный объект, который мы будем рассматривать, является разновидностью континуумзначной логики. Вместо действительных чисел из сегмента [0,1] мы возьмем множество Ес,ь всех Аг-значных последователь-
74 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ нос-тей сс, где
а = (а(1), а(2), ..а(тп), ...}, а{тп) ^ Eh для всех m (m™ 1, 2, . ..).
Обозначим через Ptмножество всех функций
/ (ЗД> ? ? ?, #я) |
определенных на наборах (а., ..a„), где оц е Ettk (г = = 1, 2, ..п), и принимающих значения из Etlb.Таким образом, функции из PClk преобразуют наборы fc-значных последовательностей в /с-значные последовательности. В Ptrh включим также все последовательности ив Е(lAt рассматривая их как функции, вависящие от пустого множества переменных (п^О), т. е. как константы.
Пример 1. Пусть к ™ 2 и
№. О, . ..), если a - (О,. О, .,.),
~ 1(1. 1. • ? ?), если а Ф (0Х 0,
Очевидно, что
f(x)tEPt, а.
Заметим, что для функции Пс>й табличное задание неприемлемо, так как множество 2?с,ь (а следовательно, и множество «строк» таблицы) имеет континуальную мощность. Отсюда же следует, что мощность множества всех функций Pt,kt зависящих ОТ переменных Хи Xit .. ., равна гинерконтинууму. Учитывая это обстоятельство, мы в дальнейшем будем рассматривать более узкий функциональный объект.
Для наборов и функций мы будем дальше употреблять векторную запись. Так, обозначая набор переменных (#1, хг, ..хг<) через X, вместо f(xu ..., #„) мы будем писать f(X). При этом значение переменной X есть вектор (набор) а—(аи ..., an), компонентами которого являются последовательности значности к:
а* = (аД1), аД2), ..., а.(то), ...} (i — 1, 2, ..,, /г).
Будем истолковывать а как последовательность векторов
a = {a(l), a(2), .... a(m),
где
а(т) = (а, (т), а2(лг), ..а„(лг)) (т = 1, 2, ...)•
Таким образом, мы считаем, что выполнено тождество ({«*(1), ос,(2), ..ос,(77г), ..
(а2(1), аг(2), ..а2(т), .....
..{а„(1), а„(2), .. а„(пг), .. .})^
«{(а,(1), а2(1), ос,,.(1)), (0,(2), а,(2), ...
..а„(2)), ..(а,(т), ая(т), ..., ап(т)), ...).
Полученную последовательность векторов можно рассматривать как последовательность наборов (аДт), а2(т)»...
..а„(лг)) или чисел в /с-ичной системе счисления. Каждое из этих чисел принадлежит множеству Ея, где Лг—кп.
Итак, функцию ]{хь ..., #„) из Р?д можно рассматривать как функцию /(X) из множества Рс,к> но зависящую от одной переменной (и принимающую значения из ЕС'к<^ ЕСгм). Таким образом, изучение функции /(я,, ...
.?„) ИЗ можно свести к изучению функции {{X) от одной переменной из Рс,/у, где N = кп. Данная редукция построена на формальных соображениях, связанных с толкованием набора последовательностей как последовательности наборов. Нише мы увидим, что для некоторого класса функций из Рс,н такое толкование приобретает определенный физический смысл.
Определение. Функция }(Х) из Рс,дг называется детерминированной, если каково бы ни было число тп и каковы бы ни были последовательности аир такие, что
а(1)=р(1), а(2)=р(2), ..., а(т)=р(т),
значения 7 и б функции /, где ? = / (а) и б — /(р), представляют собой последовательности, у которых тоже совпадают первые т членов, т. е.
Т(1)-б(1). у{2) = б(2), ..., 7-(|я)-в(т).
Через Ря,и обозначим множество всех детерминированных функций ИЗ РС,А. Рд, к, очевидно, содержит все константы из Рс.ь*
