Элементы теории множеств и математической логики

DjVu

      ПРЕДИСЛОВИЕ
      Эта книга предназначается в первую очередь для учителей математики общеобразовательных средних школ; она может оказаться небесполезной и будущим учителям — студентам пединститутов, а также школьникам старших классов, интересующимся математикой. Книга посвящена роли и месту идей современной Математики в школьном преподавании. Даже при беглом просмотре наших, (да и зарубежных) школьных учебников можно заметить появление в них вопросов, относящихся к двум разделам современной математики: теории множеств и математической логике. Освоение этой новой и непривычной тематики проходит далеко не безболезненно, причем в особенно трудном положении оказываются учителя старших поколений, во время своей учебы не изучавшие эти разделы. Сейчас, конечно, положение изменилось: появилась довольно обширная общедоступная литература по этим вопросам. Особенно популярной (благодаря многочисленным ее применениям в кибернетике) стала одна, из глав математической логики — так называемая алгебра логики. Теоретико-множественные и логические основы школьной математики неоднократно обсуждались на страницах журнала «Математика в школе» и в другой методической литературе.
      Таким образом, тема «Множества и логика» перестала быть для школьной математики в полном смысле terra incognita (так на средневековых картах обозначались далекие и неизвестные. материки). И все же области эти и их значение для школьной математики освещены явно недостаточно — явление, характерное для эпохи научно-технической революции, когда общеобразовательная школа оказалась на переломном этапе своего развития.
      Для успешного преодоления этого этапа нужна разнообразная литература. Наша книга не претендует на систематичность в изложении теории множеств и математической логики — это не учебник и не учебное пособие. Наша цель — показать, как многие темы алгебры, геометрии и анализа, такие, как «Системы уравнений и неравенств», «Графики функций» и «Элементы аналитической геометрии», могут рассматриваться с единой .точки зрения. Такой синтез приводит и к лучшему пониманию материала, и к экономии во времени.
      В качестве центральных, синтезирующих понятий мы берем понятие высказывательной формы (посвященный ему пятый параграф — основной всего текста) и, конечно, основное понятие математической логики — понятие логического следования, без четкого представления о значении которого нельзя понять, что представляет собой математическое доказательство (об этом говорится во всех параграфах).
      Теория множеств и логика — относительно новые темы для школьной математики. Однако истоки многих их основных положений уходят в классическую древность, к «отцу логики» Аристотелю, а основные идеи современной математической логики были сформулированы Г. В. Лейбницем. Не затрагивая эту предысторию, трудно оценить по существу и современный этап. Поэтому наше изложение, насколько позволяет объем, содержит некоторые исторические сведения. Мы хотели бы показать читателю, что современный этап школьной математики, в котором существенную роль играет логика, не является временной «модой», а опирается на многовековую традицию, ставшую по ряду причин особенно актуальной во время научно-технической революции.
      Вообще же наше изложение носит популярный характер, причем многое (важное даже в рамках нашей темы) здесь не затрагивается, а иные вопросы упоминаются лишь вскользь. Для расширения и углубления сказанного нужна дополнительная литература, к которой мы отсылаем читателя в довольно обширной библиографии.
      В нашей стране теория множеств и математическая логика имеют давние замечательные традиции, связанные с именами Н. Н. Лузина, М. Я. Суслина, П. С. Урысона, Л. В. Келдыш, И. И. Жегалкина, В. И. Гливенко, М. И. Шейнфинкеля и плодотворно работающих до сих пор А. Н. Колмогорова, П. С. Александрова, А. А. Маркова и Д. А. Бочвара. Приобрели мировую известность следующие научные школы: теория множеств и математическая логика академика П. С. Новикова (1901 — 1974), математическая логика и алгебра академика А. И. Мальцева (1909 — 1967), основавшие новые глубокие направления на стыке алгебры и логики. П. С. Новиков долгие годы работал в Московском пединституте и Московском университете, а А. И. Мальцев — в Ивановском пединституте и Новосибирском университете. К ним в первую очередь восходят идеи внедрения представлений и методов теории множеств и математической логики в школьную математику. Воздействие их идей постоянно ощущает и автор настоящей книги.
     
      § 1. КАК ВОЗНИКЛА ФОРМАЛЬНАЯ И МАТЕМАТИЧЕСКАЯ ЛОГИКА
     
      Единственное средство усовершенствовать ниши умозаключения состоит в том, чтобы сделать их столь же наглядными, как у математиков, — такими, что их ошибочность можно было бы попросту увидеть, увидеть глазами, а в случае возникновения разногласий достаточно было бы только сказать: «Посчитаем, милостивый государь!», чтобы без дальнейших околичностей стало ясно, кто прав.
      Г. В. Лейбниц
     
      Математика — наука «доказательная». Истинность ее утверждений устайавливается не на основании наблюдений или результатов опыта, а логически выводится из небольшого числа исходных утверждений — аксиом; такой вывод называется (математическим) доказательством. Каждый, кто изучает математику, должен уяснить этот ее характер независимо от того, посвятит ли он себя в дальнейшем этой науке, будет ли ею пользоваться в качестве мощного инструмента исследований в других областях знания или же, наконец, знакомится с ней с общеобразовательными целями.
      Но что значит «логически выводится»? Ниже мы постараемся раскрыть такие часто встречающиеся в математике термины, как «логическое следование», «логический вывод» и многие другие обороты, в которых явно встречается или хотя бы подразумевается эпитет «логический». Он ясно указывает на то, что речь идет об области, известной как логика. Более точно к математике с древних времен примыкала так называемая формальная логика, а в последние десятилетия говорят о математической логике, еще более подчеркивая связь логика — математика.
      В этом параграфе мы кратко и пока достаточно поверхностно проследим историю возникновения математической логики; более содержательному изложению этой науки, особенно ее «школьным аспектам», мы посвятим последующие параграфы.
      В своей целенаправленной практической деятельности человек опирается на законы природы и общества. Знания о них он получает» в основном тремя способами: наблюдая явления и вещи в естественных условиях и накапливая таким образом сведения об окружающем мире; «задавая природе вопросы», т. е. ставя эксперименты в искусственно созданных им условиях; рассуждая и в ходе этих рассуждений получая новые знания из полученных ранее. Эти три метода — источники науки. Доля и вес трех основных методов в разных науках различны, и в зависимости от того, какой метод преобладает, различают описательные (дескриптивные), опытные (экспериментальные, эмпирические) и дедуктивные науки. К дескриптивным наукам относят астрономию, комплекс географических наук (географию, геологию и др.), ботанику, зоологию. К экспериментальным наукам причисляют физику, химию и отчасти биологию. Дедуктивные науки — это математика, логика (а также теоретическая механика и подобные ей «формализованные» разделы других наук).
      В дедуктивных науках главным методом является вывод следствий из небольшого числа исходных положений. Конечно, эти исходные положения в свою очередь являются результатом опыта и наблюдений, но содержание и форма дедуктивных наук характеризуются главным образом тем богатством следствий, которые удается получить рассуждениями. Достаточно сослаться на пример геометрии: какая стройная, многогранная система утверждений вырастает из небольшого числа «очевидных» аксиом Евклида? А закономерности, изучаемые в теоретической механике, получающиеся из законов Ньютона, основанных в свою очередь на наблюдениях Кеплера, Тихо Браге и опытах Галилея! Конечно, следует еще раз подчеркнуть, что указанное различие не вполне четко: подразделение наук на описательные, экспериментальные и дедуктивные довольно-таки относительно. В ходе развития науки соотношение между наблюдением, экспериментом и логическим р|с-суждейием меняется. В частности, в настоящее время явно наблюдается тенденция проникновения логических и математических методов во многие разделы наук, считавшихся до сих пор науками описательными: биологию, экономику, лингвистику. Впрочем, эти вопросы выходят за рамки нашей книги.
      В последние десятилетия наблюдается усиление интереса к методам логических заключений. Одна из важнейших причин — зарождение вычислительной техники. В свое время появление и распространение паровых машин ознаменовало начало эры техники, начало первой научно-технической революции, в ходе которой человек в невиданной до того мере приумножил свои физические силы; появление электрической энергии во второй половине прошлого века еще во много раз увеличило эту ^тенденцию. Научной базой новой техники была физика. А сейчас на наших глазах появились быстродействующие электронно-вычислительные машины с программным управлением, и так же как в свое время паровые машины, электрогенераторы и электромоторы увеличили силу человека и его энерговооруженность, так теперь ЭВМ умножаюу умственные способности человека («вторая научно-техническая революция»). Теперь научная база намного шире. К ней относится, конечно, и физика, особенно радиоэлектроника, но прежде всего логика и математика, что относится уже к нашей теме. Причем, как в свое время (в прошлом столетии и в начале нашего века) рост техники на основе пара и электричества стимулировал широкое развитие термодинамики и электродинамики — центральных разделов физики, так в наше время количественный рост и быстрое усовершенствование ЭВМ стимулирует развитие формальной логики и некоторых разделов математики, Числящихся среди самых абстрактных, — общей алгебры, теории множеств, математической логики и др.
      В научно-популярных журналах и научно-фантастической литературе за последние годы много говорилось об «электронном мозге», поэтому актуален вопрос о том, что представляет собой наш собственный человеческий мозг — согласно каким законам и правилам сам человек, а не машина получает следствия из имеющихся или предполагаемых данных. А это как раз область формальной логики, но также, если внимательно присмотреться, и область математики.
      Формальная логика возникла около 2,5 тыс. лет назад в Древней Греции, главным образом в трудах Аристотеля и его последователей. Достигнув относительно высокой ступени развития, она в отличие от математики прошла затем долгий период застоя и стала снова интенсивно развиваться примерно сто лет назад. При этом она сблизилась с математикой и превратилась в науку, которая теперь называется математической логикой.
      У истоков формальной логики, как мы уже говорили, стоял древнегреческий мыслитель Аристотель (384 — 322 гг. до н.э.), родом он был из города Стагира на фракийском побережье полуострова Халькидика; по месту рождения его часто называют Стагиритом. Отец Аристотеля Никомах был врачом и другом македонского царя Аминта II (393 — 369 гг. до н. э.). Аристотель рос и учился совместно с сыном Аминта — будущим царем Филиппом II Македонским, и на протяжении всей жизни его судьба была тесно связана с македонским царским домом.
      Для продолжения образования Аристотель в возрасте 18 лет отправился в Афины к великому афинскому мыслителю Платону (427 — 347 гг. до н. э.) и провел в его школе — «академии»1 20 лет, вплоть до смерти Платона в 347 г. до н. э.
      1 Название «академия» (от него идет н современный термин «академия») происходит от имени мифического древнегреческого героя Академа. О «Платоновской академии» (она просуществовала с перерывами до эпохи Возрождения) см., например, в «Философской энциклопедии» (М., 1960) статью «Академия Платоновская».
      Аристотель был, несомненно, самым выдающимся из учеников Платона, глубоко усвоившим его знания и идеи. Но это был очень самостоятельно мыслящий ученый, далеко не всегда согласный со своим учителем, особенно в том, что касается мировоззрения. Платон, как известно, был создателем системы объективного идеализма. Аристотель же в основном вопросе философии занимал среднюю позицию между идеализмом и материализмом. Об отношениях между Аристотелем и Платоном часто цитируют изречение: «Платон мне друг, но истина еще дороже» (впрочем, дословно в такой форме это изречение не встречается в трудах Аристотеля). В 343 г. до н. э. царь Филипп пригласил друга своей юности, ставшего тем временем величайшим ученым, в качестве наставника своего сына Александра при царском дворе в г. Пелла. Когда же Александр через несколько лет сам стал царем, знаменитым Александром Македонским, Аристотель вновь вернулся к науке. В 335 г. до н. э. он возвращается в Афины и здесь в предместье Ликей1 собирает вокруг себя учащуюся молодежь, которой читает курсы различных наук.
      1 Отсюда латинизированная форма «лицей».
      Эта школа известна в истории науки и философии как «перипатетическая школа» («перипатос» — прогулка и место прогулки, греч.). Именно в это время Аристотель стал, по сяовам К. Маркса, Александром Македонским греческой философии (см. Маркс К- и Энгельс Ф. Соч. Изд. 2-е, т. 40, с. 156). Следует иметь в виду, что философия в ту эпоху означала совокупность всех наук — энциклопедию. В современном смысле Аристотель был и физиком, и биологом, и психологом, и социологом, и собственно философом (метафизика, этика, эстетика), и, наконец, что существенно для нас, логиком.
      В 323 г. до н. э. умер Александр Македонский, и в Афинах победила антимакедонская партия. Аристотель, как друг и учитель Александра, должен был покинуть Афины. Год спустя он умер, на острове Евбея.
      Логическое учение Аристотеля содержится в его знаменитых книгах: «Категории», «Об истолкованиях», «Первая аналитика», «Вторая аналитика», «Топика», «Софистические опровержения». Эти труды были объединены комментаторами Аристотеля под общим заглавием «Органон» (инструмент). По тогдашним убеждениям его логика представляла собой метод для получения научных знаний, т. е. то, что мы сегодня называли бы методологией науки.
      В «Аналитиках» Аристотель впервые строго обосновал один из первых разделов логики — учение о суждениях и силлогизмах. На протяжении многих столетий,4 вплоть до возникновения математической логики, этот раздел с некоторыми его разветвлениями отождествлялся со всей формальной логикой. Значение этого труда огромно, его часто сопоставляют с «Началами» Евклида, на которые он, несомненно, оказал большое влияние. Об этом мы поговорим более подробно в § 4. Сейчас же мы вкратце остановимся на силлогистике, чтобы на простых примерах пояснить, что представляет собой логический вывод и какие выводы следует считать правильными, а какие — неправильными.
      Вот простой пример:
      «Все птицы — животные»,
      . «Все воробьи — птицы»,
      следовательно, «Все воробьи — животные».
      Первые два предложения называются посылками, последнее — заключением. Здесь все три предложения истинны, причем истинность заключения следует по определенной схеме из истинности посылок. Схема выглядит так:
      «Все В суть С»,
      «Все А суть В», (1)
      следовательно, «Все А суть С».
      Эта схема всегда приводит от верных посылок к верному заключению. Поэтому вывод по такой схеме считается логически правильным; В предыдущем примере это не вызовет сомнения. Но логически правильным будет и такой вывод по схеме (1):
      «Все птицы — животные»,
      «Все цветы — птицы»,
      следовательно, «Все цветы — животные».
      То, что заключение — ложное утверждение, происходит не от неправильности схемы, а связано с тем, что одна из посылок ложна и хорошо налаженная машина может выдать брак, еслиее загрузить недоброкачественным сырьем.
      А вот пример неправильного вывода:
      «Некоторые французы — блондины»,
      «Некоторые курящие — французы»,
      следовательно, «Некоторые курящие — блондины».
      Такой вывод содержит логическую ошибку, несмотря на то что здесь обе посылки и заключение — истинные утверждения; Но вывод был сделан по такой схеме:
      «Некоторые В суть С»,
      «Некоторые А суть В»,
      следовательно, «Некоторые А суть С».
      А так заключать нельзя. Например, по такой схеме мы имели бы:
      «Некоторые, выпуклые фигуры — круги»,
      «Некоторые многоугольники — выпуклые фигуры», — истинные утверждения, а вывод по схеме (II) давал бы «Некоторые многоугольники — круги».
      То есть по схеме (II) можно было бы получить из истинных посылок ложное заключение, а правильными считаются лишь те схемы логических выводов, которые всегда из истинных посылок приводят к истинным заключениям.
      Отметим еще одно обстоятельство — логические выводы делаются по некоторой определенной схеме, и, как мы теперь знаем, аристотелевские силлогизмы представляют собой лишь очень малую часть возможных и употребительных схем. В следующих параграфах мы познакомимся с более общими подходами. Выводы согласно определенным схемам напоминают математические выкладки, аналогичные преобразованиям, используемым при нахождении решений систем уравнений и неравенств. Это обстоятельство было подмечено многими учеными еще в средние века, но особенно на этой стороне логических выводов настаивал великий немецкий ученый Готфрид Вильгельм Лейбниц (1646 — 1716), предложивший детальную программу логических исследований методами математики. Как и Аристотель, Лейбниц был универсальным ученым, внесшим существенный вклад в философию, юриспруденцию, историю, физику и математику. Его имя упоминается наряду с именем И. Ньютона как одного из создателей дифференциального и интегрального исчисления. Но его вклад в математику не ограничивается этим достижением: Лейбница можно считать одним из создателей комбинаторики. Значителен его вклад и в алгебру: к нему восходит теория определителей. Что касается логики, то с аристотелевской силлогистикой Лейбниц познакомился еще 14-летним мальчиком. Как и Аристотель, Лейбниц воспринимал логику как «органон наук», считая, что систему логических рассуждений следует превратить в математическое алгебро-арифметическое исчисление. Но если введенные Лейбницем и Ньютоном понятия производной, первообразной и интеграла сразу же получили дальнейшее развитие в руках современных им математиков, физиков и астрономов, то логические изыскания Лейбница, существенно опередившие эпоху, остались неизвестными до конца XIX столетия, когда они были найдены в его архиве и опубликованы французским математиком Л. Кутюра. Правда, после этого программа логических исследований Лейбница 200-летней давности с учетом, конечно, последующего развития оказала и продолжает оказывать влияние на развитие математической логики.
      Г. В. Лейбниц родился в г. Лейпциге (в Саксонии) в 1646 г.; его отец был профессором этики, а дед с материнской стороны — профессором права Лейпцигского университета.
      От отца, которого Лейбниц потерял в возрасте 6 лет, он унаследовал обширную библиотеку, в которой способный юноша параллельно со своим гимназическим образованием смог дочерпнуть глубокие познания как древней классической, так и современной науки. В частности, он познакомился с логикой Аристотеля. В 1661 г. Лейбниц становится студентом и изучает философию, юриспруденцию и математику в университетах Лейпцига, Иены и Альтдорфа. В 1666 г. он защищает сразу две диссертации на звание доцента: одну — по юриспруденции, другую — по математике. Затем Лейбниц служит при дворах немецких князей в качестве юриста и находится на дипломатической работе. С 1676 г. и до своей смерти в 1716 г. Лейбниц состоял советником и библиотекарем при дворе ганноверского герцога Эрнста Августа, затем его сына Георга Людвига, ставшего в 1714 г. английским королем Георгом I. На протяжении этих 40 лет Лейбниц вел научные исследования, публиковал многочисленные труды, поддерживал научную переписку со всеми ведущими учеными эпохи. Очень значительна и научно-организаторская деятельность Лейбница. Достаточно сказать, что он является основателем Прусской Академии наук в Берлине. Во время заграничных поездок в 1711-т — 1716 гг. с Лейбницем несколько раз встречался Петр I, советовавшийся с ним по поводу организации Академии наук в Петербурге.
      Становление математической логики в сегодняшнем понимании этого слова задержалось еще примерно на 150 лет, до середины XIX столетия.
      Отцом математической логики по праву считается английский математик и логик Джордж Буль (1815 — 1864). Именно он построил один из разделов формальной логики (исчисление классов) в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Д. Буль не получил нормального университетского образования, а изучил математику самоучкой. Этим может быть отчасти и объясняется, что, не связанный традицией, он пошел своим оригинальным путем.
      Д. Буль родился в 1815 г. в г. Ливерпуле; отец его был сапожником. Рассказывают, что это был человек очень любознательный, интересовавшийся астрономией, физикой, математикой и философией. Окончив начальную школу, Буль поступил в коммерческое училище, но вскоре покинул школу, продолжая дальнейшее образование с помощью частных уроков и самоучкой. Так он за несколько лет изучил латынь, древнегреческий, немецкий и французский языки и прочел основные философские трактаты. В возрасте 16 лет Буль поступает помощником учителя в частную школу и именно здесь, в основном по книгам, изучает математику и начинает проводить собственные исследования по математике. Результаты своих исследований Буль сообщал в письмах профессорам математики знаменитого Кембриджского университета и вскоре получил известность как крупный и оригинально мыслящий математик. В 1849 г. в г. Корк (Ирландия) открылось новое высшее учебное заведение — Куинз колледж, по рекомендации коллег-математиков Буль получил здесь профессуру, которую сохранил до своей смерти в 1864 г.
      Знаменитые труды Д. Буля по началам математической логики — «Математический анализ логики», «Исчисление логики» и особенно «Исследование законов мысли» — возникли в конце 40-х — начале 50-х гг. В них отразилось убеждение Буля о возможности изучения свойств математических операций, осуществляемых не обязательно над числами. Он говорил о символическом методе, который он применял как к изучению дифференцирования и интегрирования, так и ж логическому выводу и к теоретико-вероятностным рассуждениям. Вся глубина и плодотворность его подхода к этим вопросам обнаружилась лишь много лет спустя.
      Необходимость и возможность расширения формальной логики с применением аппарата алгебры стали тогда уже очевидны; это видно хотя бы из того, что в большой мере независимо друг от друга аналогичные исследования стали проводиться в различных странах. В частности, в России, в Казанском университете, начиная с 70-х гг., преподавал и работал крупный русский математик, астроном и логик П. С. Порецкий (1846 — 1907), построивший оригинальный метод логического исчисления, при котором некоторые классы логических задач решались аналогично тому, как решаются уравнения в элементарной алгебре. Исчисление Порецкого сейчас, спустя сто лет, привлекает вновь внимание, так Как оказалось, Что оно полезно при решении проблем, возникающих при конструировании автоматов и вычислительных устройств.
      Следует также запомнить таких ученых конца XIX в., участвовавших в становлении математической логики, как итальянец Джузеппе Пеано (1858 — 1932), предложивший аксиоматический подход к изучению арифметики, немецкие математики Эрнст Шрёдер (1841 — 1902), давший развернутое построение алгебры отношений, и Готтлоб Фреге (1848 — 1925), считающийся основателем так называемой логической семантики, и французский математик Луи Кутюра (1868 — 1914), известный, в частности, и тем, что он изучил и опубликовал наследие Лейбница в области логики.