URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Марченков С.С. Представление функций суперпозициями
Id: 109628
 
256 руб.

Представление функций суперпозициями

URSS. 2010. 192 с. Мягкая обложка. ISBN 978-5-484-01139-1.

 Аннотация

Основная цель данной книги --- продемонстрировать, как решаются проблемы представимости функций суперпозициями для классов функций различной природы. В качестве объектов исследования выбраны классы функций многозначной логики, классы примитивно рекурсивных функций иерархии Гжегорчика, классы элементарных рекурсивных перестановок, образующие группы относительно операции композиции, классы конечно-автоматных функций, классы функций, непрерывных в пространстве Бэра, и классы непрерывных функций действительных переменных. Приведены результаты как положительного характера (существование конечных либо бесконечных порождающих систем специального вида, существование специальных форм представления функций суперпозициями), так и отрицательного (невозможность представления одних функций суперпозициями других функций при заданных ограничениях). Часть результатов уже заняла подобающее им место в теориях функций соответствующих типов, другие результаты получены сравнительно недавно.

Для научных сотрудников, преподавателей высшей школы и аспирантов, занимающихся вопросами представления функций суперпозициями.


 Оглавление

Предисловие
Введение
Глава I. Функции многозначной логики
 § 1.Стандартные полные системы
 § 2.Критерий Яблонского
Глава II. Конечный базис по суперпозиции в классе ε2 иерархии Гжегорчика
 § 1.Основные понятия и формулировка центрального результата
 § 2.Машины Минского
 § 3.Конфигурации и коды конфигураций
 § 4.Основное свойство функции Q
 § 5.Доказательство основной теоремы
 § 6.Конечные базисы по суперпозиции в классах одноместных функций
Глава III. Простые базисы по суперпозиции в классе функций, элементарных по Кальмару
 § 1.Основные понятия и построение простейших функций
 § 2.Получение из функций системы S функций нод, exp2, sigma
 § 3.Однократные экзистенциальные представления отношений
 § 4.Суммирование экспоненциально полиномиальных выражений
 § 5.Основной результат
Глава IV. Конечная порождаемость некоторых групп рекурсивных перестановок
 § 1.Основные понятия
 § 2.Представление перестановок в виде композиции паросочетаний
 § 3.Конечная порождаемость групп Gr(Q)
 § 4.Конечная порождаемость групп Grn)
Глава V. Конечно-автоматные функции
 § 1.Детерминированные и конечно-автоматные функции
 § 2.Задание конечно-автоматных функций диаграммами Мура и каноническими уравнениями
 § 3.Отсутствие конечных базисов в классе конечно-автоматных функций
 § 4.Бесконечные порождающие системы в классе конечно-автоматных функций
Глава VI. Непрерывные функции на бэровском пространстве
 § 1.Основные понятия и простейшие свойства непрерывных функций
 § 2.Представление (n + 1)-местных функций суперпозициями n-местных функций
Глава VII. Теорема Колмогорова
 § 1.Формулировка теоремы Колмогорова
 § 2.План доказательства теоремы
 § 3.Этап I доказательства
 § 4.Этап II доказательства
 § 5.Этап III доказательства
Глава VIII. Невозможность получения многоместных непрерывных функций суперпозициями функций меньшего числа переменных
 § 1.Регулятор непрерывности, (k,l)-приближение и (k,l)-емкость
 § 2.Суперпозиции функций с заданным регулятором непрерывности
 § 3.Суперпозиции функций, удовлетворяющих условию Липшица
Список литературы

 Предисловие

В любом разделе математики, имеющим дело с систематическим изучением какого-либо класса функций, на некотором этапе исследований необходимо возникает потребность во введении операции суперпозиции (композиции) функций. Зачастую операция суперпозиции играет вспомогательную роль, позволяя лишь формально выразить последовательность и структуру применения конкретных функций к основным объектам исследования. Однако в ряде случаев роль операции суперпозиции существенно возрастает, операция суперпозиции сама становится основным объектом исследования либо его главным инструментом. Это относится, например, к универсальной алгебре, дискретной математике и, в частности, теории функциональных систем, теории автоматов, теории алгоритмов и другим разделам математики.

По существу все наиболее интересные задачи, связанные с операцией суперпозиции, относятся к представлению одних функций (или классов функций) в виде суперпозиций других функций. Как правило, задача состоит либо в доказательстве принципиальной возможности подобных представлений, либо в установлении некоторых специальных форм представлений. Стоит упомянуть о некоторых, наиболее известных проблемах, касающихся представления суперпозициями функций различной природы.

Прежде всего, следует отметить 13-ю проблему Гильберта, которую (имея в виду результаты Колмогорова--Арнольда) можно сформулировать следующим образом: всякую ли непрерывную функцию многих переменных, заданную на единичном кубе, можно представить в виде суперпозиции непрерывных функций меньшего числа переменных?

