Колмогоров, Драгалин - Введение в математическую логику

А. Н. Колмогоров. А. Г. Драгалин ВВЕЛ,ЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ донунтено т ашгмстерством высшего и среднего сиецнааьногю образования СССР в качестве учебного оособвя для студентов математических оиациальяостей вузов у~ Г ИЗДАТЕЛЬСТВО атосковского университета 1282 УДК 517.1 Колмогоров А. Н,, Драгалии А. Г. Введение' в математическую логику. — М.: Иад-во Моск, ун«та„1989. — 120 с. Учебное пособие предназначено для начинающих математиков, которые желают ознакомиться со строением мате.

матического языка и математичесиих теорий. Наряду с накальными понятиями теории множеств излагачотся основы логики выскбзыпамкй и леньки предикатов. Изложение не предполагает специальных знаний и рассчитано на студентов младших курсов, Виблиогр. 9 наив. Ил. 2 Репензен,ты: ка«Рещра высшей митемвтиии № 2 Ленинградского политохнического института; чл..кор.

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

Т. С. И~инякова ' те атычес иа план пмз г, м 19 ИБ За 10»з сдаво в ааеор тает.зт. подписано к певала 00.1злз, оорват 60Хзоум Буыага ччм. М 3, Гарквсура жюврвтурвая. Высокая печать Уел, печ. л. Т,Ш. Уч.-изд. л. 0,00. Заи. Зта. Тираж ГЗ ИНГ зкз. Пене За коп. Изд. ЗЬ 0540. Ордена «Знак Почечв» вздвтепьсзво Московсиого университета. 1Окни, мооква, ул. Герпеиа, злк Т1кпография ордвна «злак почета» иад-ва МГУ.

Москва, Лене«говне горы © Издательство Московского университета, 1982 г. ОГЛАВЛЕНИЕ Предисловие Введение Глава ! Глава П. Глава 11Е Р 116 !18 120 Прилож Прилож Литерат ура НАЧАЛЬНЫЕ ПОНЯТИЯ МАТЕМАТИЧЕСКОЙ ЛО* ГИКИ И ТЕОРИИ МНОЖЕСТВ...... 10 $1. Синтаксис языка математяческвх и логических знаков . . . .. . . . , . . .

10 $2. О классификации суждений н теории силлогизмов по Аристотелю . . . . . . . . . 15 $3. О понятии множества . . . , . .- . 19 $4. Отношения и функции . . . . . . . 22 $ 5. Математические структуры . . . . ', . 26 $6. Булеза алгебра . . . . . . . . . 31 6 7. Логика высказываний . . . . , . , 41 $8. Исчисление высказываний . . .

. . . . 45 $9. О логике предикатов . . . . . . . . 49 ЛОГИКО-МАТЕМАТИЧЕСКИЕ ЯЗЫКИ. ЛОГИЧЕСКИЕ ЗАКОНЫ.......... 52 $1. Язык первого порядка. Форнулы и термы .. 52 $2. О правильной подстановке тернов в формулы . 65 3. Семантика язмка. Истинность в модели... 70 4. Примеры языков и моделей...... 77 $5. Логические законы........

83 6 6. Приложения теории логмко-математических языков, Предвареиная форма. Дизъюиктнвнан и коньюиктивмая нормальная форма. Язык логики вы. сказываний и логики преднкатов..., . 91 ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ .. 95 1. Исчисление предикатов . . . . . . . 95 2. Теорема о дедукции. Техника естественного вывода . 100 3. Формальные аксноматические теории. Приме ы формальных аксиоматнческих теорий е вне 1.

Кодирование с исправлением. ошибок ение 2. Прмменевмн к. контактным схемам предисловие Эта книга задумана как первоначальный курс чатематичесйой логики. Она возникла в результате обработки конспектов лекций (читавшихся обоими авторами) семестрового . курса математической логики для студентов первого курса механико-математического факультета Московского университета.

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

Во второй главе в уточненной форме излагаются основы семантики логико-математических языков. Третья глава посвящена изложению выводимости в логике предзкатов и теориям первого порядка. Уже здесь мы стремились обсудить некоторые важные результаты математической логики, отложив полные доказательства до'второй части, в которой предполагается изложить начала теории множеств и теории алгорифмов, теорему Геделя о полноте исчисления предикатов, обсудить программу Гильберта обоснования математики.

' Изучение курса логики предполагает выполнение упражнений на семинарских занятиях. С этой целью следует использовать специальные задачники, например ~91. Все упражнения в тексте легкие, обязательны для выполнения, предназначены для самоконтроля и не могут заменить такого рода задачника. В книге используются следующие обозначения. Знак в тексте отмечает начало доказательства, а знак Б — его окончание. Знаки =, =~-, «=.

заменяют словесные обороты «есть по определению», «если, то», «тогда и толы;о тогда, когда» соответственно. Звездочкой отмечены пункты и параграфы, не обязательные при первом чтении. 4 ' Мы' предприняли.попытку концентрического нзложения предмета, когда важнейшие темы обсуждаются в процессе обучения несколько раз, постепенно приобретая полную' ясность.

Учебник разбит на две книги. Во второй книге, принятой к печати издательством Московского университета, предполагается большее внимание уделить фундаментальным результатам математической логики. Мы вновь вернемся к рассмотрению понятия множества, но уже на базе формальной аксиоматнческой теории Цермело — Френкеля.

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

Несомненен' интерес к логике среди математиков и философов эпохи расцвета греческой культуры в Ч1 — 11г вв, до н. э. Но первое дошедшее до нас большое сочинение, посвященное специально логике («Аналитики» Аристотеля, 384 — 322 гг, до н. э.), принадлежит уже позднегреческой эпохе. Независимо возникла буддистская логика, но дальнейшее развитие Логики в Европе имеет своим исходным-пунктом изучение Аристотеля. Математическая логика с внешней стороны отличается от «обычной» тем, что она широко пользуется языком математических и логических знаков, исходя из того, что в принципе они могут совсем заменить слова обычного языка и принятые в обычных живых языках способы объединения слов в предложения. Довольно рано возникла идея о том, что, записав все исходные допущения на языке специальных знаков, похожих на математические, можно заменять рассуждение вы числением гТочно же сформулированные правила таких логических вычислений можно перевести на язык вычислительной машины; которая тогда будет способна автоматически выдавать интересующие нас следствия из введенных в нее исходных допущений.

Своего рода «логическую машину» сконструировал еще в средние века Раймунд Луллий- (1235— 1315), дав ей, впрочем,,лишь совершенно фантастические применения. Более определенный и близкий к реально осуществленному впоследствии замысел универсального логического исчисления развивал Лейбниц (1646 — 1716). Лейбниц надеялся даже, что в будущем философы вместо того, чтобы бесплодно спорить, будут брать бумагу и вычислять, кто из них прав.

.Начало созданию того аппарата математической логики, который теперь мы называем логикой высказываний, положил Джордж Буль (1815 — 1864). Логико-математические языки и теория их смысла были затем значительно развиты в работах Фреге (1848 — 1925). Широко задуманное изложе. ние больших разделов математики на языке математической логики было предпринято в работах Пеано (1858 — 1932) н особенно в фундаментальной трехтомной монографии Рассела и Уайтхеда, изданной на 1910 †19 гг.

В двадцатых годах нашего века с программой обосйования математики на базе математической логики. выступил знаменитый математик Гильберт (1862 †19). С этого времени и начинается современный этап развития математической логики, характеризующийся применением точных математических методов при изучении формальных аксиоматических теорий.

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