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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ







В. Г. Алябьева




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




Допущено методическим советом Пермского государственного национального исследовательского университета в качестве учебного пособия для студентов, обучающихся по направлениям подготовки бакалавров «Прикладная математика и информатика», «Фундаментальная информатика и информационные технологии» и специальности «Компьютерная безопасность»






Пермь 2017

1

УДК 510.6
ББК 22.12
    А60


            Алябьева В. Г.


А60 Математическая логика: учеб, пособие / В. Г. Алябьева;
      Перм. гос. нац. исслед. ун-т. - Пермь, 2017. - 111 с.
      ISBN 978-5-7944-2904-6



      Учебное пособие посвящено основам математической логики и состоит из введения и четырех глав: «Логика высказываний», «Исчисление высказываний», «Логика предикатов первого порядка» и «Исчисление предикатов». Особое внимание уделено проблеме распознавания общезначимости формул логики высказываний и формул логики предикатов, использованию метода резолюций.
      Пособие предназначено для студентов, обучающихся по направлениям подготовки бакалавров «Прикладная математика и информатика», «Компьютерная безопасность», «Фундаментальная информатика и информационные технологии» и специальности «Компьютерная безопасность».

                                                      УДК 510.6
                                                      ББК 22.12



Печатается по решению редакционно-издательского совета
Пермского государственного национального исследовательского университета

Рецензенты: кафедра высшей математики Пермского государственного гуманитарно-педагогического университета (зав. кафедрой - канд. пед. наук, доцент Е. Л. Черемных), канд. пед. наук, доцент, зав. кафедрой физики и математики Пермской государственной фармацевтической академии В. И. Данилова


ISBN 978-5-7944-2904-6

©ПГНИУ, 2017
© Алябьева В. Г., 2017

2

СОДЕРЖАНИЕ


      Введение                                     4
        Список литературы                         19
      Глава1. Логика высказываний                 22
        1.1. Формулы логики высказываний          22
        1.2. Равносильные формулы логики высказываний 27
        1.3. Нормальные и совершенные формы формул логики высказываний                       29
        1.4. Логическое следствие                 33
        1.5. Распознавание общезначимости формул логики высказываний                       33
             1.5.2. Метод резолюций               35
Упражнения для самостоятельной работы    39

      Глава 2. Исчисление высказываний            45
         2.1. Язык исчисления высказываний        45
         2.2. Введение новых логических символов  55
         Упражнения для самостоятельной работы    60

      Глава 3. Логика предикатов первого порядка  62
         3.1. Синтаксис: термы и формулы логики предикатов первого порядка              62
         3.2. Семантика: интерпретация формул логики первого порядка                         65
         3.3. Проблема разрешимости для выполнимости и общезначимости формул логики предикатов первого порядка               70
         3.4. Метод резолюций в логике предикатов  74
         3.5. Арифметическая и геометрическая модели 95
         Упражнения для самостоятельной работы     100

      Глава 4. Исчисление предикатов             103
         4.1. Язык исчисления предикатов         103
         4.2. Примеры выводимых секвенций        106
         Упражнения для самостоятельной работы     109
      Список литературы                          109


3

Введение


                          Логика учит другие науки доказательству всех следствий, вытекающих из заданных посылок Лейбниц

       Предтечей математической логики явилась логика традиционная. Рассмотрим этапы становления математической логики.



            Формальная логика и Аристотель



      Основоположником традиционной (формальной) логики является гениальный мыслитель древности Аристотель (384 — 322 до н.э.) — древнегреческий философ и логик, учёный-энциклопедист, известный универсальной учёностью, создавший грандиозное, поражающее воображение собрание трудов почти по всем областям знания. Он первый систематически изложил науку логики в виде самостоятельной дисциплины.

                         Аристотель
      Аристотель родился во фракийском городе Стагира, греческой колонии, расположенной неподалёку от Афона [8, с. 34], поэтому Аристотеля называли часто "Стагирит".
      Аристотеля уважительно именовали "князем мудрости". Его популярность была столь велика, что его произведения из века в век переписывались (пока не было изобретено книгопечатание), комментировались, переводились на латинский, армянский, арабский и другие языки, поэтому они стали известны нам. Дошедшие до нас труды Аристотеля по логике и научному

