С.В. Яблонский - Введение в дискретную математику (1060464), страница 12
Текст из файла (страница 12)
При х 0 получаем Ь, — 1. При х= й, получаем 0 1 + Ь,й, +... + Ь,й', (шо») й) или й — 1 Ь,й +... +Ь»й» (шо») й), т. е. й — 1 делится на й,. Таким образом, й и й — 1 делятся на й„что возможно только при й, = 1. Мы пришли к противоречию. Следовательно, прп й ~ р функция 1»(х) не представнма полиномом по»по») й. Доказанная теорема может быть легко обобщена на случай, когда на Е, возможно определить две операции: ю и Х вЂ” сложение и умножение, относительно которых Е, образует поле.
Как показывается в алгебре, конечное поле или поле Галуа, существует тогда и только тогда, когда й = р"'. В этом случае оно определяется с точностью до изоморфизма однозначным образом. При этом относительно сложения оно образует абелеву группу характеристики р, т. е. для любого элемента с» выполняется соотношение с»»22...9а О, где 0 — нуль группы. Эту группу можно определить, рассматривая числа а, как числа в р-ичной системе счисления, т. е. в виде наборов (»2„ ..., а ), и операцию а Е р =(а, + р„ ..., сс + () ) (+ обозначает сложение по шо») р). Все элементы поля Галуа, кроме О, образуют относительно второй операции циклическую группу.
Пример 5. Пусть й 2'. Тогда операция Е имеет вид как в табл. 4. Для построения таблицы для операции Х заметим, что числа 1, 2, 3 могут быть выражены тй ч. ь Функциональные системы с ОпеРАШ1ямн как степени некоторого элемента а (следует из цикличности мультипликативной группы).
Это число а удовлетворяет уравнению аа илв, так как и чь 1, и'ЕаФ1=0. Взяв за и элемент 2 получим а' В (и ~ 1) 3. Мы по- лучаем таблицу для Х (табл. 5), поскольку 2 ° 2 а ° а 3, 2 3 а и' а' 1, 3 З=а' а' а'=а=2. Мы можем, повторяя первую часть доказательства предыдущей теоремы, показать, что каждая функция Дхо... ..., х„) из Р, при й = р представпма полпномом над соответствующим полем Галуа.
Табзсса б Табвеяз 4 В частности, в Р, возможно представление функций полиномами, но не по пзой 4, а полиномами над полем Галуа. Итак, для Р, (й ~ 3) мы получаем следующие ответы на поставленные в начале параграфа вопросы. 1. Существуют в Р, замкнутые классы, не имеющие конечного базиса. 2. Мощность множества всех замкнутых классов в Р„ равна с. 3.
Всякая функция в Р, может быть записана в виде полинома по 1поб й (соответственно над полем Галуа) в том и только том случае, когда й р (соответственно, когда й = р ). гл. з. о.-д. стнкцни с опкг»пнями Сопоставляя эти ответы с ответами для двузначного случая, мы видим, насколько существенно различие указанных логик. Кроме того, мы видим, что некоторые вопросы решаются по-разному в зависимости от значения числа й. Глава д ОГРАНИЧЕННО-ДЕТЕРМИНИРОВАННЫЕ (АВТОМАТНЫЕ) ФУНКЦИИ С ОПЕРАЦИЯМИ Мы познакомились с двумя функциональными системами с операциями: (Рм С) — алгебра логики — система функций алгебры логики с операцией суперпозиции; (Рм С) — й-значная логика — система функций йзначной логики с операцией суперпозиции.
Путем вариации функционального объекта и операции можно получать другие системы. Так, усложняя функциональные объекты, естественным образом получаем: (Р»», С) — счетнозначную логику, т. е. систему, содержащую константы 0,1,...,й,... и функции ((ло...,х.), переменные которых определены на расширенном натуральном ряде Е», (О, 1, 2, ...), а сами функции принимают значения на Е»,, с операцией суперпоанции; [Р„ С) — континуумзначную логику, т. е.
систему, содержащую константы из [О, 1] и функции, переменные которых определены на сегменте [О, 1] и сами принимают значения на [О, 1], с операцией суперпозиции. Мы не будем подробно рассматривать зти дзе системы, а познакомимся с другими, более важными. В этой главе речь будет идти о функциональной системе, сзяаанной с автоматами. $1. Детерминированные функции Функциональный объект, который мы будем рассматривать, является разновидностью континуумзначной логики. Вместо действительных чисел из сегмента [О, 1] мы возьмем множество Есь всех й-значных последователь- 11 ч.
ь отнкцнонлльнмк спсткмы с опввАПиямй костей а, где а = (а(1), а(2), ..., сс(т), ° ° ), а(т)тЕ, для всех т (т= 1, 2, ). Обозначим через Рсл множество всех функций 1(хь " х.) определенных на наборах (сс„..., сс„), где а;~ Ес,д(с 1, 2, ..., и), и принимающих значения иа Е, ю Таким образом, функции из Рс,а преобразуют наборы й-значных последовательностей в й-злачные последовательности. Б Роа включим также все последовательности из Ес,ьл рассматривая их как функции, зависящие от пустого множества переменных (и 0), т.
е. как константы. Пример 1. Пусть й ° 2 и (0,0, ...), если а (0,0, ...), 1(а) = (1, 1, ...), если а ~ (О, О, ...). Очевидно, что ~ (х) а Рс,«. Заметим, что для функции Ро«табличное задание неприемлемо, так как множество Еьа (а следовательно, и множество «строке таблицы) имеет континуальную мощность. Отсюда же следует, что мощность множества всех функций Рс,юзависящих от переменных х„х„..., равна гиперконтинууму.
Ъ'читывал это обстоятельство, мы в дальнейшем будем рассматривать более узкий функциональный объект. Для наборов и функций мы будем дальше употреблять векторную запись. Так, обозначая набор переменных (х„х„..., х„) через Х, вместо ~(хо ..., х ) мы будем писать 1(Х). При этом значение переменной Х есть вектор (набор) а =(а„..., а„), компонентами которого являются последовательности значностн рл а, ° (а~(1), а~(2), ..., а~(т), ...) (1 1, 2, ..., и). Будем истолковывать а как последовательность векторов а = (а(1), а(2), ..., а(т), ...), гл.
а о.-д. э1 нкцин с спиваниями 75 где а(т)=(а,(т), а,(т), ..., а.(т)) (т 1, 2, ...). Таким образом, мы считаем, что выполнено тождество ((а~ (1), а, (2)... „а, (т), ...), (а,(1), а,(2), ..., сц(т), ...), ... ..., (а.(1), а.(2), ..., а (т), ...)) ((а,(1), а,(1), ..., а„(1)), (а,(2), а,(2), ... ..., а„(2)), ..., (а,(т), а1(т), ..., а.(т)), ). Полученную последовательность векторов можно рассматривать как последовательность наборов (а, (т), аи (т),... ..., а„(т)) или чисел в й-ичной системе счисления. Каждое из этих чисел принадлежит множеству Е„, где У й".
Итак, функцию Дхь ..., х ) из Рса можно рассматривать как функцию 1(Х) иа множества Рьн, ио вависящуюотодной переменной (и принимающую аначенияиз Е, ьс= Еол). Таким образом, изучение функции )(хо ... ...,х.) из Роа можно свести к изучению функцкиДХ) от одной переменной иа Рьн, где У й". Данная редукция построена на формальных соображениях, связанных с толкованием набора последовательностей как последовательностк наборов. Ниже мы увидим, что для некоторого класса функций из Роь такое толкование приобретает определенный фиаическнй смысл.
Определение. Функция ((Х) из Рс я называется детерминированной, если каково бы ни было число т и каковы бы ни были последовательности а н б такие, что а(1) р(1), а(2) ~)(2), ..., а(т) ()(т), аначения ( и б функции /, где ( ~(а) и б ((р), представляют собой последовательности, у которых тоже совпадают первые т членов, т. е. '((1)= б(1), т(2) б(2), ..., "((т) б(т)', Череа Р„„обозначим множество всех детерминированных функций из Рью Р, ь, очевидно, содержит все константы из Роа Пусть Да) (. Из определения следует, что у детерминированной функции значение т(т) т-го (т 1,2,...) те ч. г. езнкцг«ональнык систнмы с опкгацияьггг члена последовательности ( полностью определяется еначеннями первых т членов и(1), а(2), ..., сс(т) последовательности а, т.
е. т(т) 1 (и(1), и(2), ..., а(т)). Поскольку 1 (и(1), а(2), ..., и(т)) 1 (и,(1), ..., и„(1), и,(2), ..., а„(т) )', то ясно, что 1 — функция иа Р„, аависящая от лт переменных. Таким обраеом, детерминированная функция 1(Х) определяется последовательностью функций й-значной логики где 1 (Хо Х«, ..., Х ), Х, (х,(1), х,(1), ..., х„(1)), Х, (х,(2), х,(2), ..., х„(2)), Х (х,(т), хг(т), ..., х„(т))', Детеръгинпрованная функция 1(хо ..., х„) может быть проинтерпрегнрована следующим образом. Пусть мы имеем некоторый «дискретный преобраеовательэ (рис. 1), в котором'существует п входов х„х«, ..., х„и один выход 1.
На входы в моменты времени г 1, 2, ... ..., т, ... подаются (входные) последовательности а, (и,(1), сс,(2), ..., и,(т), ...), и, = (и,(1), и,(2), ..., и,(т), ...), а„= (а„(1), а„(2), ..., а„(т), ...). гл, 3. О.-д. Функции с опегацнямн И в зти же моменты з на выходе возникает (выходная) последовательность.( = (((1), ((2), ..., ((т) ° » пр" чем ( = 1(а„а„..., а„). Очевидно, что в дискретном преобразователе значение ((т) зависит только от значений входных последовательностей в моменты времени 1, 2, ..., т и не зависит от значений в будущие моменты времени. Поэтому преобразова- хт . ние ( есть детерминированная функция. Заметим, что константы из Рве.
1 Р„,ь (н = О) интерпретируются дискретным преобразователем без входов (згенераторомз). Заметны также, что поступающие на входы преобразователя последовательностп, т. е. (а„аь ..., а.), можно рассматривать как последовательность наборов ((а,(1), аз(1), ..., а„(1)), (а,(2), аз(2), . „ а„(2)),...).
Здесь введенное нами тождество выполнено естественным образом. Из того, что детерминированная функцля ((хе ..., х„) полностью определена последовательностью функций к-анечкой логики, вытекает следу1ощий факт. 'Теорема 1. Мощность множества всех детерминированных функций, зависящих ог переменных хо х, ... ..., х„, равна а В заключение приведем ряд иллюстраций. П р и м е р 2. а) Функция 1е (х„..., х„), где Ф (х„..
..., х„) ж Р„, определена следующим образом: ~Ф(хь ° ~ хп) (Ф(х1(1)~ ° ~ ха(1))~ Ф(х,(2), ..., х.(2)), ..., Ф(х,(т), ..., х.(т) ), ...). Значение функции та определяется путем вычисления значений функции Ф по значениям соответствующих членов входных последовательностей. Отсюда ~е ы Р, „.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
