Математическая логика

ВЫСШЕЕ ОБРАЗОВАНИЕ





серия основана в 1 996 г.





В.И. ИГОШИН




                МАТЕМАТИЧЕСКАЯ
                ЛОГИКА





УЧЕБНОЕ ПОСОБИЕ




Рекомендовано
                       УМО по образованию в области подготовки педагогических кадров в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 44.03.05 «Педагогическое образование» (квалификация (степень) «бакалавр»)





znanium.com
электронно-библиотечная система

Москва
ИНФРА-М

2024

УДК 510(075.8)
ББК 22.12я73
     И26

   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

      Игошин В.И.
И26 Математическая логика : учебное пособие / В.И. Игошин. — Москва : ИНФРА-М, 2024. — 399 с. + Доп. материалы [Электронный ресурс]. — (Высшее образование).
         ISBN 978-5-16-019779-1 (print)
         ISBN 978-5-16-104067-6 (online)
         В учебном пособии подробно изложены основы математической логики, привлечен материал школьного курса математики для его логического анализа, охарактеризованы взаимосвязи математической логики с компьютерами и информатикой.
         Для студентов университетов, технических и педагогических вузов, обучающихся по направлениям подготовки и специальностям «Математика», «Прикладная математика», «Математик-педагог», «Учитель математики» на уровнях бакалавриата, магистратуры, а также специалитета.

УДК 510(075.8)
ББК 22.12я73





                                                  Материалы, отмеченные знаком доступны в электронно-библиотечной системе Znanium



ISBN 978-5-16-019779-1 (print)
ISBN 978-5-16-104067-6 (online)


© Игошин В.И., 2012

Подписано в печать 26.01.2023.
Формат 60x90/16. Бумага офсетная. Печать цифровая. Гарнитура Newton. Усл. печ. л. 24,94.
ППТ20. Заказ № 00000
ТК 163900-2137011-250811
ООО «Научно-издательский центр ИНФРА-М» 127214, Москва, ул. Полярная, д. 31В, стр. 1.
         Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29.
E-mail: books@infra-m.ru         http://www.infra-m.ru


Отпечатано в типографии ООО «Научно-издательский центр ИНФРА-М»
127214, Москва, ул. Полярная, д. 31В, стр. 1
Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29

            Предисловие


   Логика образует такой пласт общечеловеческой культуры, без освоения которого в настоящее время не может состояться ни одна мыслящая личность. Математическая логика - вершина развития логики, достигнутая ею в XX веке. Органично соединив в себе традиционную логику, восходящую к Аристотелю, и методы современной математики, она получила столь глубокие и поразительные результаты, не принимать в расчет которые стало просто невозможно не только тем, кто изучает, преподаёт и творит математику, по и всем, для кого методы рассуждений, обоснований и доказательств являются главными методами деятельности. Кроме того, результаты, полученные математической логикой, легли в основу проектирования и создания электронно-вычислительных машин (компьютеров) и программного обеспечения к ним, нашли широчайшие применения в областях информатики и систем искусственного интеллекта.
   Настоящая книга предназначена всем, кто изучает математическую логику. Автор знакомит будущих специалистов с основными понятиями и методами математической логики, показывает взаимосвязи математической логики с математической наукой, со школьным курсом математики, с современными компьютерами.
   В главе I дано подробное изложение алгебры (логики) высказываний, так как важно, чтобы именно на начальном этапе знакомства с предметом у студента сформировалась требуемая система понятий, составляющих фундамент математической логики. Глава завершается рассмотрением булевых функций, возникших из алгебры логики и оказавшихся действенным математическим инструментом для конструирования функциональных и релейно-контактных (переключательных) схем - элементов современных компьютеров. В главе II происходит знакомство с иным подходом к алгебре высказываний: она строится как аксиоматическая теория на базе трёх схем аксиом и одного правила вывода. Основная цель главы III, в которой излагается логика предикатов, - выработать у студентов культуру употребления кванторов общности и существования, правильного их понимания и правильного оперирования выражениями (формулами) с кванторами. В вопросах применения логики предикатов значительное внимание уделяется записям на её языке различных предложений, строению математических теорем и методам их доказательств. В главе IV рассмотрен аксиоматический

3

