И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года)

ВВК гг.)г Л18 УДК Я0.2+ Я0.5+ 510.8 Издание осуществлено при финансовой поддержке Российскою фондо фундаментальных исследований согласно проекту 94-01-2/0001 Лавров И.А., Максимова Л.Л. Задачи потеории множеств, математической логике и теории алгоритмов.— 3-е изд.— Мс Физматлит, 1995.— 1ЯВВ) 5-02-0! 4844-Х. В книге систематически изложены основы теории множеств, математической логики и теории алгоритмов в форме задач. Книга предназначсна для активного изучеяив математической логики и смежных с ней наук. Состоит из трех частей: «Теория множеств», «Математическая логика» и «Теория алгоритмов».

Задачи снабжены указаниями и ответами. Все необходимые определени» сформулированы в кратких теоретических введениях к каждому параграфу. 2-е издание — 1984 г. Сборник может быть использован как учебное пособие для математических факультетов университетов, педагогических институтов, а также в технических вузах при изучении кибернетики и информатики. Для математиков — алгебраистов, логиков и кибернетиков. 1 11 1б02020000-004 053(02) — 95 г 8 В 1»1 5-02-014844-Х Ю НЛ. Лавров, ЛЛ.

Мы««мам, а»ы СОДЕРЖАНИЕв> 4 5 Ответы, решения, указания Список литературы... Предметный указатель 158 248 250 Предисловие к третьему изданию Предисловие к первому изданию . Час!и ь А Теория множесш 8 1. Операции над множествами 8 2. Отношения и функции .

8 3. Специальные бинарные отпев~ения .... 8 4. Кардинальные числа $5. Ординальиые числа 8 6. Действия над кардинальными числами, Часть П. Математическая логика . 8 1. Алгебра высказываний . $2. Функции алгебры логики 8 3. Исчисления высказываний . 8 4. Язык логики предикатов 8 5.

Выполнимость формул логики предикатов 8 6. Исчисления предикатов . 8 7. Аксиоматические теории б 8. Фильтрованные произведения 8 9. Аксиоматизируемые классы . Часгпь ПА Теория алгоритмов . 8 1. Частично рекурсивные функции б 2. Машины Тьюринга . 8 3. Рекурсивные и рекурсивно перечислимые множества ... 8 4. Нумерации Клини и Поста . *) Пифры в скобках указывают страницы ответов. 7 7 (155) 13 (160) 22 (165) 31 (!70) 35 (! 76) 44 (183) 50 50 (187> 57 (!9!) 63 (195) 74 (200) 81 (201> 89 (206> 98 (209> !08 (215> !16 (2!9) 124 !24 (227) 136 (234> !42 (237) 148 (242> ПРЕДИСЛОВИЕ К ТРЕТЬЕМУ ИЗДАНИЮ В последние годы интерес к математической логике значительно возрос ввиду широкого распространения вычислительной техники и развития информатики, появления логического программирования, исследования проблем искусственного интеллекта. В основе программирования лежат базисные понятия математической логики — формализованные языки, исчисления, семантические модели.

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

Хотя количество задач почти не изменилось, многие из них переформулированы. К ряду задач даны более подробные ответм. Несколько обновлен список литературы, в него включены монографии по математической логике, опубликованные на русском языке после выхода в свет второго издания книги.

Авторы благодарны коллегам за полезные замечания и предложения. И.А. Лавров Л.Л. Максимова ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ В настоящее время математическая логика и смежные с ней науки привлекают все большее внимание. Это вызвано как интенсивным развитием самих этих наук, так и найденными глубокими приложениями в различных областях математики и техники. Курс математической логики несколько лет назад стал обязательным для математических факультетов университетов и педагогических институтов СССР.

На первых порах большой отряд студентов и преподавателей был практически лишен учебных пособий по этой специальности. В настоящее время этот недестаток в некоторой степени исправлен. Сейчас имеется ряд учебников и книг по математической логике. Здесь и несколько книг советских авторов, но в основном это переводная литература.

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

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

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

Большинство задач каждой части может быть решено без обращения к другим частям. Там, где необходимо, мы делаем соответствующие ссылки в самой задаче нли в указании к ней. ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ 1 декабря 1973 г. г. Новосибирск Академгородок И.

!. Лавров Л.Л. Максимова Естественно, что в книге не затронуты многие направления современной математической логики. Некоторые темы лишь намечены, для них приведены лишь самые первоначальные понятия н результаты. Так, например, аксиоматическая теория множеств !5 7 части 1!) занимает мало места, хотя в действительности все задачи из части 1 могут быть решены в рамках теории ЕР. В части 1П из различных уточнений понятия алгоритма выбраны лишь рекурсивные функции и машины Тьюринга. Мы ставили себе целью 'главным образом систематизировать уже имеющиеся задачи.

По этой причине здесь имеется стандартный набор задач н очень мало задач, специально придуманных авторами. Если задачи нам нравились, то мы брали их из других книг и не ссылались на эта. В книге употребляются следующие общепринятые обозначения; Ф; Я', й, У, Я вЂ” множества натуральных, целых, рациональных, действительных, комплексных чисел соответственно; ~ — если ..., то ...; «» — ...тогда н только тогда, когда ...; — есть по определению; (х !...х...) — множества таких элементов х, для которых выполняется условие ...х...; (х, х, ...) — множества, состоящее из элементов х, х, ...; (х, х, ..., х ) — упорядоченная последовательность элементов 1' 2''" и хпх2, ...,Х .

В основу этой книги положен наш сборник «Задачи по логике», выпущенный в ! 970 г. издательством Новосибирского государственного университета, Сборник значительно дополнен, сделана существенная переработка, мы пастаралнсь учесть многочисленные замечания, высказанные нам. Мы благодарны Л.Н. Шеврину, А.И. Омарову, Н.Г.

Хисамиеву, А.А. Акатаеву, В.А. Успенскому, Г.Е. Мннцу, С.Ю. Маслову, А.О. Слисенко, И.Д. Заславскому и другим за ценные обсуждения. Особо мы благодарны Ю.Л. Ершову, М.И. Каргаполову н М.А. Тайцлину, а также другим членам кафедры алгебры и математической логики НГУ за большую помощь при подготовке этой книги.

Мы глубока признательны Н.В. Белякину за большой труд по редактированию нашей книги. ЧАСТБ 1 ТЕОРИЯ МНОЖЕСТВ $1. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Через Е обозначается отношение принадлежности, т. е. х Я Л означает, что элемент х принадлежит множеству А. Если х не является элементом множества А, то это записывается х Ю А. Два множества А и В считаются равными, если они состоят из одних и тех же элементов. МыпишемА В, еслиАиВравны, нА ов Вв противномслучае.

Через ь обозначается отношение включения множеств, т. е. А ь В означает, что каждый элемент множества Л является элементом множества В. В этом случае А называется подмножеством В, а  — надмножест вам А. Если А С В и Л м В, то А называется собственным подмножеством В, и в этом случае пишем А С В. Множество, не содержащее элементов, называется пустым и обозначается через и. Семейство всех подмножеств данного множества А обозначается через Р(А). Объединением множеств Л и В называется множество А1.1В = (х ~ х Е Л или х Е В).