Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
С.К. Клини, Математическая логика
• Бесплатно скачать книгу, 6.09 Мб, формат .djvu
Перевод с англ., Москва, 1973 (формальная логика, изложение только для специалистов)
Глава I. Исчисление высказываний
§ 1. Лингвистические соображения; формулы
§ 2. Теория моделей; таблицы истинности, общезначимость
§ 3. Теория моделей; правило подстановки, совокупность общезначимых формул
§ 4. Теория моделей; импликация и эквивалентность
§ 5. Теория моделей; цепи эквивалентностей
§ 6. Теория моделей; двойственность
§ 7. Теория моделей; отношение следования
§ 8. Теория моделей; сокращенные таблицы истинности
§ 9. Теория доказательств; доказуемость и выводимость
§ 10. Теория доказательств; теорема о дедукции
§ 11. Теория доказательств; непротиворечивость, правила введения и удаления
§ 12. Теория доказательств; полнота
§ 13. Теория доказательств; употребление выводимых правил
§ 14. Применения к естественному языку; анализ рассуждений
§ 15. Применения к естественному языку; неполные рассуждения
Глава II. Исчисление предикатов
§ 16. Лингвистические соображения; формулы, свободные и связанные вхождения переменных
§ 17. Теория моделей; предметные области, общезначимость
§ 18. Теория моделей; основные результаты об общезначимости
§ 19. Теория моделей; дальнейшие результаты об общезначимости
§ 20. Теория моделей; следование
§ 21. Теория доказательств; доказуемость и выводимость
§ 22. Теория доказательств; теорема о дедукции
§ 23. Теория доказательств; непротиворечивость, правила введения и удаления
§ 24. Теория Доказательств; замена, цепи эквивалентностей
§ 25. Теория доказательств; изменения кванторов, предваренная
форма
§ 26. Применения к естественному языку; множества, аристотелевские категорические силлогизмы
§ 27. Применения к естественному языку; еще о переводе слов символами
Глава III. Исчисление предикатов с равенством
§ 28. Функции
§ 29. Равенство
§ 30. Равенство как эквивалентность; экстенсиональность
§ 31. Описательные определения
Глава IV. Основания математики
§ 32. Счетные множества
§ 33. Канторовский диагональный метод
§ 34. Абстрактные множества
§ 35. Парадоксы
§ 36. Математика аксиоматическая и математика интуитивная
§ 37. Формальные системы, метаматематика
§ 38. Формальная арифметика
§ 39. Некоторые другие формальные системы
Глава V. Вычислимость и разрешимость
§ 40. Разрешающие и вычислительные процедуры
§ 41. Машина Тьюринга, тезис Чёрча
§ 42. Теорема Чёрча (в терминах машин Тьюринга)
§ 43. Применения к формальной арифметике; неразрешимость
(теорема Чёрча) и неполнота (теорема Гёделя)
§ 44. Применения к формальной арифметике; доказательства непротиворечивости (вторая теорема Гёделя)
§ 45. Применения к исчислению предикатов (Чёрч, Тьюринг)
§ 46. Степени неразрешимости (Пост), иерархии (Клини, Моетовский)
§ 47. Теоремы о неразрешимости и неполноте, использующие лишь простую непротиворечивость (Россер)
Глава VI. Исчисление предикатов (дополнительные разделы)
§ 48. Теорема Гёделя о полноте; введение
§ 49. Теорема Гёделя о полноте; основной результат
§ 50. Теорема Гёделя о полноте для формальных систем генценовского типа теорема Лёвенгейма-Скулема
§ 51. Теорема Гёделя о полноте для формальных систем гильбертовского типа
§ 52. Теорема Гёделя о полноте и теорема Лёвенгейма-Скулема
для исчисления предикатов с равенством
§ 53. Парадокс Скулема и нестандартные модели арифметики
§ 54. Теорема Генцена
§ 55. Перестановочность теорема Эрбрана
§ 56. Интерполяционная теарема Крейга
§ 57. Теорема Бета об определимости; теорема Робинсона о непротиворечивости
Краткая аннотация книги
Имя одного из крупнейших современных специалистов в области математической логики С.К. Клини знакомо советскому читателю по русскому переводу его фундаментального труда "Введение в метаматематику" (ИЛ, 1957), ставшего настольной книгой для всех, кто занимается математической логикой, рекурсивными, функциями и основаниями математики. Новая его книга представляет собой существенно усовершенствованный, расширенный и приближенный к нуждам университетского преподавания вариант "чисто логической" части этой всемирно известной монографии. Тщательно продуманные иллюстративные упражнения помогают читателю усвоить излагаемый, материал.
Книга может быть использована,как учебное пособие по курсу математической логики в университетах и пединститутах; таким образом, она адресована прежде всего преподавателям, аспирантам и студентам. Она привлечет также внимание всех занимающихся или интересующихся математической логикой.
Имя автора этой книги не нуждается в рекомендации. На его "Введении в метаматематику" выросло не одно поколение специалистов по математической логике и основаниям математики. Отличия настоящей книги от классического "Введения" достаточно ясны из авторского предисловия. В двух словах они сводятся к тому, что перед нами теперь не руководство, претендующее (и не без оснований) на полноту освещения обширного комплекса проблем, а университетский учебник. С другой стороны, в этот учебник, несмотря на его скромный объем, попали многие вопросы, не нашедшие места в большой книге Клини (например, иерархия степеней неразрешимости, интерполяционная теорема, теоремы Бета и Робинсона).
Существенно и то, что характерный для "большого Клини" финитный, метаматематический, теоретико-доказательственный подход здесь часто заменяется теоретико-множественным, модельным. Как и во "Введении в метаматематику", автор тщательно различает конструктивные и неконструктивные доказательства. И все-таки трудно отделаться от ощущения, что в этой книге он охотно отдает предпочтение вторым. Считая излишним загромождать подобное издание ссылками и комментариями, мы предпочитали следовать автору, отсылая читателя в нужных случаях за разъяснениями к "Введению в метаматематику".
Исключение сделано лишь для теорем Генцена и Эрбрана. По разным причинам представляется желательным иметь метаматематические доказательства этих теорем, играющих вместе со своими обобщениями столь важную роль в современной теории доказательств. Этим доказательствам посвящены небольшие добавления редактора перевода. После выхода в свет моего "Введения в метаматематику" (1952), предназначенного для студентов старших курсов1), я не собирался писать другую книгу. Но в силу различных обстоятельств мне пришлось размышлять о необходимости краткого изложения отдельных разделов "Введения", рассчитанного на более широкую аудиторию или на менее подготовленных читателей. Эти размышления привели меня к новым вариантам изложения2), и благоприятный прием, который они встретили, в конечном счете и склонил меня к тому, чтобы подготовить теперешнюю книгу, рассчитанную на начинающих3).
Во "Введении в метаматематику" (в дальнейшем цитируется как [ВМ]) изложение математической логики как таковой начиналось лишь с пятой главы (на основе некоторых определений, данных в гл. IV). Подготовленные студенты могут пройти вводный ¦ материал первых глав [ВМ] достаточно быстро. Но для менее, подготовленных студентов или в условиях, когда на курс отведено меньше времени, трата времени на столь подробное введение является ненужной роскошью. И теперь я пришел к убеждению, что как с педагогической, так и с научной точек зрения более разумно с самого начала приступать непосредственно к изучению логики, даже если и не все мотивы и не все критерии выбора того или иного способа изложения выявлены заблаговременно. А соответствующее "введение" можно сделать и позже.
Исходя из этих соображений, я отвел часть 1 (гл. I-III) настоящей книги достаточно подробному, хотя и элементарному рассмотрению математической логики (узкому исчислению предикатов), что по существу соответствует материалу гл. V-VII и § 73 [ВМ]. Изложение здесь не Исчерпывается каким-либо одним вариантом формулировки логической теории и приобретением должных навыков в этом направлении, что можно было бы сделать даже и на более элементарном уровне. Для работ современных логиков характерно весьма гибкое изложение материала, использующее различные формулировки одних и тех же идей, с переходами от одной формулировки к другой, более соответствующей конкретным целям данного момента. В соответствии со сказанным читатель в части I книги встретится сначала с более полным, нежели в [ВМ], изложением теории моделей (основанном на истинностных таблицах), затем с гильбертовской теорией доказательств (основанной на системах постулатов с правилом modus ponens) и, наконец, с теорией доказательств, пользующейся и производными правилами вывода. Эти производные правила по существу очень близки к правилам, принятым в генценовских системах натурального вывода, которыми я пользуюсь при преподавании логики начиная с 1936 г. (В гл. VI вводится четвертая формулировка логики в виде генценовских секвенциальных систем.)
Вторая часть книги задумана как дополнение к первой (в предположении, что та усвоена достаточно основательно) и как введение в некоторые новые идеи и более глубокие результаты логических исследований нашего времени. В части II изложение носит менее элементарный характер, чем в части I. В зависимости от времени, отводимого на курс, и степени подготовки аудитории часть Ч11 можно проходить в обзорном порядке или же более подробно. Я никогда не считал, что среднему студенту полезно пропускать весь трудный материал, полностью овладеть которым могут лишь самые сильные студенты. Все -же мой опыт преподавания показывает, что если опускать более специальные параграфы, отмеченные звездочками, то в течение одного семестра удается пройти часть материала гл. VI.
Если говорить о содержании части II более конкретно, то гл. IV Служит запоздалым "введением" (сокращенным вариантом гл. I - III [ВМ]) и содержит также введение и в общий очерк формальной арифметики (гл. IV и VIII [ВМ]). Глава V содержит обзор знаменитых результатов Гёделя, Чёрча и др., касающихся неполноты и неразрешимости; изложение ведется в терминах машин Тьюринга, зачастую без подробных доказательств. (Обзор этот касается основных результатов § 42 и части III [ВМ], но не касается подробностей развитой там теории.) Эти главы посвящены не столько чистой логике, сколько основаниям математики.
В гл. VI основное внимание вновь уделяется логике. Теорема Гёделя о полноте и теорема Генцена (а также теоремы Лёвенгейма, Скулема, Эрбрана, Генкина, Бета, Крейга и А. Робинсона) доказываются здесь с помощью методов, получивших распространение лишь начиная с 1955 г. Имеются более компактные доказательства теоремы Гёделя о полноте. Избранный здесь способ изложения основ предмета удобен, по-видимому, тем, что почти с самого начала ясно общее направление движения, а кроме того, можно надеяться, что, проявив достаточно терпения при рассмотрении деталей, мы в" конце концов достигнем цели. Кроме того, такой подход позволяет быстро (хотя и неконструктивно) доказать теорему Генцена. (Глава эта соответствует части IV [ВМ], но сильно отличается от нее по общему подходу и отбору результатов.)
Прохождение всего материала гл. VI в течение одного семестра может быть облегченб за счет того, что гл. IV и V полностью исключаются из курса, который, таким образом, минуя вопросы оснований математики, полностью сосредоточивается на проблемах логики. (Из материала гл. IV и V лишь очень немногое используется затем в гл. VI, так что, опуская эти две главы, мы пожертвуем очень немногим из содержания последней главы.) В книге довольно много упражнений, но они не покрывают всех рассматриваемых в ней вопросов (особенно это относится к части II).
Книга не предназначена быть пособием для решения задач. При ее чтении следует отказаться от психологии первокурсника, полагающего, что учебник только для того и нужен, чтобы помогать в решении упражнений. Для настоящего понимания духа предмета особенно важно овладение определениями.
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.