метод в математике, его логические основы. Здесь на неформальном, содержательном, уровне показано, как математическая логика вторгается в различные разделы математической науки, образуя их фундаментальные аксиоматические основы.
    Глава V носит исторический характер: в ней рассказывается, как происходило взаимодействие математики и логики в процессе их развития и о кризисах, сопровождавших это развитие, важнейшим из которых был кризис в основаниях математики на рубеже XIX и XX веков. В главе VI представлен один из путей выхода из этого кризиса, выработанный математиками в первой половине XX века. Для этого курс математической логики поднимается на новый качественный уровень: математические теории начинают изучаться с формальной точки зрения. Сначала изучаются свойства формализованного исчисления предикатов: доказываются теоремы Гёделя о существовании модели, о полноте и адекватности этого исчисления, теорема компактности, теорема Лёвенгейма-Сколема. Затем даётся обзор формализаций теорий множеств, арифметики и числовых систем.
    Знаки ^^ и =л почти всегда используются для сокращённой записи слов п тогда и только тогда” и ’’сели..., то ...” соответственно. Исключения составляют §14 § §15, где первый знак используется для обозначения равносильности предикатов, а второй - для следования предикатов. Знак = обозначает графическое совпадение (одинаковость) формул (логики высказываний или логики предикатов). Для множеств комплексных, действительных, рациональных, целых и натуральных чисел используются стандартные обозначения: C,R,Q,Z n N соответственно. Конец доказательства отмечается значком □ .
    К пособию прилагается рабочая тетрадь по математической логике с печатной основой, которая размещена в ЭБС Znanium.com. Распечатав её, учащийся получит минимальный набор задач по данному курсу. В тетради приведены образцы решения типовых задач и задачи для самостоятельного решения. Ссылки на неё даются в тексте учебного пособия следующим образом: Тетрадь МЛ. Более объёмный набор задач содержится в сборнике: Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. М.: Изд. центр «Академия», 2008. Ссылки на него по ходу изложения теоретического материала даются следующим образом: Задачник.



В. Игошин

4

            Введение

            МАТЕМАТИЧЕСКАЯ ЛОГИКА
            В СИСТЕМЕ СОВРЕМЕННОГО
            ОБРАЗОВАНИЯ


  Предварим изучение математической логики кратким введением, в котором попытаемся осознать роль и место логики в мышлении, в науке, в математике и в обучении.
  Логика и интуиция. Мыслительная деятельность человека представляет собой сложный и многогранный процесс, происходящий как на сознательном, так и на бессознательном (подсознательном) уровнях. Главнейшим качеством мышления является его способность открывать новые факты, новые неизвестные доселе знания, способность изобретать.
  Логика и интуиция - два противоположных и неразрывно связанных между собой свойства человеческого мышления. Дедуктивное (логическое) мышление отличается тем, что оно от истинных посылок всегда приводит к истинному заключению, не опираясь при этом на опыт, интуицию и другие внешние факторы. Интуиция представляет собой способность постижения истины путём прямого её усмотрения без её обоснования с помощью логически строгого доказательства (латинское слово intuitio означает ’’пристальное всматривание”). Таким образом, интуиция выступает своего рода антиподом, противовесом логики и строгости. Логическая часть мыслительного процесса протекает на уровне сознания, интуитивная - на подсознательном уровне. Развитие науки и, в особенности, математики не мыслимо без интуиции.
  Вопрос о противопоставлении логического и интуитивного (интеллектуального и чувственного) давно переведён историей развития процесса познания в вопрос о взаимодействии этих двух ипостасей человеческого сознания в ходе этого процесса. Эта же история дала на него вполне определённый ответ. Для познания мира - и физического и духовного - абсолютно необходимы два совершенно различных метода: с одной стороны, логический, строго доказательный, а с другой - интуиция, непосредственное синтетическое суждение, не опирающееся на доказательство. Гипертрофия (преувеличение

5

роли) как строгой логики, так и интуиции являются крайностями. ’’Обе эти крайности, - справедливо считает Я.Стюарт¹, - бьют мимо цели: вся сила математики - в разумном сочетании интуиции и строгости. Контролируемый дух и вдохновенная логика!”
    Подведём итог словами выдающегося математика XX века А.Пуанкаре: ’’Таким образом, логика и интуиция играют каждая свою необходимую роль. Обе они неизбежны. Логика, которая одна может дать достоверность, есть орудие доказательства; интуиция есть орудие изобретательства.”²
    Логика традиционная и математическая логика. Термин ’’логика” происходит от греческого слова Лозо; (логос), что означает ’’мысль”, ’’разум”, ’’слово”, ’’понятие”. Традиционная или формальная логика, берущая своё начало от Аристотеля, понимается как наука, изучающая формы и законы мышления, методы, с помощью которых люди в действительности делают выводы, связь логических форм с языком. Эти логические формы, категории и законы мышления сформировались в результате общественной практики. Именно практическая деятельность человека в процессе познания окружающей действительности, миллиарды раз приводя его сознание к повторению одних и тех же логических фигур, откристаллизо-вала эти фигуры в законы логики. Таким образом, логика представляет собой определённый способ отражения действительности. Именно соблюдение логических законов делает мышление правильным, т.е. способным прн выполнении ряда условий достигать истинного знания. Логика изучает то общее, что связывает мысли в их движении к познанию истины. Она есть наука о законах и формах правильного мышления. Она изучает формы рассуждений, отвлекаясь от их конкретного содержания; устанавливает, что из чего следует, ищет ответ на вопрос, как мы рассуждаем? Специфика логики состоит в том, что она изучает не объективный мир природы и не субъективный мир переживаний и чувств, а абстрактное мышление, посредством которого человек познаёт и то и другое.
    Математическая логика, называемая также символической или теоретической логикой, выросла из логики традиционной, но явилась значительным её расширением. Эта наука, с одной стороны, применила математические методы для изучения общих структур (форм) правильного мышления и тем самым оформилась как раз

   ¹ Стюарт Я. Концепции современной математики. - Минск: Выш.шк., 1980.- 384 с. (с. 14)

   ²Пуанкаре А. О науке. - М.: Наука, 1983. - 560 с. (с.167)

