Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
   С.К. Клини, Математическая логика

   Вы можете  найти на этой странице (программа отметит желтым цветом)
   Вы можете посмотреть  список книг по высшей математике с сортировкой по алфавиту.
   Вы можете посмотреть  список книг по высшей физике с сортировкой по алфавиту.

   • Бесплатно скачать книгу, 6.09 Мб, формат .djvu
   Перевод с англ., Москва, 1973 (формальная логика, изложение только для специалистов)

   Уважаемые дамы и господа !! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши, выберите команду "Save target as ..." ("Сохранить объект как ...") и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.

Глава 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).

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