В книге систематически изложены основы теории множеств, математической логики и теории алгоритмов в форме задач. Книга предназначена для активного изучения математической логики и смежных с ней наук.

Сборник состоит из трёх частей: «Теория множеств», «Математическая логика» и «Теория алгоритмов». Задачи снабжены указаниями и ответами. Все необходимые определения сформулированы в кратких теоретических введениях к каждому параграфу. Сборник рассчитан как учебное пособие для математических факультетов университетов и педагогических институтов. Он может быть использован также в технических вузах при изучении кибернетических специальностей.

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

Курс математической логики несколько лет назад стал обязательным для математических факультетов университетов и педагогических институтов СССР. На первых порах большой отряд студентов и преподавателей был практически лишён учебных пособий по этой специальности. В настоящее время этот недостаток в некоторой степени исправлен. Сейчас имеется ряд учебников и книг по математической логике. Здесь и несколько книг советских авторов, но в основном это переводная литература. И всё же те, кто ведёт практические занятия, испытывают большие трудности. И дело не в том, что задач нет. Большое количество задач по математической логике разбросано по разным книгам. Только в самое последнее время появилась книга С. Г. Гиндикина «Алгебра логики в задачах», где собран обширный материал по алгебре логики.

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

Основные теоремы сформулированы в виде задач. Для того чтобы доказательства теорем были возможно более простыми, технические леммы также выделены в виде отдельных задач.

Большинство задач снабжено ответами и указаниями. Иногда мы даём подробные ответы к простым задачам для иллюстрации метода рассуждения, впервые встретившегося. В дальнейшем же ограничиваемся лишь кратким указанием. Трудные задачи отмечены звёздочкой.

Большинство задач каждой части может быть решено без обращения к другим частям. Там, где необходимо, мы делаем соответствующие ссылки в самой задаче или в указании к ней.

Естественно, что в книге не затронуты многие направления современной математической логики. Некоторые темы лишь намечены, для них приведены лишь самые первоначальные понятия и результаты. Так, например, аксиоматическая теория множеств (§ 7 части II) занимает мало места, хотя в действительности все задачи из части I могут быть решены в рамках теории ZF. В части III из различных уточнений понятия алгоритма выбраны лишь рекурсивные функции и машины Тьюринга.

Мы ставили себе целью главным образом систематизировать уже имеющиеся задачи. По этой причине здесь имеется стандартный набор задач и очень мало задач, специально придуманных авторами. Если задачи нам нравились, то мы брали их из других книг и не ссылались на это…

В основу этой книги положен наш сборник «Задачи по логике», выпущенный в 1970 г. издательством Новосибирского государственного университета. Сборник значительно дополнен, сделана существенная переработка, мы постарались учесть многочисленные замечания, высказанные нам…

ПРЕДИСЛОВИЕ
И. А. Лавров
Л. Л. Максимова
1 декабря 1973 г.
г. Новосибирск, Академгородок

Книги на ту же тему

1. Теория измеримых множеств и мультимножеств, Петровский А. Б., 2018
2. Арифметика. Алгоритмы. Сложность вычислений: Популярное введение в теорию чисел и арифметическую теорию сложности, Гашков С. Б., Чубариков В. Н., 1996
3. Основания теории множеств, Бар-Хиллел И., Френкель А. А., 1966
4. Лекции по дополнительным главам математического анализа, Соболев В. И., 1968
5. Введение в математическую логику, Колмогоров А. Н., Драгалин А. Г., 1982
6. Заметки по логике, Линдон Р., 1968
7. Теория алгоритмов: основные открытия и приложения, Успенский В. А., Семёнов А. Л., 1987
8. Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
9. Дополнительные главы математического анализа. Учебное пособие для студентов физико-математических факультетов педагогических институтов, Макаров И. П., 1968
10. Введение в теорию моделей и метаматематику алгебры, Робинсон А., 1967
11. Теорема Гёделя о неполноте, Успенский В. А., 1982
12. Логический подход к искусственному интеллекту: от классической логики к логическому программированию, Тей А., Грибомон П., Луи Ж., Снийерс Д., Водон П., Гоше П., Грегуар Э., Санчес Э., Дельсарт Ф., 1990
13. Структура данных и управление, Куцык Б. С., 1975
14. Введение в дискретную математику, Яблонский С. В., 1979
15. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989