6

дел математики. С другой стороны, математическая логика сделала предметом своего изучения процесс доказательства математических теорем, сами математические теории. Математическая логика явилась, таким образом, инструментом для исследований в области оснований математики. Данный раздел математической логики получил название теории доказательства, или метаматематики.
   Ни одна из этих двух логик не может в полной мере включать другую как частный случай, но они тесно связаны между собой, переплетаются друг с другом. Математическая логика, являясь более общей, более абстрактной, чем традиционная формальная логика, в то же время является и более конкретной, так как она имеет более широкое применение, даёт возможность решать множество конкретных практических задач, не разрешимых средствами традиционной формальной логики. Аппарат исчислений и формальных систем в математической логике гораздо более совершенен, нежели аппарат традиционной логики. Поэтому он может применяться к решению таких сложных задач, которые недоступны классической логике. Математическая логика способствует более глубокому пониманию логики традиционной, сохранению этой последней и поднятию её на более высокую ступень. В лице математической логики логика традиционная достигла определённого уровня совершенства, ибо ей удалось воспользоваться математикой не только по форме, но и по существу.
   Математическая логика — логика или математика? Вопрос о соотношении логики и математики в математической логике издавна интересовал философов, близких к математике, и математиков, близких к философии. Является ли математическая логика логикой в традиционном (философском) понимании, т.е. изучает ли она формы мышления и методы, с помощью которых люди в действительности делают выводы, или же она является чисто математической дисциплиной со своим абстрактным предметом, не имеющим ничего общего к реальному процессу мышления? Подобные вопросы возникли потому, что в лице математической логики математика впервые проникла в гуманитарную сферу, в её святая святых - в сферу человеческого мышления, ранее подвластную лишь философии. Это проникновение было столь стремительным и успешным, что многие философы и мыслители его просто не поняли и не осознали.
   Доказанная австрийским математиком и логиком К.Гёделем (1906 - 1978) в 1931 году теорема о неполноте формальной арифметики с небывалой силой показала, что математическая логика 
7

это, прежде всего, логика, что к человеческому мышлению эта наука имеет самое непосредственное отношение. Она убедительно показала, что совершенно безнадёжно рассчитывать на то, что можно создать полную и непротиворечивую систему аксиом для арифметики или какой-либо теории, содержащей арифметику. (Полнота системы аксиом означает, что, исходя из неё, можно вывести все истинные предложения данной науки). Отсюда следует, что аксиоматический подход к арифметике натуральных чисел не в состоянии охватить всю область истинных арифметических утверждений. Отсюда также вытекает, что то, что мы интуитивно понимаем под процессом математического доказательства, не сводится к использованию аксиоматического метода и законов традиционной и математической логики. Этот самоограничительный закон логики сама логика смогла установить, только развившись в логику математическую. Это ли не убедительнейшее доказательство того, что математическая логика имеет самое прямое отношение к мышлению и его законам.
   Известный российский логик П.С.Порецкий точно подметил, что математическая логика по предмету своему есть логика, а по методу - математика.
   Математическая логика в обучении математике. Логика и математика в процессе обучения математике взаимодействуют неизбежно. Важно, чтобы это дидактическое взаимодействие не было стихийным, а сознательно организовывалось и направлялось педагогом. В нём можно йовыделить два аспекта. Во-первых, при обучении математике логика выступает как инструмент педагогики математики, т.е. как инструмент изучения математики. Логика для педагогики математики - инструмент особый. Это - не метод, не средство и не форма обучения. Это - именно инструмент. Во-вторых логика, (как своеобразная часть математики) предстаёт как предмет педагогики математики, т.е. как объект, изучаемый в рамках математики и с помощью математики. Но и в этом своём качестве логика выступает как педагогика математики, ибо изучение логики с помощью математического материала в конечном итоге способствует более осознанному и глубокому изучению самой математики.
   Чтобы сделать логику действенным инструментом в обучении математике, а также при изучении математики, необходимо соблюдать ряд принципов. Это - те общие положения, связанные с логикой, которые имеют фундаментальное значение для методики обучения математике. Они указывают основные направления проникновения логики в методику. Нарушение этих принципов, несоблюдение их в процессе обучения математике приводит в итоге к искал

