Читать онлайн «Задачи по теории множеств, математической логике и теории алгоритмов»

И. А. Лавров, Л. Л. Максимова ЗАДАЧИ ПО ТЕОРИИ МНОЖЕСТВ, МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ Издание пятое МОСКВА • ФИЗМАТЛИТ • 2004 УДК 510. 2+510. 5+510. 6 ББК 22. 12 Л 13 Лавров И. А. , Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — 5-е изд. , исправл. — М. : ФИЗ- МАТЛИТ, 2004. - 256 с. - ISBN 5-9221-0026-2. В книге в форме задач систематически изложены основы теории множеств, математической логики и теории алгоритмов. Книга предназначена для активного изучения математической логики и смежных с ней наук. Состоит из трех частей: «Теория множеств», «Математическая логика» и «Теория алгоритмов». Задачи снабжены указаниями и ответами. Все необходимые определения сформулированы в кратких теоретических введениях к каждому параграфу Сборник может быть использован как учебное пособие для математических факультетов университетов, педагогических институтов, а также в технических вузах при изучении кибернетики и информатики. Для математиков — алгебраистов, логиков и кибернетиков. © И. А. Лавров, Л. Л. Максимова, 2002, 2003, 2004 ISBN 5-9221-0026-2 © ФИЗМАТЛИТ, 2002, 2003, 2004 СОДЕРЖАНИЕ» Предисловие к четвертому изданию 4 Предисловие к первому изданию 5 Часть 1. Теория множеств 7 § 1. Операции над множествами 7 (155) § 2. Отношения и функции 13 (160) § 3. Специальные бинарные отношения 22 (165) § 4. Кардинальные числа 31 (170) § 5. Ординальные числа 35 (176) § 6. Действия над кардинальными числами 44 (183) Часть II Математическая логика 50 § 1. Алгебра высказываний 50 (187) § 2. Функции алгебры логики 57 (191) § 3. Исчисления высказываний 63 (195) § 4. Язык логики предикатов 74 (199) § 5. Выполнимость формул логики предикатов 81 (201) § 6. Исчисления предикатов 89 (206) § 7. Аксиоматические теории 98 (209) § 8. Фильтрованные произведения 108 (215) § 9. Аксиоматизируемые классы 116 (219) Часть III Теория алгоритмов 124 § 1. Частично рекурсивные функции 124 (227) § 2. Машины Тьюринга 136 (234) § 3. Рекурсивные и рекурсивно перечислимые множества 142 (238) § 4. Нумерации Клини и Поста 148 (243) Ответы, решения, указания 155 Список литературы 248 Предметный указатель 250 Цифры в скобках указывают страницы ответов. ПРЕДИСЛОВИЕ К ЧЕТВЕРТОМУ ИЗДАНИЮ За время, прошедшее после третьего издания этой книги, стало очевидным, что она достаточно актуальна и полезна. Вместе с тем, во многих высших учебных заведениях ощущается крайний недостаток экземпляров книги. Задачник широко используется, а малый тираж последнего издания не смог удовлетворить имеющуюся потребность. В этих условиях издательство «Физико-математическая литература» решило переиздать книгу. За это авторы благодарны издательству. В данном издании мы внесли необходимые переделки задач, ответов, терминологии, расширили список литературы, а также исправили опечатки, вкравшиеся в предыдущие издания. Мы постарались учесть те замечания и предложения, которые были высказаны нашими коллегами, активно использующими книгу в своей преподавательской деятельности.