Интенсивное развитие математической логики в последнее время сопровождается увеличением её роли в математике.
Одной из основных задач математической логики остаётся анализ оснований математики. Но в настоящее время она уже вышла из рамок этой задачи и оказала существенное влияние на развитие самой математики.
Из её идей возникло точное определение понятия алгоритма, что позволило решить многие вопросы, которые без этого остались бы в принципе неразрешимыми. Возникший в математической логике аппарат нашёл применение в вопросах конструкции вычислительных машин и автоматических устройств.
Автор этой книги, выдающийся советский математик, академик Петр Сергеевич Новиков, родился в августе 1901 года.
Свою научную деятельность П. С. Новиков начал в двадцатые годы в области дескриптивной теории множеств. Петру Сергеевичу принадлежат глубокие научные результаты в области теории множеств, математической логики, теории алгоритмов и теории групп. Исключительная роль П. С. Новикова в развитии этих областей математики в СССР определяется также его многолетней педагогической деятельностью в МГПИ им. В. И. Ленина и в МГУ им. М. В. Ломоносова. П. С. Новиков создал большую научную школу в области математической логики и теории алгоритмов.
Его книга «Элементы математической логики», являющаяся первым отечественным курсом математической логики, пользуется большой популярностью как в нашей стране, так и за рубежом. Она переведена на английский, французский, итальянский и другие языки. В 1973 году вышло второе русское издание этой книги.
В книге Э. Мендельсона «Введение в математическую логику» дается доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих ее приложений.
Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств, отсутствующие в книге С. К. Клини «Введение в метаматематику», которая до настоящего времени служила наиболее полным пособием по математической логике. Следует, однако, отметить, что в отличие от книги С. К. Клини в этой книге по существу не затрагиваются интуиционистское и конструктивное направления математической логики.
Изложение материала в книге ясное и лаконичное. Основной текст перемежается с большим числом примеров и упражнений. В упражнения автор вынес также некоторые результаты, используемые затем в основном тексте. Это, наряду с лаконичностью изложения, способствовало сокращению размеров книги при весьма обширном содержании.
Человек тратит многие годы на учение и повседневную практику, прежде чем его начинают называть настоящим мастером своего дела. И лишь незначительную часть накопленных знаний и опыта удается ему использовать в новой области, если почему-либо приходится круто изменять специализацию.
Причины такого положения достаточно очевидны. Много ли общего, например, в работе электромонтера и учительницы, физиолога и чекиста? Можно ли сопоставить действия математика, слушающего доказательство новой теоремы, и искателя, готовящегося к очередному таежному путешествию, работника министерства, читающего сводки с предприятий, и радиотехника, ремонтирующего телевизор?
Тем не менее во всех перечисленных примерах разнообразных видов человеческой деятельности (число таких примеров можно было бы увеличивать до бесконечности) есть существенно общие черты. Это общность заключается в первую очередь в необходимости увязывать причины со следствиями, воздействуя с результатами, одни действия с другими действиями.
Мы продолжаем формализованное описание математики. Основным объектом первой части курса было математическое доказательство; было показано, что его подходящим формальным аналогом является понятие вывода в языке, после чего самые интересные результаты утверждали невозможность осцлерательных математических утверждений (например, гипотезы континуума).
Основным объектом этой второй части курса будет детерминированный процесс вычисления, или переработки нечисловой информации, короче, алгоритм. Будет построено подходящее формальное описание алгоритмов (точнее, результаты их действий), и самые интересные результаты окажутся утверждением о несуществовании алгоритмов, вычисляющих содержательно описываемые функции.
Содержанием математической логики является изучение языка математики. Разумеется, забота о языке и постоянная его перестройка для приведения в соответствие с меняющимся состоянием знаний характерна для любой естественной науки (ср. судьбу “флогистона” и “мирового эфира” в физике).
Тем не менее, необходимая работа обычно осуществляется по ходу дела, и то пристальное критическое рассмотрение, которому математика подвергла самое себя и свои средства выражения, представляется уникальным.
Причина этого состоит, конечно, в том, что все остальные естественные науки имеют предмет, внешний им, и эволюция языка наук определяется постоянным сравнением научного описания с описываемой реальностью.
Имя одного из крупнейших современных специалистов в области математической логики С. К. Клинк знакомо советскому читателю по русскому переводу его фундаментального труда “Введение в метаматематику” (ИЛ, 1957), ставшего настольной книгой для всех, кто занимается математической логикой, рекурсивными функциями и основаниями математики. Новая его книга представляет собой существенно усовершенствованный, расширенный и приближенный к нуждам университетского преподавания вариант чисто логической части этой всемирно известной монографии. Тщательно продуманные иллюстративные упражнения помогают читателю усвоить излагаемый материал.
Книга может быть использована как учебное пособие по курсу математической логики в университетах и пединститутах; таким образом, она адресована прежде всего преподавателям, аспирантам и студентам. Она привлекает также внимание всех занимающихся или интересующихся математической логикой.
Предлагаемая читателю книга представляет собой введение в проблематику и методы теории нумераций - нового развивающегося раздела теории алгоритмов. Насколько известно автору, впервые идею о систематическом изучении нумерованных множеств высказал А. Н. Колмогоров в середине пятидесятых годов. Реализацией этой идеи для вычислимых нумераций в то время занялся В. А. Успенский.
Основные его результаты изложены в статье 63 и в книге 10, вышедшей в 1960 году. Параллельно ряд зарубежных математиков (Райс, Деккер, Майхилл, Фридберг, Лахлан, Лакомб, Пур-Эль и др.) также занимались изучением различных вопросов, связанных с вычислимыми нумерациями. Независимо были осуществлены попытки изучения нумерованных алгебр (Фрелих — Шепердсон, Рабин), которые также обнаружили интересные специфические «нумерационные» особенности.
Предлагаемый сборник задач составлен в соответствии с программой университетского курса «Элементы математической логики и алгебры множеств».
Первые четыре параграфа посвящены двоичной булевой алгебре и ее применению в теории релейно-контактных схем, а также исчислению высказываний и предикатов. Большая часть задач двух последних параграфов связана с бинарными отношениями, которые получают все большее применение в различных областях математики.
Задачник снабжен ответами и указаниями, каждому разделу предпослано небольшое теоретическое введение.
Сборник может быть использован как пособие для учащихся юношеских математических школ и всех самостоятельно изучающих соответствующие разделы математики.
Настоящая книга написана на основе лекций, читавшихся П. С. Новиковым во второй половине пятидесятых годов.
В ней излагаются вопросы математической логики, не рассмотренные в первой книге. В этом смысле она как бы дополняет предыдущую книгу.
В то же время книга написана так, что ее можно читать независимо от предыдущей. В частности, в ней подробно излагается весь нужный по ходу дела материал, относящийся к классическим логическим исчислениям.