4

познанию комментаторы объединили под общим названием "Органон" (термин "органон" представляет собой транслитерацию соответствующего греческого слова, означающего "орудие" (метод) исследования). Сам Аристотель свои логические труды называл "Аналитиками" [1].
       Разрабатывая теорию логики Аристотель поставил перед собой задачу выяснить, "на чём же покоится принудительная сила речей, какими средствами должна обладать речь, чтобы убеждать людей, заставлять их с чем-нибудь соглашаться или признавать что-либо истинным?"
       Он показал, что правильные рассуждения подчиняются небольшому числу законов, не зависимых от частной природы объектов, о которых идёт речь. Аристотель открыл и точно сформулировал первые три закона традиционной логики. Первый закон - закон противоречия, который на языке современной математической логики можно записать в виде Vx(x ■ х) (для всякого х не может быть одновременно истинно утверждение х и отрицание того же х). Второй — закон исключённого третьего Vx(xvx) (для всякого х истинно либо х, либо X, вместе они ложны). Третий—закон тождества Vx(x -> х) (для любого х истинно, что если х , то х; х влечёт х).
       Вклад Аристотеля заключался прежде всего в том, что он отделил логические принципы и схемы рассуждений от содержания рассуждений и систематически их исследовал. В "Первой аналитике" — важнейшем логическом сочинении — была изложена силлогистика (система силлогических заключений, или силлогизмов) — главное достижение Аристотеля в логике, достижение, стоящее у истоков логики как науки. Чтобы оценить значимость этого достижения Аристотеля, обратимся к традиционному развитию всех наук. При формировании наук функционирует множество разных идей, из которых многие оказываются ошибочными. Рождаются и умирают десятки, а то и сотни теорий. Силлогистика представляет собой парадоксальное исключение. Она построена одним человеком и практически сразу. Её никто не пытался критиковать или опровергать. Её лишь уточняли и модернизировали. Со времени создания силло

5

гистики прошло более двух тысяч лет, но она по-прежнему занимает почётное место в науке.
      Аристотель определили силлогизм как высказывание, в котором "при утверждении чего-либо из него необходимо вытекает нечто, отличное от утверждаемого и (именно) в силу того, что это есть" [1, с. 10]. Силлогизм состоит из трёх суждений. В первом суждении содержится общее правило (большая посылка), во втором суждении приводится конкретный случай (меньшая посылка), третье суждение — вывод из посылок (заключение). В этих двух посылках фигурируют три класса терминов: S, Р и М. Каждая из посылок и заключение представляют собой базовые высказывания силлогистики.


                      УщЛая ПОСЫЛКЛ. М ------------------------*Р

                      fymOptLV. тщциа, -------------—-----S*⁻-------------------■ р