8

женному видению обучаемым как общей картины математики, так и отдельных её деталей.
   1)     Принцип обучения строению (структуре) математических УТВЕРЖДЕНИЙ. Здесь необходимо, во-первых, научиться видеть логическую структуру математического утверждения, будь то определение или теорема, отчётливо видеть, где и какие логические связки участвуют в формулировке. При этом, если это определение понятия, то важно, какого оно типа - через ближайший род и видовое отличие, индуктивное, рекуррентное, генетическое или аксиоматическое. Если это теорема, то необходимо чётко увидеть, что в ней дано и что требуется доказать, какова структура условий и структура заключения. Сюда относится также понимание сути необходимых и достаточных условий, прямой и обратной теорем и их различных видов. Во-вторых, необходимо научиться понимать, какие утверждения равносильны каким, т.е. научиться преобразовывать структуру математического утверждения равносильным образом. Чем больше усвоено логических равносильностей, тем выше логическая культура учителя.
   2)     Принцип обучения понятию доказательства математической ТЕОРЕМЫ. Здесь необходимо уяснить, что доказательство теоремы - это последовательность (цепочка) утверждений, каждое из которых есть либо условие теоремы, либо аксиома, либо получено из двух предыдущих утверждений последовательности по правилу вывода: из утверждений P и P ^ Q следует утверждение Q. Построив такую цепочку, мы доказываем, что из A выводится B, в результате чего делаем вывод, что справедлива теорема A ^ B. Обоснованием этому переходу служит логическая теорема о дедукции. Всякий раз при доказательстве теоремы нужно стремиться к тому, чтобы эта цепочка-доказательство вырисовывалась бы в сознании учащегося как можно более отчётливо.
   3)     Принцип обучения методам доказательства математических теорем. Здесь необходимо, во-первых, научиться методам построения цепочки утверждений A = A₀,A₁,...,A„ = B для доказательства теоремы A ^ B. Синтетический (или прямой) метод - построение цепочки в прямом направлении, от A к B. Аналитический метод (или метод восходящего анализа) - построение цепочки в обратном направлении, от B к A. Во-вторых, необходимо уяснить, что для доказательства теоремы A ^ B достаточно доказать теорему —B ^ —A, или (A Л —B) ^ —A, или (A Л —B) ^ B (варианты метода доказательства от противного), вместо теоремы A достаточно доказать теорему (—A ^ (В Л —B)) ^ A (метод приведения к

9

абсурду), вместо A ^ C - две теоремы A ^ B и B ^ C (метод цепного заключения) и т.д.
   4)     Принцип обучения строению математических теорий. Здесь имеется в виду уяснение сути аксиоматического метода при построении математической теории и при её преподавании, уяснение сути первоначальных (неопределяемых) понятий теории, её аксиом и теорем, вплоть до метатеории (свойств этой теории) - непротиворечивости, полноты, категоричности, независимости системы аксиом. Знание аксиоматических теорий, лежащих в основаниях школьных математических курсов: аксиоматические построения геометрии на основе систем аксиом Евклида, Гильберта, Вейля и т.д.; аксиоматическая теория числовых систем как основания школьного курса алгебры и начал анализа.
   Математическая логика помогает обосновать и облегчает применение указанных логических принципов. Они должны органично войти в сознание всякого преподающего и изучающего математику, ибо без их соблюдения в процессе обучения математике изучаемый предмет рискует утратить те качества и черты, которые собственно и выделяют его из системы прочих наук.
   Математическая логика и современные ЭВМ. Широчайшее распространение компьютеров, проникающих буквально во все сферы нашей жизни, требует и массового внедрения, начиная с самого раннего возраста, компьютерной культуры, т.е. понимания возможностей компьютера и умения взаимодействовать с ним. Тесная связь методов математической логики и современных компьютеров прослеживается по следующим двум направлениям. Эти методы используются как при физическом конструировании и создании компьютеров (алгебра высказываний и булевы функции - математический аппарат для конструирования переключательных и функциональных схем, составляющих элементную базу компьютеров), так и при создании математического обеспечения к ним (в основе многочисленных языков программирования лежат теория алгоритмов, теория формальных систем, логика предикатов; например, название языка PROLOG означает сокращение от слов ’’Программирование ЛОГическое”). Кроме того, синтез логики и компьютеров привёл к возникновению баз данных и экспертных систем, что явилось важнейшими этапами на пути к созданию искусственного интеллекта -машинной модели человеческого разума.
   Понимание всех этих взаимосвязей неотделимо от современного высшего математического, технического и педагогического образования.

10