Другой важной проблемой, оказавшей существенное влияние на становление и развитие целого ряда разделов математики (теория булевых функций и теория функций многозначной логики, теория функциональных систем, теория управляющих систем и др.), явилась проблема характеризации и конечной порождаемости всех замкнутых (относительно операции суперпозиции) классов булевых функций. Эта проблема решена Э.Постом в 1921 г. (подробное доказательство опубликовано в 1941 г.). Она породила огромную литературу как собственно по булевым функциям, так и в смежных областях дискретной математики и кибернетики.

Значительное место в теории рекурсивных функций занимает иерархия множества примитивно рекурсивных функций, предложенная А.Гжегорчиком в 1953 г. Одной из проблем, поставленных А.Гжегорчиком для классов иерархии, явилась проблема конечной порождаемости (относительно операции суперпозиции) классов  εn иерархии. Для n >= 2 проблема была положительно решена. Её решения породили целую серию аналогичных проблем для других классов рекурсивных функций (часть из них до сих пор не решена), а также способствовали привлечению в этот раздел теории рекурсивных функций новых подходов и методов из теории чисел, комбинаторики и математической логики.

Основная цель настоящей книги -- показать, как решаются проблемы представления функций суперпозициями для классов функций различной природы. Для достижения этой цели были выбраны классы функций, для которых упомянутые проблемы сформулированы достаточно давно, а полученные решения носят более или менее законченный характер. Помимо этого, при выборе классов функций учитывались такие факторы как значение выбранного класса для соответствующего раздела математики, объём исследований, посвящённых решению проблем представимости функций в данных классах, а также имеющиеся либо возможные приложения полученных решений в других разделах математики. Разумеется, список отобранных классов не претендует на исчерпывающую полноту, скорее, он отражает предпочтения и интересы автора в данной области. Вместе с тем список классов достаточно репрезентативен: он даёт представление об основных исследованиях, ведущихся в этом направлении, и о глубине полученных здесь результатов.

Мы остановили свой выбор на следующих классах функций: класс булевых функций и классы функций многозначной логики; классы εn примитивно рекурсивных функций, образующие иерархию Гжегорчика, и особенно классы ε2 и ε3 этой иерархии; некоторые классы примитивно рекурсивных перестановок, образующие группы по отношению к операции композиции (суперпозиции) перестановок и порождаемые классами иерархии Гжегорчика либо близкими к ним классами; класс конечно-автоматных функций; класс функций, непрерывных в пространстве Бэра; классы непрерывных функций действительных переменных.

Часть из вошедших в книгу результатов уже давно и прочно заняла место в фундаменте соответствующих разделов математики. Сюда можно отнести результаты по функциям многозначной логики, по конечно-автоматным функциям, а также широко известную теорему Колмогорова о представлении суперпозициями непрерывных функций многих переменных. Другие результаты опубликованы в 1980--1990 гг. и уже получили достаточное признание среди специалистов (это некоторые результаты по конечно-автоматным функциям, по функциям, непрерывным в пространстве Бэра, а также базирующиеся на дискретных подходах теоремы о невозможности представления некоторых непрерывных функций многих переменных суперпозициями непрерывных функций меньшего числа переменных). Результаты глав II--IV в своём окончательном виде получены после 2000 г., часть результатов снабжена новыми доказательствами, которые специально написаны для настоящей книги.

Книга состоит из восьми глав.

В главе I рассматриваются простейшие функции -- булевы функции и функции многозначной логики. По этим функциям имеется огромная литература, а основы теории функций многозначной логики, как правило, излагаются на первых курсах математических факультетов. Поэтому в главе I представлены лишь некоторые результаты принципиального характера, позволяющие в дальнейшем ориентироваться в вопросах представления функций многозначной логики суперпозициями. Здесь указаны некоторые стандартные конечные системы функций, порождающие (в стандартной форме) произвольные функции многозначной логики. Кроме того, охарактеризованы (критерии Слупецкого и Яблонского) те многоместные функции, которые вместе с множеством всех одноместных функций образуют полные системы.

В главах II--IV рассматриваются функции более сложной природы -- функции натурального аргумента. Наиболее интересные результаты здесь получены для рекурсивных функций.

В главе II исследуется класс ε2 -- "ключевой" класс иерархии Гжегорчика. Класс ε2 имеет несколько различных определений, в том числе индуктивное определение, предложенное А.Гжегорчиком, и несколько вариантов "машинных" определений. В класс ε2 входят многие арифметические и теоретико-числовые функции, и функции класса ε2 имеют относительно невысокую сложность вычисления. Неудивительно поэтому, что именно для класса ε2 проблема существования базиса по суперпозиции привлекла в своё время наибольшее внимание исследователей. Она была положительно решена автором в конце 1960-х гг. Впоследствии решение улучшалось в качественном отношении, пока в начале 2000-х гг. С.А.Волков не получил чрезвычайно оригинальное решение, которое заставило по-новому взглянуть на природу функций класса ε2. Это решение подробно излагается в главе II.