SteyScid пгм&лка. р«--------------------                                                                I
                      ЯЬтораз. nxtMa. S*-----------------—
                         За/ммъ&ше s •--------------------------* p


                                              M«------—---------------i I-------,-------


                     ffiep & Л noctfjtrta. p ♦      ------[vj

                     вторая            frl --------- ₑ c
                        ЗабЛмпемце     5 •________________p


                 Рис.1. Четыре фигуры силлогизма

      В зависимости от расположения среднего термина М в посылках, различают четыре фигуры силлогизма. Схематически эти фигуры показаны на рис. 1 [6].


6

       Для каждой фигуры имеется несколько модусов, которые отличаются друг от друга структурой посылок. Всего можно построить 256 модусов. Из них Аристотель считал правильными 19 модусов. К настоящему времени правильными считаются 15 модусов.
       Аксиома силлогизма', "всё, что утверждается (или отрицается) относительно всех предметов класса, то утверждается (или отрицается) относительно любого отдельного предмета этого класса".
       Приведём пример рассуждения, для которого выполняется аксиома силлогизма.
       Все планеты вращаются вокруг Солнца.
       Марс — планета.
       Следовательно, Марс вращается вокруг Солнца.
       "В средние века Аристотель пользовался такой популярностью, что его наверняка бы причислили к святым, если бы он не родился за четыреста лет до рождения основателя этой религии. На протяжении многих столетий силлогистика была единственной моделью дедуктивных рассуждений. В этом смысле она сыграла исключительную роль в становлении всех наук вообще, ибо стала для них методологией научного мышления" [6]. Силлогистика Аристотеля удовлетворяет, по существу, критериям логико-математической строгости, предъявляемым к современным формализованным системам. Ян Лукасевич заметил, что аристотелевская силлогистика по своей строгости превосходила даже строгость математических теорий того времени, и в этом состоит её непреходящее значение. Логическое учение Аристотеля получило название традиционной логики. К ней добавляют эпитет "формальная", подчёркивая значимость формы рассуждений.
       Заметим, что термин "логика" Аристотель не использовал. Впервые термин "логика" появился в трудах стоиков. Представители стоической школы (Зенон, ок. 336 - 264 до н.э., и др.) ввели термин "логика" для обозначения науки, исследующей законы мыслительной деятельности. Они рассматривали логику как первую часть философии, которая включает в себя также физику и этику. Цель логики — оградить ум человека о т за

7

блуждений и найти пути и критерий истины. Логика нужна, чтобы "охранять" этику, пищу для которой поставляет физика.
      Термин "формальная логика" ввёл Иммануил Кант.


            Символическая логика и Лейбниц



       Лейбниц Г.В. (1646 — 1716) понимал логику не только как искусство рассуждения и доказательства, но и как искусство изобретения и открытия новых истин. На него произвела сильное впечатление силлогистика Аристотеля. Его также вдохновляла идея, восходящая к Декарту, о "всеобщей математике" (mathesis universalis), исследующей порядок и меру. Он писал: "Изобретение силлогической формы — одно из прекраснейших и даже важнейших открытий человеческого духа. Это своего рода универсальная математика, всё значение которой ещё не достаточно понято" [15, с. 7—9].


Лейбниц

        Размышляя о математизации логики, об использовании в ней символического языка, он задумал грандиозный проект усовершенствования логики, включающий создание "универсальной характеристики" — средства, с помощью которого всё человеческое познание должно подвергнуться коренному преобразованию. Впервые соответствующие идеи Лейбниц высказал в своей (магистерской) "Диссертации о комбинаторном искусстве" (Dissertatio de arte combinatoria), изданной в 1666 году. По замыслу Лейбница, новый метод должен включать два теоретических инструмента: искусственный язык (characteristica universalis) и исчисление умозаключений (calculus ratiocinator).


8

Искусственный язык должен служить средством выражения любых мыслей, должен устранить барьеры разноязычной речи, способствовать распространению научных идей. Выражения естественного языка должны быть заменены компактными, наглядными и однозначно понимаемыми знаками — "характерами" . Все понятия следует свести к некоторым элементарным понятиям, образующим как бы алфавит, азбуку человеческих мыслей. После этого станет возможной замена обычных рассуждений оперированием со знаками.
       Правила такого оперирования должны быть заданы во второй части "всеобщей науки" — в исчислении умозаключений. Они должны однозначным образом определять последовательности выполнения действий над знаками и сами эти действия, так что при правильном их применении не останется места для разногласий. Сокровенная цель описанной программы Лейбница чётко выражена в словах о том, что единственное средство улучшения умозаключений состоит в уподоблении их математическим, т.е. в придании такой наглядности, что их "ошибочность можно было бы увидеть глазами, и, если между людьми возникают разногласия, достаточно только сказать "Вычислим!", чтобы стало ясно, кто прав"[15, с. 16]. Свой грандиозный замысел Лейбниц не реализовал, но, несомненно, идея математизации логики оказала влияние на учёных XVIII века, стимулируя использование символических обозначений.
       Заслуги Лейбница в формировании математической логики высоко оценил Норберт Винер, создатель кибернетики: "Если бы мне в анналах истории наук пришлось выбирать святого — покровителя кибернетики, то я бы выбрал Лейбница, философия которого концентрировалась вокруг двух основных идей: идеи универсальной, символики и идеи логического исчисления. Из них возникли современный математический анализ и современная символическая логика". Винер считает, что подобно тому, как в арифметическом исчислении заложена возможность развития его механизации от абака и арифмометра до сверхбыстрых вычислительных машин, так и в calculus ratiocinator Лейбница в зародыше содержится mashina rationatrix — "думающая машина" [3, с 57].

9

      Только в XIX веке математическая логика станет превращаться в самостоятельную науку, появится соответствующая символика, будут построены первые логические исчисления.


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



       Математическая логика возникла в результате применения математических, в особенности алгебраических, методов решения задач логики. До XIX века в работах математиков и логиков предпринимались попытки использования символики в логических исследованиях, однако самостоятельной научной дисциплиной математическая логика становится лишь в XIX веке.
       Создателем современной символической логики следует считать Джорджа Буля (1815 — 1864) [2, с.17].


Джордж Буль

      Буль для превращения логики в точную науку стал использовать математические обозначения. Он писал: "...необходимо связать логику не с философией, а с математикой". В 1847 г. он опубликовал свою первую работу по логике "Математический анализ логики как эссе к исчислению дедуктивного рассуждения" [9], в которой подчёркивал; "те, кто знаком с настоящим состоянием символической алгебры, отдаёт себе отчёт в том, что обоснованность процессов анализа зависит не от интерпретации используемых символов, а только от законов их комбинирования" [10, с.З]. Именно в ясном понимании абстрактности исчисления, понимании того, что исчисление определяется законами заданных в нём операций, состоит принци

10

пиальная новизна взглядов Буля на логическое учение. Через 8 лет Буль публикует свою вторую книгу "Исследование законов мышления, на которых основаны математические теории логики и вероятности" [11]. Замысел "Законов логики" Буль формулирует так: "Цель настоящего исследования состоит в том, чтобы изучить основные законы тех операций ума, посредством которых осуществляются рассуждения" [11, с. 1—2]. В этих работах Буль строит алгебру высказываний (алгебру логики) как алгебру классов, в которой классы множеств соответствуют объёмам понятий. Буль обозначает универсальное множество символом 1, пустое множество — символом 0, для обозначения классов использует переменные х,у,... . На множестве классов вводит двухместные операции х + у (сложение, соответствующее объединению множеств с исключением их общей части) и х ■ у (умножение, соответствующее пересечению множеств), одноместную операцию 1 — х (дополнение до универсума). В булевой алгебре для сложения и умножения выполняется коммутативный и ассоциативный закон, умножение дистрибутивно относительно сложения. Если использовать современные обозначения для дополнения, то следующие свойства операций в алгебре Буля можно записать в виде х-х — 0,х + х = 1. Буль отмечает, что логика отличается от алгебры тем, что в логике выполняется равенство х ■ х = х, тогда как в алгебре равенство х-х выполняется только тогда, когда х = 1 или х = 0.
       Развитие логики в XIX веке долго сдерживало отсутствие кванторов.
       Кванторы в логику ввёл немецкий математик, логик и философ Фреге Фридрих Людвиг Готлоб (Friedrich Ludwig Gottlob Frege, 1848 - 1925).
       С именем Фреге связано возникновение нового этапа в развитии математической логики, который характеризуется аксиоматической трактовкой пропозиционального исчисления, формированием основ математического доказательства. Фреге построил логику в виде формализованного языка, именуемого им "исчислением понятий" (Begriffsschrift) в работе 1879 г. [13]. Его формализованная логика стала в последствии основным орудием математики.

11