В главе III рассматривается класс K функций, элементарных по Кальмару, -- класс ε3 в иерархии Гжегорчика. Класс K -- первый и общепризнанный класс "элементарных" рекурсивных функций. Собственно, с этого класса началось решение проблемы Гжегорчика, касающейся конечной порождаемости классов его иерархии. Решение проблемы Гжегорчика для класса K прошло несколько этапов. В 1964 г. Д.Рёддинг с помощью весьма громоздких построений показал, что класс K конечно порождаем. В 1968 г. Ч.Парсонс, используя более тонкие рассуждения, нашёл систему из 19 сравнительно простых функций, которая порождает класс K. Дальнейшие продвижения в этом направлении принадлежат автору и связаны с применением в конструкциях диофантовых и экспоненциально диофантовых представлений рекурсивно перечислимых множеств. На этом пути в классе K был найден невероятно простой базис по суперпозиции, состоящий из четырёх функций. Последняя точка в построении этого базиса была поставлена в 2002 г., когда С.Маззанти нашёл специальное представление для одной теоретико-числовой функции. Пересмотренная версия этого итогового решения составляет содержание главы III.

Глава IV в некотором отношении выделяется среди других глав книги. Формально в ней продолжается линия, начатая в главах II и III. Однако объект исследования главы IV -- группы рекурсивных перестановок -- является мостиком между проблематикой конечной порождаемости классов рекурсивных (многоместных) функций и традиционными проблемами теории групп. Результаты, представленные в главе IV, во многом пионерские и, вне всякого сомнения, будут способствовать дальнейшему обмену идеями и методами между теорией рекурсивных функций и теорией групп. Группы рекурсивных перестановок, изучаемые в главе IV, порождаются классами иерархии Гжегорчика, другими подобными классами и в известном смысле представляют собой "фундаменты" соответствующих классов. Доказательства конечной порождаемости групп в главе IV (отметим: первые в данной области) используют результаты о конечной порождаемости классов рекурсивных функций, определяющих данные группы. Однако прямое перенесение конструкций из глав II, III на группы перестановок невозможно, поскольку в терминах перестановок нельзя ни использовать возможности многоместных функций, ни применять, например, обычную технику кодирования вычислений на машинах Тьюринга. Все результаты, вошедшие в главу IV, получены совсем недавно и принадлежат С.А.Волкову.

Конечно-автоматные функции, изучаемые в главе V, являются естественным звеном, связывающим рекурсивные функции с функциями непрерывными. В главе V содержатся в основном результаты, которые уже достаточно давно заняли подобающее им место в теории конечных автоматов. Это невозможность построения конечного базиса по суперпозиции в классе всех конечно-автоматных функций и важные примеры бесконечных порождающих систем.

Непрерывным функциям посвящены главы VI--VIII.

В главе VI рассматриваются функции, (равномерно) непрерывные на бэровском пространстве. Основная задача, решаемая в этой главе, -- найти условие, которое позволяет отделить множества n-местных функций, порождающие все (n + 1)-местные функции, от множеств n-местных функций, которые обладают противоположным свойством. Такое условие формулируется в терминах модуля непрерывности -- натуральнозначной функции, определяющей степень зависимости двоичных разрядов значения функции от двоичных разрядов её аргументов.

Глава VII содержит замечательный результат -- теорему Колмогорова, которая решает 13-ю проблему Гильберта. Теорема доказана в наиболее общей форме: всякая многоместная функция, определённая и непрерывная на единичном кубе, может быть представлена в виде суперпозиции одноместных функций и функции сложения.

В главе VIII исследуется эффект, в известной степени противоположный теореме Колмогорова. Принципиально он был обнаружен А.Г.Витушкиным ещё в середине 1950-х гг. Именно, при наличии некоторых ограничений на гладкость функций для любого n >= 2 имеются непрерывные функции от n + 1 переменных, которые невозможно представить в виде суперпозиций непрерывных функций от n переменных. В отличие от подхода А.Г.Витушкина, использующего аппарат многомерных вариаций, в главе VIII предложено ещё два других подхода для получения подобных результатов. Один подход основан на скорости роста так называемого регулятора непрерывности функции, другой подход использует понятие приближения непрерывной функции с помощью булевых операторов.

Книга адресована широкому кругу математиков, желающих ознакомиться с проблемами представления функций суперпозициями. Она будет полезна научным сотрудникам и преподавателям вузов, работающим в области дискретной математики, а также аспирантам математических факультетов, специализирующимся по этой специальности.


 Об авторе

Сергей Серафимович МАРЧЕНКОВ

Доктор физико-математических наук, профессор кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова. В 1967 г. окончил механико-математический факультет МГУ, в 1970 г. -- аспирантуру по кафедре математической логики. С 1970 по 2000 гг. работал в Институте прикладной математики им. М. В. Келдыша РАН, с 2000 г. преподает на факультете ВМиК МГУ.

С. С. Марченков -- автор книг "Замкнутые классы булевых функций" (М., 2000), "S-классификация функций трехзначной логики" (М., 2001), "Элементарные рекурсивные функции" (М., 2003), "Функциональные системы с операцией суперпозиции" (М., 2004), "Элементарные арифметические функции" (М.: URSS, 2010) и некоторых других. Им опубликовано более 100 статей по теории алгоритмов, математической логике, универсальной алгебре, теории функциональных систем и теории автоматов.

 
© URSS 2016.

Информация о Продавце